@orieg/expanse (expanse-node)

Native Node.js, Bun, and Deno bindings for Expanse: clean-room, pure-Rust Judy arrays and 256-ary digital tries with optimistic concurrency control (OCC).

Overview

@orieg/expanse provides drop-in, zero-dependency, ultra-fast sparse data structures for JavaScript and TypeScript runtimes:

• ExpanseSet: 64-bit unsigned integer set (compat: Judy1) with rank/select and range queries.
• ExpanseMap: 64-bit integer key/value map (compat: JudyL).
• ExpanseStrMap: Byte-lexicographically sorted string map (compat: JudySL) with prefix compression.
• ExpanseBytesMap: Unordered map over arbitrary binary keys (including \0 bytes) (compat: JudyHS).
• ExpanseBlobMap: Polymorphic blob storage with inline value packing (≤ 7 bytes stored inline with 0 heap allocations), chunked slab arenas, in-place compaction, and mmap image persistence.
• SyncExpanseMap / SyncExpanseSet: Thread-safe concurrent structures with optimistic concurrency control (OCC) and epoch-based memory reclamation.
• SyncExpanseStrMap / SyncExpanseBytesMap / SyncExpanseOrderedBytesMap / SyncExpanseBlobMap: The same concurrent form for string, byte-string, ordered byte-string and blob (byte payload plus 24-bit hot metadata) maps.

Installation

npm install @orieg/expanse
# or
bun add @orieg/expanse
# or
pnpm add @orieg/expanse

Quick Start

64-bit Integer Set (ExpanseSet)

import { ExpanseSet } from '@orieg/expanse';

const set = new ExpanseSet();
set.add(42n);
set.add(100n);
set.add(500n);

console.log(set.has(42n)); // true
console.log(set.size());   // 3n

// Rank / Select
console.log(set.rank(100n)); // 1n (1 element strictly < 100)
console.log(set.select(0n));  // 42n (0-th element)

// Navigation
console.log(set.next(42n));  // 100n
console.log(set.prev(500n)); // 100n

// Range queries
console.log(set.countRange(40n, 200n)); // 2n
console.log(set.range(40n, 200n));      // [42n, 100n]

64-bit Integer Map (ExpanseMap)

import { ExpanseMap } from '@orieg/expanse';

const map = new ExpanseMap();
map.set(100n, 9999n);
map.set(200n, 8888n);

console.log(map.get(100n)); // 9999n
console.log(map.first());   // { key: 100n, value: 9999n }

Prefix-Compressed String Map (ExpanseStrMap)

import { ExpanseStrMap } from '@orieg/expanse';

const strmap = new ExpanseStrMap();
strmap.set('apple', 1n);
strmap.set('banana', 2n);
strmap.set('cherry', 3n);

console.log(strmap.get('banana')); // 2n
console.log(strmap.first());        // { key: 'apple', value: 1n }
console.log(strmap.next('apple'));  // { key: 'banana', value: 2n }

Arbitrary Binary Map (ExpanseBytesMap)

import { ExpanseBytesMap } from '@orieg/expanse';

const bytesmap = new ExpanseBytesMap();
const binaryKey = Buffer.from([0x00, 0x01, 0x02, 0xff]);
bytesmap.set(binaryKey, 42n);

console.log(bytesmap.get(binaryKey)); // 42n

High-Performance Blob Map (ExpanseBlobMap)

import { ExpanseBlobMap } from '@orieg/expanse';

const blobmap = new ExpanseBlobMap();

// Short payloads (<= 7 bytes) written with hot metadata 0 are stored inline in the
// value slot (0 heap allocations); with metadata they are arena records that keep it
blobmap.set(1n, Buffer.from('inline'), 0);

// Larger payloads are allocated in contiguous slab arenas
blobmap.set(2n, Buffer.from('large payload allocated in slab arena'), 20);

// Lookup with metadata
const res = blobmap.getWithMeta(1n);
console.log(res);
// { payload: <Buffer 69 6e 6c 69 6e 65>, hotMeta: 10, isInline: true }

// Prune based on hot metadata
blobmap.prune((key, hotMeta) => hotMeta > 15);

// Relocatable binary image persistence
blobmap.saveImage('./data.expanse');
const reloaded = ExpanseBlobMap.openImage('./data.expanse');

Concurrent Structures (SyncExpanseMap / SyncExpanseSet)

import { SyncExpanseMap, SyncExpanseSet } from '@orieg/expanse';

const syncMap = new SyncExpanseMap();
syncMap.set(1000n, 42n);
console.log(syncMap.get(1000n)); // 42n
console.log(syncMap.next(1000n, true)); // { key: 1000n, value: 42n }

SyncExpanseMap's get, has, size, first, last, next and prev run on the optimistic path: they take no writer lock unless a read exhausts its bounded retries, in which case it falls back to the writer-excluding path. The protocol is blocking optimistic lock coupling, not lock-free. rank, select, countRange, keys, values and entries, and the ordered reads of SyncExpanseSet, run with writers excluded.

SyncExpanseMap also has atomic read-modify-write (#1194). compareExchange(key, expected, newValue) stores newValue only if the key's current value is expected, with null meaning absent on both sides ((null, v) inserts if absent, (e, null) removes if equal), and returns { stored, observed }: observed is the value the compare saw (null if absent), so a failed call hands back the value to retry against. getOrInsert(key, value) stores value only if the key is absent and returns the existing value, or null when it stored (the convention of set). update(key, fn) stores fn(current) (null removes the key) and returns the replaced value; it is a loop over compareExchange that calls fn again with the observed value when the exchange loses, so fn may run more than once per call and must be free of side effects, and an exception from fn propagates with the key unchanged. The addon's objects belong to one JavaScript thread, so an exchange loses only to a write made between the read and the exchange (for example from inside fn).

syncMap.update(7n, (cur) => (cur ?? 0n) + 1n); // atomic increment
syncMap.compareExchange(7n, 1n, null); // { stored: true, observed: 1n }: remove if equal to 1n

Concurrent string, bytes, ordered-bytes and blob maps

import {
  SyncExpanseStrMap,
  SyncExpanseBytesMap,
  SyncExpanseOrderedBytesMap,
  SyncExpanseBlobMap,
} from '@orieg/expanse';

const names = new SyncExpanseStrMap(); // NUL-free string keys, u64 values
names.set('alice', 1n);
names.update('alice', (cur) => (cur ?? 0n) + 1n); // atomic increment
names.next('alice'); // { key: ..., value: ... } | null, byte-lexicographical order

const raw = new SyncExpanseBytesMap(); // Buffer / Uint8Array / string keys, any bytes
raw.compareExchange(Buffer.from([0, 1]), null, 5n); // { stored: true, observed: null }

const ordered = new SyncExpanseOrderedBytesMap();
ordered.first(); // { key: Buffer, value: bigint } | null

const blobs = new SyncExpanseBlobMap();
blobs.set(1n, Buffer.alloc(64, 1), 5 /* hotMeta */);
blobs.get(1n); // Buffer
blobs.compareExchangeMeta(1n, 5, 6); // { stored: true, observed: 5 }
blobs.getOrInsert(2n, 'payload longer than seven bytes'); // null: stored

All four take the same compareExchange(key, expected, newValue) and getOrInsert forms as SyncExpanseMap (null is absent; { stored, observed }), and update(key, fn) on the three word-valued maps. The string map rejects a key with an embedded NUL. get, has, the point writes and the string map's first / last / next / prev run on the optimistic path; the ordered-bytes map's first / last / next / prev run with writers excluded, so each call blocks concurrent writers. Blob reads return owned Buffers; getWithMeta adds isInline, and a payload of any length keeps the hot metadata it was written with (#1548). The blob compareExchange, compareExchangeMeta and getOrInsert throw when the map refuses the value (metadata over 24 bits, a refusing arena), where the C forms return a status. Like SyncExpanseMap, the objects belong to one JavaScript thread, so an exchange loses only to a write made in between (for example inside fn).

License

Dual-licensed under MIT and Apache-2.0.