1#![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#[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#[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
56pub type Word = usize;
58
59#[repr(C)]
61pub struct JError {
62 pub je_errno: c_int,
64 pub je_err_id: c_int,
66 pub je_reserved: [Word; 4],
68}
69
70pub const JU_ERRNO_NONE: c_int = 0;
72pub const JU_ERRNO_NOMEM: c_int = 2;
74pub const JU_ERRNO_NULLPPARRAY: c_int = 3;
76pub const JU_ERRNO_NULLPINDEX: c_int = 5;
78
79#[repr(C)]
81pub struct CNodeCounts {
82 pub null: u64,
84 pub immed: u64,
86 pub leaf_linear: u64,
88 pub leaf_bitmap: u64,
90 pub branch_l3: u64,
92 pub branch_l7: u64,
94 pub branch_b: u64,
96 pub branch_u: u64,
98 pub full_expanse: u64,
100}
101
102#[repr(C)]
104pub struct CExpanseStats {
105 pub node_counts: CNodeCounts,
107 pub depth_histogram: [u64; 9],
109 pub leaf_pop_histogram: [u64; 257],
111}
112
113#[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 let map = unsafe { &*parray.cast::<ExpanseMap>() };
128 c_int::from(map.validate_defensive().is_ok())
129 } else {
130 let set = unsafe { &*parray.cast::<ExpanseSet>() };
132 c_int::from(set.validate_defensive().is_ok())
133 }
134}
135
136#[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 let map = unsafe { &*parray.cast::<ExpanseMap>() };
152 map.stats()
153 } else {
154 let set = unsafe { &*parray.cast::<ExpanseSet>() };
156 set.stats()
157 };
158
159 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 #[allow(clippy::needless_range_loop)]
173 for i in 0..9 {
174 (*out).depth_histogram[i] = stats.depth_histogram[i] as u64;
175 }
176 #[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 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 let copy = key.to_vec();
206 let got = JudyHSGet(a, copy.as_ptr().cast(), copy.len()).cast::<Word>();
207 assert_eq!(*got, 777);
208 assert!(JudyHSGet(a, kp, 5).is_null());
210 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 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 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 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 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 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 assert_eq!(
340 *JudySLIns(&raw mut a, c"hello".as_ptr().cast(), null_mut()).cast::<Word>(),
341 11
342 );
343
344 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 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 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#[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 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 let p = unsafe { dlsym(self.0, name.to_bytes_with_nul().as_ptr()) };
454 assert!(!p.is_null(), "missing symbol {name:?}");
455 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 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 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 let len = match rng.next() % 16 {
506 0 => (rng.next() as usize % (ORACLE_MAX_KEY - 64)) + 64, 1 => (rng.next() as usize % 200) + 56, _ => (rng.next() % 18) as usize, };
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); 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 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 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 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 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 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 #[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 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 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 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 #[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 unsafe fn read(p: *mut c_void) -> Option<Word> {
756 assert_ne!(p as usize, usize::MAX, "PJERR returned");
757 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 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 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 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 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 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 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 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 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 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 #[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 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 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 let wide: Vec<Word> = (0..3000).map(|_| keygen(&mut rng)).collect();
1126 probes.extend((0..400).map(|_| keygen(&mut rng)));
1127
1128 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 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 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 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 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 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 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 unsafe { Judy1FreeArray(p, pj.cast()) }
1198 }
1199 unsafe extern "C" fn our_freel(p: *mut *mut c_void, pj: *mut c_void) -> Word {
1200 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 #[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 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 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 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 let rc = unsafe { count(array, a, b, (&raw mut je).cast()) };
1287 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 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}