/*            MPI-3 distributed linked list construction example
 *            --------------------------------------------------
 *
 * James Dinan -- dinan at mcs.anl.gov
 * December, 2010
 * 
 * Construct a distributed shared linked list using proposed MPI-3 dynamic
 * windows.  Initially process 0 creates the head of the list, attaches it to
 * the window, and broadcasts the pointer to all processes.  All processes then
 * concurrently append N new items to the list.  When a process attempts to
 * attach its item to the tail of list it may discover that its tail pointer is
 * stale and it must chase ahead to the new tail before the item can be
 * attached.
 */

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>

#define NUM_ITEMS 10

/* Linked list pointer */
typedef struct {
  int      rank;
  MPI_Aint disp;
} llist_ptr_t;

/* Linked list item */
typedef struct {
  int value;
  llist_ptr_t next;
} llist_item_t;

const llist_ptr_t nil = { -1, (MPI_Aint) MPI_BOTTOM };


/* List of locally allocated list items. */
llist_item_t **my_items = NULL;
int my_items_size  = 0;
int my_items_count = 0;

/* Add an item to the list of local items so we can free it later. */
void append_item(llist_item_t *item) {
  if (my_items_size == my_items_count) {
    my_items_size += 100;
    my_items = realloc(my_items, my_items_size);
  }
  my_items[my_items_count] = item;
  my_items_count++;
}


int main(int argc, char **argv) {
  int           procid, nproc, i;
  MPI_Win       llist_win;
  llist_item_t *item_ptr;
  llist_ptr_t   head_ptr, tail_ptr;

  MPI_Init(&argc, &argv);

  MPI_Comm_rank(MPI_COMM_WORLD, &procid);
  MPI_Comm_size(MPI_COMM_WORLD, &nproc);

  MPI_Win_create_dynamic(MPI_INFO_NULL, MPI_COMM_WORLD, &llist_win);

  /* Process 0 creates the head node */
  if (procid == 0) {
    MPI_Alloc_mem(sizeof(llist_item_t), MPI_INFO_NULL, &item_ptr);
    item_ptr->value = -1;
    item_ptr->next  = nil;
    MPI_Win_register(llist_win, item_ptr, sizeof(llist_item_t));
    append_item(item_ptr);

    head_ptr.rank = procid;
    head_ptr.disp = (MPI_Aint) item_ptr;
  }

  /* Broadcast the head pointer to everyone */
  MPI_Bcast(&head_ptr, sizeof(llist_ptr_t), MPI_BYTE, 0, MPI_COMM_WORLD);
  tail_ptr = head_ptr;

  /* All processes concurrently append NUM_ITEMS items to the list */
  for (i = 0; i < NUM_ITEMS; i++) {
    llist_ptr_t new_tail_ptr;
    int success;

    /* Create a new list item and register it with the window */
    MPI_Alloc_mem(sizeof(llist_item_t), MPI_INFO_NULL, &item_ptr);
    item_ptr->value = procid;
    item_ptr->next  = nil;
    MPI_Win_register(llist_win, item_ptr, sizeof(llist_item_t));
    append_item(item_ptr);

    new_tail_ptr.rank = procid;
    new_tail_ptr.disp = (MPI_Aint) item_ptr;

    /* Append the new node to the list.  This might take multiple attempts if
       others have already appended and our tail pointer is stale.  Exclusive
       locks are used to ensure that the result of the CAS on both or neither
       elements of the llist pointer are seen.  */
    do {
      llist_ptr_t next_tail_ptr;

      MPI_Win_lock(MPI_LOCK_EXCLUSIVE, tail_ptr.rank, 0, llist_win);

      MPI_Compare_and_swap(&new_tail_ptr.proc, &nil.proc, &next_tail_ptr.proc, MPI_INT, tail_ptr.rank,
          (MPI_Aint) &(((llist_item_t*)tail_ptr.disp)->next.proc), llist_win);

      MPI_Compare_and_swap(&new_tail_ptr.disp, &nil.disp, &next_tail_ptr.disp, MPI_AINT, tail_ptr.rank,
          (MPI_Aint) &(((llist_item_t*)tail_ptr.disp)->next.disp), llist_win);

      MPI_Win_unlock(tail_ptr.rank, llist_win);
      success = (next_tail_ptr.rank == nil.rank && next_tail_ptr.disp == nil.disp);

      if (success) {
        /* If the tail is nil, update it with the new pointer. */
        tail_ptr = new_tail_ptr;

      } else {
        /* Otherwise, update the tail pointer with what we got and try again. */
        tail_ptr = next_tail_ptr;
      }

    } while (!success);
  }

  /* Free the linked list window */
  MPI_Win_free(&llist_win);

  /* Free all the items in the list */
  for ( ; my_items_count > 0; my_items_count--)
    MPI_Free_mem(my_items[my_items_count-1]);

  MPI_Finalize();

  return 0;
}