-
Notifications
You must be signed in to change notification settings - Fork 556
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
SpscGrowableArrayQueue capacity is less than requested capacity #49
Comments
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;
}
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 |
Fixed and test added |
Test below:
|
Users currently expect a power of 2 capacity to end up being the actual resulting capacity of the queue. While this is mildly arbitrary (given that for requested capacity that is less than power of 2 the capacity is rounded up) it is arguably consistent with the following guideline:
Queue capacity >= requested capacity
SpscGrowableArrayQueue breaks that assumption. If requested capacity is <= power of 2 the resulting capacity will be (power of 2 - 1).
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.
The text was updated successfully, but these errors were encountered: