OLD | NEW |
---|---|
(Empty) | |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | |
yhirano
2017/03/17 13:56:45
2017
Adam Rice
2017/03/17 14:02:08
Done.
| |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 // Queue implementation used by ReadableStream and WritableStream. | |
6 | |
7 (function(global, binding, v8) { | |
8 'use strict'; | |
9 | |
10 // Simple queue structure. Avoids scalability issues with using | |
11 // InternalPackedArray directly by using multiple arrays in a linked list and | |
12 // keeping the array size bounded. | |
13 const QUEUE_MAX_ARRAY_SIZE = 16384; | |
14 class SimpleQueue { | |
15 constructor() { | |
16 this.front = { | |
17 elements: new v8.InternalPackedArray(), | |
18 next: undefined, | |
19 }; | |
20 this.back = this.front; | |
21 // The cursor is used to avoid calling InternalPackedArray.shift(). | |
22 this.cursor = 0; | |
23 this.size = 0; | |
24 } | |
25 | |
26 get length() { | |
27 return this.size; | |
28 } | |
29 | |
30 push(element) { | |
31 ++this.size; | |
32 if (this.back.elements.length === QUEUE_MAX_ARRAY_SIZE) { | |
33 const oldBack = this.back; | |
34 this.back = { | |
35 elements: new v8.InternalPackedArray(), | |
36 next: undefined, | |
37 }; | |
38 oldBack.next = this.back; | |
39 } | |
40 this.back.elements.push(element); | |
41 } | |
42 | |
43 shift() { | |
44 // assert(this.size > 0); | |
45 --this.size; | |
46 if (this.front.elements.length === this.cursor) { | |
47 // assert(this.cursor === QUEUE_MAX_ARRAY_SIZE); | |
48 // assert(this.front.next !== undefined); | |
49 this.front = this.front.next; | |
50 this.cursor = 0; | |
51 } | |
52 const element = this.front.elements[this.cursor]; | |
53 // Permit shifted element to be garbage collected. | |
54 this.front.elements[this.cursor] = undefined; | |
55 ++this.cursor; | |
56 | |
57 return element; | |
58 } | |
59 | |
60 forEach(callback) { | |
61 let i = this.cursor; | |
62 let node = this.front; | |
63 let elements = node.elements; | |
64 while (i !== elements.length || node.next !== undefined) { | |
65 if (i === elements.length) { | |
66 // assert(node.next !== undefined); | |
67 // assert(i === QUEUE_MAX_ARRAY_SIZE); | |
68 node = node.next; | |
69 elements = node.elements; | |
70 i = 0; | |
71 } | |
72 callback(elements[i]); | |
73 ++i; | |
74 } | |
75 } | |
76 | |
77 // Return the element that would be returned if shift() was called now, | |
78 // without modifying the queue. | |
79 peek() { | |
80 // assert(this.size > 0); | |
81 if (this.front.elements.length === this.cursor) { | |
82 // assert(this.cursor === QUEUE_MAX_ARRAY_SIZE) | |
83 // assert(this.front.next !== undefined); | |
84 return this.front.next.elements[0]; | |
85 } | |
86 return this.front.elements[this.cursor]; | |
87 } | |
88 } | |
89 | |
90 binding.SimpleQueue = SimpleQueue; | |
91 }); | |
OLD | NEW |