[concurrency-interest] Concurrent indexed queue

Ashwin Jayaprakash ashwin.jayaprakash at gmail.com
Wed Aug 24 18:04:22 EDT 2011


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)



               ^                      +-----------+
               |                      |<head>     |<---+
               |                      +----^------+    |
(ConcurrentLinkedHashMap-LRU)
          +----+----+                      |           |
+------------+------------+
          |         |                 +----+------+    |   |
|key-ABC     |
      C   |         |+--------------->|version    |    |   |
|            |
      o   |         |                 |data       |    |
+------------|------------+
      n   |         |                 |alreadySeen|    |   |
|key-XYZ     |
      c   +----^----+                 +----^------+    +---+
|            |
      u        |                           |               |
|            |
      r        |                           |
+------------|------------+
      r   +----+----+                 +----+------+        |
|key-GHI     |
      e   |         |                 |version    |        |
|            |
      n   |         |                 |data       |        |
|            |
      t   |         |         +------>|alreadySeen|
+------------+------------+
      L   |         |         |       +-----------+
|                         |
      i   +----^----+         |                            |
.             |
      n        |              |      (Custom node list     |
.             |
      k        |              |       with atomic ops)     |
.             |
      e   +----+----+         |
|                         |
      d   |         |         |
|                         |
      Q   |         +---------+
|                         |
      u   |         |
|                         |
      e   |         |
|                         |
      u   +----^----+
+-------------------------+
      e        |
               |
          +---------+
          |         |



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/20110824/2102b640/attachment.html>


More information about the Concurrency-interest mailing list