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        let index = self.inner_get(key);
105        if self.data.get_key(index).borrow() == key {
106            Some(self.data.get_value(index))
107        } else {
108            None
109        }
110    }
111
112    pub const fn iter(&self) -> store::MapIter<'_, 'data, D> {
113        store::MapIter::new(&self.data)
114    }    
115}
116
117/// Medium map
118///
119/// 1024..10M
120pub struct MediumMap<'data, P, R, D, H> {
121    seed: u64,
122    slots: u32,
123    pilots: P,
124    remap: R,
125    data: D,
126    _phantom: PhantomData<&'data (P, D, R, H)>
127}
128
129impl<'data, P, R, D, H> MediumMap<'data, P, R, D, H>
130where
131    P: AccessSeq<'data, Item = u8>,
132    R: AccessSeq<'data, Item = u32>,
133    D: MapStore<'data>,
134    D::Key: Hash + Eq + Copy,
135    H: HashOne
136{
137    pub const fn new(seed: u64, slots: u32, pilots: P, remap: R, data: D)
138        -> MediumMap<'data, P, R, D, H>
139    {
140        MediumMap {
141            seed, slots, pilots, remap, data,
142            _phantom: PhantomData
143        }
144    }
145
146    pub const fn len(&self) -> usize {
147        D::LEN
148    }    
149
150    pub const fn is_empty(&self) -> bool {
151        self.len() == 0
152    }
153
154    #[inline]
155    fn inner_get<Q>(&self, key: &Q) -> usize
156    where
157        Q: Hash + ?Sized
158    {
159        let pilots_len: u32 = P::LEN.try_into().unwrap();
160        let slots_len: u32 = self.slots;
161        
162        let hash = H::hash_one(self.seed, key);
163        let bucket: usize = fast_reduct32(low(hash), pilots_len).try_into().unwrap();
164        let pilot = self.pilots.index(bucket);
165        let pilot_hash = phf::hash_pilot(self.seed, pilot);
166        let index: usize = fast_reduct32(
167            high(hash) ^ high(pilot_hash) ^ low(pilot_hash),
168            slots_len
169        ).try_into().unwrap();
170
171        match index.checked_sub(D::LEN) {
172            None => index,
173            Some(offset) => self.remap.index(offset).try_into().unwrap()
174        }
175    }
176
177    pub fn get<Q>(&self, key: &Q) -> Option<D::Value>
178    where
179        D::Key: Borrow<Q>,
180        Q: Hash + Eq + ?Sized
181    {
182        let index = self.inner_get(key);
183        if self.data.get_key(index).borrow() == key {
184            Some(self.data.get_value(index))
185        } else {
186            None
187        }
188    }
189
190    pub const fn iter(&self) -> store::MapIter<'_, 'data, D> {
191        store::MapIter::new(&self.data)
192    }    
193}
194
195// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
196#[inline]
197fn fast_reduct32(x: u32, limit: u32) -> u32 {
198    (((x as u64) * (limit as u64)) >> 32) as u32
199}
200
201#[inline]
202fn low(v: u64) -> u32 {
203    v as u32
204}
205
206#[inline]
207fn high(v: u64) -> u32 {
208    (v >> 32) as u32
209}
precomputed_map/lib.rs

precomputed_map/
lib.rs
