CopyOnWriteArrayList

If the list is altered while a read or a traversal is taking place, the entire array
must be copied.

As the name suggests, the CopyOnWriteArrayList class is a replacement for
the standard ArrayList class. CopyOnWriteArrayList has been made threadsafe
by the addition of copy-on-write semantics, which means that any operations
that mutate the list will create a new copy of the array backing the list
(as shown in figure 4.8). This also means that any iterators formed don’t have to
worry about any modifications that they didn’t expect.
This approach to shared data is ideal when a quick, consistent snapshot of data
(which may occasionally be different between readers) is more important than perfect
synchronization (and the attendant performance hit). This is often seen in non-missioncritical
data.
Let’s look at an example of copy-on-write in action. Consider a timeline of microblogging
updates. This is a classic example of data that isn’t 100 percent mission-critical
and where a performant, self-consistent snapshot for each reader is preferred over
total global consistency. This listing shows a holder class that represents an individual
user’s view of their timeline.

public class MicroBlogTimeline {
 private final CopyOnWriteArrayList<Update> updates;
 private final ReentrantLock lock;
 private final String name;
 private Iterator<Update> it;

 public MicroBlogTimeline(String name_,
   CopyOnWriteArrayList<Update> updates_, ReentrantLock lock_) {
  this.name = name_;
  this.updates = updates_;
  this.lock = lock_;
 }

 public void addUpdate(Update update_) {
  updates.add(update_);
 }

 public void prep() { // Set up Iterator
  it = updates.iterator();
 }

 public void printTimeline() {
  lock.lock();
  try {
   if (it != null) {
    System.out.print(name + ": ");
    while (it.hasNext()) {
     Update s = it.next();
     System.out.print(s + ", ");
    }
    System.out.println();
   }
  } finally {
   lock.unlock();
  }
 }
}

class CopyOnWriteArrayListTest {
 public static void main(String[] args) {
  final CountDownLatch firstLatch = new CountDownLatch(1);
  final CountDownLatch secondLatch = new CountDownLatch(1);
  final Update.Builder ub = new Update.Builder();
  final CopyOnWriteArrayList<Update> l = new CopyOnWriteArrayList<>();
  l.add(ub.author(new Author("Ben")).updateText("I like pie").build());
  l.add(ub.author(new Author("Charles")).updateText("I like ham on rye").build());
  ReentrantLock lock = new ReentrantLock();
  final MicroBlogTimeline tl1 = new MicroBlogTimeline("TL1", l, lock);
  final MicroBlogTimeline tl2 = new MicroBlogTimeline("TL2", l, lock);
  Thread t1 = new Thread() {
   public void run() {
    l.add(ub.author(new Author("Jeffrey")).updateText("I like a lot of things").build());
    tl1.prep();
    firstLatch.countDown();
    try {
     secondLatch.await();
    } catch (InterruptedException e) {
    }
    tl1.printTimeline();
   }
  };
  Thread t2 = new Thread() {
   public void run() {
    try {
     firstLatch.await();
     l.add(ub.author(new Author("Gavin")).updateText("I like otters").build());
     tl2.prep();
     secondLatch.countDown();
    } catch (InterruptedException e) {
    }
    tl2.printTimeline();
   }
  };
  t1.start();
  t2.start();
 }
}

There is a lot of scaffolding in the listing—unfortunately this is difficult to avoid.
There are quite a few things to notice about this code:
■ CountDownLatch is used to maintain close control over what is happening
between the two threads.
■ If the CopyOnWriteArrayList was replaced with an ordinary List (B), the
result would be a ConcurrentModificationException.
■ This is also an example of a Lock object being shared between two threads to
control access to a shared resource (in this case, STDOUT). This code would be
much messier if expressed in the block-structured view.


As you can see, the second output line (tagged as TL1) is missing the final update (the
one that mentions otters), despite the fact that the latching meant that mbex1 was
accessed after the list had been modified. This demonstrates that the Iterator contained
in mbex1 was copied by mbex2, and that the addition of the final update was invisible
to mbex1. This is the copy-on-write property that we want these objects to display.