yo_index/lib.rs
1//! The index plane: buckets, tag prefiltered probing, and dashtable style
2//! growth.
3//!
4//! This crate is the part of the record plane that answers "where is this key".
5//! It stores tags and addresses, never keys and never values, and it reaches
6//! the key bytes through the [`Keys`] trait so that the record format can
7//! change under it without the index changing at all.
8//!
9//! Three things carry the performance claim, and all three are in `05`:
10//!
11//! 1. A bucket is 64 bytes, which is one cache line, so a probe is one load.
12//! 2. Seven one byte tags are compared in a single 64 bit SWAR operation, so a
13//! miss costs no key comparison at all and a hit costs one.
14//! 3. Growth splits one segment at a time, so there is no rehash pause.
15//!
16//! ```
17//! use yo_index::{Index, Keys};
18//! use yo_common::Addr;
19//!
20//! // A toy record plane: the address is an offset into one flat buffer of
21//! // length prefixed keys. M1 replaces this with the real record header.
22//! struct Toy(Vec<Vec<u8>>);
23//! impl Keys for Toy {
24//! fn hash_at(&self, addr: Addr) -> u64 {
25//! yo_common::wyhash(&self.0[addr.offset() as usize], 0)
26//! }
27//! fn eq_at(&self, addr: Addr, key: &[u8]) -> bool {
28//! self.0[addr.offset() as usize] == key
29//! }
30//! }
31//!
32//! let mut recs = Toy(vec![b"greeting".to_vec()]);
33//! let mut ix = Index::new();
34//! let h = yo_common::wyhash(b"greeting", 0);
35//! ix.insert(h, b"greeting", Addr::new(yo_common::Space::Arena, 0), &recs);
36//! assert!(ix.contains(h, b"greeting", &recs));
37//! ```
38
39#![deny(missing_docs)]
40
41mod bucket;
42mod index;
43mod map;
44mod scan;
45mod tagged;
46
47pub use bucket::{Bucket, EMPTY, SLOTS, SlotMask};
48pub use index::{Index, Keys, MAX_CHAIN, SEGMENT_BUCKETS};
49pub use map::RawMap;
50pub use scan::Cursor;