Lock free list remove operation

Question

I have the following problem definition:

Design a lock-free simple linked list with the following operations:

• Add(item): add the node to the beginning (head) of the list
• Remove(item): remove the given item from the list

Below is shown the code implemented so far:

public class List<T>
{
    private readonly T _sentinel;
    private readonly Node<T> _head;

    public List()
    {
        _head = new Node<T>();
        _sentinel = default(T);
    }

    public List(T item)
    {
        _head = new Node<T>(item);
        _sentinel = item;
    }

    public void Add(T item)
    {
        Node<T> node = new Node<T>(item);

        do
        {
            node.Next = _head.Next;
        }
        while (!Atomic.CAS(ref _head.Next, node.Next, node));
    }

    public void Remove(Node<T> item)
    {
        Node<T> next;
        Node<T> oldItem = item;  

        if (item.Value.Equals(_sentinel))
            return;

        item.Value = _sentinel;

        do
        {
            next = item.Next;

            if (next == null)
            {
                Atomic.CAS(ref item.Next, null, null);
                return;
            }

        } while (!Atomic.CAS(ref item.Next, next, next.Next));

        item.Value = next.Value;
    }
}

The head is actually a dummy (sentinel) node kept for ease of use. The practical head is actually _head.Next. The problem is on the remove operation when trying to remove the last element of the list:

On the remove part there are two cases:

1. The node has a following not-null next pointer: then do the CAS operation and steal the value data of the next item removing actually the next item
2. The problematic case is when the element to remove is the last one in the list:
   • Do Atomically: If (item == oldItem and item.Next == null) then item = null where oldItem is a pointer to the item to remove;

So I want to do is in the case of removing C node:

• if(C==old-C-reference and C.Next == null) then C = null => all atomically

The problem is that I have a CAS only on a single object. How can I solve this problem atomically? Or is there a better way of doing this remove operation that I'm missing out here?

Answer 1

when removing B we do a trick by copying C's contents to B and removing C: B.Next = C.Next (in the loop) and B.Value = C.Value after the move succeeded

So you need to atomically modify two memory locations. CAS in .NET does not support that. You can, however, wrap those two values in another object that can be swapped out atomically:

class ValuePlusNext<T> {
 T Value;
 Node<T> Next;
}

class Node<T> {
 ValuePlusNext<T> Value;
}

Now you can write to both values in one atomic operation. CAS(ref Value, new ValuePlusNext<T>(next.Value, next.Value.Next). Something like that.

It is strange that ValuePlusNext has the same structure that your old Node class had. In a sense you are now managing two physical linked list node for each logical one.

while (true) {
 var old = item.Value;
 var new = new ValuePlusNext(...);
 if (CAS(ref Value, old, new)) break;
}