/rust/registry/src/index.crates.io-1949cf8c6b5b557f/papaya-0.2.3/src/raw/probe.rs
Line | Count | Source |
1 | | // A quadratic probe sequence. |
2 | | #[derive(Default)] |
3 | | pub struct Probe { |
4 | | // The current index in the probe sequence. |
5 | | pub i: usize, |
6 | | // The current length of the probe sequence. |
7 | | pub len: usize, |
8 | | } |
9 | | |
10 | | impl Probe { |
11 | | // Initialize the probe sequence. |
12 | | #[inline] |
13 | 0 | pub fn start(hash: usize, mask: usize) -> Probe { |
14 | 0 | Probe { |
15 | 0 | i: hash & mask, |
16 | 0 | len: 0, |
17 | 0 | } |
18 | 0 | } Unexecuted instantiation: <papaya::raw::probe::Probe>::start Unexecuted instantiation: <papaya::raw::probe::Probe>::start Unexecuted instantiation: <papaya::raw::probe::Probe>::start |
19 | | |
20 | | // Increment the probe sequence. |
21 | | #[inline] |
22 | 0 | pub fn next(&mut self, mask: usize) { |
23 | 0 | self.len += 1; |
24 | 0 | self.i = (self.i + self.len) & mask; |
25 | 0 | } Unexecuted instantiation: <papaya::raw::probe::Probe>::next Unexecuted instantiation: <papaya::raw::probe::Probe>::next Unexecuted instantiation: <papaya::raw::probe::Probe>::next |
26 | | } |
27 | | |
28 | | // The maximum probe length for table operations. |
29 | | // |
30 | | // Estimating a load factor for the hash-table based on probe lengths allows |
31 | | // the hash-table to avoid loading the length every insert, which is a source |
32 | | // of contention. |
33 | 0 | pub fn limit(capacity: usize) -> usize { |
34 | | // 5 * log2(capacity): Testing shows this gives us a ~85% load factor. |
35 | 0 | 5 * ((usize::BITS as usize) - (capacity.leading_zeros() as usize) - 1) |
36 | 0 | } |
37 | | |
38 | | // Returns an estimate of the number of entries needed to hold `capacity` elements. |
39 | 0 | pub fn entries_for(capacity: usize) -> usize { |
40 | | // We should rarely resize before 75%. |
41 | 0 | let capacity = capacity.checked_mul(8).expect("capacity overflow") / 6; |
42 | 0 | capacity.next_power_of_two() |
43 | 0 | } |