O(1) lock free container

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 implements Iterable {

// The capacity of the container.
final int capacity;
// The list.
AtomicReference> head = new AtomicReference>();

// Constructor
public Container(int capacity) {
this.capacity = capacity;
// Construct the list.
Node h = new Node();
Node it = h;
// One created, now add (capacity - 1) more
for (int i = 0; i ();
// 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 it = head.get();
for (int i = 0; i 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 getFree() {
Node 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 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 re

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

-
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?

-
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)\$...

StackExchange Code Review Q#12691, answer score: 6