From d47147fb6ad229b1c039aff9d0959b6e281f4df5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bartek=20Iwa=C5=84czuk?= Date: Tue, 14 Feb 2023 17:38:45 +0100 Subject: feat(ext/node): embed std/node into the snapshot (#17724) This commit moves "deno_std/node" in "ext/node" crate. The code is transpiled and snapshotted during the build process. During the first pass a minimal amount of work was done to create the snapshot, a lot of code in "ext/node" depends on presence of "Deno" global. This code will be gradually fixed in the follow up PRs to migrate it to import relevant APIs from "internal:" modules. Currently the code from snapshot is not used in any way, and all Node/npm compatibility still uses code from "https://deno.land/std/node" (or from the location specified by "DENO_NODE_COMPAT_URL"). This will also be handled in a follow up PRs. --------- Co-authored-by: crowlkats Co-authored-by: Divy Srivastava Co-authored-by: Yoshiya Hinosawa --- ext/node/polyfills/internal/fixed_queue.ts | 123 +++++++++++++++++++++++++++++ 1 file changed, 123 insertions(+) create mode 100644 ext/node/polyfills/internal/fixed_queue.ts (limited to 'ext/node/polyfills/internal/fixed_queue.ts') diff --git a/ext/node/polyfills/internal/fixed_queue.ts b/ext/node/polyfills/internal/fixed_queue.ts new file mode 100644 index 000000000..e6b8db70f --- /dev/null +++ b/ext/node/polyfills/internal/fixed_queue.ts @@ -0,0 +1,123 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright Joyent, Inc. and other Node contributors. + +// 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 { + bottom: number; + top: number; + list: undefined | Array; + next: FixedCircularBuffer | null; + + 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: unknown) { + 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; + } +} + +export class FixedQueue { + head: FixedCircularBuffer; + tail: FixedCircularBuffer; + + constructor() { + this.head = this.tail = new FixedCircularBuffer(); + } + + isEmpty() { + return this.head.isEmpty(); + } + + push(data: unknown) { + 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; + } +} -- cgit v1.2.3