123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176 |
- "use strict";
- var __importDefault = (this && this.__importDefault) || function (mod) {
- return (mod && mod.__esModule) ? mod : { "default": mod };
- };
- Object.defineProperty(exports, "__esModule", { value: true });
- exports.FixedQueue = void 0;
- /*
- * Modified Fixed Queue Implementation based on the one from Node.js Project
- * License: MIT License
- * Source: https://github.com/nodejs/node/blob/de7b37880f5a541d5f874c1c2362a65a4be76cd0/lib/internal/fixed_queue.js
- */
- const node_assert_1 = __importDefault(require("node:assert"));
- // 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 | [empty] |
- // | item | | item | | [empty] |
- // | item | | item | | [empty] |
- // | item | | item | | [empty] |
- // | item | | item | bottom --> | item |
- // | item | | item | | item |
- // | ... | | ... | | ... |
- // | item | | item | | item |
- // | item | | item | | item |
- // | [empty] | <-- top | item | | item |
- // | [empty] | | item | | item |
- // | [empty] | | [empty] | <-- top top --> | [empty] |
- // +-----------+ +-----------+ +-----------+
- //
- // 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] |
- // +-----------+ +-----------+
- // | [empty] | | item |
- // | [empty] | | item |
- // | item | <-- bottom top --> | [empty] |
- // | item | | [empty] |
- // | [empty] | <-- top bottom --> | item |
- // | [empty] | | 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 = 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;
- }
- remove(task) {
- const indexToRemove = this.list.indexOf(task);
- node_assert_1.default.notStrictEqual(indexToRemove, -1);
- let curr = indexToRemove;
- while (true) {
- const next = (curr + 1) & kMask;
- this.list[curr] = this.list[next];
- if (this.list[curr] === undefined) {
- break;
- }
- if (next === indexToRemove) {
- this.list[curr] = undefined;
- break;
- }
- curr = next;
- }
- this.top = (this.top - 1) & kMask;
- }
- }
- class FixedQueue {
- constructor() {
- this._size = 0;
- this.head = this.tail = 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 = new FixedCircularBuffer();
- }
- this.head.push(data);
- this._size++;
- }
- shift() {
- const tail = this.tail;
- const next = tail.shift();
- if (next !== null)
- this._size--;
- 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;
- }
- remove(task) {
- let prev = null;
- let buffer = this.tail;
- while (true) {
- if (buffer.list.includes(task)) {
- buffer.remove(task);
- this._size--;
- break;
- }
- if (buffer.next === null)
- break;
- prev = buffer;
- buffer = buffer.next;
- }
- if (buffer.isEmpty()) {
- // removing tail
- if (prev === null) {
- // if tail is not the last buffer
- if (buffer.next !== null)
- this.tail = buffer.next;
- }
- else {
- // removing head
- if (buffer.next === null) {
- this.head = prev;
- }
- else {
- // removing buffer from middle
- prev.next = buffer.next;
- }
- }
- }
- }
- get size() {
- return this._size;
- }
- }
- exports.FixedQueue = FixedQueue;
- ;
- //# sourceMappingURL=fixed_queue.js.map
|