ptr_hash/
pack.rs

1//! The `Packed` and `MutPacked` traits are used for the underlying storage of
2//! the remap vector.
3//!
4//! This is implemented for `Vec<u8|u16|u32|u64>`, `CachelineEfVec`, and `EliasFano` from `sucds`.
5//! `Packed` is also implemented for respective non-owning (slice) types to support epserde.
6
7use sucds::mii_sequences::EliasFanoBuilder;
8
9use cacheline_ef::{CachelineEf, CachelineEfVec};
10
11/// A trait for backing storage types.
12pub trait Packed: Sync {
13    /// This uses get_unchecked internally, so you must ensure that index is within bounds.
14    fn index(&self, index: usize) -> u64;
15    /// Prefetch the element at the given index.
16    fn prefetch(&self, _index: usize) {}
17    /// Size in bytes.
18    fn size_in_bytes(&self) -> usize;
19}
20
21/// An extension of Packed that can be used during construction.
22pub trait MutPacked: Packed + Sized {
23    fn default() -> Self;
24    fn try_new(vals: Vec<u64>) -> Option<Self>;
25    fn name() -> String;
26}
27
28macro_rules! vec_impl {
29    ($t:ty) => {
30        impl MutPacked for Vec<$t> {
31            fn default() -> Self {
32                Default::default()
33            }
34            fn try_new(vals: Vec<u64>) -> Option<Self> {
35                Some(
36                    vals.into_iter()
37                        .map(|x| {
38                            x.try_into()
39                                .expect(&format!("Value {x} is larger than backing type can hold."))
40                        })
41                        .collect(),
42                )
43            }
44            fn name() -> String {
45                stringify!(Vec<$t>).to_string()
46            }
47        }
48        impl Packed for Vec<$t> {
49            fn index(&self, index: usize) -> u64 {
50                unsafe { (*self.get_unchecked(index)) as u64 }
51            }
52            fn prefetch(&self, index: usize) {
53                crate::util::prefetch_index(self, index);
54            }
55            fn size_in_bytes(&self) -> usize {
56                std::mem::size_of_val(self.as_slice())
57            }
58        }
59    };
60}
61
62vec_impl!(u8);
63vec_impl!(u16);
64vec_impl!(u32);
65vec_impl!(u64);
66
67macro_rules! slice_impl {
68    ($t:ty) => {
69        impl Packed for [$t] {
70            fn index(&self, index: usize) -> u64 {
71                unsafe { (*self.get_unchecked(index)) as u64 }
72            }
73            fn prefetch(&self, index: usize) {
74                crate::util::prefetch_index(self, index);
75            }
76            fn size_in_bytes(&self) -> usize {
77                std::mem::size_of_val(self)
78            }
79        }
80    };
81}
82
83slice_impl!(u8);
84slice_impl!(u16);
85slice_impl!(u32);
86slice_impl!(u64);
87
88impl MutPacked for CachelineEfVec<Vec<CachelineEf>> {
89    fn default() -> Self {
90        Default::default()
91    }
92    fn try_new(vals: Vec<u64>) -> Option<Self> {
93        Self::try_new(&vals)
94    }
95    fn name() -> String {
96        "CacheLineEF".to_string()
97    }
98}
99
100impl<T: AsRef<[CachelineEf]> + Sync> Packed for CachelineEfVec<T> {
101    fn index(&self, index: usize) -> u64 {
102        unsafe { self.index_unchecked(index) }
103    }
104    fn prefetch(&self, index: usize) {
105        self.prefetch(index)
106    }
107    fn size_in_bytes(&self) -> usize {
108        self.size_in_bytes()
109    }
110}
111
112/// Wrapper around the Sucds implementation.
113pub struct EliasFano(sucds::mii_sequences::EliasFano);
114
115impl MutPacked for EliasFano {
116    fn default() -> Self {
117        EliasFano(Default::default())
118    }
119
120    fn try_new(vals: Vec<u64>) -> Option<Self> {
121        if vals.is_empty() {
122            Some(Self::default())
123        } else {
124            let mut builder =
125                EliasFanoBuilder::new(*vals.last().unwrap() as usize + 1, vals.len()).unwrap();
126            builder.extend(vals.iter().map(|&x| x as usize)).unwrap();
127            Some(EliasFano(builder.build()))
128        }
129    }
130    fn name() -> String {
131        "EF".to_string()
132    }
133}
134
135impl Packed for EliasFano {
136    fn index(&self, index: usize) -> u64 {
137        self.0.select(index as _).unwrap() as u64
138    }
139
140    fn size_in_bytes(&self) -> usize {
141        sucds::Serializable::size_in_bytes(&self.0)
142    }
143}
ptr_hash/pack.rs

ptr_hash/
pack.rs
