entropy_map/
map_with_dict_bitpacked.rs

1//! A module offering `MapWithDictBitpacked`, an efficient, immutable hash map implementation.
2//!
3//! `MapWithDictBitpacked` is a specialized version of `MapWithDict` optimized for memory usage
4//! by bit-packing its values. It uses a minimal perfect hash function (MPHF) for key indexing.
5//! Unlike `MapWithDict`, this variant stores unique `Vec<u32>` values bit-packed to the minimum
6//! possible number of bits in the byte dictionary. All values vectors *must* have same length, so
7//! that we don't need to store it which further reduces memory footprint of data structure.
8//!
9//! The structure excels in scenarios where values are within a limited range and can be encoded
10//! efficiently into bits. The MPHF grants direct key index access, mapping to bit-packed values
11//! stored in the byte dictionary. Keys are maintained for validation during retrieval. A `get`
12//! query for a non-existent key at construction returns `false`, similar to `MapWithDict`.
13
14use std::borrow::Borrow;
15use std::collections::HashMap;
16use std::hash::{Hash, Hasher};
17use std::mem::size_of_val;
18
19use bitpacking::{BitPacker, BitPacker1x};
20use num::{PrimInt, Unsigned};
21use wyhash::WyHash;
22
23use crate::mphf::{Mphf, DEFAULT_GAMMA};
24
25/// An efficient, immutable hash map with bit-packed `Vec<u32>` values for optimized space usage.
26///
27/// # Serde and untrusted input
28///
29/// Deserialization performs best-effort consistency checks (key/MPHF alignment, value index
30/// bounds, `num_bits <= 32`), but does **not** verify that every dictionary entry covers its
31/// packed blocks. A crafted payload can therefore pass deserialization and later panic in
32/// [`get_values`](Self::get_values)/[`values`](Self::values)/[`iter`](Self::iter). Only
33/// deserialize payloads you trust; do not treat this type as a security boundary.
34#[derive(Default)]
35#[cfg_attr(feature = "rkyv_derive", derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize))]
36#[cfg_attr(feature = "rkyv_derive", archive_attr(derive(rkyv::CheckBytes)))]
37#[cfg_attr(feature = "serde", derive(serde::Serialize))]
38#[cfg_attr(
39    feature = "serde",
40    serde(bound(serialize = "K: serde::Serialize, ST: serde::Serialize"))
41)]
42pub struct MapWithDictBitpacked<K, const B: usize = 32, const S: usize = 8, ST = u8, H = WyHash>
43where
44    ST: PrimInt + Unsigned,
45    H: Hasher + Default,
46{
47    /// Minimally Perfect Hash Function for keys indices retrieval
48    mphf: Mphf<B, S, ST, H>,
49    /// Map keys
50    keys: Box<[K]>,
51    /// Points to the value index in the dictionary
52    values_index: Box<[usize]>,
53    /// Bit-packed dictionary containing values
54    #[cfg_attr(feature = "serde", serde(with = "serde_bytes"))]
55    values_dict: Box<[u8]>,
56}
57
58#[cfg(feature = "serde")]
59#[derive(serde::Deserialize)]
60#[serde(bound(deserialize = "K: serde::Deserialize<'de>, ST: serde::Deserialize<'de>"))]
61struct MapWithDictBitpackedUnchecked<K, const B: usize = 32, const S: usize = 8, ST = u8, H = WyHash>
62where
63    ST: PrimInt + Unsigned,
64    H: Hasher + Default,
65{
66    mphf: Mphf<B, S, ST, H>,
67    keys: Box<[K]>,
68    values_index: Box<[usize]>,
69    #[serde(with = "serde_bytes")]
70    values_dict: Box<[u8]>,
71}
72
73/// Implements `Deserialize` with best-effort structural validation.
74/// See the type-level documentation for the untrusted-input caveat: packed-block
75/// coverage is not yet validated.
76#[cfg(feature = "serde")]
77impl<'de, K, const B: usize, const S: usize, ST, H> serde::Deserialize<'de> for MapWithDictBitpacked<K, B, S, ST, H>
78where
79    K: serde::Deserialize<'de> + Hash,
80    ST: serde::Deserialize<'de> + PrimInt + Unsigned,
81    H: Hasher + Default,
82{
83    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
84    where
85        D: serde::Deserializer<'de>,
86    {
87        use crate::{ValidateKeyResult, ValidateValueResult};
88        use serde::de::Error;
89
90        let this = MapWithDictBitpackedUnchecked::deserialize(deserializer)?;
91
92        this.mphf.validate_keys(&this.keys).map_err(|e| match e {
93            ValidateKeyResult::InvalidKeyCount => {
94                Error::custom("key count should equal the number of set bits in the MPHF")
95            }
96            ValidateKeyResult::IncorrectKeyOrder => Error::custom("keys should correspond to MPHF index"),
97        })?;
98
99        this.mphf
100            .validate_values(&this.keys, &this.values_index, &this.values_dict)
101            .map_err(|e| match e {
102                ValidateValueResult::KeyValueLenMismatch => Error::custom("key count should equal value count"),
103                ValidateValueResult::InvalidValueIndex => Error::custom("value index is out of bounds of value dict"),
104            })?;
105
106        if this.values_index.iter().any(|&i| this.values_dict[i] > 32) {
107            return Err(Error::custom("value index out of num_bits bounds"));
108        }
109
110        Ok(Self {
111            mphf: this.mphf,
112            keys: this.keys,
113            values_index: this.values_index,
114            values_dict: this.values_dict,
115        })
116    }
117}
118
119/// Errors that can occur when constructing `MapWithDictBitpacked`.
120#[derive(Debug)]
121pub enum Error {
122    /// Error occurred during mphf construction
123    MphfError(crate::mphf::MphfError),
124    /// Values lengths are not equal
125    NotEqualValuesLengths,
126}
127
128impl<K, const B: usize, const S: usize, ST, H> MapWithDictBitpacked<K, B, S, ST, H>
129where
130    K: Hash + PartialEq + Clone,
131    ST: PrimInt + Unsigned,
132    H: Hasher + Default,
133{
134    /// Constructs a `MapWithDictBitpacked` from an iterator of key-value pairs and MPHF function params.
135    pub fn from_iter_with_params<I>(iter: I, gamma: f32) -> Result<Self, Error>
136    where
137        I: IntoIterator<Item = (K, Vec<u32>)>,
138    {
139        let mut keys = vec![];
140        let mut offsets_cache = HashMap::new();
141        let mut values_index = vec![];
142        let mut values_dict = vec![];
143
144        let mut iter = iter.into_iter().peekable();
145        let v_len = iter.peek().map_or(0, |(_, v)| v.len());
146
147        for (k, v) in iter {
148            keys.push(k.clone());
149
150            if v.len() != v_len {
151                return Err(Error::NotEqualValuesLengths);
152            }
153
154            if let Some(&offset) = offsets_cache.get(&v) {
155                // re-use dictionary offset if found in cache
156                values_index.push(offset);
157            } else {
158                // store current dictionary length as an offset in both index and cache
159                let offset = values_dict.len();
160                offsets_cache.insert(v.clone(), offset);
161                values_index.push(offset);
162
163                // append packed values to the dictionary
164                pack_values(&v, &mut values_dict);
165            }
166        }
167
168        // pad dictionary to the values block size in bytes for smooth SIMD decoding
169        values_dict.resize(values_dict.len() + 4 * VALUES_BLOCK_LEN, 0);
170
171        let mphf = Mphf::from_slice(&keys, gamma).map_err(Error::MphfError)?;
172
173        // Re-order keys and values_index according to mphf
174        for i in 0..keys.len() {
175            loop {
176                let idx = mphf.get(&keys[i]).unwrap();
177                if idx == i {
178                    break;
179                }
180                keys.swap(i, idx);
181                values_index.swap(i, idx);
182            }
183        }
184
185        Ok(MapWithDictBitpacked {
186            mphf,
187            keys: keys.into_boxed_slice(),
188            values_index: values_index.into_boxed_slice(),
189            values_dict: values_dict.into_boxed_slice(),
190        })
191    }
192
193    /// Updates `values` to the array of values corresponding to the key. Returns `false` if the
194    /// key is not not present in the map.
195    ///
196    /// # Examples
197    /// ```
198    /// # use std::collections::HashMap;
199    /// # use entropy_map::MapWithDictBitpacked;
200    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(1, vec![2]), (3, vec![4])])).unwrap();
201    /// let mut values = [0];
202    /// assert_eq!(map.get_values(&1, &mut values), true);
203    /// assert_eq!(values, [2]);
204    /// assert_eq!(map.get_values(&2, &mut values), false);
205    /// ```
206    ///
207    /// # Panics
208    ///
209    /// Panics if `self` was deserialized from a crafted payload whose dictionary entry is
210    /// truncated (see the type-level note about untrusted input).
211    #[inline]
212    pub fn get_values<Q>(&self, key: &Q, values: &mut [u32]) -> bool
213    where
214        K: Borrow<Q> + PartialEq<Q>,
215        Q: Hash + Eq + ?Sized,
216    {
217        let idx = match self.mphf.get(key) {
218            Some(idx) => idx,
219            None => return false,
220        };
221
222        // SAFETY: `idx` is always within bounds (ensured during construction)
223        unsafe {
224            if self.keys.get_unchecked(idx) != key {
225                return false;
226            }
227
228            // SAFETY: `idx` and `value_idx` are always within bounds (ensure during construction)
229            let value_idx = *self.values_index.get_unchecked(idx);
230            let dict = self.values_dict.get_unchecked(value_idx..);
231            unpack_values(dict, values);
232        }
233
234        true
235    }
236
237    /// Returns the number of keys in the map.
238    ///
239    /// # Examples
240    /// ```
241    /// # use std::collections::HashMap;
242    /// # use entropy_map::MapWithDictBitpacked;
243    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(1, vec![2]), (3, vec![4])])).unwrap();
244    /// assert_eq!(map.len(), 2);
245    /// ```
246    #[inline]
247    pub fn len(&self) -> usize {
248        self.keys.len()
249    }
250
251    /// Returns `true` if the map contains no elements.
252    ///
253    /// # Examples
254    /// ```
255    /// # use std::collections::HashMap;
256    /// # use entropy_map::MapWithDictBitpacked;
257    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(0, vec![0]); 0])).unwrap();
258    /// assert_eq!(map.is_empty(), true);
259    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(1, vec![2]), (3, vec![4])])).unwrap();
260    /// assert_eq!(map.is_empty(), false);
261    /// ```
262    #[inline]
263    pub fn is_empty(&self) -> bool {
264        self.keys.is_empty()
265    }
266
267    /// Checks if the map contains the specified key.
268    ///
269    /// # Examples
270    /// ```
271    /// # use std::collections::HashMap;
272    /// # use entropy_map::MapWithDictBitpacked;
273    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(1, vec![2]), (3, vec![4])])).unwrap();
274    /// assert_eq!(map.contains_key(&1), true);
275    /// assert_eq!(map.contains_key(&2), false);
276    /// ```
277    #[inline]
278    pub fn contains_key<Q>(&self, key: &Q) -> bool
279    where
280        K: Borrow<Q> + PartialEq<Q>,
281        Q: Hash + Eq + ?Sized,
282    {
283        if let Some(idx) = self.mphf.get(key) {
284            // SAFETY: `idx` is always within bounds (ensured during construction)
285            unsafe { self.keys.get_unchecked(idx) == key }
286        } else {
287            false
288        }
289    }
290
291    /// Returns an iterator over the map, yielding key-value pairs.
292    ///
293    /// # Examples
294    /// ```
295    /// # use std::collections::HashMap;
296    /// # use entropy_map::MapWithDictBitpacked;
297    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(1, vec![2]), (3, vec![4])])).unwrap();
298    /// for (key, val) in map.iter(1) {
299    ///     println!("key: {key} val: {val:?}");
300    /// }
301    /// ```
302    #[inline]
303    pub fn iter(&self, n: usize) -> impl Iterator<Item = (&K, Vec<u32>)> {
304        self.keys().zip(self.values_index.iter()).map(move |(key, &value_idx)| {
305            let mut values = vec![0; n];
306            // SAFETY: `value_idx` is always within bounds (ensured during construction)
307            let dict = unsafe { self.values_dict.get_unchecked(value_idx..) };
308            unpack_values(dict, &mut values);
309            (key, values)
310        })
311    }
312
313    /// Returns an iterator over the keys of the map.
314    ///
315    /// # Examples
316    /// ```
317    /// # use std::collections::HashMap;
318    /// # use entropy_map::MapWithDictBitpacked;
319    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(1, vec![2]), (3, vec![4])])).unwrap();
320    /// for key in map.keys() {
321    ///     println!("{key}");
322    /// }
323    /// ```
324    #[inline]
325    pub fn keys(&self) -> impl Iterator<Item = &K> {
326        self.keys.iter()
327    }
328
329    /// Returns an iterator over the values of the map.
330    ///
331    /// # Examples
332    /// ```
333    /// # use std::collections::HashMap;
334    /// # use entropy_map::MapWithDictBitpacked;
335    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(1, vec![2]), (3, vec![4])])).unwrap();
336    /// for val in map.values(1) {
337    ///     println!("{val:?}");
338    /// }
339    /// ```
340    #[inline]
341    pub fn values(&self, n: usize) -> impl Iterator<Item = Vec<u32>> + '_ {
342        self.values_index.iter().map(move |&value_idx| {
343            let mut values = vec![0; n];
344            // SAFETY: `value_idx` is always within bounds (ensured during construction)
345            let dict = unsafe { self.values_dict.get_unchecked(value_idx..) };
346            unpack_values(dict, &mut values);
347            values
348        })
349    }
350
351    /// Returns the total number of bytes occupied by the structure.
352    ///
353    /// # Examples
354    /// ```
355    /// # use std::collections::HashMap;
356    /// # use entropy_map::MapWithDictBitpacked;
357    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(1, vec![2]), (3, vec![4])])).unwrap();
358    /// assert_eq!(map.size(), 394);
359    /// ```
360    pub fn size(&self) -> usize {
361        size_of_val(self)
362            + self.mphf.size()
363            + size_of_val(self.keys.as_ref())
364            + size_of_val(self.values_index.as_ref())
365            + size_of_val(self.values_dict.as_ref())
366    }
367}
368
369/// Creates a `MapWithDictBitpacked` from a `HashMap`.
370impl<K> TryFrom<HashMap<K, Vec<u32>>> for MapWithDictBitpacked<K>
371where
372    K: PartialEq + Hash + Clone,
373{
374    type Error = Error;
375
376    #[inline]
377    fn try_from(value: HashMap<K, Vec<u32>>) -> Result<Self, Self::Error> {
378        MapWithDictBitpacked::from_iter_with_params(value, DEFAULT_GAMMA)
379    }
380}
381
382/// Number of values bit-packed in one batch
383const VALUES_BLOCK_LEN: usize = BitPacker1x::BLOCK_LEN;
384
385/// `pack_values` bit-packs every values block and adds it to the dictionary,
386/// each block consists of bits width followed by bit-packed integers bytes
387fn pack_values(values: &[u32], dict: &mut Vec<u8>) {
388    // initialize bit packer and buffers to be used for bit-packing
389    let bitpacker = BitPacker1x::new();
390
391    for block in values.chunks(VALUES_BLOCK_LEN) {
392        let mut values_block = [0u32; VALUES_BLOCK_LEN];
393        let mut values_packed_block = [0u8; 4 * VALUES_BLOCK_LEN];
394
395        values_block[..block.len()].copy_from_slice(block);
396
397        // compute minimal bits width needed to encode each value in the block
398        let num_bits = bitpacker.num_bits(&values_block);
399
400        // bit-pack values block
401        bitpacker.compress(&values_block, &mut values_packed_block, num_bits);
402
403        // append bits width and bit-packed values block to the dictionary
404        let size = (block.len() * (num_bits as usize)).div_ceil(8);
405        dict.push(num_bits);
406        dict.extend_from_slice(&values_packed_block[..size]);
407    }
408}
409
410/// `unpack_values` bit-unpacks every values block and adds its values to the result,
411/// each block consists of bits width followed by bit-packed integers bytes
412fn unpack_values(dict: &[u8], res: &mut [u32]) {
413    let bitpacker = BitPacker1x::new();
414    let mut dict = dict;
415    for block in res.chunks_mut(VALUES_BLOCK_LEN) {
416        let mut values_block = [0u32; VALUES_BLOCK_LEN];
417
418        // fetch bits width
419        let num_bits = dict[0];
420        dict = &dict[1..];
421
422        // bit-unpack values block
423        let size = (block.len() * (num_bits as usize)).div_ceil(8);
424        bitpacker.decompress(dict, &mut values_block, num_bits);
425        dict = &dict[size..];
426
427        block.copy_from_slice(&values_block[..block.len()]);
428    }
429}
430
431/// Implement `get` for `Archived` version of `MapWithDictBitpacked` if feature is enabled
432#[cfg(feature = "rkyv_derive")]
433impl<K, const B: usize, const S: usize, ST, H> ArchivedMapWithDictBitpacked<K, B, S, ST, H>
434where
435    K: PartialEq + Hash + rkyv::Archive,
436    K::Archived: PartialEq<K>,
437    ST: PrimInt + Unsigned + rkyv::Archive<Archived = ST>,
438    H: Hasher + Default,
439{
440    /// Updates `values` to the array of values corresponding to the key. Returns `false` if the
441    /// key is not not present in the map.
442    ///
443    /// # Examples
444    /// ```
445    /// # use std::collections::HashMap;
446    /// # use entropy_map::MapWithDictBitpacked;
447    /// let map = MapWithDictBitpacked::try_from(HashMap::from([(1, vec![2]), (3, vec![4])])).unwrap();
448    /// let archived_map = rkyv::from_bytes::<MapWithDictBitpacked<u32>>(
449    ///     &rkyv::to_bytes::<_, 1024>(&map).unwrap()
450    /// ).unwrap();
451    /// let mut values = [0];
452    /// assert_eq!(archived_map.get_values(&1, &mut values), true);
453    /// assert_eq!(values, [2]);
454    /// assert_eq!(archived_map.get_values(&2, &mut values), false);
455    /// ```
456    #[inline]
457    pub fn get_values(&self, key: &K, values: &mut [u32]) -> bool {
458        let idx = match self.mphf.get(key) {
459            Some(idx) => idx,
460            None => return false,
461        };
462
463        // SAFETY: `idx` is always within bounds (ensured during construction)
464        unsafe {
465            if self.keys.get_unchecked(idx) != key {
466                return false;
467            }
468
469            // SAFETY: `idx` and `value_idx` are always within bounds (ensure during construction)
470            let value_idx = *self.values_index.get_unchecked(idx) as usize;
471            let dict = self.values_dict.get_unchecked(value_idx..);
472            unpack_values(dict, values);
473        }
474
475        true
476    }
477}
478
479#[cfg(test)]
480mod tests {
481    use super::*;
482    use paste::paste;
483    use proptest::prelude::*;
484    use rand::{Rng, SeedableRng};
485    use rand_chacha::ChaCha8Rng;
486    use std::collections::{hash_map::RandomState, HashSet};
487    use test_case::test_case;
488
489    #[test_case(
490        &[] => Vec::<u8>::new();
491        "empty values"
492    )]
493    #[test_case(
494        &[0] => vec![0];
495        "single 0-bit value"
496    )]
497    #[test_case(
498        &[0; 10] => vec![0];
499        "10 0-bit value"
500    )]
501    #[test_case(
502        &[0; 77] => vec![0, 0, 0];
503        "77 0-bit values (3 blocks)"
504    )]
505    #[test_case(
506        &[1] => vec![1, 1];
507        "single 1-bit value"
508    )]
509    #[test_case(
510        &[1; 10] => vec![1, 0b11111111, 0b00000011];
511        "10 1-bit value"
512    )]
513    #[test_case(
514        &[1; 32] => vec![1, 0b11111111, 0b11111111, 0b11111111, 0b11111111];
515        "32 1-bit value"
516    )]
517    #[test_case(
518        &[1; 33] => vec![1, 0b11111111, 0b11111111, 0b11111111, 0b11111111, 1, 0b00000001];
519        "33 1-bit value"
520    )]
521    #[test_case(
522        &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => vec![4, 0b0010_0001, 0b0100_0011, 0b0110_0101, 0b1000_0111, 0b1010_1001];
523        "10 4-bit value"
524    )]
525    fn test_pack_unpack(values: &[u32]) -> Vec<u8> {
526        let mut dict = vec![];
527        pack_values(values, &mut dict);
528
529        let mut padded_dict = dict.clone();
530        padded_dict.resize(dict.len() + 4 * VALUES_BLOCK_LEN, 0);
531
532        let mut unpacked_values = vec![0; values.len()];
533        unpack_values(&padded_dict, &mut unpacked_values);
534
535        assert_eq!(values, unpacked_values);
536
537        dict
538    }
539
540    #[test]
541    fn test_pack_unpack_random() {
542        let max_n = 200;
543        let mut rng = ChaCha8Rng::seed_from_u64(123);
544        let mut dict = vec![];
545        let mut values = vec![];
546        let mut unpacked_values = vec![];
547
548        for n in 1..=max_n {
549            for num_bits in 0..=32 {
550                values.clear();
551                values.extend((0..n).map(|_| rng.gen::<u32>() & ((1u32 << (num_bits % 32)) - 1)));
552                dict.clear();
553
554                pack_values(&values, &mut dict);
555                assert!(!dict.is_empty());
556
557                dict.resize(dict.len() + 4 * VALUES_BLOCK_LEN, 0);
558                unpacked_values.resize(n, 0);
559                unpack_values(&dict, &mut unpacked_values);
560
561                assert_eq!(values, unpacked_values);
562            }
563        }
564    }
565
566    fn gen_map(items_num: usize, values_num: usize) -> HashMap<u64, Vec<u32>> {
567        let mut rng = ChaCha8Rng::seed_from_u64(123);
568
569        (0..items_num)
570            .map(|_| {
571                let key = rng.gen::<u64>();
572                let value = (0..values_num).map(|_| rng.gen_range(1..=10)).collect();
573                (key, value)
574            })
575            .collect()
576    }
577
578    #[test]
579    fn test_map_with_dict_bitpacked() {
580        let items_num = 1000;
581        let values_num = 10;
582        let original_map = gen_map(items_num, values_num);
583
584        let map = MapWithDictBitpacked::try_from(original_map.clone()).unwrap();
585
586        // Test len
587        assert_eq!(map.len(), original_map.len());
588
589        // Test is_empty
590        assert_eq!(map.is_empty(), original_map.is_empty());
591
592        // Test get_values, contains_key
593        let mut values_buf = vec![0; values_num];
594        for (key, value) in &original_map {
595            assert!(map.get_values(key, &mut values_buf));
596            assert_eq!(value, &values_buf);
597            assert!(map.contains_key(key));
598        }
599
600        // Test iter
601        for (&k, v) in map.iter(values_num) {
602            assert_eq!(original_map.get(&k), Some(&v));
603        }
604
605        // Test keys
606        for k in map.keys() {
607            assert!(original_map.contains_key(k));
608        }
609
610        // Test values
611        for v in map.values(values_num) {
612            assert!(original_map.values().any(|val| val == &v));
613        }
614
615        // Test size
616        assert_eq!(map.size(), 22664);
617    }
618
619    #[cfg(feature = "rkyv_derive")]
620    #[test]
621    fn test_rkyv() {
622        // create regular `HashMap`, then `MapWithDictBitpacked`, then serialize to `rkyv` bytes.
623        let items_num = 1000;
624        let values_num = 10;
625        let original_map = gen_map(items_num, values_num);
626        let map = MapWithDictBitpacked::try_from(original_map.clone()).unwrap();
627        let rkyv_bytes = rkyv::to_bytes::<_, 1024>(&map).unwrap();
628
629        let rkyv_map = rkyv::check_archived_root::<MapWithDictBitpacked<u64>>(&rkyv_bytes).unwrap();
630
631        // Test get_values on `Archived` version of `MapWithDictBitpacked`
632        let mut values_buf = vec![0; values_num];
633        for (k, v) in original_map {
634            rkyv_map.get_values(&k, &mut values_buf);
635            assert_eq!(v, values_buf);
636        }
637    }
638
639    #[cfg(feature = "serde")]
640    #[test]
641    fn test_serde() {
642        // create regular `HashMap`, then `MapWithDictBitpacked`, then serialize to msgpack bytes.
643        let items_num = 1000;
644        let values_num = 10;
645        let original_map = gen_map(items_num, values_num);
646        let map = MapWithDictBitpacked::try_from(original_map.clone()).unwrap();
647
648        let bytes = rmp_serde::to_vec(&map).unwrap();
649        let de: MapWithDictBitpacked<u64> = rmp_serde::from_slice(&bytes).unwrap();
650
651        assert_eq!(de.len(), original_map.len());
652
653        // Test get_values on the deserialized `MapWithDictBitpacked`
654        let mut values_buf = vec![0; values_num];
655        for (k, v) in &original_map {
656            assert!(de.get_values(k, &mut values_buf));
657            assert_eq!(v, &values_buf);
658        }
659    }
660
661    macro_rules! proptest_map_with_dict_bitpacked_model {
662        ($(($b:expr, $s:expr, $gamma:expr, $n:expr)),* $(,)?) => {
663            $(
664                paste! {
665                    proptest! {
666                        #[test]
667                        fn [<proptest_map_with_dict_bitpacked_model_ $b _ $s _ $n _ $gamma>](model: HashMap<u64, [u32; $n]>, arbitrary: HashSet<u64>) {
668                            let entropy_map: MapWithDictBitpacked<u64, $b, $s> = MapWithDictBitpacked::from_iter_with_params(
669                                model.iter().map(|(&k, v)| (k, Vec::from(v))),
670                                $gamma as f32 / 100.0
671                            ).unwrap();
672
673                            // Assert that length matches model.
674                            assert_eq!(entropy_map.len(), model.len());
675                            assert_eq!(entropy_map.is_empty(), model.is_empty());
676
677                            // Assert that keys and values match model.
678                            assert_eq!(
679                                HashSet::<_, RandomState>::from_iter(entropy_map.keys()),
680                                HashSet::from_iter(model.keys())
681                            );
682                            assert_eq!(
683                                HashSet::<_, RandomState>::from_iter(entropy_map.values($n)),
684                                HashSet::from_iter(model.values().map(Vec::from))
685                            );
686
687                            // Assert that contains and get operations match model for contained elements.
688                            for (k, v) in &model {
689                                assert!(entropy_map.contains_key(&k));
690
691                                let mut buf = [0u32; $n];
692                                assert!(entropy_map.get_values(&k, &mut buf));
693                                assert_eq!(&buf, v);
694                            }
695
696                            // Assert that contains and get operations match model for random elements.
697                            for k in arbitrary {
698                                assert_eq!(
699                                    model.contains_key(&k),
700                                    entropy_map.contains_key(&k),
701                                );
702                                let mut buf = [0u32; $n];
703                                let contains = entropy_map.get_values(&k, &mut buf);
704                                assert_eq!(contains, model.contains_key(&k));
705                                if contains {
706                                    assert_eq!(Some(&buf), model.get(&k));
707                                }
708                            }
709                        }
710                    }
711                }
712            )*
713        };
714    }
715
716    proptest_map_with_dict_bitpacked_model!(
717        // (1, 8, 100),
718        (2, 8, 100, 10),
719        (4, 8, 100, 10),
720        (7, 8, 100, 10),
721        (8, 8, 100, 10),
722        (15, 8, 100, 10),
723        (16, 8, 100, 10),
724        (23, 8, 100, 10),
725        (24, 8, 100, 10),
726        (31, 8, 100, 10),
727        (32, 8, 100, 10),
728        (33, 8, 100, 10),
729        (48, 8, 100, 10),
730        (53, 8, 100, 10),
731        (61, 8, 100, 10),
732        (63, 8, 100, 10),
733        (64, 8, 100, 10),
734        (32, 7, 100, 10),
735        (32, 5, 100, 10),
736        (32, 4, 100, 10),
737        (32, 3, 100, 10),
738        (32, 1, 100, 10),
739        (32, 0, 100, 10),
740        (32, 8, 200, 10),
741        (32, 6, 200, 10),
742    );
743}
entropy_map/map_with_dict_bitpacked.rs

entropy_map/
map_with_dict_bitpacked.rs
