Harris with AtomicMarkableReference - remove

On a previous post we talked about an implementation of Harris Linked List using Java's AtomicMarkableReference (AMR), and how insertions work in such a data structure.
This time, we are going to see how deletions work in this technique.

Suppose we start with a very small list with just four keys, and their corresponding nodes, as shown in the picture below:


notice that all the AMR instances have a mark of 0 (or false if you prefer).


Suppose we want to remove the key B from the set, and by consequence the node B. We start the removal by creating a new AMR instance that references Node D and has a mark of 1 (true), because the reference and mark are immutable, so the only way to change them is to create a new instance:


The next step is to change node B so that it uses the new AMR instance. This is done with a compareAndSet() (CAS for short) and the goal of this operation is to logically remove the key B from the set, and to prevent further insertions after the node B. From this instant onwards, any contains(B) operation will return false because, even though the node B is still physically in the linked list, it is pointing to an AMR instance that has a mark of 1 and is, therefore, logically removed:


The old AMR instance will no longer be reachable and the Garbage Collector (GC) can now clean it up:


On the following step, we create another AMR instance that is also referencing node D, but with a mark of 0:

Then, using a CAS, in the node A we change from the current instance of AMR that references node B to the newly created AMR instance that references node D. This will unlink node B, thus physically removing node B from the linked list:


All that needs to be done now is for the GC to collect the unused AMR instances and the node B:


For those of you who were not counting, the whole procedure took 2 CAS (because there were no retries in this example), and involved the creation of two new AMR instances (actually, it was of the type Pair to be more precise, which in turn is encapsulated in the AMR class), and the GC had to cleanup one Node instance and three unused AMR instances. All of this just to remove a single key from the set, without any contention.

Obviously, this is a very wasteful technique, and we can do better than this... much better in fact, and that is what we'll look into in upcoming posts.