[concurrency-interest] Concurrent indexed queue

Ashwin Jayaprakash ashwin.jayaprakash at gmail.com
Wed Nov 30 20:00:06 EST 2011


I realized only today that my attempt at describing my data structure using
ascii art was a bad idea. Formatting got messed up. Just for my ref, here's
an image of the same:


[image: Concurrent indexed queue.PNG]



Wouldn't you need multiple datastructures to have indexed access to a
> queue?
>
> Perhaps something like this?
>
> 1. The simple queue on the left just ensures the insertion order 2. But
> first you'd have to use a map where the values are a list of nodes. Each
> node in that list has a certain version of the data 3. Add the node to that
> list (middle of figure) atomically, then enqueue a pointer to that node
> into the main queue 4. The consumer will keep reading from the head of the
> queue, follow the pointer to the versioned node (the list in the middle) 1.
> It will remove the first versioned node from the list in the middle 2. If
> there are any other nodes, then it will keep going down that list and
> toggle those nodes are alreadySeen until it hits the end 5. Obviously it
> will see this versioned chain again further down the queue. But it now
> knows that it has already seen it, so it will clear that versioned node 1.
> It can follow that chain if there are any newer versions (Like Step 4.2)
>
> This would be a really useful datastructure to have as an open source
> library (hint hint).
>
> Regards, Ashwin Jayaprakash.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20111130/c84112f5/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/png
Size: 23478 bytes
Desc: not available
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20111130/c84112f5/attachment-0001.png>


More information about the Concurrency-interest mailing list