Spaces:
Paused
Paused
| // Extracted from node/lib/internal/fixed_queue.js | |
| // Currently optimal queue size, tested on V8 6.0 - 6.6. Must be power of two. | |
| const kSize = 2048 | |
| const kMask = kSize - 1 | |
| // The FixedQueue is implemented as a singly-linked list of fixed-size | |
| // circular buffers. It looks something like this: | |
| // | |
| // head tail | |
| // | | | |
| // v v | |
| // +-----------+ <-----\ +-----------+ <------\ +-----------+ | |
| // | [null] | \----- | next | \------- | next | | |
| // +-----------+ +-----------+ +-----------+ | |
| // | item | <-- bottom | item | <-- bottom | undefined | | |
| // | item | | item | | undefined | | |
| // | item | | item | | undefined | | |
| // | item | | item | | undefined | | |
| // | item | | item | bottom --> | item | | |
| // | item | | item | | item | | |
| // | ... | | ... | | ... | | |
| // | item | | item | | item | | |
| // | item | | item | | item | | |
| // | undefined | <-- top | item | | item | | |
| // | undefined | | item | | item | | |
| // | undefined | | undefined | <-- top top --> | undefined | | |
| // +-----------+ +-----------+ +-----------+ | |
| // | |
| // Or, if there is only one circular buffer, it looks something | |
| // like either of these: | |
| // | |
| // head tail head tail | |
| // | | | | | |
| // v v v v | |
| // +-----------+ +-----------+ | |
| // | [null] | | [null] | | |
| // +-----------+ +-----------+ | |
| // | undefined | | item | | |
| // | undefined | | item | | |
| // | item | <-- bottom top --> | undefined | | |
| // | item | | undefined | | |
| // | undefined | <-- top bottom --> | item | | |
| // | undefined | | item | | |
| // +-----------+ +-----------+ | |
| // | |
| // Adding a value means moving `top` forward by one, removing means | |
| // moving `bottom` forward by one. After reaching the end, the queue | |
| // wraps around. | |
| // | |
| // When `top === bottom` the current queue is empty and when | |
| // `top + 1 === bottom` it's full. This wastes a single space of storage | |
| // but allows much quicker checks. | |
| /** | |
| * @type {FixedCircularBuffer} | |
| * @template T | |
| */ | |
| class FixedCircularBuffer { | |
| /** @type {number} */ | |
| bottom = 0 | |
| /** @type {number} */ | |
| top = 0 | |
| /** @type {Array<T|undefined>} */ | |
| list = new Array(kSize).fill(undefined) | |
| /** @type {T|null} */ | |
| next = null | |
| /** @returns {boolean} */ | |
| isEmpty () { | |
| return this.top === this.bottom | |
| } | |
| /** @returns {boolean} */ | |
| isFull () { | |
| return ((this.top + 1) & kMask) === this.bottom | |
| } | |
| /** | |
| * @param {T} data | |
| * @returns {void} | |
| */ | |
| push (data) { | |
| this.list[this.top] = data | |
| this.top = (this.top + 1) & kMask | |
| } | |
| /** @returns {T|null} */ | |
| 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 | |
| } | |
| } | |
| /** | |
| * @template T | |
| */ | |
| module.exports = class FixedQueue { | |
| constructor () { | |
| /** @type {FixedCircularBuffer<T>} */ | |
| this.head = this.tail = new FixedCircularBuffer() | |
| } | |
| /** @returns {boolean} */ | |
| isEmpty () { | |
| return this.head.isEmpty() | |
| } | |
| /** @param {T} data */ | |
| push (data) { | |
| if (this.head.isFull()) { | |
| // Head is full: Creates a new queue, sets the old queue's `.next` to it, | |
| // and sets it as the new main queue. | |
| this.head = this.head.next = new FixedCircularBuffer() | |
| } | |
| this.head.push(data) | |
| } | |
| /** @returns {T|null} */ | |
| shift () { | |
| const tail = this.tail | |
| const next = tail.shift() | |
| if (tail.isEmpty() && tail.next !== null) { | |
| // If there is another queue, it forms the new tail. | |
| this.tail = tail.next | |
| tail.next = null | |
| } | |
| return next | |
| } | |
| } | |