🚀 Socket Launch Week Day 5:Introducing Repository Access Permissions and Custom Roles.Learn more →
Sign In

@nxtedition/slice

Package Overview
Dependencies
Maintainers
10
Versions
29
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@nxtedition/slice - npm Package Compare versions

Comparing version
1.0.1
 to
1.0.2
+1
lib/index.bench.d.ts
export {};
+2
-9
lib/index.d.ts

@@ -24,11 +24,6 @@ import util from 'node:util';

}
/**
* A buddy allocator using XOR bitmap for efficient coalescing.
* Each bit tracks the XOR of a buddy pair's allocation state.
* When a bit is 0, both buddies have the same state (both free or both allocated).
* When a bit is 1, the buddies have different states.
*/
export declare class BuddyAllocator {
export declare class PoolAllocator {
#private;
constructor(poolTotal?: number);
isFromPool(slice: Slice): boolean;
realloc(slice: Slice, byteLength: number): Slice;

@@ -43,5 +38,3 @@ get stats(): {

poolCount: number;
poolList: number[];
};
isFromPool(slice: Slice | null | undefined): boolean;
}
+59
-189
lib/index.js

@@ -84,3 +84,7 @@ import util from 'node:util'

if (this.buffer === target && sourceStart === targetStart) {
if (
sourceStart === targetStart &&
this.buffer.buffer === target.buffer &&
this.buffer.byteOffset === target.byteOffset
) {
return sourceEnd - sourceStart

@@ -221,70 +225,21 @@ }

/**
* A buddy allocator using XOR bitmap for efficient coalescing.
* Each bit tracks the XOR of a buddy pair's allocation state.
* When a bit is 0, both buddies have the same state (both free or both allocated).
* When a bit is 1, the buddies have different states.
*/
export class BuddyAllocator {
#size = 0
#padding = 0
#poolCount = 0
export class PoolAllocator {
#size = 0
#pools = []
#poolBuffer
#poolTotal
#minOrder
#maxOrder
#poolOffset = 0
#poolSize = 0
#poolCount = 0
#padding = 0
// Free lists indexed by order - simple arrays with push/pop
#freeLists = []
// XOR bitmap for coalescing - single contiguous buffer for cache locality
// Each order has a view into this buffer
// Bit = 0: both buddies same state, Bit = 1: different states
#bitmaps = []
#bitmapBuffer = null
constructor(poolTotal = 128 * 1024 * 1024) {
// Handle invalid pool sizes gracefully - fall back to no pool
if (!Number.isFinite(poolTotal) || poolTotal <= 0) {
this.#poolBuffer = Buffer.allocUnsafe(0)
this.#poolTotal = 0
this.#minOrder = 3
this.#maxOrder = 0
return
this.#poolBuffer = Buffer.allocUnsafe(Number.isFinite(poolTotal) ? poolTotal : 0)
for (let n = 0; 2 ** n <= 256 * 1024; n++) {
this.#pools.push([])
}
}
// Round up to nearest power of 2
this.#maxOrder = Math.ceil(Math.log2(poolTotal))
this.#poolTotal = 1 << this.#maxOrder
// Minimum block size is 8 bytes (order 3)
this.#minOrder = 3
this.#poolBuffer = Buffer.allocUnsafe(this.#poolTotal)
// Calculate total bitmap size and offsets for each order
// Total pairs = 2^(maxOrder-minOrder) - 1, total words ≈ that / 32
let totalWords = 0
const offsets = []
for (let order = 0; order <= this.#maxOrder; order++) {
offsets.push(totalWords)
const numPairs = 1 << Math.max(0, this.#maxOrder - order - 1)
totalWords += Math.ceil(numPairs / 32)
}
// Allocate single contiguous buffer for all bitmaps
this.#bitmapBuffer = new ArrayBuffer(totalWords * 4)
// Create views into the buffer for each order
for (let order = 0; order <= this.#maxOrder; order++) {
this.#freeLists.push([])
const numPairs = 1 << Math.max(0, this.#maxOrder - order - 1)
const numWords = Math.ceil(numPairs / 32)
this.#bitmaps.push(new Uint32Array(this.#bitmapBuffer, offsets[order] * 4, numWords))
}
// Initially, the entire buffer is one free block at max order
this.#freeLists[this.#maxOrder].push(0)
isFromPool(slice ) {
return slice != null && slice.buffer === this.#poolBuffer
}

@@ -297,8 +252,2 @@

if (slice == null) {
slice = new Slice()
} else if (!(slice instanceof Slice)) {
throw new TypeError('slice must be a Slice instance')
}
if (slice.byteLength === byteLength) {

@@ -308,12 +257,16 @@ return slice

const dstOrder = byteLength === 0 ? 0 : this.#getOrder(byteLength)
// Ceil to nearest power of two.
const dstIdx = byteLength <= 8 ? 3 : 32 - Math.clz32(byteLength - 1)
if (this.isFromPool(slice)) {
// Derive order from maxByteLength
const srcOrder = 31 - Math.clz32(slice.maxByteLength)
const srcIdx = 32 - Math.clz32(slice.maxByteLength - 1)
if (slice.maxByteLength !== 1 << srcIdx) {
throw new Error(`Invalid pool state`)
}
this.#size -= slice.byteLength
this.#padding -= slice.maxByteLength - slice.byteLength
if (srcOrder === dstOrder) {
if (srcIdx === dstIdx) {
slice.byteLength = byteLength

@@ -325,5 +278,4 @@ this.#size += slice.byteLength

// Free the old block
this.#freeBlock(slice.byteOffset, srcOrder)
this.#poolCount--
this.#pools[srcIdx].push(slice.byteOffset)
this.#poolSize -= slice.maxByteLength
}

@@ -337,5 +289,27 @@

const offset = this.#allocBlock(dstOrder)
if (offset == null) {
// Fall back to regular allocation
const maxByteLength = 1 << dstIdx
if (this.#pools.length > 32 || maxByteLength < byteLength || (maxByteLength & 0x7) !== 0) {
throw new Error(`Invalid pool state`)
}
if (dstIdx < this.#pools.length && this.#pools[dstIdx]?.length) {
slice.buffer = this.#poolBuffer
slice.byteOffset = this.#pools[dstIdx].pop()
slice.byteLength = byteLength
slice.maxByteLength = maxByteLength
this.#poolSize += maxByteLength
} else if (
dstIdx < this.#pools.length &&
this.#poolOffset + maxByteLength <= this.#poolBuffer.byteLength
) {
slice.buffer = this.#poolBuffer
slice.byteOffset = this.#poolOffset
slice.byteLength = byteLength
slice.maxByteLength = maxByteLength
this.#poolOffset += maxByteLength
this.#poolCount += 1
this.#poolSize += maxByteLength
} else {
slice.buffer = Buffer.allocUnsafeSlow(byteLength)

@@ -345,13 +319,7 @@ slice.byteOffset = 0

slice.maxByteLength = byteLength
} else {
slice.buffer = this.#poolBuffer
slice.byteOffset = offset
slice.byteLength = byteLength
slice.maxByteLength = 1 << dstOrder
this.#poolCount++
this.#size += byteLength
this.#padding += slice.maxByteLength - slice.byteLength
}
this.#size += slice.byteLength
this.#padding += slice.maxByteLength - slice.byteLength
return slice

@@ -361,10 +329,2 @@ }

get stats() {
// Calculate free space from all free lists
let freeSpace = 0
for (let order = this.#minOrder; order <= this.#maxOrder; order++) {
freeSpace += this.#freeLists[order].length << order
}
const poolUsed = this.#poolTotal - freeSpace
return {

@@ -374,98 +334,8 @@ size: this.#size,

ratio: this.#size > 0 ? (this.#size + this.#padding) / this.#size : 1,
poolTotal: this.#poolTotal,
poolUsed,
poolSize: poolUsed,
poolTotal: this.#poolBuffer.byteLength,
poolUsed: this.#poolOffset,
poolSize: this.#poolSize,
poolCount: this.#poolCount,
poolList: this.#freeLists.map((list) => list.length),
}
}
isFromPool(slice ) {
return slice != null && slice.buffer === this.#poolBuffer
}
#toggleBit(offset , order ) {
if (order >= this.#maxOrder) {
return false
}
const pairIndex = offset >>> (order + 1)
const wordIndex = pairIndex >>> 5
const bitMask = 1 << (pairIndex & 31)
const bitmap = this.#bitmaps[order]
bitmap[wordIndex] ^= bitMask
return (bitmap[wordIndex] & bitMask) !== 0
}
#allocBlock(order ) {
// Try to allocate from pool
if (order > this.#maxOrder || this.#poolTotal === 0) {
return null
}
// Find the smallest order with a free block
let currentOrder = order
while (currentOrder <= this.#maxOrder && this.#freeLists[currentOrder].length === 0) {
currentOrder++
}
if (currentOrder > this.#maxOrder) {
return null
}
// Pop the free block
const offset = this.#freeLists[currentOrder].pop()
// Found block at exact order - just toggle and return
if (currentOrder === order) {
this.#toggleBit(offset, order)
return offset
}
// Split down to the requested order
while (currentOrder > order) {
currentOrder--
// Add buddy to free list
const buddyOffset = offset ^ (1 << currentOrder)
this.#freeLists[currentOrder].push(buddyOffset)
// Toggle bit - one buddy free, one allocated/kept
this.#toggleBit(offset, currentOrder)
}
return offset
}
#freeBlock(offset , order ) {
while (order < this.#maxOrder) {
// Toggle bit and check if we can coalesce
const isDifferent = this.#toggleBit(offset, order)
if (isDifferent) {
// Bit is now 1: buddy is allocated, can't coalesce
this.#freeLists[order].push(offset)
return
}
// Bit is now 0: both buddies are free, coalesce
// Remove buddy from free list
const buddyOffset = offset ^ (1 << order)
const idx = this.#freeLists[order].indexOf(buddyOffset)
if (idx !== -1) {
// Swap with last and pop for O(1) removal
const last = this.#freeLists[order].length - 1
this.#freeLists[order][idx] = this.#freeLists[order][last]
this.#freeLists[order].pop()
}
// Move up to parent level
offset = offset & ~(1 << order)
order++
}
// Reached max order
this.#freeLists[order].push(offset)
}
#getOrder(byteLength ) {
return byteLength <= 1 << this.#minOrder ? this.#minOrder : 32 - Math.clz32(byteLength - 1)
}
}
+2
-3
package.json
{
"name": "@nxtedition/slice",
"version": "1.0.1",
"version": "1.0.2",
"type": "module",

@@ -22,4 +22,3 @@ "main": "lib/index.js",

"typescript": "^5.9.3"
},
"gitHead": "2517ca631e010f17f7ba8be4e1b854ad18cbd746"
}
}