Friday, December 3, 2010

CopyOnWrite Wrappers

Java has a CopyOnWriteArrayList is a very useful class in java.util.concurrent which, when iterating, takes "snapshots" of the underlying array, and therefore never throws a ConcurrentModificationException.  It is highly effective and efficient when you need to preclude interference among concurrent threads.  But it only implements two types of collection behavior: ArrayList and a CopyOnWriteArraySet.  Unlike many of the other java.util.Collections goodies, like Collections.unmodifiableList, it is not implemented as a wrapper class, but as an actual class.  So, if you want behavior other than an ArrayList or ArraySet, or you need to protect one of your own special List implementations, you are out of luck.  Nor is there any version for a Map, i.e. there is no CopyOnWriteMap.

So I implemented it.  The files are on my wiki page at http://flyingspaniel.wikidot.com/cow.

COWListWrapper wraps any List, providing "CopyOnWrite" behavior for iteration.
COWMapWrapper wraps a Map, providing "CopyOnWrite" behavior when you iterate using keySet(), entrySet(), or values().

There are some hopefully useful utility classes that they use:

UnmodifiableCollection is an actual class, not a wrapper utility, to wrap an underlying Collection with unmodifiable behavior.  It includes static inner classes, UnmodifiableCollection.List and UnmodifiableCollection.Set, that add List or Set behavior.

UnmodifiableIterator is a class implementing ListIterator that works efficiently with the above classes and prohibits modification during iteration.

Enjoy!

A couple of notes.  For any CopyOnWrite implementation, even the "official" Java ones, you only get the iteration safety if you actually use the iterator( ).  If you use the old fashioned "C-style" integer loop

for (int i=0; i < myList.size(); i++) {
  doSomethingWith( myList.get(i));
}

and a separate thread is modifying myList, all bets are off.  You should use the new style:

for (E element:myList) {
  doSomethingWith(element);
}

The standard Java CopyOnWrite classes know exactly what collection behavior (ArrayList or ArraySet)  to implement and, at construction, they make a safe copy any incoming data, and thereafter are completely divorced from the original collection.  My wrapper classes do not, and cannot, know all possible List or Map behaviors.  They use the passed in (wrapped) List or Map for storage and most of the implementation.  For example, a call to add(Object o) is passed to the underlying object, and it implements the behavior and storage.  In other words, my wrappers do not make a "safe" copy of the data at construction time, and remain linked to the underlying collection.  You should not use the wrapped collection directly - all calls and modifications must be done through the the wrapper.  The "safe" copy of data is done only for iteration.

Recently added:
  UnmodifiableCollection.toString() implemented (useful in the unit test)
  COWWrapperTest  unit tests

2 comments:

  1. You really mean "concurrent iteration safe wrappers" instead of copy-on-write wrappers, yes?

    Anyway for this wrapper, you could do without all the synchronization blocks and instead rely on atomic booleans, I think. (With the expectation the underlying Map is thread safe but not iteration safe.) Also I noticed the order here looks inconsistent, though the order does not effectively matter:

    @Override
    public synchronized void putAll(Map m) {
    wrapee.putAll(m);
    clearIterators();

    }

    If you did away with "synchronized" you would have to instead of clearing the iterators, use atomic booleans and keep the iterators non-null. Or some other sort of trickery.

    @Override
    public synchronized Set> entrySet() {
    if (entrySetForIteration == null)
    entrySetForIteration = new UnmodifiableCollection.Set>(wrapee.entrySet());

    return entrySetForIteration;
    }

    might be:

    public Set> entrySet() {
    if (entrySetForIterationRefresh.compareAndSet(true, false))
    entrySetForIteration = new UnmodifiableCollection.Set>(wrapee.entrySet());

    return entrySetForIteration;
    }

    And:

    private void clearIterators() {
    keySetForIterationRefresh.set(true);
    ..
    }

    ReplyDelete
  2. >You really mean "concurrent iteration safe wrappers" instead of copy-on-write wrappers, yes?

    Absolutely correct. But that's a mouthful. :-) I guess they could be named CISListWrapper and CISMapWrapper. Combined with some better comments, that would make their working and intent more clear. Thanks for the suggestion.

    I hadn't considered atomics instead of synchronization. (mainly cause I have little experience with atomics) But I'm not sure if it is reasonable to expect that the underlying Map is itself thread safe. Synchronization makes it more "dummy-proof" and may save one more layer of wrappers.

    ReplyDelete