mirror of
https://github.com/oven-sh/bun
synced 2026-02-12 03:48:56 +00:00
6b577a3970
* exit event loop if there's unhandled errors * move FixedQueue to a special package * require(events) is also EventEmitter * implement events.on * move fixed_queue to internal and make it lazy in node:events * use better Promise intrinsics * move $shared to internal/shared * make test not dependent on cwd
128 lines
4.4 KiB
TypeScript
128 lines
4.4 KiB
TypeScript
// https://github.com/nodejs/node/blob/bae03c4e30f927676203f61ff5a34fe0a0c0bbc9/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 | [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<T> {
|
|
top: number;
|
|
bottom: number;
|
|
list: Array<T | undefined>;
|
|
next: FixedCircularBuffer<T> | null;
|
|
|
|
constructor() {
|
|
this.bottom = 0;
|
|
this.top = 0;
|
|
this.list = $newArrayWithSize(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() {
|
|
var { list, bottom } = this;
|
|
const nextItem = list[bottom];
|
|
if (nextItem === undefined) return null;
|
|
list[bottom] = undefined;
|
|
this.bottom = (bottom + 1) & kMask;
|
|
return nextItem;
|
|
}
|
|
}
|
|
|
|
class FixedQueue<T> {
|
|
head: FixedCircularBuffer<T>;
|
|
tail: FixedCircularBuffer<T>;
|
|
|
|
constructor() {
|
|
this.head = this.tail = new FixedCircularBuffer();
|
|
}
|
|
|
|
isEmpty() {
|
|
return this.head.isEmpty();
|
|
}
|
|
|
|
push(data: T) {
|
|
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<T>();
|
|
}
|
|
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;
|
|
tail.next = null;
|
|
}
|
|
return next;
|
|
}
|
|
}
|
|
|
|
export default {
|
|
FixedCircularBuffer,
|
|
FixedQueue,
|
|
};
|