<html><head></head><body>Did you consider a concurrent hash map?<br>
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.<br><br><div class="gmail_quote">Luke Sandberg <lukeisandberg@gmail.com> wrote:<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<p dir="ltr">A doubly linked list that exposes the nodes would have that behavior.</p>
<div class="gmail_quote">On Dec 30, 2014 9:23 AM, "Oleksandr Otenko" <<a href="mailto:oleksandr.otenko@oracle.com">oleksandr.otenko@oracle.com</a>> wrote:<br type="attribution" /><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  
    
  
  <div bgcolor="#FFFFFF" text="#000000">
    Do you know a non-concurrent structure that you are looking for?<br />
    <br />
    (eg you don't like O(n) for removal of arbitrary items - but is it
    possible to have <i>all</i> operations O(1), even in a
    non-concurrent case?)<br />
    <br />
    <br />
    Alex<br />
    <br />
    <br />
    <div>On 22/12/2014 02:35, Luke Sandberg
      wrote:<br />
    </div>
    <blockquote type="cite">
      <p dir="ltr">I have come across a few situations where i am
        looking for a datastructure and i feel like i keep coming up
        short.</p>
      <p dir="ltr">The situation is analogous to the 'waiters' list in
        java.util.concurrent.FutureTask.</p>
      <p dir="ltr">Basically, I need to be able to publish a non-null
        object reference into a data structure where<br />
        * order doesn't matter (insertion order would be nice, but i
        don't care that much)<br />
        * add and remove identity semantics<br />
        * concurrent iteration (weakly consistent is fine)<br />
        * add/remove are non-blocking</p>
      <p dir="ltr">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.</p>
      <p dir="ltr">An AtomicReferenceArray would be super easy, but i
        can't put a bound on the number of items.</p>
      <p dir="ltr">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.</p>
      <p dir="ltr">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?</p>
      <p dir="ltr">Just to motivate this a little bit, the two cases I
        am looking at in particular are:</p>
      <p dir="ltr">* maintaining a set of threads associated with a
        server 'request' (threads enter/exit when they start executing
        tasks associated with the request)<br />
        * maintaining a set of futures to be cancelled (futures are
        removed when they complete to avoid pinning their referents).</p>
      <p dir="ltr">Any pointers or ideas?</p>
      <br />
      <fieldset></fieldset>
      <br />
      <pre>_______________________________________________
Concurrency-interest mailing list
<a href="mailto:Concurrency-interest@cs.oswego.edu" target="_blank">Concurrency-interest@cs.oswego.edu</a>
<a href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest" target="_blank">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a>
</pre>
    </blockquote>
    <br />
  </div>

</blockquote></div>
<p style="margin-top: 2.5em; margin-bottom: 1em; border-bottom: 1px solid #000"></p><pre class="k9mail"><hr /><br />Concurrency-interest mailing list<br />Concurrency-interest@cs.oswego.edu<br /><a href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><br /></pre></blockquote></div><br>
-- <br>
Sent from my Android phone with K-9 Mail. Please excuse my brevity.</body></html>