From 574b351dcb46b90a6a8d0ffb15b5016392e5a63f Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Tue, 22 Aug 2023 20:31:20 +0200 Subject: [PATCH] feat: add O(1) deque MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit reference #901 Signed-off-by: Jérôme Benoit --- .eslintrc.js | 4 +- .vscode/settings.json | 1 + CHANGELOG.md | 1 + LICENSE | 2 +- src/deque.ts | 162 +++++++++++++++++++++ src/pools/worker-node.ts | 10 +- src/queue.ts | 4 +- tests/deque.test.js | 126 ++++++++++++++++ tests/pools/abstract/abstract-pool.test.js | 6 +- tests/queue.test.js | 148 +++++++++---------- 10 files changed, 379 insertions(+), 85 deletions(-) create mode 100644 src/deque.ts create mode 100644 tests/deque.test.js diff --git a/.eslintrc.js b/.eslintrc.js index 24714013..e7cf2abc 100644 --- a/.eslintrc.js +++ b/.eslintrc.js @@ -50,6 +50,7 @@ module.exports = defineConfig({ 'cpus', 'ctx', 'deprecations', + 'deque', 'dequeue', 'dequeued', 'ecma', @@ -76,7 +77,8 @@ module.exports = defineConfig({ 'piscina', 'pnpm', 'poolifier', - 'poolify', + 'prepend', + 'prepends', 'readdir', 'readonly', 'req', diff --git a/.vscode/settings.json b/.vscode/settings.json index 5be1f55a..3ae20ea4 100644 --- a/.vscode/settings.json +++ b/.vscode/settings.json @@ -12,6 +12,7 @@ "codeql", "commitlint", "Dependabot", + "deque", "eventloop", "Fastify", "FOSS", diff --git a/CHANGELOG.md b/CHANGELOG.md index d2f3b38b..56591cb7 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -10,6 +10,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Added - Add `queueMaxSize` option to tasks queue options. +- Add O(1) deque implementation implemented with doubly linked list and use it for tasks queueing. ## [2.6.31] - 2023-08-20 diff --git a/LICENSE b/LICENSE index 306f35e6..6e0988d8 100644 --- a/LICENSE +++ b/LICENSE @@ -1,6 +1,6 @@ MIT License -Copyright (c) 2019-2021 Alessandro Pio Ardizio +Copyright (c) 2019-2023 Alessandro Pio Ardizio Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal diff --git a/src/deque.ts b/src/deque.ts new file mode 100644 index 00000000..d02fd96f --- /dev/null +++ b/src/deque.ts @@ -0,0 +1,162 @@ +// Copyright Jerome Benoit. 2023. All Rights Reserved. + +class Node { + public value: T + public next?: Node + public prev?: Node + + public constructor (value: T) { + this.value = value + } +} + +/** + * Deque. + * Implemented with a doubly linked list. + * + * @typeParam T - Type of deque values. + */ +export class Deque { + private head?: Node + private tail?: Node + /** The size of the deque. */ + public size!: number + /** The maximum size of the deque. */ + public maxSize!: number + + public constructor () { + this.clear() + } + + /** + * Appends a value to the deque. + * + * @param value - Value to append. + * @returns The new size of the queue. + */ + public push (value: T): number { + const node = new Node(value) + if (this.tail == null) { + this.head = this.tail = node + } else { + node.prev = this.tail + this.tail = this.tail.next = node + } + return this.incrementSize() + } + + /** + * Prepends a value to the deque. + * + * @param value - Value to prepend. + * @returns The new size of the queue. + */ + public unshift (value: T): number { + const node = new Node(value) + if (this.head == null) { + this.head = this.tail = node + } else { + node.next = this.head + this.head = this.head.prev = node + } + return this.incrementSize() + } + + /** + * Pops a value from the deque. + */ + public pop (): T | undefined { + if (this.head == null) { + return undefined + } + const tail = this.tail + this.tail = (this.tail as Node).prev + if (this.tail == null) { + this.head = undefined + } else { + this.tail.next = undefined + } + --this.size + return tail?.value + } + + /** + * Shifts a value from the deque. + * + * @returns The shifted value or `undefined` if the deque is empty. + */ + public shift (): T | undefined { + if (this.head == null) { + return undefined + } + const head = this.head + this.head = this.head.next + if (this.head == null) { + this.tail = undefined + } else { + this.head.prev = undefined + } + --this.size + return head?.value + } + + /** + * Peeks at the first value. + * @returns The first value or `undefined` if the queue is empty. + */ + public peekFirst (): T | undefined { + return this.head?.value + } + + /** + * Peeks at the last value. + * @returns The last value or `undefined` if the queue is empty. + */ + public peekLast (): T | undefined { + return this.tail?.value + } + + /** + * Clears the deque. + */ + public clear (): void { + this.head = undefined + this.tail = undefined + this.size = 0 + this.maxSize = 0 + } + + /** + * Returns an iterator for the deque. + * + * @returns An iterator for the deque. + * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols + */ + [Symbol.iterator] (): Iterator { + let node = this.head + return { + next: () => { + if (node == null) { + return { + value: undefined, + done: true + } + } + const ret = { + value: node.value, + done: false + } + node = node.next as Node + return ret + } + } + } + + private incrementSize (): number { + ++this.size + if (this.size > this.maxSize) { + this.maxSize = this.size + } + return this.size + } +} diff --git a/src/pools/worker-node.ts b/src/pools/worker-node.ts index 545ee7e8..d7f96e64 100644 --- a/src/pools/worker-node.ts +++ b/src/pools/worker-node.ts @@ -1,8 +1,8 @@ import { MessageChannel } from 'node:worker_threads' import { CircularArray } from '../circular-array' -import { Queue } from '../queue' import type { Task } from '../utility-types' import { DEFAULT_TASK_NAME } from '../utils' +import { Deque } from '../deque' import { type IWorker, type IWorkerNode, @@ -31,7 +31,7 @@ implements IWorkerNode { /** @inheritdoc */ public tasksQueueBackPressureSize: number private readonly taskFunctionsUsage: Map - private readonly tasksQueue: Queue> + private readonly tasksQueue: Deque> /** * Constructs a new worker node. @@ -70,7 +70,7 @@ implements IWorkerNode { } this.usage = this.initWorkerUsage() this.taskFunctionsUsage = new Map() - this.tasksQueue = new Queue>() + this.tasksQueue = new Deque>() this.tasksQueueBackPressureSize = tasksQueueBackPressureSize } @@ -90,12 +90,12 @@ implements IWorkerNode { /** @inheritdoc */ public enqueueTask (task: Task): number { - return this.tasksQueue.enqueue(task) + return this.tasksQueue.push(task) } /** @inheritdoc */ public dequeueTask (): Task | undefined { - return this.tasksQueue.dequeue() + return this.tasksQueue.shift() } /** @inheritdoc */ diff --git a/src/queue.ts b/src/queue.ts index dba55f1c..d38296b2 100644 --- a/src/queue.ts +++ b/src/queue.ts @@ -1,7 +1,7 @@ -// Copyright Jerome Benoit. 2021-2023. All Rights Reserved. +// Copyright Jerome Benoit. 2022-2023. All Rights Reserved. /** - * Queue + * Queue. * * @typeParam T - Type of queue items. */ diff --git a/tests/deque.test.js b/tests/deque.test.js new file mode 100644 index 00000000..dec96b35 --- /dev/null +++ b/tests/deque.test.js @@ -0,0 +1,126 @@ +const { expect } = require('expect') +const { Deque } = require('../lib/deque') + +describe('Deque test suite', () => { + it('Verify push() behavior', () => { + const deque = new Deque() + let rtSize = deque.push(1) + expect(deque.size).toBe(1) + expect(deque.maxSize).toBe(1) + expect(rtSize).toBe(deque.size) + expect(deque.head).toMatchObject({ value: 1 }) + expect(deque.tail).toMatchObject({ value: 1 }) + rtSize = deque.push(2) + expect(deque.size).toBe(2) + expect(deque.maxSize).toBe(2) + expect(rtSize).toBe(deque.size) + expect(deque.head).toMatchObject({ value: 1 }) + expect(deque.tail).toMatchObject({ value: 2 }) + rtSize = deque.push(3) + expect(deque.size).toBe(3) + expect(deque.maxSize).toBe(3) + expect(rtSize).toBe(deque.size) + expect(deque.head).toMatchObject({ value: 1 }) + expect(deque.tail).toMatchObject({ value: 3 }) + }) + + it('Verify unshift() behavior', () => { + const deque = new Deque() + let rtSize = deque.unshift(1) + expect(deque.size).toBe(1) + expect(deque.maxSize).toBe(1) + expect(rtSize).toBe(deque.size) + expect(deque.head).toMatchObject({ value: 1 }) + expect(deque.tail).toMatchObject({ value: 1 }) + rtSize = deque.unshift(2) + expect(deque.size).toBe(2) + expect(deque.maxSize).toBe(2) + expect(rtSize).toBe(deque.size) + expect(deque.head).toMatchObject({ value: 2 }) + expect(deque.tail).toMatchObject({ value: 1 }) + rtSize = deque.unshift(3) + expect(deque.size).toBe(3) + expect(deque.maxSize).toBe(3) + expect(rtSize).toBe(deque.size) + expect(deque.head).toMatchObject({ value: 3 }) + expect(deque.tail).toMatchObject({ value: 1 }) + }) + + it('Verify pop() behavior', () => { + const deque = new Deque() + deque.push(1) + deque.push(2) + deque.push(3) + let rtItem = deque.pop() + expect(deque.size).toBe(2) + expect(deque.maxSize).toBe(3) + expect(rtItem).toBe(3) + expect(deque.head).toMatchObject({ value: 1 }) + expect(deque.tail).toMatchObject({ value: 2 }) + rtItem = deque.pop() + expect(deque.size).toBe(1) + expect(deque.maxSize).toBe(3) + expect(rtItem).toBe(2) + expect(deque.head).toMatchObject({ value: 1 }) + expect(deque.tail).toMatchObject({ value: 1 }) + rtItem = deque.pop() + expect(deque.size).toBe(0) + expect(deque.maxSize).toBe(3) + expect(rtItem).toBe(1) + expect(deque.head).toBeUndefined() + expect(deque.tail).toBeUndefined() + }) + + it('Verify shift() behavior', () => { + const deque = new Deque() + deque.push(1) + deque.push(2) + deque.push(3) + let rtItem = deque.shift() + expect(deque.size).toBe(2) + expect(deque.maxSize).toBe(3) + expect(rtItem).toBe(1) + expect(deque.head).toMatchObject({ value: 2 }) + expect(deque.tail).toMatchObject({ value: 3 }) + rtItem = deque.shift() + expect(deque.size).toBe(1) + expect(deque.maxSize).toBe(3) + expect(rtItem).toBe(2) + expect(deque.head).toMatchObject({ value: 3 }) + expect(deque.tail).toMatchObject({ value: 3 }) + rtItem = deque.shift() + expect(deque.size).toBe(0) + expect(deque.maxSize).toBe(3) + expect(rtItem).toBe(3) + expect(deque.head).toBeUndefined() + expect(deque.tail).toBeUndefined() + }) + + it('Verify clear() behavior', () => { + const deque = new Deque() + deque.push(1) + deque.push(2) + deque.push(3) + expect(deque.size).toBe(3) + expect(deque.maxSize).toBe(3) + expect(deque.head).toMatchObject({ value: 1 }) + expect(deque.tail).toMatchObject({ value: 3 }) + deque.clear() + expect(deque.size).toBe(0) + expect(deque.maxSize).toBe(0) + expect(deque.head).toBeUndefined() + expect(deque.tail).toBeUndefined() + }) + + it('Verify iterator behavior', () => { + const deque = new Deque() + deque.push(1) + deque.push(2) + deque.push(3) + let i = 1 + for (const value of deque) { + expect(value).toBe(i) + ++i + } + }) +}) diff --git a/tests/pools/abstract/abstract-pool.test.js b/tests/pools/abstract/abstract-pool.test.js index 0ffc9e12..8a8f779c 100644 --- a/tests/pools/abstract/abstract-pool.test.js +++ b/tests/pools/abstract/abstract-pool.test.js @@ -11,7 +11,7 @@ const { WorkerTypes } = require('../../../lib') const { CircularArray } = require('../../../lib/circular-array') -const { Queue } = require('../../../lib/queue') +const { Deque } = require('../../../lib/deque') const { version } = require('../../../package.json') const { waitPoolEvents } = require('../../test-utils') @@ -642,7 +642,7 @@ describe('Abstract pool test suite', () => { ) for (const workerNode of pool.workerNodes) { expect(workerNode.tasksQueue).toBeDefined() - expect(workerNode.tasksQueue).toBeInstanceOf(Queue) + expect(workerNode.tasksQueue).toBeInstanceOf(Deque) expect(workerNode.tasksQueue.size).toBe(0) expect(workerNode.tasksQueue.maxSize).toBe(0) } @@ -654,7 +654,7 @@ describe('Abstract pool test suite', () => { ) for (const workerNode of pool.workerNodes) { expect(workerNode.tasksQueue).toBeDefined() - expect(workerNode.tasksQueue).toBeInstanceOf(Queue) + expect(workerNode.tasksQueue).toBeInstanceOf(Deque) expect(workerNode.tasksQueue.size).toBe(0) expect(workerNode.tasksQueue.maxSize).toBe(0) } diff --git a/tests/queue.test.js b/tests/queue.test.js index f4b83d57..f123a053 100644 --- a/tests/queue.test.js +++ b/tests/queue.test.js @@ -1,77 +1,79 @@ -const { expect } = require('expect') -const { Queue } = require('../lib/queue') +// const { expect } = require('expect') +// const { Queue } = require('../lib/queue') -describe('Queue test suite', () => { - it('Verify enqueue() behavior', () => { - const queue = new Queue() - let rtSize = queue.enqueue(1) - expect(queue.size).toBe(1) - expect(rtSize).toBe(queue.size) - expect(queue.offset).toBe(0) - expect(queue.maxSize).toBe(1) - expect(queue.items).toStrictEqual([1]) - rtSize = queue.enqueue(2) - expect(queue.size).toBe(2) - expect(rtSize).toBe(queue.size) - expect(queue.offset).toBe(0) - expect(queue.maxSize).toBe(2) - expect(queue.items).toStrictEqual([1, 2]) - rtSize = queue.enqueue(3) - expect(queue.size).toBe(3) - expect(rtSize).toBe(queue.size) - expect(queue.offset).toBe(0) - expect(queue.maxSize).toBe(3) - expect(queue.items).toStrictEqual([1, 2, 3]) - }) +// describe('Queue test suite', () => { +// it('Verify enqueue() behavior', () => { +// const queue = new Queue() +// let rtSize = queue.enqueue(1) +// expect(queue.size).toBe(1) +// expect(rtSize).toBe(queue.size) +// expect(queue.offset).toBe(0) +// expect(queue.maxSize).toBe(1) +// expect(queue.items).toStrictEqual([1]) +// rtSize = queue.enqueue(2) +// expect(queue.size).toBe(2) +// expect(rtSize).toBe(queue.size) +// expect(queue.offset).toBe(0) +// expect(queue.maxSize).toBe(2) +// expect(queue.items).toStrictEqual([1, 2]) +// rtSize = queue.enqueue(3) +// expect(queue.size).toBe(3) +// expect(rtSize).toBe(queue.size) +// expect(queue.offset).toBe(0) +// expect(queue.maxSize).toBe(3) +// expect(queue.items).toStrictEqual([1, 2, 3]) +// }) - it('Verify dequeue() behavior', () => { - const queue = new Queue() - queue.enqueue(1) - queue.enqueue(2) - queue.enqueue(3) - let rtItem = queue.dequeue() - expect(queue.size).toBe(2) - expect(rtItem).toBe(1) - expect(queue.offset).toBe(1) - expect(queue.maxSize).toBe(3) - expect(queue.items).toStrictEqual([1, 2, 3]) - rtItem = queue.dequeue() - expect(queue.size).toBe(1) - expect(rtItem).toBe(2) - expect(queue.offset).toBe(0) - expect(queue.maxSize).toBe(3) - expect(queue.items).toStrictEqual([3]) - rtItem = queue.dequeue() - expect(queue.size).toBe(0) - expect(rtItem).toBe(3) - expect(queue.offset).toBe(0) - expect(queue.maxSize).toBe(3) - expect(queue.items).toStrictEqual([]) - }) +// it('Verify dequeue() behavior', () => { +// const queue = new Queue() +// queue.enqueue(1) +// queue.enqueue(2) +// queue.enqueue(3) +// let rtItem = queue.dequeue() +// expect(queue.size).toBe(2) +// expect(rtItem).toBe(1) +// expect(queue.offset).toBe(1) +// expect(queue.maxSize).toBe(3) +// expect(queue.items).toStrictEqual([1, 2, 3]) +// rtItem = queue.dequeue() +// expect(queue.size).toBe(1) +// expect(rtItem).toBe(2) +// expect(queue.offset).toBe(0) +// expect(queue.maxSize).toBe(3) +// expect(queue.items).toStrictEqual([3]) +// rtItem = queue.dequeue() +// expect(queue.size).toBe(0) +// expect(rtItem).toBe(3) +// expect(queue.offset).toBe(0) +// expect(queue.maxSize).toBe(3) +// expect(queue.items).toStrictEqual([]) +// }) - it('Verify clear() behavior', () => { - const queue = new Queue() - queue.enqueue(1) - queue.enqueue(2) - queue.enqueue(3) - expect(queue.size).toBe(3) - expect(queue.maxSize).toBe(3) - queue.clear() - expect(queue.size).toBe(0) - expect(queue.maxSize).toBe(0) - expect(queue.items).toStrictEqual([]) - expect(queue.offset).toBe(0) - }) +// it('Verify clear() behavior', () => { +// const queue = new Queue() +// queue.enqueue(1) +// queue.enqueue(2) +// queue.enqueue(3) +// expect(queue.size).toBe(3) +// expect(queue.maxSize).toBe(3) +// expect(queue.items).toStrictEqual([1, 2, 3]) +// expect(queue.offset).toBe(0) +// queue.clear() +// expect(queue.size).toBe(0) +// expect(queue.maxSize).toBe(0) +// expect(queue.items).toStrictEqual([]) +// expect(queue.offset).toBe(0) +// }) - it('Verify iterator behavior', () => { - const queue = new Queue() - queue.enqueue(1) - queue.enqueue(2) - queue.enqueue(3) - let i = 1 - for (const item of queue) { - expect(item).toBe(i) - ++i - } - }) -}) +// it('Verify iterator behavior', () => { +// const queue = new Queue() +// queue.enqueue(1) +// queue.enqueue(2) +// queue.enqueue(3) +// let i = 1 +// for (const item of queue) { +// expect(item).toBe(i) +// ++i +// } +// }) +// }) -- 2.34.1