4

does anyone know of an (open source) implementation of a bounded concrrent cyclic queue , or an available API class built into android/java ?

the concurrent (not synchronized or lock based) operations i need for this collection are at least enqueue and dequeue , but enqueue can also be enough .

for those who are not sure about the collection i need , here's some more info:

  • bounded - has max number of items that can be in it .
  • concurrent - allows multiple threads to run operations efficiently without any kind of locking. that's the opposite of synchronized solutions , which only allows a single thread to run operations.
  • cyclic - if we put items into a filled collection , the new item will replace the oldest item.

please help

android developer
  • 114,585
  • 152
  • 739
  • 1,270
  • sounds like you should just copy `ArrayBlockingQueue.java` (it's available in the framework source) and change the `#offer(T)` and `#put(T)` methods to dequeue the last item - and presto - instant bounded queue that expels the last item. – Jens May 10 '12 at 12:56
  • @Jens - ArrayBlockingQueue doesn't permit concurrent access by multiple threads, judging by the source. – mcfinnigan May 10 '12 at 13:00
  • correct .not only that , but it isn't cyclic as well: if you try to put an item into a filled queue , it will wait on it till it's not filled , and the opposite - if you try to get an item from an empty queue , it will wait on it till it's not empty . – android developer May 10 '12 at 13:05
  • 1
    ArrayBlockingQueue `#offer(T)` is non-blocking, just as `#poll()` - the blocking versions are `#put(T)` and `#take()` respectively - so *yeah*, they're used when you need concurrent non-blocking poll & offer.. @androiddeveloper: Yes, that's why you'd have to copy & modify the source to dequeue when the queue is full. – Jens May 10 '12 at 13:08
  • 1
    "concurrent - allows multiple threads to run operations efficiently without any kind of locking" -- by definition, this is impossible. – CommonsWare May 10 '12 at 13:24
  • @CommonsWare: I'm guessing he meant "blocking". – Jens May 10 '12 at 13:30
  • both of us are correct - i meant non-blocking algorithm , so it is lock free and doesn't use any locks (excluding the hardware features) .those terms are about the same: http://en.wikipedia.org/wiki/Non-blocking_algorithm . basically, you can use a hardware solution like CAS in order to avoid using locks , but it's very hard to design a correct algorithm . you can read more about it on many websites , such as this: http://www.cs.tau.ac.il/~multi/?p=slides . – android developer May 10 '12 at 15:40

1 Answers1

0

What you describe sounds very much like disruptor, but it's an external library, not built in. As far as I know, there is no built-in ring buffer data structure in Java standard library.

Michał Kosmulski
  • 9,855
  • 1
  • 32
  • 51
  • correct. it does look similar . do you think it's exactly what i need? do they have a sample code of usage? if so , i will give you a V . :) – android developer May 11 '12 at 13:42
  • There is a code sample in point 4.7 of the [technical description document](http://disruptor.googlecode.com/files/Disruptor-1.0.pdf) [PDF] as well as [in the wiki](http://code.google.com/p/disruptor/wiki/CodeExampleDisruptor2x). Whether disruptor is exactly what you need, only you can tell :) – Michał Kosmulski May 11 '12 at 17:49
  • the sample code doesn't look any similar to what a queue really is . also, i'm not sure what is the purpose of the BatchHandler ,batchConsumer , ConsumerBarrier , and ProducerBarrier. kindly show some code that implements the enqueue & dequeue methods which use this library? – android developer May 12 '12 at 12:48