| 1 |
#![allow(unsafe_code)] |
| 2 |
//! This module encapsulates the `unsafe` access to `hashbrown::raw::RawTable`, |
| 3 |
//! mostly in dealing with its bucket "pointers". |
| 4 |
|
| 5 |
use super::{equivalent, Bucket, Entry, HashValue, IndexMapCore, VacantEntry}; |
| 6 |
use core::fmt; |
| 7 |
use core::mem::replace; |
| 8 |
use hashbrown::raw::RawTable; |
| 9 |
|
| 10 |
type RawBucket = hashbrown::raw::Bucket<usize>; |
| 11 |
|
| 12 |
/// Inserts many entries into a raw table without reallocating. |
| 13 |
/// |
| 14 |
/// ***Panics*** if there is not sufficient capacity already. |
| 15 |
pub(super) fn insert_bulk_no_grow<K, V>(indices: &mut RawTable<usize>, entries: &[Bucket<K, V>]) { |
| 16 |
assert!(indices.capacity() - indices.len() >= entries.len()); |
| 17 |
for entry in entries { |
| 18 |
// SAFETY: we asserted that sufficient capacity exists for all entries. |
| 19 |
unsafe { |
| 20 |
indices.insert_no_grow(entry.hash.get(), indices.len()); |
| 21 |
} |
| 22 |
} |
| 23 |
} |
| 24 |
|
| 25 |
pub(super) struct DebugIndices<'a>(pub &'a RawTable<usize>); |
| 26 |
impl fmt::Debug for DebugIndices<'_> { |
| 27 |
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| 28 |
// SAFETY: we're not letting any of the buckets escape this function |
| 29 |
let indices = unsafe { self.0.iter().map(|raw_bucket| raw_bucket.read()) }; |
| 30 |
f.debug_list().entries(indices).finish() |
| 31 |
} |
| 32 |
} |
| 33 |
|
| 34 |
impl<K, V> IndexMapCore<K, V> { |
| 35 |
/// Sweep the whole table to erase indices start..end |
| 36 |
pub(super) fn erase_indices_sweep(&mut self, start: usize, end: usize) { |
| 37 |
// SAFETY: we're not letting any of the buckets escape this function |
| 38 |
unsafe { |
| 39 |
let offset = end - start; |
| 40 |
for bucket in self.indices.iter() { |
| 41 |
let i = bucket.read(); |
| 42 |
if i >= end { |
| 43 |
bucket.write(i - offset); |
| 44 |
} else if i >= start { |
| 45 |
self.indices.erase(bucket); |
| 46 |
} |
| 47 |
} |
| 48 |
} |
| 49 |
} |
| 50 |
|
| 51 |
pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V> |
| 52 |
where |
| 53 |
K: Eq, |
| 54 |
{ |
| 55 |
let eq = equivalent(&key, &self.entries); |
| 56 |
match self.indices.find(hash.get(), eq) { |
| 57 |
// SAFETY: The entry is created with a live raw bucket, at the same time |
| 58 |
// we have a &mut reference to the map, so it can not be modified further. |
| 59 |
Some(raw_bucket) => Entry::Occupied(OccupiedEntry { |
| 60 |
map: self, |
| 61 |
raw_bucket, |
| 62 |
key, |
| 63 |
}), |
| 64 |
None => Entry::Vacant(VacantEntry { |
| 65 |
map: self, |
| 66 |
hash, |
| 67 |
key, |
| 68 |
}), |
| 69 |
} |
| 70 |
} |
| 71 |
|
| 72 |
pub(super) fn indices_mut(&mut self) -> impl Iterator<Item = &mut usize> { |
| 73 |
// SAFETY: we're not letting any of the buckets escape this function, |
| 74 |
// only the item references that are appropriately bound to `&mut self`. |
| 75 |
unsafe { self.indices.iter().map(|bucket| bucket.as_mut()) } |
| 76 |
} |
| 77 |
|
| 78 |
/// Return the raw bucket for the given index |
| 79 |
fn find_index(&self, index: usize) -> RawBucket { |
| 80 |
// We'll get a "nice" bounds-check from indexing `self.entries`, |
| 81 |
// and then we expect to find it in the table as well. |
| 82 |
let hash = self.entries[index].hash.get(); |
| 83 |
self.indices |
| 84 |
.find(hash, move |&i| i == index) |
| 85 |
.expect("index not found") |
| 86 |
} |
| 87 |
|
| 88 |
pub(crate) fn swap_indices(&mut self, a: usize, b: usize) { |
| 89 |
// SAFETY: Can't take two `get_mut` references from one table, so we |
| 90 |
// must use raw buckets to do the swap. This is still safe because we |
| 91 |
// are locally sure they won't dangle, and we write them individually. |
| 92 |
unsafe { |
| 93 |
let raw_bucket_a = self.find_index(a); |
| 94 |
let raw_bucket_b = self.find_index(b); |
| 95 |
raw_bucket_a.write(b); |
| 96 |
raw_bucket_b.write(a); |
| 97 |
} |
| 98 |
self.entries.swap(a, b); |
| 99 |
} |
| 100 |
} |
| 101 |
|
| 102 |
/// A view into an occupied entry in a `IndexMap`. |
| 103 |
/// It is part of the [`Entry`] enum. |
| 104 |
/// |
| 105 |
/// [`Entry`]: enum.Entry.html |
| 106 |
// SAFETY: The lifetime of the map reference also constrains the raw bucket, |
| 107 |
// which is essentially a raw pointer into the map indices. |
| 108 |
pub struct OccupiedEntry<'a, K, V> { |
| 109 |
map: &'a mut IndexMapCore<K, V>, |
| 110 |
raw_bucket: RawBucket, |
| 111 |
key: K, |
| 112 |
} |
| 113 |
|
| 114 |
// `hashbrown::raw::Bucket` is only `Send`, not `Sync`. |
| 115 |
// SAFETY: `&self` only accesses the bucket to read it. |
| 116 |
unsafe impl<K: Sync, V: Sync> Sync for OccupiedEntry<'_, K, V> {} |
| 117 |
|
| 118 |
// The parent module also adds methods that don't threaten the unsafe encapsulation. |
| 119 |
impl<'a, K, V> OccupiedEntry<'a, K, V> { |
| 120 |
/// Gets a reference to the entry's key in the map. |
| 121 |
/// |
| 122 |
/// Note that this is not the key that was used to find the entry. There may be an observable |
| 123 |
/// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like |
| 124 |
/// extra fields or the memory address of an allocation. |
| 125 |
pub fn key(&self) -> &K { |
| 126 |
&self.map.entries[self.index()].key |
| 127 |
} |
| 128 |
|
| 129 |
/// Gets a reference to the entry's value in the map. |
| 130 |
pub fn get(&self) -> &V { |
| 131 |
&self.map.entries[self.index()].value |
| 132 |
} |
| 133 |
|
| 134 |
/// Gets a mutable reference to the entry's value in the map. |
| 135 |
/// |
| 136 |
/// If you need a reference which may outlive the destruction of the |
| 137 |
/// `Entry` value, see `into_mut`. |
| 138 |
pub fn get_mut(&mut self) -> &mut V { |
| 139 |
let index = self.index(); |
| 140 |
&mut self.map.entries[index].value |
| 141 |
} |
| 142 |
|
| 143 |
/// Put the new key in the occupied entry's key slot |
| 144 |
pub(crate) fn replace_key(self) -> K { |
| 145 |
let index = self.index(); |
| 146 |
let old_key = &mut self.map.entries[index].key; |
| 147 |
replace(old_key, self.key) |
| 148 |
} |
| 149 |
|
| 150 |
/// Return the index of the key-value pair |
| 151 |
#[inline] |
| 152 |
pub fn index(&self) -> usize { |
| 153 |
// SAFETY: we have &mut map keep keeping the bucket stable |
| 154 |
unsafe { self.raw_bucket.read() } |
| 155 |
} |
| 156 |
|
| 157 |
/// Converts into a mutable reference to the entry's value in the map, |
| 158 |
/// with a lifetime bound to the map itself. |
| 159 |
pub fn into_mut(self) -> &'a mut V { |
| 160 |
let index = self.index(); |
| 161 |
&mut self.map.entries[index].value |
| 162 |
} |
| 163 |
|
| 164 |
/// Remove and return the key, value pair stored in the map for this entry |
| 165 |
/// |
| 166 |
/// Like `Vec::swap_remove`, the pair is removed by swapping it with the |
| 167 |
/// last element of the map and popping it off. **This perturbs |
| 168 |
/// the position of what used to be the last element!** |
| 169 |
/// |
| 170 |
/// Computes in **O(1)** time (average). |
| 171 |
pub fn swap_remove_entry(self) -> (K, V) { |
| 172 |
// SAFETY: This is safe because it can only happen once (self is consumed) |
| 173 |
// and map.indices have not been modified since entry construction |
| 174 |
let index = unsafe { self.map.indices.remove(self.raw_bucket) }; |
| 175 |
self.map.swap_remove_finish(index) |
| 176 |
} |
| 177 |
|
| 178 |
/// Remove and return the key, value pair stored in the map for this entry |
| 179 |
/// |
| 180 |
/// Like `Vec::remove`, the pair is removed by shifting all of the |
| 181 |
/// elements that follow it, preserving their relative order. |
| 182 |
/// **This perturbs the index of all of those elements!** |
| 183 |
/// |
| 184 |
/// Computes in **O(n)** time (average). |
| 185 |
pub fn shift_remove_entry(self) -> (K, V) { |
| 186 |
// SAFETY: This is safe because it can only happen once (self is consumed) |
| 187 |
// and map.indices have not been modified since entry construction |
| 188 |
let index = unsafe { self.map.indices.remove(self.raw_bucket) }; |
| 189 |
self.map.shift_remove_finish(index) |
| 190 |
} |
| 191 |
} |