javainterlockedatomicreferenceatomic-swap

Possible to create AtomicReference that can be swapped atomically?


Is there any way to implement a type of reference whose value can be exchanged with another atomically?


In Java we have AtomicReference which can be swapped with a local variable but not with another AtomicReference.

You can do:

AtomicReference r1 = new AtomicReference("hello");
AtomicReference r2 = new AtomicReference("world");

and swap them with a combination of two operations:

r1.set(r2.getAndSet(r1.get()));

But this leaves them in an inconsistent state in between, where both contain "hello". Also even if you could swap them atomically, you still could not read them (as a pair) atomically.


What I would like to be able to do is:

PairableAtomicReference r1 = new PairableAtomicReference("hello");
PairableAtomicReference r2 = new PairableAtomicReference("world");
AtomicRefPair rp = new AtomicRefPair(r1, r2);

then

Object[] oldVal, newVal;
do {
    oldVal = rp.get();
    newVal = new Object[] {oldVal[1], oldVal[0]};
} while (! rp.compareAndSet(oldVal, newVal));

to swap the values, and in another thread:

AtomicRefPair otherRP = new AtomicRefPair(r1, r2);
System.out.println(Arrays.toString(otherRP.get()));

and be certain that the output will be either [hello, world] or [world, hello].

Notes:

Is it possible to implement a lock-free version of AtomicRefPair? I have a hunch that it isn't, but if not then maybe there is an article somewhere that explains why?


Related: How do I atomically swap 2 ints in C#?


Solution

  • I don't know if there's a nice solution, but the following ugly one could work:

    public final class MyReference<T> extends ReentrantLock implements Comparable<MyReference<T>> {
        public MyReference() {
            id = counter.incrementAndGet();
        }
    
        public void swap(MyReference<T> other) {
            if (id < other.id) {
                lock();
                other.lock();
            } else {
                other.lock();
                lock();
            }
            final T tmp = value;
            value = other.value;
            other.value = tmp;
            unlock();
            other.unlock();
        }
    
        public static <T> List<T> consistentGet(List<MyReference<T>> references) {
            final ArrayList<MyReference<T>> sortedReferences = Lists.newArrayList(references);
            Collections.sort(sortedReferences);
            for (val r : sortedReferences) r.lock();
            final List<T> result = Lists.newArrayListWithExpectedSize(sortedReferences.size());
            for (val r : references) result.add(r.value);
            for (val r : sortedReferences) r.unlock();
            return result;
        }
    
        @Override
        public int compareTo(MyReference<T> o) {
            return id < o.id ? -1 : id > o.id ? 1 : 0;
        }
    
        private final static AtomicInteger counter = new AtomicInteger();
    
        private T value;
        private final int id;
    }