Now we need to deal with actual inserts somehow. The best we can afford (in terms of scalability) is a lockfree algorithm. The algorithm for ordered singly-linked list insertion is well-known, and takes 1 CAS operation in the best (and average) case (note that the function takes as parameters hints for previous and next nodes, which are discovered during preceding searching) (C++0x synchronization primitives are used):
/** ordered singly-linked list insert
* @prev hint for the previous element
* discovered by a find operation
* it's key is smaller than inserting key
* @next hint for the next element
* discovered by a find operation
* it's key is larger than inserting key
* @node the node to insert
* @return true if inserted
* false if the key is already present in the list
*/
bool slist_insert(node_t* prev, node_t* next, node_t* node)
{
for (;;)
{
// try to insert the node with CAS operation
node->next.store(next, memory_order_relaxed);
if (prev->next.compare_exchange_strong(next, node, memory_order_release))
// if the CAS succeeded, the node is inserted
return true;
// otherwise, something has changed,
// and we need to find a new location for the insertion
// (i.e. update 'prev' and 'next')
for (;;)
{
// re-compare the values
int cmp = traits_t::compare(node->item, next->item);
if (cmp > 0)
{
// new 'next' node's key is smaller than the inserting key
// so remember it as a 'prev', and repeat the comparation
prev = next;
next = prev->next.load(memory_order_consume);
if (next == 0)
break;
continue;
}
else if (cmp == 0)
{
// the key is present in the list
return false;
}
else /* (cmp < 0) */
{
// new 'next' node's key is still larger than the inserting key
// so just retry the CAS
break;
}
}
}
}
Move on to Node Count Maintenance