1'use strict'; 2 3const { 4 Array, 5} = primordials; 6 7// Currently optimal queue size, tested on V8 6.0 - 6.6. Must be power of two. 8const kSize = 2048; 9const kMask = kSize - 1; 10 11// The FixedQueue is implemented as a singly-linked list of fixed-size 12// circular buffers. It looks something like this: 13// 14// head tail 15// | | 16// v v 17// +-----------+ <-----\ +-----------+ <------\ +-----------+ 18// | [null] | \----- | next | \------- | next | 19// +-----------+ +-----------+ +-----------+ 20// | item | <-- bottom | item | <-- bottom | [empty] | 21// | item | | item | | [empty] | 22// | item | | item | | [empty] | 23// | item | | item | | [empty] | 24// | item | | item | bottom --> | item | 25// | item | | item | | item | 26// | ... | | ... | | ... | 27// | item | | item | | item | 28// | item | | item | | item | 29// | [empty] | <-- top | item | | item | 30// | [empty] | | item | | item | 31// | [empty] | | [empty] | <-- top top --> | [empty] | 32// +-----------+ +-----------+ +-----------+ 33// 34// Or, if there is only one circular buffer, it looks something 35// like either of these: 36// 37// head tail head tail 38// | | | | 39// v v v v 40// +-----------+ +-----------+ 41// | [null] | | [null] | 42// +-----------+ +-----------+ 43// | [empty] | | item | 44// | [empty] | | item | 45// | item | <-- bottom top --> | [empty] | 46// | item | | [empty] | 47// | [empty] | <-- top bottom --> | item | 48// | [empty] | | item | 49// +-----------+ +-----------+ 50// 51// Adding a value means moving `top` forward by one, removing means 52// moving `bottom` forward by one. After reaching the end, the queue 53// wraps around. 54// 55// When `top === bottom` the current queue is empty and when 56// `top + 1 === bottom` it's full. This wastes a single space of storage 57// but allows much quicker checks. 58 59class FixedCircularBuffer { 60 constructor() { 61 this.bottom = 0; 62 this.top = 0; 63 this.list = new Array(kSize); 64 this.next = null; 65 } 66 67 isEmpty() { 68 return this.top === this.bottom; 69 } 70 71 isFull() { 72 return ((this.top + 1) & kMask) === this.bottom; 73 } 74 75 push(data) { 76 this.list[this.top] = data; 77 this.top = (this.top + 1) & kMask; 78 } 79 80 shift() { 81 const nextItem = this.list[this.bottom]; 82 if (nextItem === undefined) 83 return null; 84 this.list[this.bottom] = undefined; 85 this.bottom = (this.bottom + 1) & kMask; 86 return nextItem; 87 } 88} 89 90module.exports = class FixedQueue { 91 constructor() { 92 this.head = this.tail = new FixedCircularBuffer(); 93 } 94 95 isEmpty() { 96 return this.head.isEmpty(); 97 } 98 99 push(data) { 100 if (this.head.isFull()) { 101 // Head is full: Creates a new queue, sets the old queue's `.next` to it, 102 // and sets it as the new main queue. 103 this.head = this.head.next = new FixedCircularBuffer(); 104 } 105 this.head.push(data); 106 } 107 108 shift() { 109 const tail = this.tail; 110 const next = tail.shift(); 111 if (tail.isEmpty() && tail.next !== null) { 112 // If there is another queue, it forms the new tail. 113 this.tail = tail.next; 114 } 115 return next; 116 } 117}; 118