sparse_hash_map/
growth_policy.rs

1//! Growth policies that map a hash to a bucket and decide the next table size.
2//!
3//! A policy owns the current bucket count and translates a hash into a bucket
4//! index. Three strategies are provided:
5//!
6//! - [`PowerOfTwo`] keeps the bucket count a power of two and maps with a mask.
7//!   Fast, and the default.
8//! - [`Mod`] grows by a rational factor and maps with a modulo. Useful for
9//!   slower growth.
10//! - [`Prime`] uses a fixed table of primes. It spreads values better when the
11//!   hash function is poor, such as an identity hash of pointers.
12//!
13//! Each policy is constructed from a minimum bucket count. The policy may round
14//! that value up and reports the value it settled on. A request above the
15//! policy maximum returns [`LengthError`].
16
17/// The requested bucket count exceeds what a growth policy can represent.
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub struct LengthError;
20
21impl core::fmt::Display for LengthError {
22    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
23        f.write_str("the hash table exceeds its maximum size")
24    }
25}
26
27impl std::error::Error for LengthError {}
28
29/// Strategy for sizing the bucket array and mapping a hash to a bucket.
30///
31/// A policy is created with [`GrowthPolicy::new`], which returns the policy and
32/// the bucket count it settled on. That count is at least the requested
33/// minimum. [`GrowthPolicy::bucket_for_hash`] and [`GrowthPolicy::clear`] must
34/// not allocate or panic.
35pub trait GrowthPolicy: Clone {
36    /// Build a policy for at least `min_bucket_count` buckets.
37    ///
38    /// Returns the policy and the bucket count it settled on. That count is the
39    /// requested minimum rounded up as the policy requires. Returns
40    /// [`LengthError`] when the request is above [`GrowthPolicy::max_bucket_count`].
41    ///
42    /// When `min_bucket_count` is 0 the settled count is 0 and
43    /// `bucket_for_hash` returns 0 for every hash.
44    fn new(min_bucket_count: usize) -> Result<(Self, usize), LengthError>;
45
46    /// Map `hash` to a bucket in `[0, bucket_count)`.
47    fn bucket_for_hash(&self, hash: usize) -> usize;
48
49    /// The bucket count to use on the next growth.
50    ///
51    /// Returns [`LengthError`] when the table cannot grow further.
52    fn next_bucket_count(&self) -> Result<usize, LengthError>;
53
54    /// The largest bucket count the policy can represent.
55    fn max_bucket_count(&self) -> usize;
56
57    /// Reset the policy to the state of a 0-bucket table.
58    fn clear(&mut self);
59
60    /// Whether this policy keeps the bucket count a power of two.
61    ///
62    /// The engine uses this to pick the mask-based probe path.
63    fn is_power_of_two() -> bool {
64        false
65    }
66}
67
68use crate::util::{is_power_of_two, round_up_to_power_of_two};
69
70/// Grow by a power-of-two factor and map with a mask.
71///
72/// `FACTOR` must be a power of two and at least 2. The default is 2.
73#[derive(Clone)]
74pub struct PowerOfTwo<const FACTOR: usize = 2> {
75    mask: usize,
76}
77
78impl<const FACTOR: usize> GrowthPolicy for PowerOfTwo<FACTOR> {
79    fn new(min_bucket_count: usize) -> Result<(Self, usize), LengthError> {
80        assert!(
81            is_power_of_two(FACTOR) && FACTOR >= 2,
82            "growth factor must be a power of two >= 2"
83        );
84
85        let max = Self::max_bucket_count_static();
86        if min_bucket_count > max {
87            return Err(LengthError);
88        }
89
90        if min_bucket_count > 0 {
91            let rounded = round_up_to_power_of_two(min_bucket_count);
92            Ok((Self { mask: rounded - 1 }, rounded))
93        } else {
94            Ok((Self { mask: 0 }, 0))
95        }
96    }
97
98    #[inline]
99    fn bucket_for_hash(&self, hash: usize) -> usize {
100        hash & self.mask
101    }
102
103    fn next_bucket_count(&self) -> Result<usize, LengthError> {
104        if (self.mask + 1) > Self::max_bucket_count_static() / FACTOR {
105            return Err(LengthError);
106        }
107        Ok((self.mask + 1) * FACTOR)
108    }
109
110    fn max_bucket_count(&self) -> usize {
111        Self::max_bucket_count_static()
112    }
113
114    fn clear(&mut self) {
115        self.mask = 0;
116    }
117
118    fn is_power_of_two() -> bool {
119        true
120    }
121}
122
123impl<const FACTOR: usize> PowerOfTwo<FACTOR> {
124    #[inline]
125    fn max_bucket_count_static() -> usize {
126        // Largest power of two representable in a usize.
127        (usize::MAX / 2) + 1
128    }
129}
130
131/// Grow by the rational factor `NUM / DEN` and map with a modulo.
132///
133/// The factor must be at least 1.1. The default is 3/2.
134#[derive(Clone)]
135pub struct Mod<const NUM: usize = 3, const DEN: usize = 2> {
136    modulo: usize,
137}
138
139impl<const NUM: usize, const DEN: usize> Mod<NUM, DEN> {
140    #[inline]
141    fn factor() -> f64 {
142        NUM as f64 / DEN as f64
143    }
144
145    #[inline]
146    fn max_bucket_count_static() -> usize {
147        (usize::MAX as f64 / Self::factor()) as usize
148    }
149}
150
151impl<const NUM: usize, const DEN: usize> GrowthPolicy for Mod<NUM, DEN> {
152    fn new(min_bucket_count: usize) -> Result<(Self, usize), LengthError> {
153        assert!(DEN != 0, "growth factor denominator must be nonzero");
154        assert!(Self::factor() >= 1.1, "growth factor should be >= 1.1");
155
156        if min_bucket_count > Self::max_bucket_count_static() {
157            return Err(LengthError);
158        }
159
160        let modulo = if min_bucket_count > 0 {
161            min_bucket_count
162        } else {
163            1
164        };
165        // Mod does not change the requested count. It uses it as the modulus.
166        Ok((Self { modulo }, min_bucket_count))
167    }
168
169    #[inline]
170    fn bucket_for_hash(&self, hash: usize) -> usize {
171        hash % self.modulo
172    }
173
174    fn next_bucket_count(&self) -> Result<usize, LengthError> {
175        let max = Self::max_bucket_count_static();
176        if self.modulo == max {
177            return Err(LengthError);
178        }
179
180        let next = (self.modulo as f64 * Self::factor()).ceil();
181        if !next.is_normal() {
182            return Err(LengthError);
183        }
184
185        if next > max as f64 {
186            Ok(max)
187        } else {
188            Ok(next as usize)
189        }
190    }
191
192    fn max_bucket_count(&self) -> usize {
193        Self::max_bucket_count_static()
194    }
195
196    fn clear(&mut self) {
197        self.modulo = 1;
198    }
199}
200
201#[cfg(test)]
202mod tests {
203    use super::{GrowthPolicy, Mod};
204
205    #[test]
206    #[should_panic(expected = "growth factor denominator must be nonzero")]
207    fn mod_policy_rejects_zero_denominator() {
208        let _ = Mod::<2, 0>::new(0);
209    }
210}
211
212/// The prime table used by [`Prime`]. Ascending, 40 entries.
213///
214/// Exposed so callers can reason about the growth sequence. A `Prime` policy
215/// steps through these on each growth.
216pub const PRIMES_TABLE: [usize; 40] = [
217    1, 5, 17, 29, 37, 53, 67, 79, 97, 131, 193, 257, 389, 521, 769, 1031, 1543, 2053, 3079, 6151,
218    12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917,
219    25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473,
220    4294967291,
221];
222
223/// Grow by stepping through a fixed table of primes and map with a modulo.
224///
225/// A modulo by a compile-time-unknown prime is still fast here because the
226/// table is small and the index selects the divisor. This policy spreads values
227/// better than [`PowerOfTwo`] when the hash is poor.
228#[derive(Clone)]
229pub struct Prime {
230    iprime: usize,
231}
232
233impl GrowthPolicy for Prime {
234    fn new(min_bucket_count: usize) -> Result<(Self, usize), LengthError> {
235        // Lower bound: first prime not less than the request.
236        let iprime = PRIMES_TABLE.partition_point(|&p| p < min_bucket_count);
237        if iprime == PRIMES_TABLE.len() {
238            return Err(LengthError);
239        }
240
241        let settled = if min_bucket_count > 0 {
242            PRIMES_TABLE[iprime]
243        } else {
244            0
245        };
246        Ok((Self { iprime }, settled))
247    }
248
249    #[inline]
250    fn bucket_for_hash(&self, hash: usize) -> usize {
251        hash % PRIMES_TABLE[self.iprime]
252    }
253
254    fn next_bucket_count(&self) -> Result<usize, LengthError> {
255        if self.iprime + 1 >= PRIMES_TABLE.len() {
256            return Err(LengthError);
257        }
258        Ok(PRIMES_TABLE[self.iprime + 1])
259    }
260
261    fn max_bucket_count(&self) -> usize {
262        PRIMES_TABLE[PRIMES_TABLE.len() - 1]
263    }
264
265    fn clear(&mut self) {
266        self.iprime = 0;
267    }
268}
sparse_hash_map/growth_policy.rs

sparse_hash_map/
growth_policy.rs
