[concurrency-interest] Looking for a data struture

Luke Sandberg lukeisandberg at gmail.com
Tue Dec 30 19:22:43 EST 2014


A doubly linked list that exposes the nodes would have that behavior.
On Dec 30, 2014 9:23 AM, "Oleksandr Otenko" <oleksandr.otenko at oracle.com>
wrote:

>  Do you know a non-concurrent structure that you are looking for?
>
> (eg you don't like O(n) for removal of arbitrary items - but is it
> possible to have *all* operations O(1), even in a non-concurrent case?)
>
>
> Alex
>
>
> On 22/12/2014 02:35, Luke Sandberg wrote:
>
> 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?
>
>
> _______________________________________________
> Concurrency-interest mailing listConcurrency-interest at cs.oswego.eduhttp://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141230/7544284b/attachment.html>


More information about the Concurrency-interest mailing list