Concurrently Iterable Poor Array List As I wrote on SO, I need an ArrayList-like structure allowing just the following operations


get(int index)
add(E element)
set(int index, E element)
iterator()


while supporting iterations concurrent with modifications. While I'm waiting for something better, I tried it myself. It was a bit harder than expected, so I used synchronization, which made it easy again. I'm linking to the full code and the test and showing here the relevant part (i.e., everything but the imports).

/**
 * A data structure implementing a tiny subset of List operations and allowing concurrent access.
 *
 * See https://stackoverflow.com/q/26424030/581205 for requirements.
 */
public class ConcurrentIterable&lt;E&gt; implements Iterable&lt;E&gt; {
    class MyIterator extends UnmodifiableIterator&lt;E&gt; {
        @Override public boolean hasNext() {
            return index &lt; size();
        }

        @Override public E next() {
            try {
                return get(index++); // Safe as the array never shrinks.
            } catch (final IndexOutOfBoundsException e) {
                // This is hacky, but better than checking the size upfront, as the size may change.
                throw new NoSuchElementException();
            }
        }

        private int index;
    }

    /**
     * The returned iterator may or may not see the changes made after its creation.
     * The only guarantee in case of concurrent modifications is is that
     * it sees no garbage provided that the items are immutable.
     */
    @Override public Iterator&lt;E&gt; iterator() {
        return new MyIterator();
    }

    public synchronized int size() {
        return size;
    }

    @SuppressWarnings("unchecked")
    public synchronized E get(int index) {
        checkElementIndex(index, size);
        return (E) data[index];
    }

    public synchronized void add(E element) {
        if (data.length == size) grow();
        data[size++] = element;
    }

    public synchronized void set(int index, E element) {
        checkElementIndex(index, size);
        data[index] = element;
    }

    private void grow() {
        data = Arrays.copyOf(data, newSize(data.length));
    }

    private static int newSize(int oldSize) {
        int result = oldSize + (oldSize&gt;&gt;3) + 4; // Grow by about 1/8 only.
        if (result-MAX_ARRAY_SIZE &gt; 0) result = MAX_ARRAY_SIZE; // Handle overflow.
        if (result&lt;=oldSize) throw new OutOfMemoryError();
        return result;
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // See ArrayList.

    private int size;
    private Object[] data = new Object[4];
}


I'm aware that it's incompatible with the Collection or List interfaces, but it's not meant to be general use class (though it may change). I need no additional constructors or other features.

Concerning spacing and single line conditional statements... yes, I know, I just don't care (my own conventions differ slightly).

I'll probably try to re-implement this without synchronization as a challenge.
General

private static int newSize(int oldSize) {
    int result = oldSize + (oldSize&gt;&gt;3) + 4; // Grow by about 1/8 only.
    if (result-MAX_ARRAY_SIZE &gt; 0) result = MAX_ARRAY_SIZE; // Handle overflow.
    if (result&lt;=oldSize) throw new OutOfMemoryError();
    return result;
}


Alright, leaving aside the 1-liners (OK, I said it... it sucks), there are other things here too:

YOU THROW OutOfMemoryError

Ouch.
Additionally, the method is only called from one place (grow()), and the call-site has only one line of code. Moving this logic in to the grow() call would be fine.
Other methods call checkElementIndex(), but that method is not included with your code.
You have the Object[] data variable. This is a horrible datatype to use because it introduces the need to do the explicit casts in the rest of the code, like:

return (E) data[index];


it is now relatively common in Java to require the class is given at the same time as the constructor. If you have the following code:
private E[] data;

public ConcurrentIterable(Class&lt;E&gt; clazz) {
    @SuppressWarnings(&quot;unchecked&quot;)
    data = (E[])Array.newInstance(clazz, 4);
}

Then, when you want to create your list, you create it with:
ConcurrentIterable&lt;MyClass&gt; myiterable = new ConcurrentIterable&lt;&gt;(MyClass.class);

from that point on, the inner-content of the class never needs to do an explicit cast from the data store.
Synchronization
Synchronizing on the instance itself is an anti-pattern, generally. In your class, you have synchronized methods: public synchronized void add(E element), etc.
What this means is that anyone who has an instance of your class, can mess with your synchronization and create deadlocks. Someone does the following:
public class MyClass {
    private final ConcurrentIterable&lt;String&gt; iterable = new ConcurrentIterable&lt;&gt;();

    ....

    public void doSomething() {
        synchronized(iterable) {
            Thread.sleep(100000);
        }
    }

Now, suddenly, your code hangs and does not complete.
When using synchronization it is almost always a bug to have a synchronization point on a public/leaked instance.
Apart from that issue, the synchronization looks complete, but excessively scoped. You lock the whole data structure. Your instance is 'serialized', no matter how many threads you have, only one thread can be doing anything at any one time.
There has to be a better way....
Alternate scheme
If it was me, I would consider a combination of the AtomicReferenceArray an AtomicInteger, and a ReentrantLock. The system would look something like:
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceArray;
import java.util.concurrent.locks.ReentrantLock;


public class ConcurrentIterable&lt;T&gt; implements Iterable&lt;T&gt; {
    
    private static final int CONTAINER_SHIFT = 10; // 1024 per container.
    private static final int CONTAINER_SIZE = 1 &lt;&lt; CONTAINER_SHIFT;
    private static final int CONTAINER_MASK = CONTAINER_SIZE - 1;
    
    private final AtomicInteger size = new AtomicInteger();
    private final ReentrantLock lock = new ReentrantLock();
    private final ArrayList&lt;AtomicReferenceArray&lt;T&gt;&gt; containers = new ArrayList&lt;&gt;();
    
    private final AtomicReferenceArray&lt;T&gt; getContainer(int index) {
        int cont = index &gt;&gt;&gt; CONTAINER_SHIFT;
        lock.lock();
        try {
            while (cont &gt;= containers.size()) {
                containers.add(new AtomicReferenceArray&lt;T&gt;(CONTAINER_SIZE));
            }
            return containers.get(cont);
        } finally {
            lock.unlock();
        }
    }
    
    private void checkIndex(final int index) {
        final int sz = size.get();
        if (index &gt;= sz) {
            throw new NoSuchElementException(String.format(&quot;No element %d in structure of size %d&quot;, index, sz));
        }
    }

    public T get(final int index) {
        checkIndex(index);
        return getContainer(index).get(index &amp; CONTAINER_MASK);
    }

    public T set(final int index, T value) {
        checkIndex(index);
        return getContainer(index).getAndSet(index &amp; CONTAINER_MASK, value);
    }
    
    public void add(T value) {
        int index = size.getAndIncrement();
        getContainer(index).set(index &amp; CONTAINER_MASK, value);
    }
    
    @Override
    public Iterator&lt;T&gt; iterator() {
        return new Iterator&lt;T&gt;() {
            
            int next = 0;
            final int last = size.get();

            @Override
            public boolean hasNext() {
                return next &lt; last;
            }

            @Override
            public T next() {
                return get(next++);
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
            
        };
    }

}

There is a race condition in the above, but I would probably solve it with documentation, not logic. The race condition is that there is a moment when you add a member, the size will be incremented, but the get() could return null in one thread in the instant before the value is set to the new value in another thread.
If you document that the container can hold null values, and that the iterator/get may return a null before the value is added, then you have the bonus of being able to support null values in the data too.
Note, it would be relatively trivial for the calling code to handle null return values.
There's a second caveat. I set up the iterator to loop to the last value that was added when the iterator was created. If you change the line:
return next &lt; last;

to be
return next &lt; size.get();

then you will iterate over all values added up to the last add. (but with slightly more risk that the last values may be null)