[concurrency-interest] Looking for a data struture

Aleksandar Prokopec aleksandar.prokopec at gmail.com
Wed Dec 31 05:22:34 EST 2014

Did you consider a concurrent hash map?
It is slightly slower than a data structure based on just a linked list, but it does not sound like you would notice the difference.

Luke Sandberg <lukeisandberg at gmail.com> wrote:
>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>
>>  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
>> Alex
>> On 22/12/2014 02:35, Luke Sandberg wrote:
>> I have come across a few situations where i am looking for a
>> 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
>> 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 +
>> entry overhead is a deal breaker.
>> An AtomicReferenceArray would be super easy, but i can't put a bound
>> the number of items.
>> Also, it would be fine for the code that adds items, to store
>> state (an index, a 'Node' reference), in order to facilitate removal.
>> The best thing i have seen from looking around appears to be
>> like what FutureTask does to implement 'awaitDone', but even there
>> removeWaitier() is O(n).  that seems like a pretty good compromise
>> lists are short, but what would be a better solution when lists are
>> 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'
>> enter/exit when they start executing tasks associated with the
>> * maintaining a set of futures to be cancelled (futures are removed
>> 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
>Concurrency-interest mailing list
>Concurrency-interest at cs.oswego.edu

Sent from my Android phone with K-9 Mail. Please excuse my brevity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141231/5952e2fc/attachment.html>

More information about the Concurrency-interest mailing list