Look for `key` in `table`. The provided `hash` value must have been computed from `key` using the same hash function that was used to construct the table. Returns `Ok(idx)` with the table index containing the found entry, or `Err(idx)` with the empty sentinel entry if no entry could be found.
(
table: &T,
key: K,
hash: usize,
)
| 31 | /// Returns `Ok(idx)` with the table index containing the found entry, or `Err(idx)` with the empty |
| 32 | /// sentinel entry if no entry could be found. |
| 33 | pub fn probe<K: Copy + Eq, T: Table<K> + ?Sized>( |
| 34 | table: &T, |
| 35 | key: K, |
| 36 | hash: usize, |
| 37 | ) -> Result<usize, usize> { |
| 38 | debug_assert!(table.len().is_power_of_two()); |
| 39 | let mask = table.len() - 1; |
| 40 | |
| 41 | let mut idx = hash; |
| 42 | let mut step = 0; |
| 43 | |
| 44 | loop { |
| 45 | idx &= mask; |
| 46 | |
| 47 | match table.key(idx) { |
| 48 | None => return Err(idx), |
| 49 | Some(k) if k == key => return Ok(idx), |
| 50 | _ => {} |
| 51 | } |
| 52 | |
| 53 | // Quadratic probing. |
| 54 | step += 1; |
| 55 | |
| 56 | // When `table.len()` is a power of two, it can be proven that `idx` will visit all |
| 57 | // entries. This means that this loop will always terminate if the hash table has even |
| 58 | // one unused entry. |
| 59 | debug_assert!(step < table.len()); |
| 60 | idx += step; |
| 61 | } |
| 62 | } |