Atomic operations over a list

Question

Suppose I have a list, and I want to use a test_and_set operation a parameter of which is the calculation of some pointer address l->a.next->next. This, I think, will not be atomic, and the test_and_set will be useless. Is there a way to calculate that pointer value atomically so that the TAS will work atomically?

Answer 1

You probably mean CAS (more useful).

In general: yes it is often used to implement transactional or wait-free datastructures,

Buf first things first: let's separate address-calculations from atomic operations on an address, you first get the specific address at which something should be swapped, the CAS does not care how you got there.

Specifically you should first let each of your threads navigate the list until they find a place where they want to replace a next-pointer, then they can try-repeat this by using CAS. It depends on your scenario whether the thread has to re-walk the list for the retry.

The tricky part is actually at a different place in the code: where you free (or re-use) the list-nodes. In general you have to assume that you cannot re-use or free node-chains that were disconnected from your list ever. In practice there are heursitics you can use but this depends on your use-case.