Remove from a collection during iteration

Question

I have set of connection objects (library code I cannot change) that have a send method. If the sending fails, they call back a generic onClosed listener which I implement that calls removeConnection() in my code, which will remove the connection from the collection.

The onClosed callback is generic and can be called at any time. It is called when the peer closes the connection, for example, and not just when a write fails.

However, if I have some code that loops over my connections and sends, then the onClosed callback will attempt to modify a collection during iteration.

My current code creates a copy of the connections list before each iteration over it; however, in profiling this has shown to be very expensive.

Set<Connection> connections = new ....;

public void addConnection(Connection conn) {
    connections.add(conn);
    conn.addClosedListener(this);
}

@Override void onClosed(Connection conn) {
    connections.remove(conn);
}

void send(Message msg) {
    // how to make this so that the onClosed callback can be safely invoked, and efficient?
    for(Connection conn: connections)
        conn.send(msg);
}

How can I efficiently cope with modifying collections during iteration?

`An Iterator is an object that enables you to traverse through a collection and to remove elements from the collection selectively, if desired` may be I don't understand clearly your situation but I think that you can remove elements from collection during iteration and you don't get any exception — Aliaksei Bulhak, May 24 '13 at 08:21
on what @aleksei bulgak said http://stackoverflow.com/questions/1196586/calling-remove-in-foreach-loop-in-java — benst, May 24 '13 at 08:21

score 3 · Answer 1 · answered May 24 '13 at 08:18

3

To iterate a collection with the concurrent modification without any exceptions use List Iterator.

http://www.mkyong.com/java/how-do-loop-iterate-a-list-in-java/ - example

If you use simple for or foreach loops, you will receive ConcurrentModificationException during the element removing - be careful on that.

As an addition, you could override the List Iterator with your own one and add the needed logic. Just implement the java.util.Iterator interface.

answered May 24 '13 at 08:18

user

3,058
23
45

1

but the removal has to happen through the iterator, and the callback does not know this.... – Will May 24 '13 at 08:19
If you do not have access to the iterator, then you have to stay with your copied collection. – mschenk74 May 24 '13 at 08:21
+1 and article on this theme : How to Avoid ConcurrentModificationException when using an Iterator http://www.javacodegeeks.com/2011/05/avoid-concurrentmodificationexception.html – Dmitry Zagorulkin May 24 '13 at 08:40
1

-1 This was never a solution based on the OP's stated problem. – Tim Bender May 24 '13 at 08:57

OldCurmudgeon · Answer 2 · 2013-05-24T23:43:05.243

I would write a collection wrapper that:

Keeps a set of objects that are to be removed. If the iteration across the underlying collection comes across one of these it is skipped.
On completion of iteration, takes a second pass across the list to remove all of the gathered objects.

Perhaps something like this:

class ModifiableIterator<T> implements Iterator<T> {
  // My iterable.
  final Iterable<T> it;
  // The Iterator we are walking.
  final Iterator<T> i;
  // The removed objects.
  Set<T> removed = new HashSet<T>();
  // The next actual one to return.
  T next = null;

  public ModifiableIterator(Iterable<T> it) {
    this.it = it;
    i = it.iterator();
  }

  @Override
  public boolean hasNext() {
    while ( next == null && i.hasNext() ) {
      // Pull a new one.
      next = i.next();
      if ( removed.contains(next)) {
        // Not that one.
        next = null;
      }
    }
    if ( next == null ) {
      // Finished! Close.
      close();
    }
    return next != null;
  }

  @Override
  public T next() {
    T n = next;
    next = null;
    return n;
  }

  // Close down - remove all removed.
  public void close () {
    if ( !removed.isEmpty() ) {
      Iterator<T> i = it.iterator();

      while ( i.hasNext() ) {
        if ( removed.contains(i.next())) {
          i.remove();
        }
      }
      // Clear down.
      removed.clear();
    }
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException("Not supported.");
  }

  public void remove(T t) {
    removed.add(t);
  }

}

public void test() {
  List<String> test = new ArrayList(Arrays.asList("A","B","C","D","E"));
  ModifiableIterator i = new ModifiableIterator(test);
  i.remove("A");
  i.remove("E");
  System.out.println(test);
  while ( i.hasNext() ) {
    System.out.println(i.next());
  }
  System.out.println(test);
}

You may need to consider whether your list could contain null values, in which case you will need to tweak it somewhat.

Please remember to close the iterator if you abandon the iteration before it completes.

Tim Bender · Accepted Answer · 2013-05-24T08:44:20.810

1

A ConcurrentSkipListSet is probably what you want.

You could also use a CopyOnWriteArraySet. This of course will still make a copy, however, it will only do so when the set is modified. So as long as Connection objects are not added or removed regularly, this would be more efficient.

edited May 24 '13 at 08:44

answered May 24 '13 at 08:36

Tim Bender

20,112
2
49
58

I discovered that the skip list needs objects to be comparable ... which is a runtime exception, not a compiler error. Nasty. But CopyOnWriteArraySet was much easier to retrofit, and seems to be working. Am benchmarking now. Thx! – Will May 24 '13 at 09:05

score 1 · Answer 4 · answered May 24 '13 at 08:42

1

You can also use ConcurrentHashMap. ConcurrentHashMap is thread-safe, so you don't need to make a copy in order to be able to iterate. Take a look at this implementation.. http://www.java2s.com/Tutorial/Java/0140__Collections/Concurrentset.htm

answered May 24 '13 at 08:42

awsome

2,143
2
23
41

Remove from a collection during iteration

4 Answers4