thread-safe CopyOnWriteArrayList reverse iteration

Question

Consider the following code snippet:

private List<Listener<E>> listenerList = new CopyOnWriteArrayList<Listener<E>>();

public void addListener(Listener<E> listener) {
    if (listener != null) {
        listenerList.add(listener);
    }
}

public void removeListener(Listener<E> listener) {
    if (listener != null) {
        listenerList.remove(listener);
    }
}

protected final void fireChangedForward(Event<E> event) {
    for (Listener<E> listener : listenerList) {
        listener.changed(event);
    }
}

protected final void fireChangedReversed(Event<E> event) {
    final ListIterator<Listener<E>> li = listenerList.listIterator(listenerList.size());
    while (li.hasPrevious()) {
        li.previous().changed(event);
    }
}

There is a listener list that can be modified and iterated. I think the forward iteration (see method #fireChangedForward) should be safe. The question is: is the reverse iteration (see method #fireChangedReversed) also safe in a multi-threaded environment? I doubt that, because there are two calls involved: #size and #listIterator. If it's not thread-safe, what is the most efficient way to implement #fireChangedReversed under the following circumstances:

optimize for traversal
avoid usage of locking if possible
avoid usage of javax.swing.event.EventListenerList
prefer solution without usage of third-party lib, e.g. implementation in own code possible

Stuart Marks · Accepted Answer · 2017-02-04T23:48:43.590

5

Indeed, listenerList.listIterator(listenerList.size()) is not thread-safe, for exactly the reason you suggested: the list could change size between the calls to size() and listIterator(), resulting in either the omission of an element from the iteration, or IndexOutOfBoundsException being thrown.

The best way to deal with this is to clone the CopyOnWriteArrayList before getting the iterator:

    CopyOnWriteArrayList<Listener<E>> listenerList = ... ;
    @SuppressWarnings("unchecked")
    List<Listener<E>> copy = (List<Listener<E>>)listenerList.clone();
    ListIterator<Listener<E>> li = copy.listIterator(copy.size());

The clone makes a shallow copy of the list. In particular, the clone shares the internal array with the original. This isn't entirely obvious from the specification, which says merely

Returns a shallow copy of this list. (The elements themselves are not copied.)

(When I read this, I thought "Of course the elements aren't copied; this is a shallow copy!" What this really means is that neither the elements nor the array that contains them are copied.)

This is fairly inconvenient, including the lack of a covariant override of clone(), requiring an unchecked cast.

Some potential enhancements are discussed in JDK-6821196 and JDK-8149509. The former bug also links to a discussion of this issue on the concurrency-interest mailing list.

edited Feb 04 '17 at 23:48

answered Feb 04 '17 at 23:12

Stuart Marks

127,867
37
205
259

1

The code should read `(List)((CopyOnWriteArrayList>)listenerList).clone()`, or else the code doesn't compile because it's looking for the `clone` method in `Object`, which is a protected method (I know that that's what you meant to write, but it took me a few minutes to find out what the error was). – MikaelF Feb 04 '17 at 23:34
Ah, that's interesting. I wouldn't have come up with this idea. I think that's the best solution so far. – Holger Feb 04 '17 at 23:42
@MikaelF "Works for me." :-) I had assumed the declaration of `listenerList` was `CopyOnWriteArrayList>` in Holger's original example, but you're right, it wasn't. I'll edit the snippet to make it clearer. – Stuart Marks Feb 04 '17 at 23:45
@Holger I missed it too! I only knew about it because I had previously dug up the old concurrency-interest thread. – Stuart Marks Feb 04 '17 at 23:46
1

@Stuart Marks Oh... My Intellij keeps underlining the `clone` in red and saying "'clone()' has protected access in java.lang.Object". The double cast is also what the accepted answer recommends in [clone() has protected access - made public Object clone()](http://stackoverflow.com/questions/16044887/clone-has-protected-access-made-public-object-clone), and other similar questions. I don't know why it works for you and not for me... but good if it works for OP! thx – MikaelF Feb 04 '17 at 23:50
1

@StuartMarks I see, I didn't understand what the problem was, but now I get it, the double cast is only necessary if the list was declared as a `List` and not as its actual implementation. Smarter every day (hopefully)... – MikaelF Feb 05 '17 at 00:22

score 1 · Answer 2 · answered Feb 04 '17 at 20:36

1

One simple way to do that is to call #toArray method and iterate over the array in reverse order.

answered Feb 04 '17 at 20:36

AdamSkywalker

11,408
3
38
76

Yes, that should be safe, but also requires an extra array copy for every iteration. I'll wait some time for more answers. – Holger Feb 04 '17 at 20:48
@Holger you can use reflection hacks to avoid array copy – AdamSkywalker Feb 04 '17 at 21:03

MikaelF · Answer 3 · 2017-02-06T18:42:30.727

You could always just get a ListIterator and "fast-forward" to the end of the list as such:

final ListIterator<Listener<E>> li = listenerList.listIterator();
if (li.hasNext()) {
    do{
    li.next();
    } while (li.hasNext());
}
while (li.hasPrevious()) {
        li.previous().changed(event);
    }

EDIT I switched the quirky exception-handling of my previous answer for a do/while loop that places the cursor of the ListIterator after the last element, in order to be ready for the next previous call.

RE-EDIT As pointed out by @MikeFHay, a do/while loop on an iterator will throw a NoSuchElementException on an empty list. To prevent this from happening, I wrapped the do/while loop with if (li.hasNext()).

That code looks like it will throw a `NoSuchElementException` if the list is empty. — MikeFHay, Feb 06 '17 at 18:34

thread-safe CopyOnWriteArrayList reverse iteration

3 Answers3

Linked