0

I am looking for a thread safe infinite blocking fifo which is backed by a fixed buffer such as an array. The semantics would be that multiple readers and writer threads can accesses it safely. Writers block if the buffer is full and overwrite the oldest item. Readers block if the buffer is empty. Fifo ordering must be maintained when the counter of total added and total removed has wrapped around the internal buffer size one or many times.

Interestingly the usual places that I would look for this (java's own concurrent collections, commons collections, guava) don't see to have an instant answer to such an 'obvious' requirement.

simbo1905
  • 6,321
  • 5
  • 58
  • 86

5 Answers5

3

You are actually describing an ArrayBlockingQueue.

It is thread-safe and has been designed for that exact purpose:

  • writers wait for space to become available if the queue is full
  • readers can wait up to a specified wait time if necessary for an element to become available
Jean Logeart
  • 52,687
  • 11
  • 83
  • 118
  • thanks for your answer. the first thing that i tried was ArrayBlockingQueue. the unit tests started failing when there were random additions and random removals with attempts to overflow and batch inserts and batch removals. i want fifo ordering guarenteed without having to externally track the order or sorting if possible. – simbo1905 Feb 18 '13 at 16:37
  • i mean random reads/write to the logical head and logical tail not random within the logical fifo ordering. if i always want the buffer to be full efficiently then circular buffer semantics seem like something beyond the raw ABQ. – simbo1905 Feb 18 '13 at 16:54
  • @simbo1905 - ABQ _is_ a circular buffer. it's not clear what functionality you are looking for which ABQ lacks? – jtahlborn Feb 18 '13 at 16:56
  • by random i mean random adds/removes from the logical head and tail of the collection which is not the physical head/tail of a linear collection if you attempt circular buffer semantics (meaning its always full and you overrite the oldest value when you insert the new value) – simbo1905 Feb 18 '13 at 16:57
  • @simbo1905 - you're going to have to be clearer than that... maybe you could show some sample code which fails with ABQ? – jtahlborn Feb 18 '13 at 16:58
  • @jtahlborn agreed. in my defence see this prior art where people have had to write their own http://stackoverflow.com/questions/7266042/java-ring-buffer i was asking the community due to my surprise of having to write unit tests for this sort of 'obvious functionality' – simbo1905 Feb 18 '13 at 17:04
  • @simbo1905 - okay, if you want functionality like that, why does your question state "writers block if the buffer is full"? in the example you linked, a writer would never block, it would overwrite the oldest item. – jtahlborn Feb 18 '13 at 17:05
  • question edited. apologies for lack of clarity and thankyou for your consideration. – simbo1905 Feb 18 '13 at 17:07
  • turns out my failing junit using an ABQ to test a disruptor was failing as the objects passed by the queue were not immutable. ArrayBlockingQueue is answer. thanks for your persistence :-) – simbo1905 Feb 19 '13 at 23:29
0

It sounds like you're looking for ArrayBlockingQueue.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • i have edited the question to make it clearer that i am looking for something that could be a blocking circular buffer where the writer overwrites the oldest items. – simbo1905 Feb 18 '13 at 17:08
0

What about java.util.concurrent.ArrayBlockingQueue

Stanislav Levental
  • 2,165
  • 1
  • 14
  • 28
  • thanks for your answer. on other answers which suggest ABQ I indicate that i am more looking for a circular buffer which is not out-of-the-box with ABQ. – simbo1905 Feb 18 '13 at 16:51
0

It's not clear if you are looking for infinity blocking queue or for bounded blocking queue.

  1. Bounded blocking queue: java.util.concurrent.ArrayBlockingQueue
  2. Infinity blocking queue(limited only by RAM constraint): java.util.concurrent.LinkedBlockingQueue

For all the cases I will suggest to use ArrayBlockingQueue.

max
  • 11
  • 3
  • thanks for your answer. on other answers which suggest ABQ I indicate that i am more looking for a circular buffer which is not out-of-the-box with ABQ. – simbo1905 Feb 18 '13 at 16:52
  • hum. i was stuck on having an array as i didn't necessarily want the garbage collection of adding and removing links. yet thats probably something that may be acceptable and linked blocking queue may do the trick. will give it a go and let you know. – simbo1905 Feb 18 '13 at 17:12
0

For an infinite queue you would have to create you own class implementing the BlockingQueue interface using a queue delegate (maybe ArrayBlockingQueue) and when the queue runs full, adapt the size, creating a new and bigger delegate. This should be infinite up to MAX_INT and avoid the GC overhead involved with linked queues (which need to create nodes for each inserted object). If needed, you can shrink the delegate, too.

Ralf H
  • 1,392
  • 1
  • 9
  • 17
  • what about maintaining fifo ordering with lots of random adds and removes? – simbo1905 Feb 18 '13 at 16:39
  • Not sure what you mean here. In a FIFO (a.k.a list or queue) there should be no random writes in the middle. – Ralf H Feb 18 '13 at 16:45
  • apologies i did not mean random access i meant randomised reads from the head or tail. if you try to make a circular buffer with an ArrayBlockingQueue such that it remains full but the head and tail are not at position 0 or position (size-1) then making sure that you always have the next read from the logical tail and the next read from the logical head is not so easy as calling the built in head/tain methods on the stucture which model a linear structure not an infinite circular buffer. – simbo1905 Feb 18 '13 at 16:49
  • yes ArrayBlockingQueue you can infinitely add and infinitely remove. – simbo1905 Feb 19 '13 at 23:30