Skip to main content

Crate expanse_trie

Crate expanse_trie 

Source
Expand description

§Expanse — clean-room Judy arrays for modern hardware

Judy arrays (invented by Doug Baskins at Hewlett-Packard) are sparse, dynamic associative data structures built as 256-ary digital tries that partition keys by expanse (decoding keys byte by byte over fixed digit ranges) rather than by population like comparison-based trees — the defining term this project is named after. The original C implementation (Judy IV, ~2002) achieves its speed through adaptive node compression: linear, bitmap, and uncompressed branches; linear and bitmap leaves; and keys stored immediately inside pointers.

This crate is a clean-room reimplementation: no code from the LGPL C library has been consulted or ported. The design derives from published algorithm descriptions and modernizes the 2002 architecture for current hardware:

  • node geometries sized to 64-byte cache lines (the original assumed 128-byte lines);
  • hardware popcnt/tzcnt and SIMD byte scanning instead of SWAR bit hacks and unrolled scalar loops;
  • no upper-bit pointer stealing: the tag byte and the population/decode field live in word 1 of the 16-byte Edge, so word 0 keeps the raw untruncated 64-bit pointer (correct under 57-bit LA57 and 52-bit ARM64 LVA);
  • a modern allocation strategy instead of the custom 2001 chunk allocator;
  • optimistic concurrency control for optimistic reads.

The classic C Judy.h API (Judy1*, JudyL*, JudySL*) is provided as a drop-in binary-compatible layer by the sibling expanse-capi crate (libexpanse); this crate holds the core implementation and the native Rust API (ExpanseSet, ExpanseMap, ExpanseStrMap, ExpanseBytesMap, ExpanseOrderedBytesMap).

Re-exports§

pub use blobmap::BlobArena;
pub use blobmap::BlobView;
pub use blobmap::ExpanseBlobMap;
pub use cursor::MapCursor;
pub use cursor::MapRangeCursor;
pub use cursor::SetCursor;
pub use domain::DomainError;
pub use domain::DomainMismatch;
pub use domain::DomainOrdinal;
pub use domain::DomainSet;
pub use domain::ExpanseDomainDict;
pub use domain::ResolveIter;
pub use map::ExpanseMap;
pub use ordered_bytesmap::ExpanseOrderedBytesMap;
pub use set::ExpanseSet;
pub use slot::SlotTag;
pub use slot::ValueSlot;
pub use blobmap32::BlobMap32Error;
pub use blobmap32::BlobView32;
pub use blobmap32::ExpanseBlobMap32;
pub use cursor32::MapCursor32;
pub use cursor32::MapRangeCursor32;
pub use cursor32::SetCursor32;
pub use map32::ExpanseMap32;
pub use occ32::SeqVersion32;
pub use set32::ExpanseSet32;
pub use slot32::SlotTag32;
pub use slot32::ValueSlot32;
pub use sync32::SyncExpanseMap32;
pub use sync32::SyncExpanseSet32;
pub use types32::Edge32;
pub use types32::Key32;
pub use types32::Tag32;
pub use types32::Value32;

Modules§

alloc
Phase 5: the allocation subsystem.
bits
Phase 2: hardware-accelerated bit and byte-vector primitives.
blobmap
Chunked slab/arena allocator and high-level blob map.
blobmap32
32-Bit Polymorphic Blob Map (ExpanseBlobMap32).
bytesmap
ExpanseBytesMap: an unordered map from arbitrary byte strings to u64 values (compat: JudyHS).
codec
Zero-allocation lightweight in-register value compression codecs (#392).
cursor
Stateful ordered cursors with advance_to for skip-scans (issue #340).
cursor32
Stateful ordered cursors for the 32-bit twins (issue #340).
domain
Interned set domain: shared dictionary vending posting-list sets over a single ordinal space (issue #611).
get
Phase 4: the read-only lookup engine.
iter
High-performance stack-based in-order iterator for Expanse tries.
leaf
Phase 5: variable-length linear-leaf layout and search.
map
Phase 6b: ExpanseMap, the public map-flavor tree (compat: JudyL).
map32
32-Bit Ordered Associative Map / JudyL Array (ExpanseMap32).
mutate
Phase 6: the set-flavor mutation engine.
node
Phase 3: cache-line-native node layouts.
node32
32-Bit Digital Tree Node Geometries & Cache-Line Alignment.
occ
Phase 7: optimistic concurrency primitives — the seqlock version word readers validate against, and epoch-based reclamation (EBR) so a reader never dereferences a freed node.
occ32
32-bit Optimistic Concurrency Control (OCC) primitives.
occ_stats
Optional counting instrumentation for the OCC read/write protocol.
ordered_bytesmap
ExpanseOrderedBytesMap: an ordered digital trie map from arbitrary byte sequences (&[u8]) to u64 values (Refs #808, docs/ARCHITECTURE.md §3.7).
set
Phase 6: ExpanseSet, the public set-flavor tree (compat: Judy1).
set32
32-Bit Integer Set / Judy1 Array (ExpanseSet32).
short_bytesmap
A byte-string map that keeps keys of at most one machine word out of the hash path (#1681).
slot
Polymorphic 64-bit value slots and columnar predicate filter kernels.
slot32
Polymorphic 32-Bit Value Slot (ValueSlot32).
strmap
ExpanseStrMap: a sorted map from C-style byte strings to u64 values (compat: JudySL).
sync
Phase 7: concurrent wrappers — one writer, many optimistic readers.
sync32
Concurrent single-writer/many-reader wrappers for the 32-bit engine (SyncExpanseMap32, SyncExpanseSet32).
sync_cursor
Validated batch cursor on concurrent map readers (#1142).
sync_str_cursor
Validated batch cursor on the shared string map’s readers (#1143).
types
Phase 1 foundation: key/value word types, node geometry constants, the edge type-tag encoding, and digit extraction.
types32
32-bit machine types, constants, and compact 8-byte Edge32 descriptor.
validate
Defensive trie structure validation and statistics collection.