Commit b8c06dc
lib: ensure no holey array in fixed_queue
Co-authored-by: Jake Yuesong Li <jake.yuesong@gmail.com>
PR-URL: #54537
Fixes: #54472
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Michaël Zasso <targos@protonmail.com>
Reviewed-By: Benjamin Gruenbaum <benjamingr@gmail.com>
Reviewed-By: Jake Yuesong Li <jake.yuesong@gmail.com>1 parent fe3155c commit b8c06dc
2 files changed
Lines changed: 27 additions & 14 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -2,6 +2,7 @@ | |||
| 2 | 2 | ||
| 3 | 3 | const { | |
| 4 | 4 | Array, | |
| 5 | + ArrayPrototypeFill, | ||
| 5 | 6 | } = primordials; | |
| 6 | 7 | ||
| 7 | 8 | // Currently optimal queue size, tested on V8 6.0 - 6.6. Must be power of two. | |
@@ -17,18 +18,18 @@ const kMask = kSize - 1; | |||
| 17 | 18 | // +-----------+ <-----\ +-----------+ <------\ +-----------+ | |
| 18 | 19 | // | [null] | \----- | next | \------- | next | | |
| 19 | 20 | // +-----------+ +-----------+ +-----------+ | |
| 20 | - // | item | <-- bottom | item | <-- bottom | [empty] | | ||
| 21 | - // | item | | item | | [empty] | | ||
| 22 | - // | item | | item | | [empty] | | ||
| 23 | - // | item | | item | | [empty] | | ||
| 21 | + // | item | <-- bottom | item | <-- bottom | undefined | | ||
| 22 | + // | item | | item | | undefined | | ||
| 23 | + // | item | | item | | undefined | | ||
| 24 | + // | item | | item | | undefined | | ||
| 24 | 25 | // | item | | item | bottom --> | item | | |
| 25 | 26 | // | item | | item | | item | | |
| 26 | 27 | // | ... | | ... | | ... | | |
| 27 | 28 | // | item | | item | | item | | |
| 28 | 29 | // | item | | item | | item | | |
| 29 | - // | [empty] | <-- top | item | | item | | ||
| 30 | - // | [empty] | | item | | item | | ||
| 31 | - // | [empty] | | [empty] | <-- top top --> | [empty] | | ||
| 30 | + // | undefined | <-- top | item | | item | | ||
| 31 | + // | undefined | | item | | item | | ||
| 32 | + // | undefined | | undefined | <-- top top --> | undefined | | ||
| 32 | 33 | // +-----------+ +-----------+ +-----------+ | |
| 33 | 34 | // | |
| 34 | 35 | // Or, if there is only one circular buffer, it looks something | |
@@ -40,12 +41,12 @@ const kMask = kSize - 1; | |||
| 40 | 41 | // +-----------+ +-----------+ | |
| 41 | 42 | // | [null] | | [null] | | |
| 42 | 43 | // +-----------+ +-----------+ | |
| 43 | - // | [empty] | | item | | ||
| 44 | - // | [empty] | | item | | ||
| 45 | - // | item | <-- bottom top --> | [empty] | | ||
| 46 | - // | item | | [empty] | | ||
| 47 | - // | [empty] | <-- top bottom --> | item | | ||
| 48 | - // | [empty] | | item | | ||
| 44 | + // | undefined | | item | | ||
| 45 | + // | undefined | | item | | ||
| 46 | + // | item | <-- bottom top --> | undefined | | ||
| 47 | + // | item | | undefined | | ||
| 48 | + // | undefined | <-- top bottom --> | item | | ||
| 49 | + // | undefined | | item | | ||
| 49 | 50 | // +-----------+ +-----------+ | |
| 50 | 51 | // | |
| 51 | 52 | // Adding a value means moving `top` forward by one, removing means | |
@@ -60,7 +61,7 @@ class FixedCircularBuffer { | |||
| 60 | 61 | constructor() { | |
| 61 | 62 | this.bottom = 0; | |
| 62 | 63 | this.top = 0; | |
| 63 | - this.list = new Array(kSize); | ||
| 64 | + this.list = ArrayPrototypeFill(new Array(kSize), undefined); | ||
| 64 | 65 | this.next = null; | |
| 65 | 66 | } | |
| 66 | 67 | ||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -32,3 +32,15 @@ const FixedQueue = require('internal/fixed_queue'); | |||
| 32 | 32 | assert.strictEqual(queue.shift(), 'a'); | |
| 33 | 33 | assert(queue.isEmpty()); | |
| 34 | 34 | } | |
| 35 | + | ||
| 36 | + { | ||
| 37 | + // FixedQueue must not be holey array | ||
| 38 | + // Refs: https://github.com/nodejs/node/issues/54472 | ||
| 39 | + const queue = new FixedQueue(); | ||
| 40 | + for (let i = 0; i < queue.head.list.length; i++) { | ||
| 41 | + assert(i in queue.head.list); | ||
| 42 | + } | ||
| 43 | + for (let i = 0; i < queue.tail.list.length; i++) { | ||
| 44 | + assert(i in queue.tail.list); | ||
| 45 | + } | ||
| 46 | + } | ||
0 commit comments