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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
// Copyright 2017 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Queue implementation used by ReadableStream and WritableStream.
(function(global, binding, v8) {
'use strict';
const _front = v8.createPrivateSymbol('front');
const _back = v8.createPrivateSymbol('back');
const _cursor = v8.createPrivateSymbol('cursor');
const _size = v8.createPrivateSymbol('size');
const _elements = v8.createPrivateSymbol('elements');
const _next = v8.createPrivateSymbol('next');
// Take copies of global objects to protect against them being replaced.
const RangeError = global.RangeError;
// shift() and peek() can only be called on a non-empty queue. This function
// throws an exception with the message mentioning |functionName| if |queue|
// is empty.
function requireNonEmptyQueue(queue, functionName) {
if (queue[_size] === 0) {
throw new RangeError(
`${functionName}() must not be called on an empty queue`);
}
}
// Simple queue structure. Avoids scalability issues with using
// InternalPackedArray directly by using multiple arrays in a linked list and
// keeping the array size bounded.
const QUEUE_MAX_ARRAY_SIZE = 16384;
class SimpleQueue {
constructor() {
// [_front] and [_back] are always defined.
this[_front] = {
[_elements]: new v8.InternalPackedArray(),
[_next]: undefined,
};
this[_back] = this[_front];
// The cursor is used to avoid calling InternalPackedArray.shift(). It
// contains the index of the front element of the array inside the
// frontmost node. It is always in the range [0, QUEUE_MAX_ARRAY_SIZE).
this[_cursor] = 0;
// When there is only one node, size === elements.length - cursor.
this[_size] = 0;
}
get length() {
return this[_size];
}
// For exception safety, this method is structured in order:
// 1. Read state
// 2. Calculate required state mutations
// 3. Perform state mutations
push(element) {
const oldBack = this[_back];
let newBack = oldBack;
// assert(oldBack[_next] === undefined);
if (oldBack[_elements].length === QUEUE_MAX_ARRAY_SIZE - 1) {
newBack = {
[_elements]: new v8.InternalPackedArray(),
[_next]: undefined,
};
}
// push() is the mutation most likely to throw an exception, so it
// goes first.
oldBack[_elements].push(element);
if (newBack !== oldBack) {
this[_back] = newBack;
oldBack[_next] = newBack;
}
++this[_size];
}
// Like push(), shift() follows the read -> calculate -> mutate pattern for
// exception safety.
shift() {
requireNonEmptyQueue(this, 'shift');
const oldFront = this[_front];
let newFront = oldFront;
const oldCursor = this[_cursor];
let newCursor = oldCursor + 1;
const elements = oldFront[_elements];
const element = elements[oldCursor];
if (newCursor === QUEUE_MAX_ARRAY_SIZE) {
// assert(elements.length === QUEUE_MAX_ARRAY_SIZE);
// assert(oldFront[_next] !== undefined);
newFront = oldFront[_next];
newCursor = 0;
}
// No mutations before this point.
--this[_size];
this[_cursor] = newCursor;
if (oldFront !== newFront) {
this[_front] = newFront;
}
// Permit shifted element to be garbage collected.
elements[oldCursor] = undefined;
return element;
}
// The tricky thing about forEach() is that it can be called
// re-entrantly. The queue may be mutated inside the callback. It is easy to
// see that push() within the callback has no negative effects since the end
// of the queue is checked for on every iteration. If shift() is called
// repeatedly within the callback then the next iteration may return an
// element that has been removed. In this case the callback will be called
// with undefined values until we either "catch up" with elements that still
// exist or reach the back of the queue.
forEach(callback) {
let i = this[_cursor];
let node = this[_front];
let elements = node[_elements];
while (i !== elements.length || node[_next] !== undefined) {
if (i === elements.length) {
// assert(node[_next] !== undefined);
// assert(i === QUEUE_MAX_ARRAY_SIZE);
node = node[_next];
elements = node[_elements];
i = 0;
if (elements.length === 0) {
break;
}
}
callback(elements[i]);
++i;
}
}
// Return the element that would be returned if shift() was called now,
// without modifying the queue.
peek() {
requireNonEmptyQueue(this, 'peek');
const front = this[_front];
const cursor = this[_cursor];
return front[_elements][cursor];
}
}
binding.SimpleQueue = SimpleQueue;
});
|
