blob: f918849c44c5335c6b49002bc3b35604b3a06646 (
plain) (
blame)
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
125
126
127
128
129
130
131
132
133
134
135
|
'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
}
}
|
