07:07 PM

Lockless Linked List

For some recent work I needed to make a lockless linked list. These kind of lists are awesome because, for the most part, you can add things to the list from multiple threads with minimal cost. For my case a limitation on the needs of the list was that it only needed lockless insert, removals would be managed from a single thread. This allowed for a pretty awesomely efficient insertion function which I document here. Unfortunately this implementation is Windows specific but could probably be switched to whatever CAS your local OS uses. Enjoy.

template<typename T>
void Insert(const T \&amp; d)
{
    volatile Node<T> * current = _root;
    Node<T> * n = new Node<T>(d);
    volatile PVOID * ptr;
    do 
    {
        // Traverse to the end
        while(current->next != NULL)
        {
            current = current->next;
        }
        ptr = (volatile PVOID *)(&amp; (current->next));
        // Attempt to swap in our new node
    } while (InterlockedCompareExchangePointer(ptr, n, NULL) != NULL);
    InterlockedIncrement(&amp;_nElements);
}

Cheers, Loren

2 Comments

Comments

  1. Cool interlocked beans. :)

    But I think some of the formatting of the source code was nizzled along with the html entities

    eddie on

  2. Yeah, I’ve been looking at some javascript code formatting systems. Hopefully get one integrated here at some point. And thanks :)

    chromex on