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/tzcntand 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 tou64values (compat: JudyHS).- codec
- Zero-allocation lightweight in-register value compression codecs (#392).
- cursor
- Stateful ordered cursors with
advance_tofor 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]) tou64values (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 tou64values (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
Edge32descriptor. - validate
- Defensive trie structure validation and statistics collection.