[concurrency-interest] Looking for a data struture

Luke Sandberg lukeisandberg at gmail.com
Mon Dec 22 13:08:34 EST 2014


My items aren't necessarily comparable. (though maybe i could use guavas
Ordering#arbitrary() which uses identity hashcodes).  Also, CSLS has log(n)
add/remove.

On Mon, Dec 22, 2014 at 10:05 AM, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:
>
> ConcurrentSkipListSet?
>
>
> On Sunday, December 21, 2014, Luke Sandberg <lukeisandberg at gmail.com>
> 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?
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141222/82835bb6/attachment.html>


More information about the Concurrency-interest mailing list