1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// Copyright 2018-2022 the Deno authors. All rights reserved. MIT license.// Copyright Joyent, Inc. and other Node contributors.
// 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 {  bottom: number;  top: number;  list: undefined | Array<unknown>;  next: FixedCircularBuffer | null;
  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: unknown) {    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;  }}
export class FixedQueue {  head: FixedCircularBuffer;  tail: FixedCircularBuffer;
  constructor() {    this.head = this.tail = new FixedCircularBuffer();  }
  isEmpty() {    return this.head.isEmpty();  }
  push(data: unknown) {    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.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;    }    return next;  }}