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::{Entry, Equivalent, HashValue, IndexMapCore, VacantEntry}; 6 use crate::util::enumerate; 7 use core::fmt; 8 use core::mem::replace; 9 use hashbrown::raw::RawTable; 10 11 type RawBucket = hashbrown::raw::Bucket<usize>; 12 13 pub(super) struct DebugIndices<'a>(pub &'a RawTable<usize>); 14 impl fmt::Debug for DebugIndices<'_> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result15 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 16 let indices = unsafe { self.0.iter().map(|raw_bucket| raw_bucket.read()) }; 17 f.debug_list().entries(indices).finish() 18 } 19 } 20 21 impl<K, V> IndexMapCore<K, V> { 22 /// Return the raw bucket with an equivalent key find_equivalent<Q>(&self, hash: HashValue, key: &Q) -> Option<RawBucket> where Q: ?Sized + Equivalent<K>,23 fn find_equivalent<Q>(&self, hash: HashValue, key: &Q) -> Option<RawBucket> 24 where 25 Q: ?Sized + Equivalent<K>, 26 { 27 self.indices.find(hash.get(), { 28 move |&i| Q::equivalent(key, &self.entries[i].key) 29 }) 30 } 31 32 /// Return the raw bucket for the given index find_index(&self, hash: HashValue, index: usize) -> Option<RawBucket>33 fn find_index(&self, hash: HashValue, index: usize) -> Option<RawBucket> { 34 self.indices.find(hash.get(), move |&i| i == index) 35 } 36 37 /// Return the index in `entries` where an equivalent key can be found get_index_of<Q>(&self, hash: HashValue, key: &Q) -> Option<usize> where Q: ?Sized + Equivalent<K>,38 pub(crate) fn get_index_of<Q>(&self, hash: HashValue, key: &Q) -> Option<usize> 39 where 40 Q: ?Sized + Equivalent<K>, 41 { 42 match self.find_equivalent(hash, key) { 43 Some(raw_bucket) => Some(unsafe { raw_bucket.read() }), 44 None => None, 45 } 46 } 47 48 /// Erase the given index from `indices`. 49 /// 50 /// The index doesn't need to be valid in `entries` while calling this. No other index 51 /// adjustments are made -- this is only used by `pop` for the greatest index. erase_index(&mut self, hash: HashValue, index: usize)52 pub(super) fn erase_index(&mut self, hash: HashValue, index: usize) { 53 debug_assert_eq!(index, self.indices.len() - 1); 54 let raw_bucket = self.find_index(hash, index).unwrap(); 55 unsafe { self.indices.erase(raw_bucket) }; 56 } 57 58 /// Erase `start..end` from `indices`, and shift `end..` indices down to `start..` 59 /// 60 /// All of these items should still be at their original location in `entries`. 61 /// This is used by `drain`, which will let `Vec::drain` do the work on `entries`. erase_indices(&mut self, start: usize, end: usize)62 pub(super) fn erase_indices(&mut self, start: usize, end: usize) { 63 let (init, shifted_entries) = self.entries.split_at(end); 64 let (start_entries, erased_entries) = init.split_at(start); 65 66 let erased = erased_entries.len(); 67 let shifted = shifted_entries.len(); 68 let half_capacity = self.indices.buckets() / 2; 69 70 // Use a heuristic between different strategies 71 if erased == 0 { 72 // Degenerate case, nothing to do 73 } else if start + shifted < half_capacity && start < erased { 74 // Reinsert everything, as there are few kept indices 75 self.indices.clear(); 76 77 // Reinsert stable indices 78 for (i, entry) in enumerate(start_entries) { 79 self.indices.insert_no_grow(entry.hash.get(), i); 80 } 81 82 // Reinsert shifted indices 83 for (i, entry) in (start..).zip(shifted_entries) { 84 self.indices.insert_no_grow(entry.hash.get(), i); 85 } 86 } else if erased + shifted < half_capacity { 87 // Find each affected index, as there are few to adjust 88 89 // Find erased indices 90 for (i, entry) in (start..).zip(erased_entries) { 91 let bucket = self.find_index(entry.hash, i).unwrap(); 92 unsafe { self.indices.erase(bucket) }; 93 } 94 95 // Find shifted indices 96 for ((new, old), entry) in (start..).zip(end..).zip(shifted_entries) { 97 let bucket = self.find_index(entry.hash, old).unwrap(); 98 unsafe { bucket.write(new) }; 99 } 100 } else { 101 // Sweep the whole table for adjustments 102 unsafe { 103 for bucket in self.indices.iter() { 104 let i = bucket.read(); 105 if i >= end { 106 bucket.write(i - erased); 107 } else if i >= start { 108 self.indices.erase(bucket); 109 } 110 } 111 } 112 } 113 114 debug_assert_eq!(self.indices.len(), start + shifted); 115 } 116 entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V> where K: Eq,117 pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V> 118 where 119 K: Eq, 120 { 121 match self.find_equivalent(hash, &key) { 122 // Safety: The entry is created with a live raw bucket, at the same time we have a &mut 123 // reference to the map, so it can not be modified further. 124 Some(raw_bucket) => Entry::Occupied(OccupiedEntry { 125 map: self, 126 raw_bucket, 127 key, 128 }), 129 None => Entry::Vacant(VacantEntry { 130 map: self, 131 hash, 132 key, 133 }), 134 } 135 } 136 137 /// Remove an entry by shifting all entries that follow it shift_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> where Q: ?Sized + Equivalent<K>,138 pub(crate) fn shift_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> 139 where 140 Q: ?Sized + Equivalent<K>, 141 { 142 match self.find_equivalent(hash, key) { 143 Some(raw_bucket) => unsafe { Some(self.shift_remove_bucket(raw_bucket)) }, 144 None => None, 145 } 146 } 147 148 /// Remove an entry by shifting all entries that follow it shift_remove_index(&mut self, index: usize) -> Option<(K, V)>149 pub(crate) fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { 150 let raw_bucket = match self.entries.get(index) { 151 Some(entry) => self.find_index(entry.hash, index).unwrap(), 152 None => return None, 153 }; 154 unsafe { 155 let (_, key, value) = self.shift_remove_bucket(raw_bucket); 156 Some((key, value)) 157 } 158 } 159 160 /// Remove an entry by shifting all entries that follow it 161 /// 162 /// Safety: The caller must pass a live `raw_bucket`. 163 #[allow(unused_unsafe)] shift_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V)164 unsafe fn shift_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V) { 165 // use Vec::remove, but then we need to update the indices that point 166 // to all of the other entries that have to move 167 let index = unsafe { self.indices.remove(raw_bucket) }; 168 let entry = self.entries.remove(index); 169 170 // correct indices that point to the entries that followed the removed entry. 171 // use a heuristic between a full sweep vs. a `find()` for every shifted item. 172 let raw_capacity = self.indices.buckets(); 173 let shifted_entries = &self.entries[index..]; 174 if shifted_entries.len() > raw_capacity / 2 { 175 // shift all indices greater than `index` 176 unsafe { 177 for bucket in self.indices.iter() { 178 let i = bucket.read(); 179 if i > index { 180 bucket.write(i - 1); 181 } 182 } 183 } 184 } else { 185 // find each following entry to shift its index 186 for (i, entry) in (index + 1..).zip(shifted_entries) { 187 let shifted_bucket = self.find_index(entry.hash, i).unwrap(); 188 unsafe { shifted_bucket.write(i - 1) }; 189 } 190 } 191 192 (index, entry.key, entry.value) 193 } 194 195 /// Remove an entry by swapping it with the last swap_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> where Q: ?Sized + Equivalent<K>,196 pub(crate) fn swap_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> 197 where 198 Q: ?Sized + Equivalent<K>, 199 { 200 match self.find_equivalent(hash, key) { 201 Some(raw_bucket) => unsafe { Some(self.swap_remove_bucket(raw_bucket)) }, 202 None => None, 203 } 204 } 205 206 /// Remove an entry by swapping it with the last swap_remove_index(&mut self, index: usize) -> Option<(K, V)>207 pub(crate) fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { 208 let raw_bucket = match self.entries.get(index) { 209 Some(entry) => self.find_index(entry.hash, index).unwrap(), 210 None => return None, 211 }; 212 unsafe { 213 let (_, key, value) = self.swap_remove_bucket(raw_bucket); 214 Some((key, value)) 215 } 216 } 217 218 /// Remove an entry by swapping it with the last 219 /// 220 /// Safety: The caller must pass a live `raw_bucket`. 221 #[allow(unused_unsafe)] swap_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V)222 unsafe fn swap_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V) { 223 // use swap_remove, but then we need to update the index that points 224 // to the other entry that has to move 225 let index = unsafe { self.indices.remove(raw_bucket) }; 226 let entry = self.entries.swap_remove(index); 227 228 // correct index that points to the entry that had to swap places 229 if let Some(entry) = self.entries.get(index) { 230 // was not last element 231 // examine new element in `index` and find it in indices 232 let last = self.entries.len(); 233 let swapped_bucket = self.find_index(entry.hash, last).unwrap(); 234 unsafe { swapped_bucket.write(index) }; 235 } 236 237 (index, entry.key, entry.value) 238 } 239 reverse(&mut self)240 pub(crate) fn reverse(&mut self) { 241 self.entries.reverse(); 242 243 // No need to save hash indices, can easily calculate what they should 244 // be, given that this is an in-place reversal. 245 let len = self.entries.len(); 246 unsafe { 247 for raw_bucket in self.indices.iter() { 248 let i = raw_bucket.read(); 249 raw_bucket.write(len - i - 1); 250 } 251 } 252 } 253 } 254 255 /// A view into an occupied entry in a `IndexMap`. 256 /// It is part of the [`Entry`] enum. 257 /// 258 /// [`Entry`]: enum.Entry.html 259 // SAFETY: The lifetime of the map reference also constrains the raw bucket, 260 // which is essentially a raw pointer into the map indices. 261 pub struct OccupiedEntry<'a, K, V> { 262 map: &'a mut IndexMapCore<K, V>, 263 raw_bucket: RawBucket, 264 key: K, 265 } 266 267 // `hashbrown::raw::Bucket` is only `Send`, not `Sync`. 268 // SAFETY: `&self` only accesses the bucket to read it. 269 unsafe impl<K: Sync, V: Sync> Sync for OccupiedEntry<'_, K, V> {} 270 271 // The parent module also adds methods that don't threaten the unsafe encapsulation. 272 impl<'a, K, V> OccupiedEntry<'a, K, V> { key(&self) -> &K273 pub fn key(&self) -> &K { 274 &self.key 275 } 276 get(&self) -> &V277 pub fn get(&self) -> &V { 278 &self.map.entries[self.index()].value 279 } 280 get_mut(&mut self) -> &mut V281 pub fn get_mut(&mut self) -> &mut V { 282 let index = self.index(); 283 &mut self.map.entries[index].value 284 } 285 286 /// Put the new key in the occupied entry's key slot replace_key(self) -> K287 pub(crate) fn replace_key(self) -> K { 288 let index = self.index(); 289 let old_key = &mut self.map.entries[index].key; 290 replace(old_key, self.key) 291 } 292 293 /// Return the index of the key-value pair 294 #[inline] index(&self) -> usize295 pub fn index(&self) -> usize { 296 unsafe { self.raw_bucket.read() } 297 } 298 into_mut(self) -> &'a mut V299 pub fn into_mut(self) -> &'a mut V { 300 let index = self.index(); 301 &mut self.map.entries[index].value 302 } 303 304 /// Remove and return the key, value pair stored in the map for this entry 305 /// 306 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the 307 /// last element of the map and popping it off. **This perturbs 308 /// the postion of what used to be the last element!** 309 /// 310 /// Computes in **O(1)** time (average). swap_remove_entry(self) -> (K, V)311 pub fn swap_remove_entry(self) -> (K, V) { 312 // This is safe because it can only happen once (self is consumed) 313 // and map.indices have not been modified since entry construction 314 unsafe { 315 let (_, key, value) = self.map.swap_remove_bucket(self.raw_bucket); 316 (key, value) 317 } 318 } 319 320 /// Remove and return the key, value pair stored in the map for this entry 321 /// 322 /// Like `Vec::remove`, the pair is removed by shifting all of the 323 /// elements that follow it, preserving their relative order. 324 /// **This perturbs the index of all of those elements!** 325 /// 326 /// Computes in **O(n)** time (average). shift_remove_entry(self) -> (K, V)327 pub fn shift_remove_entry(self) -> (K, V) { 328 // This is safe because it can only happen once (self is consumed) 329 // and map.indices have not been modified since entry construction 330 unsafe { 331 let (_, key, value) = self.map.shift_remove_bucket(self.raw_bucket); 332 (key, value) 333 } 334 } 335 } 336