CODEWITHSUNDEEP
javamultithreadingcollectionsthread-safetyjava.util.concurrent
maaartinus
maaartinus

Reputation: 46432

Thread-safe find and remove an object from a Collection

I wonder how can I do something like the following

class MyCollection<E> implements Collection<E> {
    @Nullable E findAndRemove(Predicate<E> predicate) {
        for (E e : this) {
            if (predicate.test(e)) {
                remove(e);
                return e;
            }
        }
        return null;
    }   
}

in a thread-safe manner. It doesn't really have to be a Collection, as the only needed operations are add and findAndRemove. Note that

Concerning premature optimization and XY problem: Yes, I know! I went into this when fooling around with something I may or mayn't need one day, but I find this problem interesting per se.

Upvotes: 4

Views: 2126

Answers (2)

BeeOnRope
BeeOnRope

Reputation: 64955

Since you only need the add and findAndRemove methods, some type of concurrent hash is a natural choice, as there has been a good implementation (ConcurrentHashMap) since Java 1.5. Now since we don't actually need a Map but rather a Set we can just use (since Java 8 anyway) ConcurrentHashMap.newKeySet() to create a concurrent set using the same implementation as the concurrent map.

Then, given a concurrent set, we can pretty much use your loop above, and optimistically remove the element, and then simply continue searching on failure (which means that a thread concurrently removed the element that matched):

class MyCollection<E> {

  private Set<E> underlying = ConcurrentHashMap.newKeySet();

  void add(E elem) {
    underlying.add(elem);
  }

  @Nullable E findAndRemove(Predicate<E> predicate) {
    for (E e : underlying) {
        if (predicate.test(e) && remove(e)) {
          return e;
        }
    }
    return null;
  }   
}

The only real change with respect to your example code is that we check the result of Set.remove() to see if the element was actually removed. For the concurrent set, this works "safely" - i.e., only the thread which actually removed the object will see true, so this set will correctly return the element only if it was actually removed, and no other thread will then be able to return that element.

It should satisfy all your requirements and perform as well as the underlying concurrent map implementations, which on modern JDKs is "very well".

Note that the use of a Set implies that duplicate elements aren't allowed. It wasn't clear from your description whether you planned to support duplicates or not, but if you did, you could use the same approach built on a concurrent multimap1, or simply using ConcurrentHashMap<E, AtomicInteger>, where the AtomicInteger value a reference count of the number of elements with the same key, the add and findAndRemove methods manipulate the reference count2.

1 In a quick search, however, I couldn't find an obvious open source implementation of a concurrent multimap. Note that you don't actually need a capital-M Multimap implementation with all its functionality - you really only need "some multiset" with the ability to add an element, iterate over available elements, and "remove" an element (i.e., decrement its refcount in the set).

2 I'm actually glossing over a few details of the reference counted implementation since in this case there is a possible race between the thread that decrements the refcount to zero and any thread calling add for the same element which may increment the refcount above zero (but the entry has already been removed). This can be avoided but I don't go into details yet since it isn't clear if you want to support duplicates.

Upvotes: 3

gati sahu
gati sahu

Reputation: 2626

You can use read and write lock for mutation in collection or you can use ConcurrentHashMap to represent collection as set.

Set set =Collections.newSetFromMap(new ConcurrentHashMap<Object,Boolean>());

Upvotes: 1

Related Questions