Prev

Next

MCAS

• Ordered linked list with two sentinels

 typedef struct { int key; struct node *next; } node;
 typedef struct { node *head; } list;
 void list_insert_mcas (list *l, int k) 
 {
    node *n := new node(k);
    do { 
       node *prev := MCASRead( &(l->head) );
       node *curr := MCASRead( &(prev->next) );
       while ( curr->key < k ) {
          prev := curr;
          curr := MCASRead( &(curr->next) );
       }
       n->next := curr;
	   // prev->next := n
    } while ( !MCAS (1, [&prev->next], [curr], [n]) );
 }

• Delete has to update two locations (to prevent insertion after the deleted node), Fig1.
• Not composable
• Software implementation uses 2 reserved bits in each pointer

6