Skip to content

FixedCircularBuffer isFull(), isEmpty() and wrapping off by one #53139

Closed
@jerome-benoit

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Assignees

No one assigned

    Labels

    bufferIssues and PRs related to the buffer subsystem.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions