fixed_queue.js 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176
  1. "use strict";
  2. var __importDefault = (this && this.__importDefault) || function (mod) {
  3. return (mod && mod.__esModule) ? mod : { "default": mod };
  4. };
  5. Object.defineProperty(exports, "__esModule", { value: true });
  6. exports.FixedQueue = void 0;
  7. /*
  8. * Modified Fixed Queue Implementation based on the one from Node.js Project
  9. * License: MIT License
  10. * Source: https://github.com/nodejs/node/blob/de7b37880f5a541d5f874c1c2362a65a4be76cd0/lib/internal/fixed_queue.js
  11. */
  12. const node_assert_1 = __importDefault(require("node:assert"));
  13. // Currently optimal queue size, tested on V8 6.0 - 6.6. Must be power of two.
  14. const kSize = 2048;
  15. const kMask = kSize - 1;
  16. // The FixedQueue is implemented as a singly-linked list of fixed-size
  17. // circular buffers. It looks something like this:
  18. //
  19. // head tail
  20. // | |
  21. // v v
  22. // +-----------+ <-----\ +-----------+ <------\ +-----------+
  23. // | [null] | \----- | next | \------- | next |
  24. // +-----------+ +-----------+ +-----------+
  25. // | item | <-- bottom | item | <-- bottom | [empty] |
  26. // | item | | item | | [empty] |
  27. // | item | | item | | [empty] |
  28. // | item | | item | | [empty] |
  29. // | item | | item | bottom --> | item |
  30. // | item | | item | | item |
  31. // | ... | | ... | | ... |
  32. // | item | | item | | item |
  33. // | item | | item | | item |
  34. // | [empty] | <-- top | item | | item |
  35. // | [empty] | | item | | item |
  36. // | [empty] | | [empty] | <-- top top --> | [empty] |
  37. // +-----------+ +-----------+ +-----------+
  38. //
  39. // Or, if there is only one circular buffer, it looks something
  40. // like either of these:
  41. //
  42. // head tail head tail
  43. // | | | |
  44. // v v v v
  45. // +-----------+ +-----------+
  46. // | [null] | | [null] |
  47. // +-----------+ +-----------+
  48. // | [empty] | | item |
  49. // | [empty] | | item |
  50. // | item | <-- bottom top --> | [empty] |
  51. // | item | | [empty] |
  52. // | [empty] | <-- top bottom --> | item |
  53. // | [empty] | | item |
  54. // +-----------+ +-----------+
  55. //
  56. // Adding a value means moving `top` forward by one, removing means
  57. // moving `bottom` forward by one. After reaching the end, the queue
  58. // wraps around.
  59. //
  60. // When `top === bottom` the current queue is empty and when
  61. // `top + 1 === bottom` it's full. This wastes a single space of storage
  62. // but allows much quicker checks.
  63. class FixedCircularBuffer {
  64. constructor() {
  65. this.bottom = 0;
  66. this.top = 0;
  67. this.list = new Array(kSize);
  68. this.next = null;
  69. }
  70. isEmpty() {
  71. return this.top === this.bottom;
  72. }
  73. isFull() {
  74. return ((this.top + 1) & kMask) === this.bottom;
  75. }
  76. push(data) {
  77. this.list[this.top] = data;
  78. this.top = (this.top + 1) & kMask;
  79. }
  80. shift() {
  81. const nextItem = this.list[this.bottom];
  82. if (nextItem === undefined) {
  83. return null;
  84. }
  85. this.list[this.bottom] = undefined;
  86. this.bottom = (this.bottom + 1) & kMask;
  87. return nextItem;
  88. }
  89. remove(task) {
  90. const indexToRemove = this.list.indexOf(task);
  91. node_assert_1.default.notStrictEqual(indexToRemove, -1);
  92. let curr = indexToRemove;
  93. while (true) {
  94. const next = (curr + 1) & kMask;
  95. this.list[curr] = this.list[next];
  96. if (this.list[curr] === undefined) {
  97. break;
  98. }
  99. if (next === indexToRemove) {
  100. this.list[curr] = undefined;
  101. break;
  102. }
  103. curr = next;
  104. }
  105. this.top = (this.top - 1) & kMask;
  106. }
  107. }
  108. class FixedQueue {
  109. constructor() {
  110. this._size = 0;
  111. this.head = this.tail = new FixedCircularBuffer();
  112. }
  113. isEmpty() {
  114. return this.head.isEmpty();
  115. }
  116. push(data) {
  117. if (this.head.isFull()) {
  118. // Head is full: Creates a new queue, sets the old queue's `.next` to it,
  119. // and sets it as the new main queue.
  120. this.head = this.head.next = new FixedCircularBuffer();
  121. }
  122. this.head.push(data);
  123. this._size++;
  124. }
  125. shift() {
  126. const tail = this.tail;
  127. const next = tail.shift();
  128. if (next !== null)
  129. this._size--;
  130. if (tail.isEmpty() && tail.next !== null) {
  131. // If there is another queue, it forms the new tail.
  132. this.tail = tail.next;
  133. tail.next = null;
  134. }
  135. return next;
  136. }
  137. remove(task) {
  138. let prev = null;
  139. let buffer = this.tail;
  140. while (true) {
  141. if (buffer.list.includes(task)) {
  142. buffer.remove(task);
  143. this._size--;
  144. break;
  145. }
  146. if (buffer.next === null)
  147. break;
  148. prev = buffer;
  149. buffer = buffer.next;
  150. }
  151. if (buffer.isEmpty()) {
  152. // removing tail
  153. if (prev === null) {
  154. // if tail is not the last buffer
  155. if (buffer.next !== null)
  156. this.tail = buffer.next;
  157. }
  158. else {
  159. // removing head
  160. if (buffer.next === null) {
  161. this.head = prev;
  162. }
  163. else {
  164. // removing buffer from middle
  165. prev.next = buffer.next;
  166. }
  167. }
  168. }
  169. }
  170. get size() {
  171. return this._size;
  172. }
  173. }
  174. exports.FixedQueue = FixedQueue;
  175. ;
  176. //# sourceMappingURL=fixed_queue.js.map