[concurrency-interest] Looking for a data struture

Luke Sandberg lukeisandberg at gmail.com
Sun Dec 21 21:35:29 EST 2014


I have come across a few situations where i am looking for a datastructure
and i feel like i keep coming up short.

The situation is analogous to the 'waiters' list in
java.util.concurrent.FutureTask.

Basically, I need to be able to publish a non-null object reference into a
data structure where
* order doesn't matter (insertion order would be nice, but i don't care
that much)
* add and remove identity semantics
* concurrent iteration (weakly consistent is fine)
* add/remove are non-blocking

CLQ is an obvious choice but removal is O(n), another choice would a simple
synchronized identity hash set which is fine but the lock + high entry
overhead is a deal breaker.

An AtomicReferenceArray would be super easy, but i can't put a bound on the
number of items.

Also, it would be fine for the code that adds items, to store additional
state (an index, a 'Node' reference), in order to facilitate removal.

The best thing i have seen from looking around appears to be something like
what FutureTask does to implement 'awaitDone', but even there
removeWaitier() is O(n).  that seems like a pretty good compromise when
lists are short, but what would be a better solution when lists are long?

Just to motivate this a little bit, the two cases I am looking at in
particular are:

* maintaining a set of threads associated with a server 'request' (threads
enter/exit when they start executing tasks associated with the request)
* maintaining a set of futures to be cancelled (futures are removed when
they complete to avoid pinning their referents).

Any pointers or ideas?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141221/3ea92696/attachment.html>


More information about the Concurrency-interest mailing list