How does ArrayBlockingQueue avoid shuffling array elements?

Question

Scenario: My producer fills the array up, say capacity new int[10], before my consumer gets a chance to consume any. My producer sees the array is full and blocks.

Then my consumer comes along and removes int[0], and signals to the producer that the array now has an empty slot to fill.

My producer wakes up, and tries to add a new element to the array. Considering only int[0] is free, and we are implementing FIFO, does ArrayBlockingQueue shuffle all the remaining 9 elements to the left, filling 0-8 indexes and leave int[9] free for the producer?

I've looked at the implementation but don't see any array copy functionality,

Sergey Kalinichenko · Accepted Answer · 2016-11-10 11:56:32Z

No copying of array elements is performed, because ArrayBlockingQueue uses the array as a circular buffer. It maintaining two indexes, takeIndex and putIndex, and wraps them around when they reach the end of the array.

After an operation that adds or takes an element it calls a private "increment" method called inc, which wraps the index around the end:

final int inc(int i) { return (++i == items.length)? 0 : i; }

Here is an example of how this method is used:

private void insert(E x) { items[putIndex] = x; putIndex = inc(putIndex); // <<== Wraps around ++count; notEmpty.signal(); }

Umais Gillani · Accepted Answer · 2016-11-10 12:03:16Z

ArrayBlockingQueue maintain two variables suppose frontIndex and rearIndex to handle this instead of shifting elements. If the queue is full. and any element is pulled up by consumer from the index a[0] then the rearIndex moved to index 1 and next time whenever producer tries to add any element frontIndex will be moved to the 0 index after the 9 Index. and the next put operation will be done on a[0].

Here FrontIndex==RearIndex means the queue is full.

Collectives™ on Stack Overflow

How does ArrayBlockingQueue avoid shuffling array elements?

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related