From 097dea68fd73ac0d6f6db7b13c585bf8b6726418 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sat, 6 Jul 2024 22:39:43 +0200 Subject: [PATCH] perf: optimize tasks queuing implementation MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- src/fixed-priority-queue.ts | 97 ++++---------- src/fixed-queue.ts | 126 ++++++++++++++++++ src/index.ts | 7 +- src/pools/abstract-pool.ts | 12 +- src/priority-queue.ts | 73 ++++++----- src/utility-types.ts | 89 +++++++++++++ tests/fixed-priority-queue.test.mjs | 17 +-- tests/fixed-queue.test.mjs | 197 ++++++++++++++++++++++++++++ tests/pools/abstract-pool.test.mjs | 3 +- tests/priority-queue.test.mjs | 15 ++- 10 files changed, 507 insertions(+), 129 deletions(-) create mode 100644 src/fixed-queue.ts create mode 100644 tests/fixed-queue.test.mjs diff --git a/src/fixed-priority-queue.ts b/src/fixed-priority-queue.ts index 1cc1480a..1597860e 100644 --- a/src/fixed-priority-queue.ts +++ b/src/fixed-priority-queue.ts @@ -1,89 +1,59 @@ -/** - * Default buffer size. - */ -export const defaultQueueSize = 2048 - -/** - * Fixed priority queue node. - * @typeParam T - Type of priority queue node data. - * @internal - */ -export interface FixedPriorityQueueNode { - data: T - priority: number -} +import { defaultQueueSize, type FixedQueueNode, type IFixedQueue } from './utility-types.js' /** * Fixed priority queue. * @typeParam T - Type of fixed priority queue data. * @internal */ -export class FixedPriorityQueue { +export class FixedPriorityQueue implements IFixedQueue { private start!: number - private readonly nodeArray: FixedPriorityQueueNode[] - /** The fixed priority queue capacity. */ + /** @inheritdoc */ public readonly capacity: number - /** The fixed priority queue size. */ + /** @inheritdoc */ public size!: number - /** Whether to enable priority. */ - public enablePriority: boolean + /** @inheritdoc */ + public nodeArray: FixedQueueNode[] /** * Constructs a fixed priority queue. * @param size - Fixed priority queue size. @defaultValue defaultQueueSize - * @param enablePriority - Whether to enable priority. @defaultValue false * @returns FixedPriorityQueue. */ - constructor (size: number = defaultQueueSize, enablePriority = false) { + constructor (size: number = defaultQueueSize) { this.checkSize(size) this.capacity = size - this.enablePriority = enablePriority - this.nodeArray = new Array>(this.capacity) + this.nodeArray = new Array>(this.capacity) this.clear() } - /** - * Checks if the fixed priority queue is empty. - * @returns `true` if the fixed priority queue is empty, `false` otherwise. - */ + /** @inheritdoc */ public empty (): boolean { return this.size === 0 } - /** - * Checks if the fixed priority queue is full. - * @returns `true` if the fixed priority queue is full, `false` otherwise. - */ + /** @inheritdoc */ public full (): boolean { return this.size === this.capacity } - /** - * Enqueue data into the fixed priority queue. - * @param data - Data to enqueue. - * @param priority - Priority of the data. Lower values have higher priority. - * @returns The new size of the priority queue. - * @throws If the fixed priority queue is full. - */ + /** @inheritdoc */ public enqueue (data: T, priority?: number): number { if (this.full()) { throw new Error('Priority queue is full') } priority = priority ?? 0 let inserted = false - if (this.enablePriority) { - let index = this.start - for (let i = 0; i < this.size; i++) { - if (this.nodeArray[index].priority > priority) { - this.nodeArray.splice(index, 0, { data, priority }) - this.nodeArray.length = this.capacity - inserted = true - break - } - ++index - if (index === this.capacity) { - index = 0 - } + let index = this.start + for (let i = 0; i < this.size; i++) { + if (this.nodeArray[index].priority > priority) { + this.nodeArray.splice(index, 0, { data, priority }) + this.nodeArray.length = this.capacity + inserted = true + break + } + ++index + if (index === this.capacity) { + index = 0 } } if (!inserted) { @@ -96,11 +66,7 @@ export class FixedPriorityQueue { return ++this.size } - /** - * Gets data from the fixed priority queue. - * @param index - The index of the data to get. - * @returns The data at the index or `undefined` if the fixed priority queue is empty or the index is out of bounds. - */ + /** @inheritdoc */ public get (index: number): T | undefined { if (this.empty() || index >= this.size) { return undefined @@ -112,10 +78,7 @@ export class FixedPriorityQueue { return this.nodeArray[index].data } - /** - * Dequeue data from the fixed priority queue. - * @returns The dequeued data or `undefined` if the priority queue is empty. - */ + /** @inheritdoc */ public dequeue (): T | undefined { if (this.empty()) { return undefined @@ -129,19 +92,13 @@ export class FixedPriorityQueue { return this.nodeArray[index].data } - /** - * Clears the fixed priority queue. - */ + /** @inheritdoc */ public clear (): void { this.start = 0 this.size = 0 } - /** - * Returns an iterator for the fixed priority queue. - * @returns An iterator for the fixed priority queue. - * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols - */ + /** @inheritdoc */ public [Symbol.iterator] (): Iterator { let index = this.start let i = 0 @@ -168,7 +125,7 @@ export class FixedPriorityQueue { } /** - * Checks the queue size. + * Checks the fixed queue size. * @param size - Queue size. */ private checkSize (size: number): void { diff --git a/src/fixed-queue.ts b/src/fixed-queue.ts new file mode 100644 index 00000000..4856b304 --- /dev/null +++ b/src/fixed-queue.ts @@ -0,0 +1,126 @@ +import { defaultQueueSize, type FixedQueueNode, type IFixedQueue } from './utility-types.js' + +/** + * Fixed queue. + * @typeParam T - Type of fixed queue data. + * @internal + */ +export class FixedQueue implements IFixedQueue { + private start!: number + /** @inheritdoc */ + public readonly capacity: number + /** @inheritdoc */ + public size!: number + /** @inheritdoc */ + public nodeArray: FixedQueueNode[] + + /** + * Constructs a fixed queue. + * @param size - Fixed queue size. @defaultValue defaultQueueSize + * @returns FixedQueue. + */ + constructor (size: number = defaultQueueSize) { + this.checkSize(size) + this.capacity = size + this.nodeArray = new Array>(this.capacity) + this.clear() + } + + /** @inheritdoc */ + public empty (): boolean { + return this.size === 0 + } + + /** @inheritdoc */ + public full (): boolean { + return this.size === this.capacity + } + + /** @inheritdoc */ + public enqueue (data: T, priority?: number): number { + if (this.full()) { + throw new Error('Priority queue is full') + } + let index = this.start + this.size + if (index >= this.capacity) { + index -= this.capacity + } + this.nodeArray[index] = { data, priority: priority ?? 0 } + return ++this.size + } + + /** @inheritdoc */ + public get (index: number): T | undefined { + if (this.empty() || index >= this.size) { + return undefined + } + index += this.start + if (index >= this.capacity) { + index -= this.capacity + } + return this.nodeArray[index].data + } + + /** @inheritdoc */ + public dequeue (): T | undefined { + if (this.empty()) { + return undefined + } + const index = this.start + --this.size + ++this.start + if (this.start === this.capacity) { + this.start = 0 + } + return this.nodeArray[index].data + } + + /** @inheritdoc */ + public clear (): void { + this.start = 0 + this.size = 0 + } + + /** @inheritdoc */ + public [Symbol.iterator] (): Iterator { + let index = this.start + let i = 0 + return { + next: () => { + if (i >= this.size) { + return { + value: undefined, + done: true, + } + } + const value = this.nodeArray[index].data + ++index + ++i + if (index === this.capacity) { + index = 0 + } + return { + value, + done: false, + } + }, + } + } + + /** + * Checks the fixed queue size. + * @param size - Queue size. + */ + private checkSize (size: number): void { + if (!Number.isSafeInteger(size)) { + throw new TypeError( + `Invalid fixed queue size: '${size.toString()}' is not an integer` + ) + } + if (size < 0) { + throw new RangeError( + `Invalid fixed queue size: ${size.toString()} < 0` + ) + } + } +} diff --git a/src/index.ts b/src/index.ts index e779bf0c..178eeed2 100644 --- a/src/index.ts +++ b/src/index.ts @@ -1,8 +1,4 @@ export type { CircularBuffer } from './circular-buffer.js' -export type { - FixedPriorityQueue, - FixedPriorityQueueNode, -} from './fixed-priority-queue.js' export type { AbstractPool } from './pools/abstract-pool.js' export { DynamicClusterPool } from './pools/cluster/dynamic.js' export type { ClusterPoolOptions } from './pools/cluster/fixed.js' @@ -53,8 +49,9 @@ export type { WorkerUsage, } from './pools/worker.js' export { WorkerTypes } from './pools/worker.js' -export type { PriorityQueue, PriorityQueueNode } from './priority-queue.js' +export type { PriorityQueue } from './priority-queue.js' export type { + IFixedQueue, MessageValue, PromiseResponseWrapper, Task, diff --git a/src/pools/abstract-pool.ts b/src/pools/abstract-pool.ts index 603409f0..e11a2bbb 100644 --- a/src/pools/abstract-pool.ts +++ b/src/pools/abstract-pool.ts @@ -4,12 +4,12 @@ import { EventEmitterAsyncResource } from 'node:events' import { performance } from 'node:perf_hooks' import type { TransferListItem } from 'node:worker_threads' -import { defaultBucketSize } from '../priority-queue.js' -import type { - MessageValue, - PromiseResponseWrapper, - Task, - TaskFunctionProperties, +import { + defaultBucketSize, + type MessageValue, + type PromiseResponseWrapper, + type Task, + type TaskFunctionProperties, } from '../utility-types.js' import { average, diff --git a/src/priority-queue.ts b/src/priority-queue.ts index 2a266d28..ac75fc06 100644 --- a/src/priority-queue.ts +++ b/src/priority-queue.ts @@ -1,20 +1,8 @@ // Copyright Jerome Benoit. 2024. All Rights Reserved. import { FixedPriorityQueue } from './fixed-priority-queue.js' - -/** - * Default bucket size. - */ -export const defaultBucketSize = 2048 - -/** - * Priority queue node. - * @typeParam T - Type of priority queue node data. - * @internal - */ -export interface PriorityQueueNode extends FixedPriorityQueue { - next?: FixedPriorityQueue -} +import { FixedQueue } from './fixed-queue.js' +import { defaultBucketSize, type FixedQueueNode, type IFixedQueue, type PriorityQueueNode } from './utility-types.js' /** * Priority queue. @@ -25,6 +13,7 @@ export class PriorityQueue { private head!: PriorityQueueNode private tail!: PriorityQueueNode private readonly bucketSize: number + private priorityEnabled: boolean /** The priority queue maximum size. */ public maxSize!: number @@ -47,11 +36,8 @@ export class PriorityQueue { throw new RangeError(`Invalid bucket size: ${bucketSize.toString()} < 0`) } this.bucketSize = bucketSize - this.head = this.tail = new FixedPriorityQueue( - this.bucketSize, - enablePriority - ) - this.maxSize = 0 + this.priorityEnabled = enablePriority + this.clear() } /** @@ -69,18 +55,38 @@ export class PriorityQueue { } public get enablePriority (): boolean { - return this.head.enablePriority + return this.priorityEnabled } public set enablePriority (enablePriority: boolean) { - if (this.head.enablePriority === enablePriority) { + if (this.priorityEnabled === enablePriority) { return } + this.priorityEnabled = enablePriority + let head: PriorityQueueNode + let tail: PriorityQueueNode + let prevNode : PriorityQueueNode | undefined let node: PriorityQueueNode | undefined = this.tail + let buckets = 0 while (node != null) { - node.enablePriority = enablePriority + const currentNode = this.getPriorityQueueNode(node.nodeArray) + if (buckets === 0) { + tail = currentNode + } + if (prevNode != null) { + prevNode.next = currentNode + } + prevNode = currentNode + if (node.next == null) { + head = currentNode + } + ++buckets node = node.next } + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + this.head = head! + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + this.tail = tail! } /** @@ -99,10 +105,7 @@ export class PriorityQueue { */ public enqueue (data: T, priority?: number): number { if (this.head.full()) { - this.head = this.head.next = new FixedPriorityQueue( - this.bucketSize, - this.enablePriority - ) + this.head = this.head.next = this.getPriorityQueueNode() } this.head.enqueue(data, priority) const size = this.size @@ -168,10 +171,7 @@ export class PriorityQueue { * Clears the priority queue. */ public clear (): void { - this.head = this.tail = new FixedPriorityQueue( - this.bucketSize, - this.enablePriority - ) + this.head = this.tail = this.getPriorityQueueNode() this.maxSize = 0 } @@ -204,4 +204,17 @@ export class PriorityQueue { }, } } + + private getPriorityQueueNode (nodeArray?: FixedQueueNode[]): PriorityQueueNode { + let fixedQueue: IFixedQueue + if (this.priorityEnabled) { + fixedQueue = new FixedPriorityQueue(this.bucketSize) + } else { + fixedQueue = new FixedQueue(this.bucketSize) + } + if (nodeArray != null) { + fixedQueue.nodeArray = nodeArray + } + return fixedQueue + } } diff --git a/src/utility-types.ts b/src/utility-types.ts index f13cce6a..e40d7b52 100644 --- a/src/utility-types.ts +++ b/src/utility-types.ts @@ -206,4 +206,93 @@ export interface PromiseResponseWrapper { readonly asyncResource?: AsyncResource } +/** + * Remove readonly modifier from all properties of T. + * @typeParam T - Type to remove readonly modifier. + * @internal + */ export type Writable = { -readonly [P in keyof T]: T[P] } + +/** + * Default queue size. + * @internal + */ +export const defaultQueueSize = 2048 + +/** + * Fixed queue node. + * @typeParam T - Type of fixed queue node data. + * @internal + */ +export interface FixedQueueNode { + data: T + priority: number +} + +/** + * Fixed queue. + * @typeParam T - Type of fixed queue data. + * @internal + */ +export interface IFixedQueue { + /** The fixed queue capacity. */ + readonly capacity: number + /** The fixed queue size. */ + readonly size: number + /** The fixed queue node array. */ + nodeArray: FixedQueueNode[] + /** + * Checks if the fixed queue is empty. + * @returns `true` if the fixed queue is empty, `false` otherwise. + */ + empty(): boolean + /** + * Checks if the fixed queue is full. + * @returns `true` if the fixed queue is full, `false` otherwise. + */ + full(): boolean + /** + * Enqueue data into the fixed queue. + * @param data - Data to enqueue. + * @param priority - Priority of the data. Lower values have higher priority. + * @returns The new size of the fixed queue. + * @throws If the fixed queue is full. + */ + enqueue (data: T, priority?: number): number + /** + * Gets data from the fixed queue. + * @param index - The index of the data to get. + * @returns The data at the index or `undefined` if the fixed queue is empty or the index is out of bounds. + */ + get (index: number): T | undefined + /** + * Dequeue data from the fixed queue. + * @returns The dequeued data or `undefined` if the fixed queue is empty. + */ + dequeue (): T | undefined + /** + * Clears the fixed queue. + */ + clear (): void + /** + * Returns an iterator for the fixed queue. + * @returns An iterator for the fixed queue. + * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols + */ + [Symbol.iterator] (): Iterator +} + +/** + * Default bucket size. + * @internal + */ +export const defaultBucketSize = 2048 + +/** + * Priority queue node. + * @typeParam T - Type of priority queue node data. + * @internal + */ +export interface PriorityQueueNode extends IFixedQueue { + next?: IFixedQueue +} diff --git a/tests/fixed-priority-queue.test.mjs b/tests/fixed-priority-queue.test.mjs index 40b55643..e474bd1c 100644 --- a/tests/fixed-priority-queue.test.mjs +++ b/tests/fixed-priority-queue.test.mjs @@ -1,9 +1,9 @@ import { expect } from 'expect' import { - defaultQueueSize, FixedPriorityQueue, } from '../lib/fixed-priority-queue.cjs' +import { defaultQueueSize } from '../lib/utility-types.cjs' describe('Fixed priority queue test suite', () => { it('Verify constructor() behavior', () => { @@ -13,23 +13,16 @@ describe('Fixed priority queue test suite', () => { expect(() => new FixedPriorityQueue(-1)).toThrow( new RangeError('Invalid fixed priority queue size: -1 < 0') ) - let fixedPriorityQueue = new FixedPriorityQueue() + const fixedPriorityQueue = new FixedPriorityQueue() expect(fixedPriorityQueue.start).toBe(0) expect(fixedPriorityQueue.size).toBe(0) expect(fixedPriorityQueue.nodeArray).toBeInstanceOf(Array) expect(fixedPriorityQueue.capacity).toBe(defaultQueueSize) - expect(fixedPriorityQueue.enablePriority).toBe(false) - fixedPriorityQueue = new FixedPriorityQueue(2, true) - expect(fixedPriorityQueue.start).toBe(0) - expect(fixedPriorityQueue.size).toBe(0) - expect(fixedPriorityQueue.nodeArray).toBeInstanceOf(Array) - expect(fixedPriorityQueue.capacity).toBe(2) - expect(fixedPriorityQueue.enablePriority).toBe(true) }) it('Verify enqueue() behavior', () => { const queueSize = 5 - const fixedPriorityQueue = new FixedPriorityQueue(queueSize, true) + const fixedPriorityQueue = new FixedPriorityQueue(queueSize) let rtSize = fixedPriorityQueue.enqueue(1) expect(fixedPriorityQueue.start).toBe(0) expect(fixedPriorityQueue.size).toBe(1) @@ -86,7 +79,7 @@ describe('Fixed priority queue test suite', () => { }) it('Verify get() behavior', () => { - const fixedPriorityQueue = new FixedPriorityQueue(defaultQueueSize, true) + const fixedPriorityQueue = new FixedPriorityQueue() fixedPriorityQueue.enqueue(1) fixedPriorityQueue.enqueue(2, -1) fixedPriorityQueue.enqueue(3) @@ -98,7 +91,7 @@ describe('Fixed priority queue test suite', () => { it('Verify dequeue() behavior', () => { const queueSize = 5 - const fixedPriorityQueue = new FixedPriorityQueue(queueSize, true) + const fixedPriorityQueue = new FixedPriorityQueue(queueSize) fixedPriorityQueue.enqueue(1) fixedPriorityQueue.enqueue(2, -1) fixedPriorityQueue.enqueue(3) diff --git a/tests/fixed-queue.test.mjs b/tests/fixed-queue.test.mjs new file mode 100644 index 00000000..941b7916 --- /dev/null +++ b/tests/fixed-queue.test.mjs @@ -0,0 +1,197 @@ +import { expect } from 'expect' + +import { + FixedQueue, +} from '../lib/fixed-queue.cjs' +import { defaultQueueSize } from '../lib/utility-types.cjs' + +describe('Fixed queue test suite', () => { + it('Verify constructor() behavior', () => { + expect(() => new FixedQueue('')).toThrow( + new TypeError("Invalid fixed queue size: '' is not an integer") + ) + expect(() => new FixedQueue(-1)).toThrow( + new RangeError('Invalid fixed queue size: -1 < 0') + ) + const fixedQueue = new FixedQueue() + expect(fixedQueue.start).toBe(0) + expect(fixedQueue.size).toBe(0) + expect(fixedQueue.nodeArray).toBeInstanceOf(Array) + expect(fixedQueue.capacity).toBe(defaultQueueSize) + }) + + it('Verify enqueue() behavior', () => { + const queueSize = 5 + const fixedQueue = new FixedQueue(queueSize) + let rtSize = fixedQueue.enqueue(1) + expect(fixedQueue.start).toBe(0) + expect(fixedQueue.size).toBe(1) + expect(rtSize).toBe(fixedQueue.size) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + ]) + expect(fixedQueue.capacity).toBe(queueSize) + rtSize = fixedQueue.enqueue(2) + expect(fixedQueue.start).toBe(0) + expect(fixedQueue.size).toBe(2) + expect(rtSize).toBe(fixedQueue.size) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + ]) + expect(fixedQueue.capacity).toBe(queueSize) + rtSize = fixedQueue.enqueue(3) + expect(fixedQueue.start).toBe(0) + expect(fixedQueue.size).toBe(3) + expect(rtSize).toBe(fixedQueue.size) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 }, + ]) + expect(fixedQueue.capacity).toBe(queueSize) + rtSize = fixedQueue.enqueue(3, -1) + expect(fixedQueue.start).toBe(0) + expect(fixedQueue.size).toBe(4) + expect(rtSize).toBe(fixedQueue.size) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 }, + { data: 3, priority: -1 }, + ]) + expect(fixedQueue.capacity).toBe(queueSize) + rtSize = fixedQueue.enqueue(1, 1) + expect(fixedQueue.start).toBe(0) + expect(fixedQueue.size).toBe(5) + expect(rtSize).toBe(fixedQueue.size) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 }, + { data: 3, priority: -1 }, + { data: 1, priority: 1 }, + ]) + expect(fixedQueue.capacity).toBe(queueSize) + expect(() => fixedQueue.enqueue(4)).toThrow( + new Error('Priority queue is full') + ) + }) + + it('Verify get() behavior', () => { + const fixedQueue = new FixedQueue() + fixedQueue.enqueue(1) + fixedQueue.enqueue(2, -1) + fixedQueue.enqueue(3) + expect(fixedQueue.get(0)).toBe(1) + expect(fixedQueue.get(1)).toBe(2) + expect(fixedQueue.get(2)).toBe(3) + expect(fixedQueue.get(3)).toBe(undefined) + }) + + it('Verify dequeue() behavior', () => { + const queueSize = 5 + const fixedQueue = new FixedQueue(queueSize) + fixedQueue.enqueue(1) + fixedQueue.enqueue(2, -1) + fixedQueue.enqueue(3) + expect(fixedQueue.start).toBe(0) + expect(fixedQueue.size).toBe(3) + expect(fixedQueue.capacity).toBe(queueSize) + let rtItem = fixedQueue.dequeue() + expect(fixedQueue.start).toBe(1) + expect(fixedQueue.size).toBe(2) + expect(rtItem).toBe(1) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: -1 }, + { data: 3, priority: 0 }, + ]) + expect(fixedQueue.capacity).toBe(queueSize) + rtItem = fixedQueue.dequeue() + expect(fixedQueue.start).toBe(2) + expect(fixedQueue.size).toBe(1) + expect(rtItem).toBe(2) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: -1 }, + { data: 3, priority: 0 }, + ]) + expect(fixedQueue.capacity).toBe(queueSize) + rtItem = fixedQueue.dequeue() + expect(fixedQueue.start).toBe(3) + expect(fixedQueue.size).toBe(0) + expect(rtItem).toBe(3) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: -1 }, + { data: 3, priority: 0 }, + ]) + expect(fixedQueue.capacity).toBe(queueSize) + rtItem = fixedQueue.dequeue() + expect(fixedQueue.start).toBe(3) + expect(fixedQueue.size).toBe(0) + expect(rtItem).toBe(undefined) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: -1 }, + { data: 3, priority: 0 }, + ]) + expect(fixedQueue.capacity).toBe(queueSize) + }) + + it('Verify iterator behavior', () => { + const fixedQueue = new FixedQueue() + fixedQueue.enqueue(1) + fixedQueue.enqueue(2) + fixedQueue.enqueue(3) + let i = fixedQueue.start + 1 + for (const value of fixedQueue) { + expect(value).toBe(i) + ++i + } + fixedQueue.dequeue() + i = fixedQueue.start + 1 + for (const value of fixedQueue) { + expect(value).toBe(i) + ++i + } + }) + + it('Verify empty() behavior', () => { + const fixedQueue = new FixedQueue() + expect(fixedQueue.empty()).toBe(true) + fixedQueue.enqueue(1) + expect(fixedQueue.empty()).toBe(false) + fixedQueue.dequeue() + expect(fixedQueue.empty()).toBe(true) + }) + + it('Verify full() behavior', () => { + const fixedQueue = new FixedQueue(2) + expect(fixedQueue.full()).toBe(false) + fixedQueue.enqueue(1) + expect(fixedQueue.full()).toBe(false) + fixedQueue.enqueue(2) + expect(fixedQueue.full()).toBe(true) + fixedQueue.dequeue() + expect(fixedQueue.full()).toBe(false) + }) + + it('Verify clear() behavior', () => { + const fixedQueue = new FixedQueue() + fixedQueue.start = 1 + fixedQueue.size = 2 + fixedQueue.nodeArray = [ + { data: 2, priority: 0 }, + { data: 3, priority: 0 }, + ] + fixedQueue.clear() + expect(fixedQueue.start).toBe(0) + expect(fixedQueue.size).toBe(0) + expect(fixedQueue.nodeArray).toMatchObject([ + { data: 2, priority: 0 }, + { data: 3, priority: 0 }, + ]) + }) +}) diff --git a/tests/pools/abstract-pool.test.mjs b/tests/pools/abstract-pool.test.mjs index 7661bf67..276ecf14 100644 --- a/tests/pools/abstract-pool.test.mjs +++ b/tests/pools/abstract-pool.test.mjs @@ -20,7 +20,8 @@ import { WorkerTypes, } from '../../lib/index.cjs' import { WorkerNode } from '../../lib/pools/worker-node.cjs' -import { defaultBucketSize, PriorityQueue } from '../../lib/priority-queue.cjs' +import { PriorityQueue } from '../../lib/priority-queue.cjs' +import { defaultBucketSize } from '../../lib/utility-types.cjs' import { DEFAULT_TASK_NAME } from '../../lib/utils.cjs' import { waitPoolEvents } from '../test-utils.cjs' diff --git a/tests/priority-queue.test.mjs b/tests/priority-queue.test.mjs index d65d6f16..c9b141b2 100644 --- a/tests/priority-queue.test.mjs +++ b/tests/priority-queue.test.mjs @@ -1,7 +1,9 @@ import { expect } from 'expect' import { FixedPriorityQueue } from '../lib/fixed-priority-queue.cjs' -import { defaultBucketSize, PriorityQueue } from '../lib/priority-queue.cjs' +import { FixedQueue } from '../lib/fixed-queue.cjs' +import { PriorityQueue } from '../lib/priority-queue.cjs' +import { defaultBucketSize } from '../lib/utility-types.cjs' describe('Priority queue test suite', () => { it('Verify constructor() behavior', () => { @@ -17,10 +19,10 @@ describe('Priority queue test suite', () => { expect(priorityQueue.size).toBe(0) expect(priorityQueue.maxSize).toBe(0) expect(priorityQueue.enablePriority).toBe(false) - expect(priorityQueue.head).toBeInstanceOf(FixedPriorityQueue) + expect(priorityQueue.head).toBeInstanceOf(FixedQueue) expect(priorityQueue.head.next).toBe(undefined) expect(priorityQueue.head.capacity).toBe(defaultBucketSize) - expect(priorityQueue.tail).toBeInstanceOf(FixedPriorityQueue) + expect(priorityQueue.tail).toBeInstanceOf(FixedQueue) expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) const bucketSize = 2 priorityQueue = new PriorityQueue(bucketSize, true) @@ -308,18 +310,21 @@ describe('Priority queue test suite', () => { let buckets = 0 let node = priorityQueue.tail while (node != null) { - expect(node.enablePriority).toBe(false) + expect(node).toBeInstanceOf(FixedQueue) node = node.next ++buckets } expect(buckets).toBe(2) priorityQueue.enablePriority = true expect(priorityQueue.enablePriority).toBe(true) + buckets = 0 node = priorityQueue.tail while (node != null) { - expect(node.enablePriority).toBe(true) + expect(node).toBeInstanceOf(FixedPriorityQueue) node = node.next + ++buckets } + expect(buckets).toBe(2) }) it('Verify iterator behavior', () => { -- 2.34.1