SpscGrowableArrayQueue capacity is less than requested capacity about jctools HOT 3 CLOSED

In case the capacity is power of 2, the following code I suggested in #45 should utilize the full capacity:

if (null == lvElement(buffer, calcElementOffset(index + 1, mask))) { // buffer is not full, keep last slot for resize indicator
    return writeToQueue(buffer, e, index, offset);
} else if (mask == maxSize) {
    if (null == lvElement(buffer, offset)) { // try using the last slot as there won't be any resize anymore
        return writeToQueue(buffer, e, index, offset);
    }
    // we're full and can't grow
    return false;
}

To fix the issue I would like to re-structure the queue such that a marker value is used to signal queue is full, but the link to next queue is pointed to in an extra slot.

What happens when the producer grows twice while the consumer is still in the first array?

Edit: I did some testing and the following test fails on the last assert:

@Test
public void testPowerOf2Capacity() {
    int n = 128;
    SpscGrowableArrayQueue<Integer> q = new SpscGrowableArrayQueue<>(8, n);

    for (int i = 0; i < n; i++) {
        assertTrue(q.offer(i));
    }
    assertFalse(q.offer(n));
}

The reason is that if the queue grows, the last grown array contains null in its front (up to index 62) and the producerLookAhead is adjusted so that it points to array index 0. Even if there is no look-ahead, the next producerIndex will point to a null element and thus accepting the offer, making the effective queue capacity 243 elements (7 + 15 + 31 + 63 + 127).

from jctools.

Fixed and test added

from jctools.

Test below:

@Test
public void testPowerOf2Capacity() {
    assumeThat(spec.isBounded(), is(true));
    int n = Pow2.roundToPowerOfTwo(spec.capacity);

    for (int i = 0; i < n; i++) {
        assertTrue("Failed to insert:"+i,queue.offer(i));
    }
    assertFalse(queue.offer(n));
}

from jctools.