summaryrefslogtreecommitdiff
path: root/cli/js
diff options
context:
space:
mode:
Diffstat (limited to 'cli/js')
-rw-r--r--cli/js/rbtree.ts241
-rw-r--r--cli/js/timers.ts75
2 files changed, 265 insertions, 51 deletions
diff --git a/cli/js/rbtree.ts b/cli/js/rbtree.ts
new file mode 100644
index 000000000..5de9f125d
--- /dev/null
+++ b/cli/js/rbtree.ts
@@ -0,0 +1,241 @@
+// Derived from https://github.com/vadimg/js_bintrees. MIT Licensed.
+
+class RBNode<T> {
+ public left: this | null;
+ public right: this | null;
+ public red: boolean;
+
+ constructor(public data: T) {
+ this.left = null;
+ this.right = null;
+ this.red = true;
+ }
+
+ getChild(dir: boolean | number): this | null {
+ return dir ? this.right : this.left;
+ }
+
+ setChild(dir: boolean | number, val: this | null): void {
+ if (dir) {
+ this.right = val;
+ } else {
+ this.left = val;
+ }
+ }
+}
+
+class RBTree<T> {
+ private root: RBNode<T> | null;
+
+ constructor(private comparator: (a: T, b: T) => number) {
+ this.root = null;
+ }
+
+ // returns null if tree is empty
+ min(): T | null {
+ let res = this.root;
+ if (res === null) {
+ return null;
+ }
+ while (res.left !== null) {
+ res = res.left;
+ }
+ return res.data;
+ }
+
+ // returns node data if found, null otherwise
+ find(data: T): T | null {
+ let res = this.root;
+ while (res !== null) {
+ const c = this.comparator(data, res.data!);
+ if (c === 0) {
+ return res.data;
+ } else {
+ res = res.getChild(c > 0);
+ }
+ }
+ return null;
+ }
+
+ // returns true if inserted, false if duplicate
+ insert(data: T): boolean {
+ let ret = false;
+
+ if (this.root === null) {
+ // empty tree
+ this.root = new RBNode(data);
+ ret = true;
+ } else {
+ const head = new RBNode((null as unknown) as T); // fake tree root
+
+ let dir = 0;
+ let last = 0;
+
+ // setup
+ let gp = null; // grandparent
+ let ggp = head; // grand-grand-parent
+ let p: RBNode<T> | null = null; // parent
+ let node: RBNode<T> | null = this.root;
+ ggp.right = this.root;
+
+ // search down
+ while (true) {
+ if (node === null) {
+ // insert new node at the bottom
+ node = new RBNode(data);
+ p!.setChild(dir, node);
+ ret = true;
+ } else if (isRed(node.left) && isRed(node.right)) {
+ // color flip
+ node.red = true;
+ node.left!.red = false;
+ node.right!.red = false;
+ }
+
+ // fix red violation
+ if (isRed(node) && isRed(p)) {
+ const dir2 = ggp.right === gp;
+
+ if (node === p!.getChild(last)) {
+ ggp.setChild(dir2, singleRotate(gp!, !last));
+ } else {
+ ggp.setChild(dir2, doubleRotate(gp!, !last));
+ }
+ }
+
+ const cmp = this.comparator(node.data!, data);
+
+ // stop if found
+ if (cmp === 0) {
+ break;
+ }
+
+ last = dir;
+ dir = Number(cmp < 0); // Fix type
+
+ // update helpers
+ if (gp !== null) {
+ ggp = gp;
+ }
+ gp = p;
+ p = node;
+ node = node.getChild(dir);
+ }
+
+ // update root
+ this.root = head.right;
+ }
+
+ // make root black
+ this.root!.red = false;
+
+ return ret;
+ }
+
+ // returns true if removed, false if not found
+ remove(data: T): boolean {
+ if (this.root === null) {
+ return false;
+ }
+
+ const head = new RBNode((null as unknown) as T); // fake tree root
+ let node = head;
+ node.right = this.root;
+ let p = null; // parent
+ let gp = null; // grand parent
+ let found = null; // found item
+ let dir: boolean | number = 1;
+
+ while (node.getChild(dir) !== null) {
+ const last = dir;
+
+ // update helpers
+ gp = p;
+ p = node;
+ node = node.getChild(dir)!;
+
+ const cmp = this.comparator(data, node.data);
+
+ dir = cmp > 0;
+
+ // save found node
+ if (cmp === 0) {
+ found = node;
+ }
+
+ // push the red node down
+ if (!isRed(node) && !isRed(node.getChild(dir))) {
+ if (isRed(node.getChild(!dir))) {
+ const sr = singleRotate(node, dir);
+ p.setChild(last, sr);
+ p = sr;
+ } else if (!isRed(node.getChild(!dir))) {
+ const sibling = p.getChild(!last);
+ if (sibling !== null) {
+ if (
+ !isRed(sibling.getChild(!last)) &&
+ !isRed(sibling.getChild(last))
+ ) {
+ // color flip
+ p.red = false;
+ sibling.red = true;
+ node.red = true;
+ } else {
+ const dir2 = gp!.right === p;
+
+ if (isRed(sibling.getChild(last))) {
+ gp!.setChild(dir2, doubleRotate(p, last));
+ } else if (isRed(sibling.getChild(!last))) {
+ gp!.setChild(dir2, singleRotate(p, last));
+ }
+
+ // ensure correct coloring
+ const gpc = gp!.getChild(dir2)!;
+ gpc.red = true;
+ node.red = true;
+ gpc.left!.red = false;
+ gpc.right!.red = false;
+ }
+ }
+ }
+ }
+ }
+
+ // replace and remove if found
+ if (found !== null) {
+ found.data = node.data;
+ p!.setChild(p!.right === node, node.getChild(node.left === null));
+ }
+
+ // update root and make it black
+ this.root = head.right;
+ if (this.root !== null) {
+ this.root.red = false;
+ }
+
+ return found !== null;
+ }
+}
+
+function isRed<T>(node: RBNode<T> | null): boolean {
+ return node !== null && node.red;
+}
+
+function singleRotate<T>(root: RBNode<T>, dir: boolean | number): RBNode<T> {
+ const save = root.getChild(!dir)!;
+
+ root.setChild(!dir, save.getChild(dir));
+ save.setChild(dir, root);
+
+ root.red = true;
+ save.red = false;
+
+ return save;
+}
+
+function doubleRotate<T>(root: RBNode<T>, dir: boolean | number): RBNode<T> {
+ root.setChild(!dir, singleRotate(root.getChild(!dir)!, !dir));
+ return singleRotate(root, dir);
+}
+
+export { RBTree };
diff --git a/cli/js/timers.ts b/cli/js/timers.ts
index 9ebe4f6cb..ef7318126 100644
--- a/cli/js/timers.ts
+++ b/cli/js/timers.ts
@@ -3,6 +3,7 @@ import { assert } from "./util.ts";
import { window } from "./window.ts";
import * as dispatch from "./dispatch.ts";
import { sendSync, sendAsync } from "./dispatch_json.ts";
+import { RBTree } from "./rbtree.ts";
const { console } = window;
@@ -15,14 +16,6 @@ interface Timer {
scheduled: boolean;
}
-// We'll subtract EPOCH every time we retrieve the time with Date.now(). This
-// ensures that absolute time values stay below UINT32_MAX - 2, which is the
-// maximum object key that EcmaScript considers "numerical". After running for
-// about a month, this is no longer true, and Deno explodes.
-// TODO(piscisaureus): fix that ^.
-const EPOCH = Date.now();
-const APOCALYPSE = 2 ** 32 - 2;
-
// Timeout values > TIMEOUT_MAX are set to 1.
const TIMEOUT_MAX = 2 ** 31 - 1;
@@ -30,14 +23,8 @@ let globalTimeoutDue: number | null = null;
let nextTimerId = 1;
const idMap = new Map<number, Timer>();
-const dueMap: { [due: number]: Timer[] } = Object.create(null);
-
-function getTime(): number {
- // TODO: use a monotonic clock.
- const now = Date.now() - EPOCH;
- assert(now >= 0 && now < APOCALYPSE);
- return now;
-}
+type DueNode = { due: number; timers: Timer[] };
+const dueTree = new RBTree<DueNode>((a, b) => a.due - b.due);
function clearGlobalTimeout(): void {
globalTimeoutDue = null;
@@ -73,12 +60,14 @@ function schedule(timer: Timer, now: number): void {
assert(!timer.scheduled);
assert(now <= timer.due);
// Find or create the list of timers that will fire at point-in-time `due`.
- let list = dueMap[timer.due];
- if (list === undefined) {
- list = dueMap[timer.due] = [];
+ const maybeNewDueNode = { due: timer.due, timers: [] };
+ let dueNode = dueTree.find(maybeNewDueNode);
+ if (dueNode === null) {
+ dueTree.insert(maybeNewDueNode);
+ dueNode = maybeNewDueNode;
}
// Append the newly scheduled timer to the list and mark it as scheduled.
- list.push(timer);
+ dueNode!.timers.push(timer);
timer.scheduled = true;
// If the new timer is scheduled to fire before any timer that existed before,
// update the global timeout to reflect this.
@@ -91,21 +80,18 @@ function unschedule(timer: Timer): void {
if (!timer.scheduled) {
return;
}
+ const searchKey = { due: timer.due, timers: [] };
// Find the list of timers that will fire at point-in-time `due`.
- const list = dueMap[timer.due];
+ const list = dueTree.find(searchKey)!.timers;
if (list.length === 1) {
// Time timer is the only one in the list. Remove the entire list.
assert(list[0] === timer);
- delete dueMap[timer.due];
+ dueTree.remove(searchKey);
// If the unscheduled timer was 'next up', find when the next timer that
// still exists is due, and update the global alarm accordingly.
if (timer.due === globalTimeoutDue) {
- let nextTimerDue: number | null = null;
- for (const key in dueMap) {
- nextTimerDue = Number(key);
- break;
- }
- setOrClearGlobalTimeout(nextTimerDue, getTime());
+ const nextDueNode: DueNode | null = dueTree.min();
+ setOrClearGlobalTimeout(nextDueNode && nextDueNode.due, Date.now());
}
} else {
// Multiple timers that are due at the same point in time.
@@ -129,7 +115,7 @@ function fire(timer: Timer): void {
} else {
// Interval timer: compute when timer was supposed to fire next.
// However make sure to never schedule the next interval in the past.
- const now = getTime();
+ const now = Date.now();
timer.due = Math.max(now, timer.due + timer.delay);
schedule(timer, now);
}
@@ -140,40 +126,27 @@ function fire(timer: Timer): void {
}
function fireTimers(): void {
- const now = getTime();
+ const now = Date.now();
// Bail out if we're not expecting the global timer to fire.
if (globalTimeoutDue === null || pendingEvents > 0) {
return;
}
- // After firing the timers that are due now, this will hold the due time of
- // the first timer that hasn't fired yet.
- let nextTimerDue: number | null = null;
- // Walk over the keys of the 'due' map. Since dueMap is actually a regular
- // object and its keys are numerical and smaller than UINT32_MAX - 2,
- // keys are iterated in ascending order.
- for (const key in dueMap) {
- // Convert the object key (a string) to a number.
- const due = Number(key);
- // Break out of the loop if the next timer isn't due to fire yet.
- if (Number(due) > now) {
- nextTimerDue = due;
- break;
- }
- // Get the list of timers that have this due time, then drop it.
- const list = dueMap[key];
- delete dueMap[key];
+ // After firing the timers that are due now, this will hold the first timer
+ // list that hasn't fired yet.
+ let nextDueNode: DueNode | null;
+ while ((nextDueNode = dueTree.min()) !== null && nextDueNode.due <= now) {
+ dueTree.remove(nextDueNode);
// Fire all the timers in the list.
- for (const timer of list) {
+ for (const timer of nextDueNode.timers) {
// With the list dropped, the timer is no longer scheduled.
timer.scheduled = false;
// Place the callback on the microtask queue.
Promise.resolve(timer).then(fire);
}
}
-
// Update the global alarm to go off when the first-up timer that hasn't fired
// yet is due.
- setOrClearGlobalTimeout(nextTimerDue, now);
+ setOrClearGlobalTimeout(nextDueNode && nextDueNode.due, now);
}
export type Args = unknown[];
@@ -201,7 +174,7 @@ function setTimer(
// In the browser, the delay value must be coercible to an integer between 0
// and INT32_MAX. Any other value will cause the timer to fire immediately.
// We emulate this behavior.
- const now = getTime();
+ const now = Date.now();
if (delay > TIMEOUT_MAX) {
console.warn(
`${delay} does not fit into` +
generated by cgit v1.2.3 (git 2.25.1) at 2025-06-27 10:43:00 +0000