Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 1282x 1282x 1282x 1282x 1282x 26x 26x 1781445x 1781445x 26x 26x 690533x 690533x 26x 26x 690531x 690531x 690531x 26x 26x 890390x 890390x 890390x 687814x 687814x 687814x 890390x 26x 26x 26x 26x 1244x 1244x 26x 26x 891061x 891061x 26x 26x 690532x 38x 38x 38x 38x 690531x 690532x 26x 26x 890398x 890398x 890398x 38x 38x 38x 890384x 890398x 26x | 'use strict';
const {
Array,
} = primordials;
// 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 {
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.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;
}
};
|