precomputed_map/
lib.rs

1#![cfg_attr(not(feature = "builder"), no_std)]
2#![doc = include_str!("../README.md")]
3
4#[cfg(feature = "builder")]
5pub mod builder;
6pub mod store;
7pub mod seq;
8pub mod aligned;
9pub mod phf;
10
11use core::borrow::Borrow;
12use core::hash::Hash;
13use core::marker::PhantomData;
14use phf::HashOne;
15use store::{ MapStore, AccessSeq, Searchable };
16
17
18/// Tiny map
19///
20/// 0..16
21pub struct TinyMap<'data, D> {
22    data: D,
23    _phantom: PhantomData<&'data D>
24}
25
26impl<'data, D> TinyMap<'data, D>
27where
28    D: MapStore<'data> + Searchable<'data>,
29    D::Key: Eq,
30{
31    pub const fn new(data: D) -> TinyMap<'data, D> {
32        TinyMap { data, _phantom: PhantomData }
33    }
34
35    pub const fn len(&self) -> usize {
36        D::LEN
37    }
38
39    pub const fn is_empty(&self) -> bool {
40        self.len() == 0
41    }
42
43    pub fn get<Q>(&self, key: &Q)
44        -> Option<D::Value>
45    where
46        D::Key: Borrow<Q>,
47        Q: Ord + ?Sized
48    {
49        self.data.search(key)
50    }
51
52    pub const fn iter(&self) -> store::MapIter<'_, 'data, D> {
53        store::MapIter::new(&self.data)
54    }
55}
56
57/// Small map
58///
59/// 0..12
60pub struct SmallMap<'data, D, H> {
61    seed: u64,
62    data: D,
63    _phantom: PhantomData<&'data (D, H)>
64}
65
66impl<'data, D, H> SmallMap<'data, D, H>
67where
68    D: MapStore<'data>,
69    D::Key: Hash + Eq + Copy,
70    H: HashOne
71{
72    pub const fn new(seed: u64, data: D) -> SmallMap<'data, D, H> {
73        SmallMap {
74            seed, data,
75            _phantom: PhantomData
76        }
77    }
78
79    pub const fn len(&self) -> usize {
80        D::LEN
81    }    
82
83    pub const fn is_empty(&self) -> bool {
84        self.len() == 0
85    }
86    
87    #[inline]
88    fn inner_get<Q>(&self, key: &Q) -> usize
89    where
90        Q: Hash + ?Sized
91    {
92        let size: u32 = D::LEN.try_into().unwrap();
93
94        let hash = H::hash_one(self.seed, key);
95        let index = fast_reduct32(high(hash) ^ low(hash), size);
96        index.try_into().unwrap()
97    }
98
99    pub fn get<Q>(&self, key: &Q) -> Option<D::Value>
100    where
101        D::Key: Borrow<Q>,
102        Q: Hash + Eq + ?Sized
103    {
104        if self.is_empty() {
105            return None;
106        }
107        
108        let index = self.inner_get(key);
109        if self.data.get_key(index).borrow() == key {
110            Some(self.data.get_value(index))
111        } else {
112            None
113        }
114    }
115
116    pub const fn iter(&self) -> store::MapIter<'_, 'data, D> {
117        store::MapIter::new(&self.data)
118    }    
119}
120
121/// Medium map
122///
123/// 1024..10M
124pub struct MediumMap<'data, P, R, D, H> {
125    seed: u64,
126    slots: u32,
127    pilots: P,
128    remap: R,
129    data: D,
130    _phantom: PhantomData<&'data (P, D, R, H)>
131}
132
133impl<'data, P, R, D, H> MediumMap<'data, P, R, D, H>
134where
135    P: AccessSeq<'data, Item = u8>,
136    R: AccessSeq<'data, Item = u32>,
137    D: MapStore<'data>,
138    D::Key: Hash + Eq + Copy,
139    H: HashOne
140{
141    pub const fn new(seed: u64, slots: u32, pilots: P, remap: R, data: D)
142        -> MediumMap<'data, P, R, D, H>
143    {
144        MediumMap {
145            seed, slots, pilots, remap, data,
146            _phantom: PhantomData
147        }
148    }
149
150    pub const fn len(&self) -> usize {
151        D::LEN
152    }    
153
154    pub const fn is_empty(&self) -> bool {
155        self.len() == 0
156    }
157
158    #[inline]
159    fn inner_get<Q>(&self, key: &Q) -> usize
160    where
161        Q: Hash + ?Sized
162    {
163        let pilots_len: u32 = P::LEN.try_into().unwrap();
164        let slots_len: u32 = self.slots;
165        
166        let hash = H::hash_one(self.seed, key);
167        let bucket: usize = fast_reduct32(low(hash), pilots_len).try_into().unwrap();
168        let pilot = self.pilots.index(bucket);
169        let pilot_hash = phf::hash_pilot(self.seed, pilot);
170        let index: usize = fast_reduct32(
171            high(hash) ^ high(pilot_hash) ^ low(pilot_hash),
172            slots_len
173        ).try_into().unwrap();
174
175        match index.checked_sub(D::LEN) {
176            None => index,
177            Some(offset) => self.remap.index(offset).try_into().unwrap()
178        }
179    }
180
181    pub fn get<Q>(&self, key: &Q) -> Option<D::Value>
182    where
183        D::Key: Borrow<Q>,
184        Q: Hash + Eq + ?Sized
185    {
186        if self.is_empty() {
187            return None;
188        }
189        
190        let index = self.inner_get(key);
191        if self.data.get_key(index).borrow() == key {
192            Some(self.data.get_value(index))
193        } else {
194            None
195        }
196    }
197
198    pub const fn iter(&self) -> store::MapIter<'_, 'data, D> {
199        store::MapIter::new(&self.data)
200    }    
201}
202
203// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
204#[inline]
205fn fast_reduct32(x: u32, limit: u32) -> u32 {
206    (((x as u64) * (limit as u64)) >> 32) as u32
207}
208
209#[inline]
210fn low(v: u64) -> u32 {
211    v as u32
212}
213
214#[inline]
215fn high(v: u64) -> u32 {
216    (v >> 32) as u32
217}
precomputed_map/lib.rs

precomputed_map/
lib.rs
