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

precomputed_map/
lib.rs
