Closed
Description
Version
Not relevant
Platform
Not relevant
Subsystem
Not relevant
What steps will reproduce the bug?
No response
How often does it reproduce? Is there a required condition?
No response
What is the expected behavior? Why is that the expected behavior?
No response
What do you see instead?
Implementation copied from lib/internal/fixed_queue.js:
const kSize = 4;
const kMask = kSize - 1;
class FixedCircularBuffer {
constructor() {
this.bottom = 0;
this.top = 0;
this.list = new Array(kSize);
this.next = null;
}
isEmpty() {
return this.top === this.bottom;
}
isFull() {
return ((this.top + 1) & kMask) === this.bottom;
}
push(data) {
this.list[this.top] = data;
this.top = (this.top + 1) & kMask;
}
shift() {
const nextItem = this.list[this.bottom];
if (nextItem === undefined)
return null;
this.list[this.bottom] = undefined;
this.bottom = (this.bottom + 1) & kMask;
return nextItem;
}
}
const circularBuffer = new FixedCircularBuffer();
console.log(circularBuffer.isFull()); // false
console.log(circularBuffer.isEmpty()); // true
circularBuffer.push(1);
console.log(circularBuffer.list);
console.log(circularBuffer.isFull()); // false
console.log(circularBuffer.isEmpty()); // false
circularBuffer.push(2);
console.log(circularBuffer.list);
console.log(circularBuffer.isFull()); // false
console.log(circularBuffer.isEmpty()); // false
circularBuffer.push(3);
console.log(circularBuffer.list);
console.log(circularBuffer.isFull()); // false, received true
console.log(circularBuffer.isEmpty()); // false
circularBuffer.push(4);
console.log(circularBuffer.list);
console.log(circularBuffer.isFull()); // true, received false
console.log(circularBuffer.isEmpty()); // false, received true
One way to fix it to count the number of elements in list
at push()
and shift()
and test it against zero or the 'list` fixed array size.
It's current usage in FixedQueue does not expose the issue with wrapping when full and the resulting incorrect FIFO semantic at shift()
because a new buffer is created. But the trade off at losing one array space each 2047 elements is debatable vs. integer property increment/decrement + branching one more.
Additional information
No response
Activity