Home‎ > ‎Parallel Computing‎ > ‎Concurrent Skip List‎ > ‎

Lockfree Insert Operation

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

Comments