repo_description: Node.js JavaScript runtime ✨🐢🚀✨
repo_topics: javascript js linux macos mit node nodejs runtime windows
code: 'use strict';
  
  const {
    Array,
    ArrayPrototypeFill,
  } = primordials;
  
  // 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.
  
  class FixedCircularBuffer {
    constructor() {
      this.bottom = 0;
      this.top = 0;
      this.list = ArrayPrototypeFill(new Array(kSize), undefined);
      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;
    }
  }
  
  module.exports = class FixedQueue {
    static #pool = [];
  
    constructor() {
      this.head = this.tail = FixedQueue.#pool.pop() ?? new FixedCircularBuffer();
    }
  
    isEmpty() {
      return this.head.isEmpty();
    }
  
    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 = FixedQueue.#pool.pop() ?? new FixedCircularBuffer();
      }
      this.head.push(data);
    }
  
    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;
        tail.bottom = 0;
        tail.top = 0;
  
        if (FixedQueue.#pool.length < 64) {
          FixedQueue.#pool.push(tail); // Recycle old tail
        }
      }
      return next;
    }
  };
  