From 9a3ae2fe9d6ddff6a0de81acb5e0a8c068c0c79d Mon Sep 17 00:00:00 2001
From: Anatoli Papirovski <apapirovski@mac.com>
Date: Wed, 2 May 2018 15:39:08 +0200
Subject: lib: expose FixedQueue internally and fix nextTick bug

A bug was introduced together with the FixedQueue implementation for
process.nextTick which meant that the queue wouldn't necessarily
fully clear on each run through. Fix it and abstract the data
structure into an internal module that can later be used elsewhere.

PR-URL: https://github.com/nodejs/node/pull/20468
Reviewed-By: Benjamin Gruenbaum <benjamingr@gmail.com>
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Anna Henningsen <anna@addaleax.net>
Reviewed-By: Ruben Bridgewater <ruben@bridgewater.de>
Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
---
 lib/internal/fixed_queue.js | 113 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 113 insertions(+)
 create mode 100644 lib/internal/fixed_queue.js

(limited to 'lib/internal/fixed_queue.js')

diff --git a/lib/internal/fixed_queue.js b/lib/internal/fixed_queue.js
new file mode 100644
index 0000000000..7571a8f67e
--- /dev/null
+++ b/lib/internal/fixed_queue.js
@@ -0,0 +1,113 @@
+'use strict';
+
+// 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.
+
+const FixedCircularBuffer = 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;
+  }
+};
+
+module.exports = class FixedQueue {
+  constructor() {
+    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);
+  }
+
+  shift() {
+    const { tail } = this;
+    const next = tail.shift();
+    if (tail.isEmpty() && tail.next !== null) {
+      // If there is another queue, it forms the new tail.
+      this.tail = tail.next;
+    }
+    return next;
+  }
+};
-- 
cgit v1.2.3