TheCoder TheCoder - 24 days ago 18
Java Question

How does ArrayBlockingQueue avoid shuffling array elements?

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,

Answer

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();
}
Comments