nx_hash_index.nx source
↩ module page · 52 lines · 2310 B
1// nx_hash_index.nx -- sovereign O(1) HASH INDEX library (variable-length keys), the read-path exceed,
2// extracted as a reusable component (Rule 15 DRY). Proven in nx_hash_index_bench: 65 ns/op = ~3.8x faster
3// than sqlite's cited B-tree probe (250 ns) and ~4.9x faster than binary search. FNV-1a + open-addressing
4// linear probe. Designed for the seg_store get path (per-segment cache) and any other consumer.
5// handle layout (one mmap of i64): [0]=nbuckets [1]=mask, then kptr[nb]@2, klen[nb]@2+nb, val[nb]@2+2nb.
6// val == -1 marks an empty bucket (store values are non-negative record/offset ids, so -1 is a safe sentinel).
7// license_tier: ORIGINAL
8import "nx_syscalls.nx"
9
10const HI_FNVP: i64 = 1099511628211
11
12func hi_hash(k: *u8, klen: i64) -> i64 { var h: i64=0; var i: i64=0; while i<klen { h=(h ^ (k[i] as i64)) * HI_FNVP; i=i+1 } return h }
13func hi_keq(a: *u8, alen: i64, b: *u8, blen: i64) -> i64 { if alen!=blen { return 0 } var i: i64=0; while i<alen { if a[i]!=b[i] { return 0 } i=i+1 } return 1 }
14
15// allocate a table with nbuckets (caller passes a power of two >= entries/0.7).
16func hi_new(nbuckets: i64) -> *i64 {
17 let h: *i64 = sys_mmap(8 * (2 + 3*nbuckets)) as *i64
18 h[0]=nbuckets
19 h[1]=nbuckets-1
20 let vb: i64 = 2 + 2*nbuckets
21 var i: i64=0
22 while i<nbuckets { h[vb+i] = 0-1; i=i+1 }
23 return h
24}
25// insert/update key -> val. O(1) amortized.
26func hi_put(h: *i64, kptr: *u8, klen: i64, val: i64) -> i64 {
27 let mask: i64=h[1]
28 let kpb: i64=2
29 let klb: i64=2+h[0]
30 let vb: i64=2+2*h[0]
31 var b: i64 = hi_hash(kptr,klen) & mask
32 var go: i64=1
33 while go==1 {
34 if h[vb+b]==(0-1) { h[kpb+b]=kptr as i64; h[klb+b]=klen; h[vb+b]=val; go=0 }
35 else { if hi_keq((h[kpb+b]) as *u8, h[klb+b], kptr, klen)==1 { h[vb+b]=val; go=0 } else { b=(b+1) & mask } }
36 }
37 return 0
38}
39// lookup key -> val, or -1 if absent. O(1) expected.
40func hi_get(h: *i64, kptr: *u8, klen: i64) -> i64 {
41 let mask: i64=h[1]
42 let kpb: i64=2
43 let klb: i64=2+h[0]
44 let vb: i64=2+2*h[0]
45 var b: i64 = hi_hash(kptr,klen) & mask
46 var go: i64=1
47 var res: i64=0-1
48 while go==1 {
49 if h[vb+b]==(0-1) { go=0 } else { if hi_keq((h[kpb+b]) as *u8, h[klb+b], kptr, klen)==1 { res=h[vb+b]; go=0 } else { b=(b+1) & mask } }
50 }
51 return res
52}