RobotDaily/node_modules/undici/lib/dispatcher/fixed-queue.js

'use strict'

// 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
  }
}