[concurrency-interest] Looking for a data struture

Martin Buchholz martinrb at google.com
Tue Dec 30 11:49:47 EST 2014


On Mon, Dec 22, 2014 at 8:10 AM, Luke Sandberg <lukeisandberg at gmail.com>
wrote:

>
> RE: CLQ with some extra method.  I had thought it would have been nice to
> have CLQ return a Node object for this usecase.  Though if i wouldn't be
> able to physically remove the node then it seems simpler to just build my
> own Trieber stack and implement remove by nulling out the 'item' field in
> the Node object.
>

If you add a Node-returning method to CLQ, you can't guarantee that Nodes
can always be unlinked, but it's possible to sweep a few successor Nodes
whenever an element is removed, which is likely to be good enough in
practice. Taking another look at CLQ, I see CLQ.iterator().remove() makes
no effort to do any unlinking, leaving that task to a future traversal.  If
you have a Node-returning method, it's less likely there will be a "future
iteration".

If you use my pet ConcurrentLinkedDeque instead of ConcurrentLinkedQueue,
you get guaranteed amortized O(1) deletion with negligible garbage
accumulation, and you get an already written unlink(Node) method, so it's
pretty easy to add the "handle-returning method" without dealing with CLD's
extremely tricky unlinking mechanics.  If you want to go this way, I'm
willing to code something up.  Seems generally useful anyways, but is a
fundamental new feature in java collections.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141230/2ecd851b/attachment-0001.html>


More information about the Concurrency-interest mailing list