Skip to main content

expanse/
lib.rs

1//! # expanse-capi — `libexpanse`, the drop-in C ABI for libjudy
2//!
3//! Exports the classic `Judy.h` surface (`Judy1*` backed by `ExpanseSet`,
4//! `JudyL*` backed by `ExpanseMap`) with matching symbol names, calling
5//! convention, and documented semantics, so existing consumers of the C
6//! library link-swap or `LD_PRELOAD` `libexpanse` in place of `libJudy`
7//! without source changes. The contract — target surface, guarantees,
8//! non-goals, doc-gap resolutions, acceptance gates — is `docs/COMPAT.md`;
9//! the shipped header is `include/Judy.h`.
10//!
11//! Array-handle convention: a `Pvoid_t` array word is null when the array
12//! is empty and otherwise holds a pointer to the boxed tree. Removing the
13//! last key returns the word to null, matching the classic representation
14//! of an empty array.
15//!
16//! `JudySL*` is backed by `ExpanseStrMap` (a meta-trie of word maps);
17//! `JudyHS*` lands with `ExpanseShortBytesMap`.
18
19// The entry points below are C ABI exports whose safety contract is the
20// documented Judy C API itself (docs/COMPAT.md); per-call obligations are
21// stated in SAFETY comments inside each body rather than per-fn sections.
22#![allow(clippy::missing_safety_doc)]
23#![cfg_attr(not(feature = "std"), no_std)]
24
25#[cfg(not(feature = "std"))]
26extern crate alloc as core_alloc;
27
28// Bare-metal support lives behind `not(std)`: the global allocator and the
29// opt-in panic handler a staticlib link requires (#558).
30#[cfg(not(feature = "std"))]
31mod alloc_bridge;
32
33use core::ffi::c_int;
34#[cfg(target_pointer_width = "64")]
35use core::ffi::c_void;
36#[cfg(target_pointer_width = "64")]
37pub mod blobmap;
38#[cfg(target_pointer_width = "64")]
39mod compat;
40#[cfg(target_pointer_width = "64")]
41pub use compat::*;
42pub mod modern;
43// The 32-bit-only concurrent surface: `sync32` needs no `std`, so this is
44// present in every 32-bit build (see the `!EXPANSE_WIDE_SURFACE` block of
45// `include/expanse.h`), and in `cfg(test)` so unit tests run on 64-bit hosts.
46#[cfg(any(target_pointer_width = "32", test))]
47pub mod modern_sync32;
48
49#[cfg(target_pointer_width = "64")]
50use expanse_trie::ExpanseMap;
51#[cfg(target_pointer_width = "64")]
52use expanse_trie::ExpanseSet;
53#[cfg(target_pointer_width = "64")]
54use expanse_trie::strmap::ExpanseStrMap;
55
56/// `Word_t`: pointer-width unsigned integer (see COMPAT.md doc-gap D1).
57pub type Word = usize;
58
59/// The classic `JError_t` error record (see COMPAT.md doc-gap D2).
60#[repr(C)]
61pub struct JError {
62    /// A `JU_ERRNO_*` code.
63    pub je_errno: c_int,
64    /// Internal error location id (always 0 here).
65    pub je_err_id: c_int,
66    /// Reserved words, kept for layout compatibility.
67    pub je_reserved: [Word; 4],
68}
69
70/// No error.
71pub const JU_ERRNO_NONE: c_int = 0;
72/// Out of memory (see COMPAT.md doc-gap D3: allocation failure aborts).
73pub const JU_ERRNO_NOMEM: c_int = 2;
74/// A null `PPArray` was passed where one is required.
75pub const JU_ERRNO_NULLPPARRAY: c_int = 3;
76/// A null `PIndex` was passed where one is required.
77pub const JU_ERRNO_NULLPINDEX: c_int = 5;
78
79/// C-compatible counts of nodes by their specific form.
80#[repr(C)]
81pub struct CNodeCounts {
82    /// NULL edges (empty slots).
83    pub null: u64,
84    /// Immed edges (key bytes stored inside the edge pointer).
85    pub immed: u64,
86    /// Packed linear leaf nodes.
87    pub leaf_linear: u64,
88    /// Bitmap leaf nodes.
89    pub leaf_bitmap: u64,
90    /// Linear branch nodes (up to 3 children).
91    pub branch_l3: u64,
92    /// Linear branch nodes (up to 7 children).
93    pub branch_l7: u64,
94    /// Bitmap branch nodes.
95    pub branch_b: u64,
96    /// Uncompressed branch nodes.
97    pub branch_u: u64,
98    /// Full expanse edges (set-flavor only).
99    pub full_expanse: u64,
100}
101
102/// C-compatible diagnostic statistics for an Expanse trie.
103#[repr(C)]
104pub struct CExpanseStats {
105    /// Counts of nodes by their specific form.
106    pub node_counts: CNodeCounts,
107    /// Histogram of node depths (0 to 8).
108    pub depth_histogram: [u64; 9],
109    /// Histogram of leaf populations (0 to 256).
110    pub leaf_pop_histogram: [u64; 257],
111}
112
113/// Defensively validates a Judy1 or JudyL array structure.
114///
115/// `parray` is the pointer to the array (which is `*const c_void`).
116/// `is_map` should be non-zero for JudyL arrays, and zero for Judy1 arrays.
117///
118/// Returns 1 if the array is valid (or empty/null), 0 if any structural corruption is detected.
119#[cfg(target_pointer_width = "64")]
120#[unsafe(no_mangle)]
121pub unsafe extern "C" fn expanse_validate(parray: *const c_void, is_map: c_int) -> c_int {
122    if parray.is_null() {
123        return 1;
124    }
125    if is_map != 0 {
126        // SAFETY: pointer is a valid ExpanseMap.
127        let map = unsafe { &*parray.cast::<ExpanseMap>() };
128        c_int::from(map.validate_defensive().is_ok())
129    } else {
130        // SAFETY: pointer is a valid ExpanseSet.
131        let set = unsafe { &*parray.cast::<ExpanseSet>() };
132        c_int::from(set.validate_defensive().is_ok())
133    }
134}
135
136/// Gathers structural statistics of the trie.
137///
138/// Returns 1 on success (with stats written to `out`), 0 on null pointer arguments.
139#[cfg(target_pointer_width = "64")]
140#[unsafe(no_mangle)]
141pub unsafe extern "C" fn expanse_stats(
142    parray: *const c_void,
143    is_map: c_int,
144    out: *mut CExpanseStats,
145) -> c_int {
146    if parray.is_null() || out.is_null() {
147        return 0;
148    }
149    let stats = if is_map != 0 {
150        // SAFETY: pointer is a valid ExpanseMap.
151        let map = unsafe { &*parray.cast::<ExpanseMap>() };
152        map.stats()
153    } else {
154        // SAFETY: pointer is a valid ExpanseSet.
155        let set = unsafe { &*parray.cast::<ExpanseSet>() };
156        set.stats()
157    };
158
159    // SAFETY: out checked non-null.
160    unsafe {
161        (*out).node_counts.null = stats.node_counts.null as u64;
162        (*out).node_counts.immed = stats.node_counts.immed as u64;
163        (*out).node_counts.leaf_linear = stats.node_counts.leaf_linear as u64;
164        (*out).node_counts.leaf_bitmap = stats.node_counts.leaf_bitmap as u64;
165        (*out).node_counts.branch_l3 = stats.node_counts.branch_l3 as u64;
166        (*out).node_counts.branch_l7 = stats.node_counts.branch_l7 as u64;
167        (*out).node_counts.branch_b = stats.node_counts.branch_b as u64;
168        (*out).node_counts.branch_u = stats.node_counts.branch_u as u64;
169        (*out).node_counts.full_expanse = stats.node_counts.full_expanse as u64;
170
171        // Index form kept so codegen is unchanged; reviewed in #1724.
172        #[allow(clippy::needless_range_loop)]
173        for i in 0..9 {
174            (*out).depth_histogram[i] = stats.depth_histogram[i] as u64;
175        }
176        // Index form kept so codegen is unchanged; reviewed in #1724.
177        #[allow(clippy::needless_range_loop)]
178        for i in 0..257 {
179            (*out).leaf_pop_histogram[i] = stats.leaf_pop_histogram[i] as u64;
180        }
181    }
182    1
183}
184
185#[cfg(test)]
186mod tests {
187    use super::*;
188    use core::ptr::null_mut;
189
190    fn arr() -> *mut c_void {
191        null_mut()
192    }
193
194    #[test]
195    fn judyhs_smoke() {
196        // SAFETY: valid pointers throughout; handles managed per contract.
197        unsafe {
198            let mut a = arr();
199            let key = b"hello\0world";
200            let kp = key.as_ptr().cast::<c_void>();
201            let slot = JudyHSIns(&raw mut a, kp, key.len(), null_mut()).cast::<Word>();
202            assert_eq!(*slot, 0);
203            *slot = 777;
204            // Same bytes, different buffer: hash + byte-compare match.
205            let copy = key.to_vec();
206            let got = JudyHSGet(a, copy.as_ptr().cast(), copy.len()).cast::<Word>();
207            assert_eq!(*got, 777);
208            // A prefix is a different key.
209            assert!(JudyHSGet(a, kp, 5).is_null());
210            // Zero-length key is a valid key (null index allowed at 0).
211            let empty = JudyHSIns(&raw mut a, null_mut(), 0, null_mut()).cast::<Word>();
212            *empty = 1;
213            assert_eq!(*JudyHSGet(a, null_mut(), 0).cast::<Word>(), 1);
214            assert_eq!(JudyHSDel(&raw mut a, kp, key.len(), null_mut()), 1);
215            assert_eq!(JudyHSDel(&raw mut a, kp, key.len(), null_mut()), 0);
216            assert!(JudyHSFreeArray(&raw mut a, null_mut()) > 0);
217            assert!(a.is_null());
218        }
219    }
220
221    #[test]
222    fn judy1_smoke() {
223        // SAFETY: valid pointers throughout; handles managed per contract.
224        unsafe {
225            let mut a = arr();
226            assert_eq!(Judy1Set(&raw mut a, 42, null_mut()), 1);
227            assert_eq!(Judy1Set(&raw mut a, 42, null_mut()), 0);
228            assert_eq!(Judy1Set(&raw mut a, 7, null_mut()), 1);
229            assert_eq!(Judy1Set(&raw mut a, usize::MAX, null_mut()), 1);
230            assert_eq!(Judy1Test(a, 42, null_mut()), 1);
231            assert_eq!(Judy1Test(a, 43, null_mut()), 0);
232            assert_eq!(Judy1Count(a, 0, usize::MAX, null_mut()), 3);
233            assert_eq!(Judy1Count(a, 8, 42, null_mut()), 1);
234
235            let mut idx: Word = 0;
236            assert_eq!(Judy1First(a, &raw mut idx, null_mut()), 1);
237            assert_eq!(idx, 7);
238            assert_eq!(Judy1Next(a, &raw mut idx, null_mut()), 1);
239            assert_eq!(idx, 42);
240            idx = usize::MAX;
241            assert_eq!(Judy1Last(a, &raw mut idx, null_mut()), 1);
242            assert_eq!(idx, usize::MAX);
243            assert_eq!(Judy1Prev(a, &raw mut idx, null_mut()), 1);
244            assert_eq!(idx, 42);
245
246            let mut nth: Word = 0;
247            assert_eq!(Judy1ByCount(a, 2, &raw mut nth, null_mut()), 1);
248            assert_eq!(nth, 42);
249            assert_eq!(Judy1ByCount(a, 4, &raw mut nth, null_mut()), 0);
250
251            idx = 7;
252            assert_eq!(Judy1FirstEmpty(a, &raw mut idx, null_mut()), 1);
253            assert_eq!(idx, 8);
254            idx = usize::MAX;
255            assert_eq!(Judy1LastEmpty(a, &raw mut idx, null_mut()), 1);
256            assert_eq!(idx, usize::MAX - 1);
257
258            assert_eq!(Judy1Unset(&raw mut a, 43, null_mut()), 0);
259            assert_eq!(Judy1Unset(&raw mut a, 42, null_mut()), 1);
260            assert!(Judy1MemUsed(a) > 0);
261            let freed = Judy1FreeArray(&raw mut a, null_mut());
262            assert!(freed > 0);
263            assert!(a.is_null());
264
265            // Emptying by Unset also nulls the handle.
266            assert_eq!(Judy1Set(&raw mut a, 5, null_mut()), 1);
267            assert_eq!(Judy1Unset(&raw mut a, 5, null_mut()), 1);
268            assert!(a.is_null());
269        }
270    }
271
272    #[test]
273    fn judyl_smoke() {
274        // SAFETY: valid pointers throughout; slots written before any
275        // further structural mutation, per the JudyL contract.
276        unsafe {
277            let mut a = arr();
278            let slot = JudyLIns(&raw mut a, 100, null_mut()).cast::<Word>();
279            assert!(!slot.is_null() && slot != PJERR.cast());
280            assert_eq!(*slot, 0, "new slots are zero-initialized");
281            *slot = 12345;
282
283            // Re-insert keeps the existing value.
284            let slot2 = JudyLIns(&raw mut a, 100, null_mut()).cast::<Word>();
285            assert_eq!(*slot2, 12345);
286
287            let got = JudyLGet(a, 100, null_mut()).cast::<Word>();
288            assert_eq!(*got, 12345);
289            assert!(JudyLGet(a, 101, null_mut()).is_null());
290
291            *JudyLIns(&raw mut a, 5, null_mut()).cast::<Word>() = 55;
292            *JudyLIns(&raw mut a, usize::MAX, null_mut()).cast::<Word>() = 99;
293
294            let mut idx: Word = 0;
295            let first = JudyLFirst(a, &raw mut idx, null_mut()).cast::<Word>();
296            assert_eq!((idx, *first), (5, 55));
297            let next = JudyLNext(a, &raw mut idx, null_mut()).cast::<Word>();
298            assert_eq!((idx, *next), (100, 12345));
299
300            assert_eq!(JudyLCount(a, 0, usize::MAX, null_mut()), 3);
301            let mut nth: Word = 0;
302            let bc = JudyLByCount(a, 3, &raw mut nth, null_mut()).cast::<Word>();
303            assert_eq!((nth, *bc), (usize::MAX, 99));
304
305            idx = 5;
306            assert_eq!(JudyLFirstEmpty(a, &raw mut idx, null_mut()), 1);
307            assert_eq!(idx, 6);
308
309            assert_eq!(JudyLDel(&raw mut a, 100, null_mut()), 1);
310            assert_eq!(JudyLDel(&raw mut a, 100, null_mut()), 0);
311            let freed = JudyLFreeArray(&raw mut a, null_mut());
312            assert!(freed > 0);
313            assert!(a.is_null());
314        }
315    }
316
317    #[test]
318    fn judysl_smoke() {
319        // SAFETY: valid pointers; slots written before further mutation.
320        unsafe {
321            let mut a = arr();
322            let s1 = JudySLIns(&raw mut a, c"hello".as_ptr().cast(), null_mut()).cast::<Word>();
323            *s1 = 11;
324            *JudySLIns(&raw mut a, c"help".as_ptr().cast(), null_mut()).cast::<Word>() = 22;
325            *JudySLIns(
326                &raw mut a,
327                c"a-much-longer-key-crossing-chunks".as_ptr().cast(),
328                null_mut(),
329            )
330            .cast::<Word>() = 33;
331            *JudySLIns(&raw mut a, c"".as_ptr().cast(), null_mut()).cast::<Word>() = 44;
332
333            assert_eq!(
334                *JudySLGet(a, c"hello".as_ptr().cast(), null_mut()).cast::<Word>(),
335                11
336            );
337            assert!(JudySLGet(a, c"hell".as_ptr().cast(), null_mut()).is_null());
338            // Re-insert keeps the value.
339            assert_eq!(
340                *JudySLIns(&raw mut a, c"hello".as_ptr().cast(), null_mut()).cast::<Word>(),
341                11
342            );
343
344            // Ordered sweep with the documented buffer contract.
345            let mut buf = [0u8; 64];
346            let mut got: Vec<(Vec<u8>, Word)> = Vec::new();
347            buf[0] = 0;
348            let mut slot = JudySLFirst(a, buf.as_mut_ptr(), null_mut());
349            while !slot.is_null() {
350                let len = buf.iter().position(|&b| b == 0).unwrap();
351                got.push((buf[..len].to_vec(), *slot.cast::<Word>()));
352                slot = JudySLNext(a, buf.as_mut_ptr(), null_mut());
353            }
354            let expected: Vec<(Vec<u8>, Word)> = vec![
355                (b"".to_vec(), 44),
356                (b"a-much-longer-key-crossing-chunks".to_vec(), 33),
357                (b"hello".to_vec(), 11),
358                (b"help".to_vec(), 22),
359            ];
360            assert_eq!(got, expected, "byte-lexicographic sweep");
361
362            // Backward from the top.
363            buf[..2].copy_from_slice(b"z\0");
364            let slot = JudySLLast(a, buf.as_mut_ptr(), null_mut());
365            assert!(!slot.is_null());
366            let len = buf.iter().position(|&b| b == 0).unwrap();
367            assert_eq!(&buf[..len], b"help");
368
369            assert_eq!(
370                JudySLDel(&raw mut a, c"hello".as_ptr().cast(), null_mut()),
371                1
372            );
373            assert_eq!(
374                JudySLDel(&raw mut a, c"hello".as_ptr().cast(), null_mut()),
375                0
376            );
377            let freed = JudySLFreeArray(&raw mut a, null_mut());
378            assert!(freed > 0);
379            assert!(a.is_null());
380        }
381    }
382
383    #[test]
384    fn null_argument_errors() {
385        // SAFETY: exercising the documented error paths.
386        unsafe {
387            let mut err = JError {
388                je_errno: JU_ERRNO_NONE,
389                je_err_id: 0,
390                je_reserved: [0; 4],
391            };
392            assert_eq!(Judy1Set(null_mut(), 1, &raw mut err), JERR_INT);
393            assert_eq!(err.je_errno, JU_ERRNO_NULLPPARRAY);
394            assert_eq!(JudyLIns(null_mut(), 1, &raw mut err), PJERR);
395            let a = arr();
396            assert_eq!(Judy1First(a, null_mut(), &raw mut err), JERR_INT);
397            assert_eq!(err.je_errno, JU_ERRNO_NULLPINDEX);
398        }
399    }
400}
401
402/// Differential oracle against a stock libjudy, loaded with `dlopen` so
403/// our exported `Judy*` symbols never collide with the reference library's
404/// at link time (COMPAT.md gate G1). Enabled by the `oracle` feature; the
405/// CI job installs `libjudy-dev` (locally: Homebrew `judy` on macOS).
406#[cfg(all(
407    test,
408    feature = "oracle",
409    any(target_os = "linux", target_os = "macos")
410))]
411mod oracle {
412    use super::*;
413    use core::ptr::null_mut;
414
415    unsafe extern "C" {
416        fn dlopen(filename: *const u8, flags: c_int) -> *mut c_void;
417        fn dlsym(handle: *mut c_void, symbol: *const u8) -> *mut c_void;
418    }
419    const RTLD_NOW: c_int = 2;
420
421    type F2i = unsafe extern "C" fn(*mut *mut c_void, Word, *mut c_void) -> c_int;
422    type F2t = unsafe extern "C" fn(*const c_void, Word, *mut c_void) -> c_int;
423    type FCount = unsafe extern "C" fn(*const c_void, Word, Word, *mut c_void) -> Word;
424    type FNav = unsafe extern "C" fn(*const c_void, *mut Word, *mut c_void) -> c_int;
425    type FByC = unsafe extern "C" fn(*const c_void, Word, *mut Word, *mut c_void) -> c_int;
426    type FFree = unsafe extern "C" fn(*mut *mut c_void, *mut c_void) -> Word;
427    type FpIns = unsafe extern "C" fn(*mut *mut c_void, Word, *mut c_void) -> *mut c_void;
428    type FpGet = unsafe extern "C" fn(*const c_void, Word, *mut c_void) -> *mut c_void;
429    type FpNav = unsafe extern "C" fn(*const c_void, *mut Word, *mut c_void) -> *mut c_void;
430    type FpByC = unsafe extern "C" fn(*const c_void, Word, *mut Word, *mut c_void) -> *mut c_void;
431
432    struct Lib(*mut c_void);
433    impl Lib {
434        fn open() -> Self {
435            let names: [&core::ffi::CStr; 4] = [
436                c"libJudy.so.1",
437                c"libJudy.so",
438                c"/opt/homebrew/opt/judy/lib/libJudy.dylib",
439                c"libJudy.dylib",
440            ];
441            for name in names.map(core::ffi::CStr::to_bytes_with_nul) {
442                // SAFETY: valid NUL-terminated name.
443                let h = unsafe { dlopen(name.as_ptr(), RTLD_NOW) };
444                if !h.is_null() {
445                    return Self(h);
446                }
447            }
448            panic!("stock libjudy not found — install libjudy-dev");
449        }
450        fn sym<T: Copy>(&self, name: &core::ffi::CStr) -> T {
451            // SAFETY: valid handle + NUL-terminated name; the caller names
452            // the correct fn-pointer type for the symbol.
453            let p = unsafe { dlsym(self.0, name.to_bytes_with_nul().as_ptr()) };
454            assert!(!p.is_null(), "missing symbol {name:?}");
455            // SAFETY: fn-pointer transmute of a resolved symbol.
456            unsafe { core::mem::transmute_copy(&p) }
457        }
458    }
459
460    struct XorShift(u64);
461    impl XorShift {
462        fn next(&mut self) -> u64 {
463            let mut x = self.0;
464            x ^= x << 13;
465            x ^= x >> 7;
466            x ^= x << 17;
467            self.0 = x;
468            x
469        }
470    }
471
472    fn keygen(rng: &mut XorShift) -> Word {
473        (match rng.next() % 5 {
474            0 => rng.next() % 512,
475            1 => 0xAB_CD00_0000 + (rng.next() % 300),
476            2 => (rng.next() % 1024) << 48,
477            // 256-aligned run at a fixed deep base: exercises the
478            // narrow-pointer (skip-carrying leaf) paths against stock.
479            3 => 0x99_8877_6655_4400 + (rng.next() % 256),
480            _ => rng.next(),
481        }) as Word
482    }
483
484    type FSlIns = unsafe extern "C" fn(*mut *mut c_void, *const u8, *mut c_void) -> *mut c_void;
485    type FSlDel = unsafe extern "C" fn(*mut *mut c_void, *const u8, *mut c_void) -> c_int;
486    type FSlGet = unsafe extern "C" fn(*const c_void, *const u8, *mut c_void) -> *mut c_void;
487    type FSlNav = unsafe extern "C" fn(*const c_void, *mut u8, *mut c_void) -> *mut c_void;
488
489    /// Longest key the oracle generates, and therefore the sweep-buffer
490    /// size. `ExpanseStrMap` is a meta-trie over 8-byte chunks, so key
491    /// length *is* tree depth: 4 KiB is ~512 levels, which is deep
492    /// enough to exercise the chunk-chain paths that short keys never
493    /// reach, while staying well inside any reasonable stack for the
494    /// stock library too (we cannot inspect its recursion depth —
495    /// clean-room — so the extreme 64 KiB cases live in our own unit
496    /// tests, not in a differential comparison).
497    const ORACLE_MAX_KEY: usize = 4096;
498
499    fn strgen(rng: &mut XorShift) -> std::ffi::CString {
500        const PREFIXES: [&[u8]; 4] = [b"", b"user:profile:", b"shared/deep/path/", b"x"];
501        let p = PREFIXES[(rng.next() % 4) as usize];
502        // Mostly short keys (the common shape), with a deliberate tail of
503        // long ones: without a chunk-chain of real depth this comparison
504        // cannot see the class of bug that lives there.
505        let len = match rng.next() % 16 {
506            0 => (rng.next() as usize % (ORACLE_MAX_KEY - 64)) + 64, // deep
507            1 => (rng.next() as usize % 200) + 56,                   // medium
508            _ => (rng.next() % 18) as usize,                         // short
509        };
510        let mut k = p.to_vec();
511        for _ in 0..len {
512            k.push((rng.next() % 255 + 1) as u8);
513        }
514        k.truncate(ORACLE_MAX_KEY - 1); // leave room for the NUL
515        std::ffi::CString::new(k).expect("NUL-free")
516    }
517
518    #[test]
519    fn judysl_matches_stock_libjudy() {
520        let lib = Lib::open();
521        let o_ins: FSlIns = lib.sym(c"JudySLIns");
522        let o_del: FSlDel = lib.sym(c"JudySLDel");
523        let o_get: FSlGet = lib.sym(c"JudySLGet");
524        let o_first: FSlNav = lib.sym(c"JudySLFirst");
525        let o_next: FSlNav = lib.sym(c"JudySLNext");
526        let o_free: FFree = lib.sym(c"JudySLFreeArray");
527
528        for seed in [0x51u64, 0x52, 0x53] {
529            let mut rng = XorShift(seed | 1);
530            let mut ours: *mut c_void = null_mut();
531            let mut theirs: *mut c_void = null_mut();
532            // SAFETY: both stacks driven per the C contract with valid
533            // NUL-terminated keys and adequate navigation buffers.
534            unsafe {
535                for _ in 0..2500 {
536                    let k = strgen(&mut rng);
537                    let kp = k.as_ptr().cast::<u8>();
538                    match rng.next() % 5 {
539                        0..=1 => {
540                            let v = rng.next() as Word;
541                            let s1 = JudySLIns(&raw mut ours, kp, null_mut()).cast::<Word>();
542                            let s2 = o_ins(&raw mut theirs, kp, null_mut()).cast::<Word>();
543                            assert_eq!(*s1, *s2, "ins existing {k:?}");
544                            *s1 = v;
545                            *s2 = v;
546                        }
547                        2 => assert_eq!(
548                            JudySLDel(&raw mut ours, kp, null_mut()),
549                            o_del(&raw mut theirs, kp, null_mut()),
550                            "del {k:?}"
551                        ),
552                        _ => {
553                            let s1 = JudySLGet(ours, kp, null_mut()).cast::<Word>();
554                            let s2 = o_get(theirs, kp, null_mut()).cast::<Word>();
555                            assert_eq!(s1.is_null(), s2.is_null(), "get null-ness {k:?}");
556                            if !s1.is_null() {
557                                assert_eq!(*s1, *s2, "get value {k:?}");
558                            }
559                        }
560                    }
561                }
562                // Full lexicographic sweep must agree byte for byte.
563                let (mut b1, mut b2) = ([0u8; ORACLE_MAX_KEY], [0u8; ORACLE_MAX_KEY]);
564                let mut s1 = JudySLFirst(ours, b1.as_mut_ptr(), null_mut());
565                let mut s2 = o_first(theirs, b2.as_mut_ptr(), null_mut());
566                let mut n = 0u32;
567                while !s1.is_null() || !s2.is_null() {
568                    assert_eq!(s1.is_null(), s2.is_null(), "sweep null-ness at {n}");
569                    assert_eq!(b1, b2, "sweep key at {n}");
570                    assert_eq!(*s1.cast::<Word>(), *s2.cast::<Word>(), "sweep value at {n}");
571                    n += 1;
572                    s1 = JudySLNext(ours, b1.as_mut_ptr(), null_mut());
573                    s2 = o_next(theirs, b2.as_mut_ptr(), null_mut());
574                }
575                assert!(JudySLFreeArray(&raw mut ours, null_mut()) > 0);
576                assert!(o_free(&raw mut theirs, null_mut()) > 0);
577                assert!(ours.is_null() && theirs.is_null());
578            }
579        }
580    }
581
582    type FHsIns =
583        unsafe extern "C" fn(*mut *mut c_void, *const c_void, Word, *mut c_void) -> *mut c_void;
584    type FHsDel = unsafe extern "C" fn(*mut *mut c_void, *const c_void, Word, *mut c_void) -> c_int;
585    type FHsGet = unsafe extern "C" fn(*const c_void, *const c_void, Word) -> *mut c_void;
586
587    fn bytesgen(rng: &mut XorShift) -> Vec<u8> {
588        // Arbitrary bytes (NULs included), lengths 0..=32 with repeats.
589        let len = (rng.next() % 33) as usize;
590        (0..len).map(|_| (rng.next() % 5) as u8 * 0x3F).collect()
591    }
592
593    #[test]
594    fn judyhs_matches_stock_libjudy() {
595        let lib = Lib::open();
596        let o_ins: FHsIns = lib.sym(c"JudyHSIns");
597        let o_del: FHsDel = lib.sym(c"JudyHSDel");
598        let o_get: FHsGet = lib.sym(c"JudyHSGet");
599        let o_free: FFree = lib.sym(c"JudyHSFreeArray");
600
601        for seed in [0x61u64, 0x62, 0x63] {
602            let mut rng = XorShift(seed | 1);
603            let mut ours: *mut c_void = null_mut();
604            let mut theirs: *mut c_void = null_mut();
605            // SAFETY: both stacks driven per the C contract with valid
606            // (pointer, length) byte strings.
607            unsafe {
608                for _ in 0..2500 {
609                    let k = bytesgen(&mut rng);
610                    let (kp, kl) = (k.as_ptr().cast::<c_void>(), k.len() as Word);
611                    match rng.next() % 5 {
612                        0..=1 => {
613                            let v = rng.next() as Word;
614                            let s1 = JudyHSIns(&raw mut ours, kp, kl, null_mut()).cast::<Word>();
615                            let s2 = o_ins(&raw mut theirs, kp, kl, null_mut()).cast::<Word>();
616                            assert_eq!(*s1, *s2, "ins existing {k:02x?}");
617                            *s1 = v;
618                            *s2 = v;
619                        }
620                        2 => assert_eq!(
621                            JudyHSDel(&raw mut ours, kp, kl, null_mut()),
622                            o_del(&raw mut theirs, kp, kl, null_mut()),
623                            "del {k:02x?}"
624                        ),
625                        _ => {
626                            let s1 = JudyHSGet(ours, kp, kl).cast::<Word>();
627                            let s2 = o_get(theirs, kp, kl).cast::<Word>();
628                            assert_eq!(s1.is_null(), s2.is_null(), "get null-ness {k:02x?}");
629                            if !s1.is_null() {
630                                assert_eq!(*s1, *s2, "get value {k:02x?}");
631                            }
632                        }
633                    }
634                }
635                // JudyHS has no navigation surface; the byte totals of
636                // FreeArray are implementation-defined (doc-gap D4) —
637                // only emptiness semantics must agree.
638                assert!(JudyHSFreeArray(&raw mut ours, null_mut()) > 0);
639                assert!(o_free(&raw mut theirs, null_mut()) > 0);
640                assert!(ours.is_null() && theirs.is_null());
641            }
642        }
643    }
644
645    /// Black-box probe (#1681, docs/COMPAT.md D10): does a JudyHS value slot
646    /// stay at one address across unrelated inserts? Each library takes a
647    /// probe key, then 20,000 other keys of the same length class, and the
648    /// probe key's slot address is compared before and after. Prints both
649    /// libraries' answer per class; asserts only that the value survives.
650    #[test]
651    fn judyhs_slot_address_across_unrelated_inserts() {
652        let lib = Lib::open();
653        let o_ins: FHsIns = lib.sym(c"JudyHSIns");
654        let o_get: FHsGet = lib.sym(c"JudyHSGet");
655        let o_free: FFree = lib.sym(c"JudyHSFreeArray");
656        unsafe extern "C" fn our_ins(
657            pp: *mut *mut c_void,
658            k: *const c_void,
659            n: Word,
660            pj: *mut c_void,
661        ) -> *mut c_void {
662            // SAFETY: forwarded unchanged.
663            unsafe { JudyHSIns(pp, k, n, pj.cast()) }
664        }
665        unsafe extern "C" fn our_get(p: *const c_void, k: *const c_void, n: Word) -> *mut c_void {
666            // SAFETY: forwarded unchanged.
667            unsafe { JudyHSGet(p, k, n) }
668        }
669        for (class, len) in [("8-byte", 8usize), ("40-byte", 40)] {
670            let key = |i: u64| -> Vec<u8> {
671                let mut k = vec![0u8; len];
672                k[len - 8..].copy_from_slice(&i.to_be_bytes());
673                k
674            };
675            let mut moved = Vec::new();
676            let libs: [(&str, FHsIns, FHsGet); 2] =
677                [("libexpanse", our_ins, our_get), ("stock", o_ins, o_get)];
678            for (name, ins, get) in libs {
679                let mut arr: *mut c_void = null_mut();
680                let probe = key(u64::MAX / 3);
681                // SAFETY: standard JudyHS usage with live byte strings; the
682                // slot address is compared, and dereferenced only through a
683                // fresh JudyHSGet.
684                unsafe {
685                    let p0 = ins(&raw mut arr, probe.as_ptr().cast(), len as Word, null_mut());
686                    *p0.cast::<Word>() = 0xC0FFEE;
687                    for i in 0..20_000u64 {
688                        let k = key(i.wrapping_mul(0x9E37_79B9_7F4A_7C15));
689                        ins(&raw mut arr, k.as_ptr().cast(), len as Word, null_mut());
690                    }
691                    let p1 = get(arr, probe.as_ptr().cast(), len as Word);
692                    assert_eq!(*p1.cast::<Word>(), 0xC0FFEE, "{name} {class}: value lost");
693                    moved.push((name, p0 != p1));
694                    if name == "stock" {
695                        o_free(&raw mut arr, null_mut());
696                    } else {
697                        JudyHSFreeArray(&raw mut arr, null_mut());
698                    }
699                }
700            }
701            println!("JudyHS slot moved across 20,000 unrelated inserts ({class} keys): {moved:?}");
702        }
703    }
704
705    /// zmap's dedup window (#1672): JudyHS as a fixed-capacity LRU index.
706    /// Each arrival is tested with `JudyHSGet`; a miss evicts the oldest key
707    /// with `JudyHSDel` once the window is full and inserts the arrival, so
708    /// evicted keys recur and are inserted again. Both libraries run the same
709    /// sequence in lockstep against one model, and every return is compared:
710    /// `Get` presence and value, `Del`'s 0/1, the fresh slot `Ins` hands
711    /// back, and whether the array word is null. Key shapes: zmap's 8-byte
712    /// `target_t {ip, port, status}` (libexpanse's short-key tries), 0..=8
713    /// byte keys differing only in trailing zeros, and 16- and 40-byte keys
714    /// (the hashed path). The integration test
715    /// `tests/test_judyhs_lru.rs` runs the same pattern on libexpanse alone.
716    #[test]
717    fn judyhs_lru_evict_reinsert_matches_stock_libjudy() {
718        use std::collections::{BTreeMap, VecDeque};
719        let lib = Lib::open();
720        let o_ins: FHsIns = lib.sym(c"JudyHSIns");
721        let o_del: FHsDel = lib.sym(c"JudyHSDel");
722        let o_get: FHsGet = lib.sym(c"JudyHSGet");
723        let o_free: FFree = lib.sym(c"JudyHSFreeArray");
724
725        fn target_t(i: u64) -> Vec<u8> {
726            let ip = 0x0A00_0000u32 + (i / 3) as u32;
727            let port = [80u16, 443, 0][(i % 3) as usize];
728            let status = u16::from(i.is_multiple_of(7));
729            let mut k = ip.to_ne_bytes().to_vec();
730            k.extend_from_slice(&port.to_ne_bytes());
731            k.extend_from_slice(&status.to_ne_bytes());
732            k
733        }
734        fn zero_padded(i: u64) -> Vec<u8> {
735            let Some(j) = i.checked_sub(1) else {
736                return Vec::new();
737            };
738            let mut k = vec![0u8; 1 + (j % 8) as usize];
739            k[0] = (j / 8) as u8;
740            k
741        }
742        fn target_t_16(i: u64) -> Vec<u8> {
743            let mut k = target_t(i);
744            k.resize(16, 0);
745            k
746        }
747        fn wide_40(i: u64) -> Vec<u8> {
748            let mut k = vec![0u8; 40];
749            k[32..].copy_from_slice(&i.wrapping_mul(0x9E37_79B9_7F4A_7C15).to_be_bytes());
750            k
751        }
752        /// Every slot read and write goes through these two, so the null
753        /// check sits with the dereference. `p` is null or a live slot with
754        /// no change to its array since the call that returned it.
755        unsafe fn read(p: *mut c_void) -> Option<Word> {
756            assert_ne!(p as usize, usize::MAX, "PJERR returned");
757            // SAFETY: per the contract above; `as_ref` maps null to `None`.
758            unsafe { p.cast::<Word>().as_ref().copied() }
759        }
760        unsafe fn write(p: *mut c_void, v: Word) {
761            assert_ne!(p as usize, usize::MAX, "PJERR returned");
762            // SAFETY: per the contract above; `as_mut` maps null to `None`.
763            let slot = unsafe { p.cast::<Word>().as_mut() }.expect("JudyHSIns returned null");
764            *slot = v;
765        }
766        type KeyFn = fn(u64) -> Vec<u8>;
767        let shapes: [(&str, KeyFn, u64); 4] = [
768            ("target_t", target_t, 3000),
769            ("zero_padded", zero_padded, 1 + 8 * 256),
770            ("target_t_16", target_t_16, 3000),
771            ("wide_40", wide_40, 3000),
772        ];
773        for (shape, key, pool) in shapes {
774            let keys: Vec<Vec<u8>> = (0..pool).map(key).collect();
775            let wide = keys.len() / 3;
776            for (capacity, seed) in [(1usize, 0x1672u64), (37, 0x1673), (wide, 0x1674)] {
777                let mut rng = XorShift(seed | 1);
778                let mut ours: *mut c_void = null_mut();
779                let mut theirs: *mut c_void = null_mut();
780                let mut model: BTreeMap<&[u8], Word> = BTreeMap::new();
781                let mut order: VecDeque<&[u8]> = VecDeque::new();
782                let mut reinserts = 0usize;
783                let mut evicted: BTreeMap<&[u8], ()> = BTreeMap::new();
784                let at = |s: &str, step: usize| format!("{shape} cap {capacity} step {step}: {s}");
785                // SAFETY: both stacks driven per the C contract with live
786                // (pointer, length) byte strings; a slot pointer is used
787                // only before the next call that changes its array.
788                unsafe {
789                    for step in 0..20_000usize {
790                        let k: &[u8] = &keys[(rng.next() % pool) as usize];
791                        let (kp, kl) = (k.as_ptr().cast::<c_void>(), k.len() as Word);
792                        let g1 = read(JudyHSGet(ours, kp, kl));
793                        let g2 = read(o_get(theirs, kp, kl));
794                        assert_eq!(g1, g2, "{}", at("get", step));
795                        let want = model.get(k).copied();
796                        assert_eq!(g1, want, "{}", at("get vs model", step));
797                        if want.is_some() {
798                            continue;
799                        }
800                        if order.len() == capacity {
801                            let old = order.pop_front().expect("window is full");
802                            let (op, ol) = (old.as_ptr().cast::<c_void>(), old.len() as Word);
803                            let d1 = JudyHSDel(&raw mut ours, op, ol, null_mut());
804                            let d2 = o_del(&raw mut theirs, op, ol, null_mut());
805                            assert_eq!((d1, d2), (1, 1), "{}", at("evict", step));
806                            assert_eq!(ours.is_null(), theirs.is_null(), "{}", at("word", step));
807                            let r1 = JudyHSDel(&raw mut ours, op, ol, null_mut());
808                            let r2 = o_del(&raw mut theirs, op, ol, null_mut());
809                            assert_eq!((r1, r2), (0, 0), "{}", at("re-delete", step));
810                            model.remove(old);
811                            evicted.insert(old, ());
812                        }
813                        if evicted.remove(k).is_some() {
814                            reinserts += 1;
815                        }
816                        let s1 = JudyHSIns(&raw mut ours, kp, kl, null_mut());
817                        let s2 = o_ins(&raw mut theirs, kp, kl, null_mut());
818                        let fresh = (read(s1), read(s2));
819                        assert_eq!(fresh, (Some(0), Some(0)), "{}", at("fresh slot", step));
820                        let v = (step as Word) << 1 | 1;
821                        write(s1, v);
822                        write(s2, v);
823                        model.insert(k, v);
824                        order.push_back(k);
825                    }
826                    assert!(reinserts > 0, "{shape} cap {capacity}: no re-insert");
827                    // Drain oldest first: both words empty to null together.
828                    while let Some(old) = order.pop_front() {
829                        let (op, ol) = (old.as_ptr().cast::<c_void>(), old.len() as Word);
830                        let d1 = JudyHSDel(&raw mut ours, op, ol, null_mut());
831                        let d2 = o_del(&raw mut theirs, op, ol, null_mut());
832                        assert_eq!((d1, d2), (1, 1), "{shape} cap {capacity}: drain");
833                        assert_eq!(ours.is_null(), theirs.is_null(), "{shape}: drain word");
834                    }
835                    assert!(ours.is_null() && theirs.is_null(), "{shape}: emptied word");
836                    // Refill and free whole; byte totals are D4, only
837                    // emptiness semantics are compared.
838                    for k in keys.iter().take(capacity) {
839                        let (kp, kl) = (k.as_ptr().cast::<c_void>(), k.len() as Word);
840                        write(JudyHSIns(&raw mut ours, kp, kl, null_mut()), 7);
841                        write(o_ins(&raw mut theirs, kp, kl, null_mut()), 7);
842                    }
843                    assert!(JudyHSFreeArray(&raw mut ours, null_mut()) > 0);
844                    assert!(o_free(&raw mut theirs, null_mut()) > 0);
845                    assert!(ours.is_null() && theirs.is_null());
846                    assert_eq!(JudyHSFreeArray(&raw mut ours, null_mut()), 0);
847                    assert_eq!(o_free(&raw mut theirs, null_mut()), 0);
848                }
849            }
850        }
851    }
852
853    #[test]
854    fn judy1_matches_stock_libjudy() {
855        let lib = Lib::open();
856        let o_set: F2i = lib.sym(c"Judy1Set");
857        let o_unset: F2i = lib.sym(c"Judy1Unset");
858        let o_test: F2t = lib.sym(c"Judy1Test");
859        let o_count: FCount = lib.sym(c"Judy1Count");
860        let o_byc: FByC = lib.sym(c"Judy1ByCount");
861        let o_first: FNav = lib.sym(c"Judy1First");
862        let o_next: FNav = lib.sym(c"Judy1Next");
863        let _o_last: FNav = lib.sym(c"Judy1Last");
864        let o_prev: FNav = lib.sym(c"Judy1Prev");
865        let o_fe: FNav = lib.sym(c"Judy1FirstEmpty");
866        let o_le: FNav = lib.sym(c"Judy1LastEmpty");
867        let o_free: FFree = lib.sym(c"Judy1FreeArray");
868
869        for seed in [0xA1u64, 0xB2, 0xC3] {
870            let mut rng = XorShift(seed | 1);
871            let mut ours: *mut c_void = null_mut();
872            let mut theirs: *mut c_void = null_mut();
873            // SAFETY: both stacks driven through their C contracts with
874            // valid pointers; sequences identical on both sides.
875            unsafe {
876                for _ in 0..4000 {
877                    let k = keygen(&mut rng);
878                    match rng.next() % 8 {
879                        0..=2 => assert_eq!(
880                            Judy1Set(&raw mut ours, k, null_mut()),
881                            o_set(&raw mut theirs, k, null_mut()),
882                            "set {k:#x}"
883                        ),
884                        3 => assert_eq!(
885                            Judy1Unset(&raw mut ours, k, null_mut()),
886                            o_unset(&raw mut theirs, k, null_mut()),
887                            "unset {k:#x}"
888                        ),
889                        4 => assert_eq!(
890                            Judy1Test(ours, k, null_mut()),
891                            o_test(theirs, k, null_mut()),
892                            "test {k:#x}"
893                        ),
894                        5 => {
895                            let k2 = keygen(&mut rng);
896                            let (a, b) = (k.min(k2), k.max(k2));
897                            assert_eq!(
898                                Judy1Count(ours, a, b, null_mut()),
899                                o_count(theirs, a, b, null_mut()),
900                                "count {a:#x}..={b:#x}"
901                            );
902                        }
903                        6 => {
904                            let (mut i1, mut i2) = (k, k);
905                            let r1 = Judy1Next(ours, &raw mut i1, null_mut());
906                            let r2 = o_next(theirs, &raw mut i2, null_mut());
907                            assert_eq!((r1, i1), (r2, i2), "next {k:#x}");
908                            let (mut i1, mut i2) = (k, k);
909                            let r1 = Judy1Prev(ours, &raw mut i1, null_mut());
910                            let r2 = o_prev(theirs, &raw mut i2, null_mut());
911                            assert_eq!((r1, i1), (r2, i2), "prev {k:#x}");
912                        }
913                        _ => {
914                            let (mut i1, mut i2) = (k, k);
915                            let r1 = Judy1FirstEmpty(ours, &raw mut i1, null_mut());
916                            let r2 = o_fe(theirs, &raw mut i2, null_mut());
917                            assert_eq!((r1, i1), (r2, i2), "fe {k:#x}");
918                            let (mut i1, mut i2) = (k, k);
919                            let r1 = Judy1LastEmpty(ours, &raw mut i1, null_mut());
920                            let r2 = o_le(theirs, &raw mut i2, null_mut());
921                            assert_eq!((r1, i1), (r2, i2), "le {k:#x}");
922                        }
923                    }
924                }
925                // Full ordered sweep must agree in both directions.
926                let (mut i1, mut i2) = (0 as Word, 0 as Word);
927                let (mut r1, mut r2) = (
928                    Judy1First(ours, &raw mut i1, null_mut()),
929                    o_first(theirs, &raw mut i2, null_mut()),
930                );
931                let mut n = 0u64;
932                while r1 == 1 || r2 == 1 {
933                    assert_eq!((r1, i1), (r2, i2), "sweep step {n}");
934                    n += 1;
935                    r1 = Judy1Next(ours, &raw mut i1, null_mut());
936                    r2 = o_next(theirs, &raw mut i2, null_mut());
937                }
938                // Rank agreement over the whole population.
939                for nth in [1 as Word, 2, n as Word / 2, n as Word] {
940                    let (mut i1, mut i2) = (0 as Word, 0 as Word);
941                    let r1 = Judy1ByCount(ours, nth, &raw mut i1, null_mut());
942                    let r2 = o_byc(theirs, nth, &raw mut i2, null_mut());
943                    assert_eq!(
944                        (r1, i1),
945                        (r2, if r2 == 1 { i2 } else { i1 }),
946                        "bycount {nth}"
947                    );
948                }
949                assert!(Judy1FreeArray(&raw mut ours, null_mut()) > 0);
950                assert!(o_free(&raw mut theirs, null_mut()) > 0);
951                assert!(ours.is_null() && theirs.is_null());
952            }
953        }
954    }
955
956    #[test]
957    fn judyl_matches_stock_libjudy() {
958        let lib = Lib::open();
959        let o_ins: FpIns = lib.sym(c"JudyLIns");
960        let o_del: F2i = lib.sym(c"JudyLDel");
961        let o_get: FpGet = lib.sym(c"JudyLGet");
962        let o_count: FCount = lib.sym(c"JudyLCount");
963        let o_byc: FpByC = lib.sym(c"JudyLByCount");
964        let o_first: FpNav = lib.sym(c"JudyLFirst");
965        let o_next: FpNav = lib.sym(c"JudyLNext");
966        let o_free: FFree = lib.sym(c"JudyLFreeArray");
967
968        for seed in [0x11u64, 0x22, 0x33] {
969            let mut rng = XorShift(seed | 1);
970            let mut ours: *mut c_void = null_mut();
971            let mut theirs: *mut c_void = null_mut();
972            // SAFETY: as in the Judy1 oracle; slots written immediately
973            // after the call that returned them.
974            unsafe {
975                for _ in 0..4000 {
976                    let k = keygen(&mut rng);
977                    match rng.next() % 6 {
978                        0..=2 => {
979                            let v = rng.next() as Word;
980                            let s1 = JudyLIns(&raw mut ours, k, null_mut()).cast::<Word>();
981                            let s2 = o_ins(&raw mut theirs, k, null_mut()).cast::<Word>();
982                            assert_eq!(*s1, *s2, "ins existing value {k:#x}");
983                            *s1 = v;
984                            *s2 = v;
985                        }
986                        3 => assert_eq!(
987                            JudyLDel(&raw mut ours, k, null_mut()),
988                            o_del(&raw mut theirs, k, null_mut()),
989                            "del {k:#x}"
990                        ),
991                        4 => {
992                            let s1 = JudyLGet(ours, k, null_mut()).cast::<Word>();
993                            let s2 = o_get(theirs, k, null_mut()).cast::<Word>();
994                            assert_eq!(s1.is_null(), s2.is_null(), "get null-ness {k:#x}");
995                            if !s1.is_null() {
996                                assert_eq!(*s1, *s2, "get value {k:#x}");
997                            }
998                        }
999                        _ => {
1000                            let k2 = keygen(&mut rng);
1001                            let (a, b) = (k.min(k2), k.max(k2));
1002                            assert_eq!(
1003                                JudyLCount(ours, a, b, null_mut()),
1004                                o_count(theirs, a, b, null_mut()),
1005                                "count {a:#x}..={b:#x}"
1006                            );
1007                        }
1008                    }
1009                }
1010                // Ordered sweep with value agreement.
1011                let (mut i1, mut i2) = (0 as Word, 0 as Word);
1012                let (mut s1, mut s2) = (
1013                    JudyLFirst(ours, &raw mut i1, null_mut()),
1014                    o_first(theirs, &raw mut i2, null_mut()),
1015                );
1016                let mut n: Word = 0;
1017                while !s1.is_null() || !s2.is_null() {
1018                    assert_eq!(s1.is_null(), s2.is_null(), "sweep null-ness at {n}");
1019                    assert_eq!(i1, i2, "sweep key at {n}");
1020                    assert_eq!(*s1.cast::<Word>(), *s2.cast::<Word>(), "sweep value at {n}");
1021                    n += 1;
1022                    s1 = JudyLNext(ours, &raw mut i1, null_mut());
1023                    s2 = o_next(theirs, &raw mut i2, null_mut());
1024                }
1025                for nth in [1 as Word, n / 2, n] {
1026                    let (mut i1, mut i2) = (0 as Word, 0 as Word);
1027                    let s1 = o_byc(theirs, nth, &raw mut i2, null_mut());
1028                    let s2 = JudyLByCount(ours, nth, &raw mut i1, null_mut());
1029                    assert_eq!(s2.is_null(), s1.is_null(), "bycount null-ness {nth}");
1030                    if !s1.is_null() {
1031                        assert_eq!(i1, i2, "bycount key {nth}");
1032                        assert_eq!(
1033                            *s2.cast::<Word>(),
1034                            *s1.cast::<Word>(),
1035                            "bycount value {nth}"
1036                        );
1037                    }
1038                }
1039                assert!(JudyLFreeArray(&raw mut ours, null_mut()) > 0);
1040                assert!(o_free(&raw mut theirs, null_mut()) > 0);
1041                assert!(ours.is_null() && theirs.is_null());
1042            }
1043        }
1044    }
1045
1046    /// What `First`/`Next`/`Last`/`Prev` leave in `*PIndex` on a miss, for
1047    /// Judy1 and JudyL. The man pages define `*PIndex` only on a hit; this
1048    /// compares the unmasked `(found, index)` pair of every call, so the
1049    /// miss path is settled here (COMPAT.md D8): on a non-empty array stock
1050    /// writes one step past the probe in the search direction, wrapping,
1051    /// and on a null array it writes nothing. The arrays include one
1052    /// emptied back to null by removal, and probes at both ends of the key
1053    /// space, where the step wraps.
1054    #[test]
1055    fn nav_miss_index_matches_stock_libjudy() {
1056        let lib = Lib::open();
1057        let o_set: F2i = lib.sym(c"Judy1Set");
1058        let o_unset: F2i = lib.sym(c"Judy1Unset");
1059        let o_free1: FFree = lib.sym(c"Judy1FreeArray");
1060        let o_ins: FpIns = lib.sym(c"JudyLIns");
1061        let o_del: F2i = lib.sym(c"JudyLDel");
1062        let o_freel: FFree = lib.sym(c"JudyLFreeArray");
1063        let o_nav1: [FNav; 4] = [
1064            lib.sym(c"Judy1First"),
1065            lib.sym(c"Judy1Next"),
1066            lib.sym(c"Judy1Last"),
1067            lib.sym(c"Judy1Prev"),
1068        ];
1069        let o_navl: [FpNav; 4] = [
1070            lib.sym(c"JudyLFirst"),
1071            lib.sym(c"JudyLNext"),
1072            lib.sym(c"JudyLLast"),
1073            lib.sym(c"JudyLPrev"),
1074        ];
1075        unsafe extern "C" fn adapt1<const F: usize>(
1076            p: *const c_void,
1077            i: *mut Word,
1078            pj: *mut c_void,
1079        ) -> c_int {
1080            // SAFETY: forwarded unchanged; `pj` is null or a live JError.
1081            unsafe {
1082                match F {
1083                    0 => Judy1First(p, i, pj.cast()),
1084                    1 => Judy1Next(p, i, pj.cast()),
1085                    2 => Judy1Last(p, i, pj.cast()),
1086                    _ => Judy1Prev(p, i, pj.cast()),
1087                }
1088            }
1089        }
1090        unsafe extern "C" fn adaptl<const F: usize>(
1091            p: *const c_void,
1092            i: *mut Word,
1093            pj: *mut c_void,
1094        ) -> *mut c_void {
1095            // SAFETY: as above.
1096            unsafe {
1097                match F {
1098                    0 => JudyLFirst(p, i, pj.cast()),
1099                    1 => JudyLNext(p, i, pj.cast()),
1100                    2 => JudyLLast(p, i, pj.cast()),
1101                    _ => JudyLPrev(p, i, pj.cast()),
1102                }
1103            }
1104        }
1105        let our_nav1: [FNav; 4] = [adapt1::<0>, adapt1::<1>, adapt1::<2>, adapt1::<3>];
1106        let our_navl: [FpNav; 4] = [adaptl::<0>, adaptl::<1>, adaptl::<2>, adaptl::<3>];
1107
1108        let shapes: [&[Word]; 6] = [
1109            &[],
1110            &[100],
1111            &[100, 200, 300],
1112            &[0],
1113            &[Word::MAX],
1114            &[0x99_8877_6655_4400, 0x99_8877_6655_4410],
1115        ];
1116        let mut probes: Vec<Word> = vec![0, 1, 99, 100, 101, 199, 200, 201, 299, 300, 301];
1117        probes.extend([1 << 32, (1 << 63) - 1, 1 << 63, Word::MAX - 1, Word::MAX]);
1118        probes.extend([
1119            0x99_8877_6655_43FF,
1120            0x99_8877_6655_4405,
1121            0x99_8877_6655_4411,
1122        ]);
1123        let mut rng = XorShift(0x5EED_D8D8);
1124        // A larger array of every key shape, so a miss can end at any depth.
1125        let wide: Vec<Word> = (0..3000).map(|_| keygen(&mut rng)).collect();
1126        probes.extend((0..400).map(|_| keygen(&mut rng)));
1127
1128        // One transcript per library: (shape, probe, function, found, index).
1129        let transcript = |set: [F2i; 2],
1130                          ins: FpIns,
1131                          del: F2i,
1132                          free: [FFree; 2],
1133                          nav1: [FNav; 4],
1134                          navl: [FpNav; 4]| {
1135            let mut out = Vec::new();
1136            let all = shapes.iter().copied().chain([wide.as_slice()]);
1137            for (shape, keys) in all.enumerate() {
1138                let (mut a1, mut al) = (null_mut::<c_void>(), null_mut::<c_void>());
1139                // SAFETY: both arrays are owned here and driven through
1140                // their C contracts; each slot is written right after the
1141                // call that returned it.
1142                unsafe {
1143                    for &k in keys {
1144                        set[0](&raw mut a1, k, null_mut());
1145                        *ins(&raw mut al, k, null_mut()).cast::<Word>() = k;
1146                    }
1147                    for &p in &probes {
1148                        for f in 0..4 {
1149                            let mut i = p;
1150                            let r = nav1[f](a1, &raw mut i, null_mut());
1151                            out.push((shape, p, f, r == 1, i));
1152                            let mut i = p;
1153                            let r = navl[f](al, &raw mut i, null_mut());
1154                            out.push((shape, p, 4 + f, !r.is_null(), i));
1155                        }
1156                    }
1157                    if shape == 1 {
1158                        // Emptied back to null by removal, then probed again.
1159                        assert_eq!(set[1](&raw mut a1, 100, null_mut()), 1);
1160                        assert_eq!(del(&raw mut al, 100, null_mut()), 1);
1161                        assert!(a1.is_null() && al.is_null(), "emptied array is null");
1162                        for &p in &probes {
1163                            for f in 0..4 {
1164                                let mut i = p;
1165                                let r = nav1[f](a1, &raw mut i, null_mut());
1166                                out.push((99, p, f, r == 1, i));
1167                                let mut i = p;
1168                                let r = navl[f](al, &raw mut i, null_mut());
1169                                out.push((99, p, 4 + f, !r.is_null(), i));
1170                            }
1171                        }
1172                    }
1173                    free[0](&raw mut a1, null_mut());
1174                    free[1](&raw mut al, null_mut());
1175                }
1176            }
1177            out
1178        };
1179        unsafe extern "C" fn our_set(p: *mut *mut c_void, k: Word, pj: *mut c_void) -> c_int {
1180            // SAFETY: forwarded unchanged.
1181            unsafe { Judy1Set(p, k, pj.cast()) }
1182        }
1183        unsafe extern "C" fn our_unset(p: *mut *mut c_void, k: Word, pj: *mut c_void) -> c_int {
1184            // SAFETY: forwarded unchanged.
1185            unsafe { Judy1Unset(p, k, pj.cast()) }
1186        }
1187        unsafe extern "C" fn our_ins(p: *mut *mut c_void, k: Word, pj: *mut c_void) -> *mut c_void {
1188            // SAFETY: forwarded unchanged.
1189            unsafe { JudyLIns(p, k, pj.cast()) }
1190        }
1191        unsafe extern "C" fn our_del(p: *mut *mut c_void, k: Word, pj: *mut c_void) -> c_int {
1192            // SAFETY: forwarded unchanged.
1193            unsafe { JudyLDel(p, k, pj.cast()) }
1194        }
1195        unsafe extern "C" fn our_free1(p: *mut *mut c_void, pj: *mut c_void) -> Word {
1196            // SAFETY: forwarded unchanged.
1197            unsafe { Judy1FreeArray(p, pj.cast()) }
1198        }
1199        unsafe extern "C" fn our_freel(p: *mut *mut c_void, pj: *mut c_void) -> Word {
1200            // SAFETY: forwarded unchanged.
1201            unsafe { JudyLFreeArray(p, pj.cast()) }
1202        }
1203        let ours = transcript(
1204            [our_set, our_unset],
1205            our_ins,
1206            our_del,
1207            [our_free1, our_freel],
1208            our_nav1,
1209            our_navl,
1210        );
1211        let theirs = transcript(
1212            [o_set, o_unset],
1213            o_ins,
1214            o_del,
1215            [o_free1, o_freel],
1216            o_nav1,
1217            o_navl,
1218        );
1219        assert_eq!(ours.len(), theirs.len());
1220        let misses = theirs.iter().filter(|t| !t.3).count();
1221        assert!(
1222            misses > 1000,
1223            "the probes must reach the miss path: {misses}"
1224        );
1225        for (o, t) in ours.iter().zip(&theirs) {
1226            assert_eq!(
1227                o, t,
1228                "(shape, probe, fn 0-3 Judy1 F/N/L/P 4-7 JudyL, found, index)"
1229            );
1230        }
1231    }
1232
1233    /// What `Judy1Count`/`JudyLCount` write to `*PJError`, case by case.
1234    /// The man pages (`Judy1_funcs(3)`) document only that a 0 return
1235    /// with `JU_ERRNO_NONE` is a real empty count; whether a nonzero count
1236    /// or a reversed range writes it is settled here (COMPAT.md D7).
1237    /// Each call starts from a sentinel errno, so "left untouched" and
1238    /// "written" are told apart.
1239    #[test]
1240    fn count_errno_matches_stock_libjudy() {
1241        const SENTINEL: c_int = 99;
1242        let lib = Lib::open();
1243        let o_set: F2i = lib.sym(c"Judy1Set");
1244        let o_count1: FCount = lib.sym(c"Judy1Count");
1245        let o_free1: FFree = lib.sym(c"Judy1FreeArray");
1246        let o_ins: FpIns = lib.sym(c"JudyLIns");
1247        let o_countl: FCount = lib.sym(c"JudyLCount");
1248        let o_freel: FFree = lib.sym(c"JudyLFreeArray");
1249        let ranges: [(Word, Word); 7] = [
1250            (0, Word::MAX),
1251            (10, 30),
1252            (11, 19),
1253            (25, 25),
1254            (31, Word::MAX),
1255            (30, 10),
1256            (Word::MAX, 0),
1257        ];
1258        // Our entry points take `*mut JError`; the probe takes the stock
1259        // library's untyped signature.
1260        unsafe extern "C" fn our_count1(
1261            p: *const c_void,
1262            a: Word,
1263            b: Word,
1264            pj: *mut c_void,
1265        ) -> Word {
1266            // SAFETY: forwarded unchanged; `pj` is null or a live JError.
1267            unsafe { Judy1Count(p, a, b, pj.cast()) }
1268        }
1269        unsafe extern "C" fn our_countl(
1270            p: *const c_void,
1271            a: Word,
1272            b: Word,
1273            pj: *mut c_void,
1274        ) -> Word {
1275            // SAFETY: as above.
1276            unsafe { JudyLCount(p, a, b, pj.cast()) }
1277        }
1278        let probe = |count: FCount, array: *const c_void, a: Word, b: Word| {
1279            let mut je = JError {
1280                je_errno: SENTINEL,
1281                je_err_id: 0,
1282                je_reserved: [0; 4],
1283            };
1284            // SAFETY: `array` is null or a live array of the family
1285            // `count` belongs to; `je` is a live, writable JError.
1286            let rc = unsafe { count(array, a, b, (&raw mut je).cast()) };
1287            // SAFETY: a null PJError is part of the documented contract.
1288            let rc_null = unsafe { count(array, a, b, null_mut()) };
1289            assert_eq!(rc, rc_null, "count {a:#x}..={b:#x} with a null PJError");
1290            (a, b, rc, je.je_errno)
1291        };
1292        // SAFETY: both libraries' entry points driven through their C
1293        // contracts with identical sequences and valid pointers.
1294        unsafe {
1295            for populated in [false, true] {
1296                let (mut ours1, mut theirs1) = (null_mut::<c_void>(), null_mut::<c_void>());
1297                let (mut oursl, mut theirsl) = (null_mut::<c_void>(), null_mut::<c_void>());
1298                if populated {
1299                    for k in [10, 20, 30] {
1300                        assert_eq!(Judy1Set(&raw mut ours1, k, null_mut()), 1);
1301                        assert_eq!(o_set(&raw mut theirs1, k, null_mut()), 1);
1302                        *JudyLIns(&raw mut oursl, k, null_mut()).cast::<Word>() = k;
1303                        *o_ins(&raw mut theirsl, k, null_mut()).cast::<Word>() = k;
1304                    }
1305                }
1306                let ours: Vec<_> = ranges
1307                    .iter()
1308                    .flat_map(|&(a, b)| {
1309                        [
1310                            probe(our_count1, ours1, a, b),
1311                            probe(our_countl, oursl, a, b),
1312                        ]
1313                    })
1314                    .collect();
1315                let theirs: Vec<_> = ranges
1316                    .iter()
1317                    .flat_map(|&(a, b)| {
1318                        [
1319                            probe(o_count1, theirs1, a, b),
1320                            probe(o_countl, theirsl, a, b),
1321                        ]
1322                    })
1323                    .collect();
1324                assert_eq!(
1325                    ours, theirs,
1326                    "(index1, index2, count, errno) per call, Judy1 then JudyL; populated = {populated}"
1327                );
1328                if populated {
1329                    assert!(Judy1FreeArray(&raw mut ours1, null_mut()) > 0);
1330                    assert!(o_free1(&raw mut theirs1, null_mut()) > 0);
1331                    assert!(JudyLFreeArray(&raw mut oursl, null_mut()) > 0);
1332                    assert!(o_freel(&raw mut theirsl, null_mut()) > 0);
1333                }
1334            }
1335        }
1336    }
1337}