Ggthjy

This is a lock-free Container class. By Container I mean it will hold objects for iteration at a later time. To achieve $O(1)$ it returns a token from the put method which you can then use to remove the object. The token is actually the node in which the object has been placed.

It is instantiated with a fixed size and throws an exception if capacity is exhausted. Internally it uses a ring buffer.

It is not intended as a candidate for the Collections toolbox.

Please try to find a way to break it if you can, or point out any areas where you think it might fail under certain situations.

/**

 * Container

 * ---------

 *

 * A lock-free container that offers a close-to O(1) add/remove performance.

 *

 */

public class Container<T> implements Iterable<T> {



  // The capacity of the container.

  final int capacity;

  // The list.

  AtomicReference<Node<T>> head = new AtomicReference<Node<T>>();



  // Constructor

  public Container(int capacity) {

    this.capacity = capacity;

    // Construct the list.

    Node<T> h = new Node<T>();

    Node<T> it = h;

    // One created, now add (capacity - 1) more

    for (int i = 0; i < capacity - 1; i++) {

      // Add it.

      it.next = new Node<T>();

      // Step on to it.

      it = it.next;

    }

    // Make it a ring.

    it.next = h;

    // Install it.

    head.set(h);

  }



  // Empty ... NOT thread safe.

  public void clear() {

    Node<T> it = head.get();

    for (int i = 0; i < capacity; i++) {

      // Trash the element

      it.element = null;

      // Mark it free.

      it.free.set(true);

      it = it.next;

    }

  }



  // Add a new one.

  public Node<T> add(T element) {

    // Get a free node and attach the element.

    return getFree().attach(element);

  }



  // Find the next free element and mark it not free.

  private Node<T> getFree() {

    Node<T> freeNode = head.get();

    int skipped = 0;

    // Stop when we hit the end of the list

    // ... or we successfully transit a node from free to not-free.

    while (skipped < capacity && !freeNode.free.compareAndSet(true, false)) {

      skipped += 1;

      freeNode = freeNode.next;

    }

    if (skipped < capacity) {

      // Put the head as next.

      // Doesn't matter if it fails. That would just mean someone else was doing the same.

      head.set(freeNode.next);

    } else {

      // We hit the end! No more free nodes.

      throw new IllegalStateException("Capacity exhausted.");

    }

    return freeNode;

  }



  // Mark it free.

  public void remove(Node<T> it, T element) {

    // Remove the element first.

    it.detach(element);

    // Mark it as free.

    if (!it.free.compareAndSet(false, true)) {

      throw new IllegalStateException("Freeing a freed node.");

    }

  }



  // The Node class. It is static so needs the <T> repeated.

  public static class Node<T> {



    // The element in the node.

    private T element;

    // Are we free?

    private AtomicBoolean free = new AtomicBoolean(true);

    // The next reference in whatever list I am in.

    private Node<T> next;



    // Construct a node of the list

    private Node() {

      // Start empty.

      element = null;

    }



    // Attach the element.

    public Node<T> attach(T element) {

      // Sanity check.

      if (this.element == null) {

        this.element = element;

      } else {

        throw new IllegalArgumentException("There is already an element attached.");

      }

      // Useful for chaining.

      return this;

    }



    // Detach the element.

    public Node<T> detach(T element) {

      // Sanity check.

      if (this.element == element) {

        this.element = null;

      } else {

        throw new IllegalArgumentException("Removal of wrong element.");

      }

      // Useful for chaining.

      return this;

    }



    public T get () {

      return element;

    }



    @Override

    public String toString() {

      return element != null ? element.toString() : "null";

    }

  }



  // Provides an iterator across all items in the container.

  @Override

  public Iterator<T> iterator() {

    return new UsedNodesIterator<T>(this);

  }



  // Iterates across used nodes.

  private static class UsedNodesIterator<T> implements Iterator<T> {



    // Where next to look for the next used node.

    Node<T> it;

    int limit = 0;

    T next = null;



    public UsedNodesIterator(Container<T> c) {

      // Snapshot the head node at this time.

      it = c.head.get();

      limit = c.capacity;

    }



    @Override

    public boolean hasNext() {

      // Made into a `while` loop to fix issue reported by @Nim

      while (next == null && limit > 0) {

        // Scan to the next non-free node.

        while (limit > 0 && it.free.get() == true) {

          it = it.next;

          // Step down 1.

          limit -= 1;

        }

        if (limit != 0) {

          next = it.element;

        }

      }

      return next != null;

    }



    @Override

    public T next() {

      T n = null;

      if ( hasNext () ) {

        // Give it to them.

        n = next;

        next = null;

        // Step forward.

        it = it.next;

        limit -= 1;

      } else {

        // Not there!!

        throw new NoSuchElementException ();

      }

      return n;

    }



    @Override

    public void remove() {

      throw new UnsupportedOperationException("Not supported.");

    }

  }



}

Having posted this request I now find myself searching aggressively for areas of doubt in the code. Some of those follow but I plan to edit the code and remove these as and when you point me in the right direction.

1. Should Node<T>.element be volatile? I think perhaps.


2. Should Node<T>.next be volatile? I think not but I am not sure why.


3. Have I chosen a good method for the iterator? I picked a counter rather than seeing the head for the second time to ensure I am resilient to an increase/decrease in size of the ring. This has the small downside of having slightly less predictability but it guarantees termination and is only a bit strange under high parallelism.

NB: Container is not intended to be used between a producer and a consumer. It is designed more for keeping a note of which objects have a particular feature in an iterable way. I use it to keep track of threads in the process of calling put on a BlockingQueue (which may of course block) so I can interrupt them if the queue needs to close.

I thought about a comment, but too long, several things I can think of:

1. This does not guarantee order, i.e. an item is entered into the next free slot, and if there is a fast producer, the order the consumer sees is not guaranteed. Is this intentional?




2. There is no atomic combined detach/attach operation, this means that for example:
   Thread A: Attach starts, calls getFree(), which marks the node as not free (and is switched out before the element reference is set)
   Thread B: is iterating, and hits this node, sees it's not free, so valid node, and returns this, if access to element is done (without a null pointer check), will result in an exception - I guess this is okay(?) Or should you test in your iterator and throw a ConcurrentModification?

I think it's simpler if you maintain an AtomicReference in the node to the element and test that rather than a separate boolean and the reference.

Edit 1:

Looking at this:

  // Doesn't matter if it fails. That would just mean someone else was doing the same.

  head.set(freeNode.next);

Is this necessarily correct? If Thread A sets $n+1$ as head at the same time as Thread B setting n as head, and B succeeds - is the ring in a consistent state? I guess the no ordering guarantee means that this doesn't matter too much, but it would violate the $O(1)$ claim! ;) In fact, I would question the whole $O(1)$ claim, this is at best $O(1)$ and at worst $O(n)$...

If thread A does Container.remove() and then gets interrupted by thread B after the .detach() but before the //Mark it free, and thread B then iterates, it's going to get a ref to an item that's null, which is probably Not What You Want.