Skip to main content

expanse_trie/
lib.rs

1//! # Expanse — clean-room Judy arrays for modern hardware
2//!
3//! Judy arrays (invented by Doug Baskins at Hewlett-Packard) are sparse,
4//! dynamic associative data structures built as 256-ary digital tries that
5//! partition keys by **expanse** (decoding keys byte by byte over fixed
6//! digit ranges) rather than by population like comparison-based trees —
7//! the defining term this project is named after. The original C
8//! implementation (Judy IV, ~2002) achieves its speed through adaptive node
9//! compression: linear, bitmap, and uncompressed branches; linear and
10//! bitmap leaves; and keys stored immediately inside pointers.
11//!
12//! This crate is a **clean-room reimplementation**: no code from the LGPL
13//! C library has been consulted or ported. The design derives from published
14//! algorithm descriptions and modernizes the 2002 architecture for current
15//! hardware:
16//!
17//! - node geometries sized to **64-byte cache lines** (the original assumed
18//!   128-byte lines);
19//! - hardware `popcnt`/`tzcnt` and SIMD byte scanning instead of SWAR bit
20//!   hacks and unrolled scalar loops;
21//! - no upper-bit pointer stealing: the tag byte and the
22//!   population/decode field live in word 1 of the
23//!   16-byte `Edge`, so word 0 keeps the raw untruncated 64-bit pointer
24//!   (correct under 57-bit LA57 and 52-bit ARM64 LVA);
25//! - a modern allocation strategy instead of the custom 2001 chunk allocator;
26//! - optimistic concurrency control for optimistic reads.
27//!
28//! The classic C `Judy.h` API (`Judy1*`, `JudyL*`, `JudySL*`) is provided as
29//! a drop-in binary-compatible layer by the sibling `expanse-capi` crate
30//! (`libexpanse`); this crate holds the core implementation and the native
31//! Rust API (`ExpanseSet`, `ExpanseMap`, `ExpanseStrMap`, `ExpanseBytesMap`, `ExpanseOrderedBytesMap`).
32#![cfg_attr(not(feature = "std"), no_std)]
33
34extern crate alloc as core_alloc;
35
36#[cfg(not(any(target_pointer_width = "64", target_pointer_width = "32")))]
37compile_error!("expanse supports 64-bit and 32-bit targets");
38
39#[cfg(feature = "ablation-striped-freelist")]
40compile_error!(
41    "ablation-striped-freelist is deprecated; per-stripe freelists are now the production default. \
42     To measure unstriped freelists, use ablation-unstriped-freelist."
43);
44
45#[cfg(feature = "ablation-sharded-alloc")]
46compile_error!(
47    "ablation-sharded-alloc is retired; sharded allocator accounting counters are now the \
48     production default. To measure the shared counters they replaced, use \
49     ablation-unsharded-alloc."
50);
51
52#[cfg(feature = "lock-padded")]
53compile_error!(
54    "lock-padded is retired; the writer mutex, writer gate, tree population counter and version \
55     word are on their own cache lines by default. To measure the packed layout, use \
56     ablation-unpadded-lock."
57);
58
59#[cfg(feature = "ablation-striped-epoch")]
60compile_error!(
61    "ablation-striped-epoch is retired; striped epoch bins are the production default. It was \
62     previously a no-op alias, which compared the default with itself. To measure multi-writer \
63     scaling on the default build, use the writer_scaling suite."
64);
65
66#[cfg(feature = "ablation-unlocked-plain-acct")]
67compile_error!(
68    "ablation-unlocked-plain-acct is retired (Refs #1679): a plain tree's accounting updates are \
69     unlocked by default. To measure the locked updates they replaced, use \
70     ablation-locked-plain-acct."
71);
72
73#[cfg(feature = "packed-suffix")]
74compile_error!(
75    "packed-suffix has been promoted to the default (Refs #1586, concurrency METHODOLOGY §47): \
76     string suffix leaves are NodeAlloc blocks in every build. Use ablation-unpacked-suffix to \
77     restore one global allocation per suffix."
78);
79
80#[cfg(feature = "ablation-blob-writer-arenas")]
81compile_error!(
82    "ablation-blob-writer-arenas has been promoted to the default architecture (Refs #929); \
83     use ablation-blob-shared-arena to restore the shared-arena path."
84);
85
86#[cfg(all(
87    feature = "ablation-blob-shared-arena",
88    feature = "ablation-blob-serial-writers"
89))]
90compile_error!(
91    "ablation-blob-shared-arena changes the blob wrapper's optimistic insert path, which \
92     ablation-blob-serial-writers removes; the combination would measure the serial path alone. \
93     Enable one of the two."
94);
95
96#[cfg(target_pointer_width = "64")]
97mod algebra;
98#[cfg(target_pointer_width = "64")]
99mod algebra_build;
100#[cfg(target_pointer_width = "64")]
101pub mod alloc;
102#[cfg(target_pointer_width = "64")]
103pub mod bits;
104#[cfg(target_pointer_width = "64")]
105pub mod blobmap;
106#[cfg(target_pointer_width = "64")]
107pub mod bytesmap;
108#[cfg(all(target_pointer_width = "64", feature = "layout-census"))]
109pub mod census;
110#[cfg(target_pointer_width = "64")]
111pub mod codec;
112mod common;
113#[cfg(target_pointer_width = "64")]
114pub mod cursor;
115#[cfg(target_pointer_width = "64")]
116pub mod domain;
117#[cfg(target_pointer_width = "64")]
118pub mod get;
119#[cfg(target_pointer_width = "64")]
120pub mod iter;
121#[cfg(target_pointer_width = "64")]
122pub mod leaf;
123#[cfg(target_pointer_width = "64")]
124pub mod map;
125#[cfg(target_pointer_width = "64")]
126pub mod mutate;
127#[cfg(target_pointer_width = "64")]
128mod mutate_map;
129#[cfg(target_pointer_width = "64")]
130mod nav;
131#[cfg(target_pointer_width = "64")]
132pub mod node;
133#[cfg(target_pointer_width = "64")]
134pub mod occ;
135#[cfg(target_pointer_width = "64")]
136pub mod occ_stats;
137// `ordered_bytesmap` wraps `strmap::ExpanseStrMap`, which is restricted to
138// 64-bit targets (`pub mod strmap;` below). It will expand to 32-bit targets if/when
139// `strmap32` is introduced.
140#[cfg(target_pointer_width = "64")]
141pub mod ordered_bytesmap;
142#[cfg(target_pointer_width = "64")]
143pub mod set;
144#[cfg(target_pointer_width = "64")]
145pub mod short_bytesmap;
146#[cfg(target_pointer_width = "64")]
147pub mod slot;
148#[cfg(target_pointer_width = "64")]
149pub mod strmap;
150#[cfg(all(target_pointer_width = "64", feature = "std"))]
151pub mod sync;
152#[cfg(all(target_pointer_width = "64", feature = "std"))]
153pub mod sync_cursor;
154#[cfg(all(target_pointer_width = "64", feature = "std"))]
155mod sync_nav;
156#[cfg(all(target_pointer_width = "64", feature = "std"))]
157pub mod sync_str_cursor;
158#[cfg(target_pointer_width = "64")]
159pub mod types;
160#[cfg(target_pointer_width = "64")]
161pub mod validate;
162
163pub mod blobmap32;
164pub mod cursor32;
165pub mod map32;
166pub mod node32;
167pub mod occ32;
168pub mod set32;
169pub mod slot32;
170pub mod sync32;
171mod trie32;
172pub mod types32;
173
174#[cfg(target_pointer_width = "64")]
175pub use blobmap::{BlobArena, BlobView, ExpanseBlobMap};
176#[cfg(target_pointer_width = "64")]
177pub use cursor::{MapCursor, MapRangeCursor, SetCursor};
178#[cfg(target_pointer_width = "64")]
179pub use domain::{
180    DomainError, DomainMismatch, DomainOrdinal, DomainSet, ExpanseDomainDict, ResolveIter,
181};
182#[cfg(target_pointer_width = "64")]
183pub use map::ExpanseMap;
184#[cfg(target_pointer_width = "64")]
185pub use ordered_bytesmap::ExpanseOrderedBytesMap;
186#[cfg(target_pointer_width = "64")]
187pub use set::ExpanseSet;
188#[cfg(target_pointer_width = "64")]
189pub use slot::{SlotTag, ValueSlot};
190
191#[cfg(target_pointer_width = "32")]
192pub use blobmap32::ExpanseBlobMap32 as ExpanseBlobMap;
193#[cfg(target_pointer_width = "32")]
194pub use cursor32::{
195    MapCursor32 as MapCursor, MapRangeCursor32 as MapRangeCursor, SetCursor32 as SetCursor,
196};
197#[cfg(target_pointer_width = "32")]
198pub use map32::ExpanseMap32 as ExpanseMap;
199#[cfg(target_pointer_width = "32")]
200pub use set32::ExpanseSet32 as ExpanseSet;
201#[cfg(target_pointer_width = "32")]
202pub use slot32::ValueSlot32 as ValueSlot;
203
204pub use blobmap32::{BlobMap32Error, BlobView32, ExpanseBlobMap32};
205pub use cursor32::{MapCursor32, MapRangeCursor32, SetCursor32};
206pub use map32::ExpanseMap32;
207pub use occ32::SeqVersion32;
208pub use set32::ExpanseSet32;
209pub use slot32::{SlotTag32, ValueSlot32};
210pub use sync32::{SyncExpanseMap32, SyncExpanseSet32};
211pub use types32::{Edge32, Key32, Tag32, Value32};