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 hashbrown::raw::RawTable; 7 use std::fmt; 8 use std::mem::replace; 9 10 type RawBucket = hashbrown::raw::Bucket<usize>; 11 12 pub(super) struct DebugIndices<'a>(pub &'a RawTable<usize>); 13 impl fmt::Debug for DebugIndices<'_> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result14 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 15 let indices = unsafe { self.0.iter().map(|raw_bucket| raw_bucket.read()) }; 16 f.debug_list().entries(indices).finish() 17 } 18 } 19 20 impl<K, V> IndexMapCore<K, V> { 21 /// Return the raw bucket with an equivalent key find_equivalent<Q>(&self, hash: HashValue, key: &Q) -> Option<RawBucket> where Q: ?Sized + Equivalent<K>,22 fn find_equivalent<Q>(&self, hash: HashValue, key: &Q) -> Option<RawBucket> 23 where 24 Q: ?Sized + Equivalent<K>, 25 { 26 self.indices.find(hash.get(), { 27 move |&i| Q::equivalent(key, &self.entries[i].key) 28 }) 29 } 30 31 /// Return the raw bucket for the given index find_index(&self, hash: HashValue, index: usize) -> Option<RawBucket>32 fn find_index(&self, hash: HashValue, index: usize) -> Option<RawBucket> { 33 self.indices.find(hash.get(), move |&i| i == index) 34 } 35 36 /// 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>,37 pub(crate) fn get_index_of<Q>(&self, hash: HashValue, key: &Q) -> Option<usize> 38 where 39 Q: ?Sized + Equivalent<K>, 40 { 41 match self.find_equivalent(hash, key) { 42 Some(raw_bucket) => Some(unsafe { raw_bucket.read() }), 43 None => None, 44 } 45 } 46 erase_index(&mut self, hash: HashValue, index: usize)47 pub(super) fn erase_index(&mut self, hash: HashValue, index: usize) { 48 let raw_bucket = self.find_index(hash, index).unwrap(); 49 unsafe { self.indices.erase(raw_bucket) }; 50 } 51 entry(&mut self, hash: HashValue, key: K) -> Entry<K, V> where K: Eq,52 pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<K, V> 53 where 54 K: Eq, 55 { 56 match self.find_equivalent(hash, &key) { 57 // Safety: The entry is created with a live raw bucket, at the same time we have a &mut 58 // 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 /// 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>,73 pub(crate) fn shift_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> 74 where 75 Q: ?Sized + Equivalent<K>, 76 { 77 match self.find_equivalent(hash, key) { 78 Some(raw_bucket) => unsafe { Some(self.shift_remove_bucket(raw_bucket)) }, 79 None => None, 80 } 81 } 82 83 /// Remove an entry by shifting all entries that follow it shift_remove_index(&mut self, index: usize) -> Option<(K, V)>84 pub(crate) fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> { 85 let raw_bucket = match self.entries.get(index) { 86 Some(entry) => self.find_index(entry.hash, index).unwrap(), 87 None => return None, 88 }; 89 unsafe { 90 let (_, key, value) = self.shift_remove_bucket(raw_bucket); 91 Some((key, value)) 92 } 93 } 94 95 /// Remove an entry by shifting all entries that follow it 96 /// 97 /// Safety: The caller must pass a live `raw_bucket`. 98 #[allow(unused_unsafe)] shift_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V)99 unsafe fn shift_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V) { 100 // use Vec::remove, but then we need to update the indices that point 101 // to all of the other entries that have to move 102 let index = unsafe { self.indices.remove(raw_bucket) }; 103 let entry = self.entries.remove(index); 104 105 // correct indices that point to the entries that followed the removed entry. 106 // use a heuristic between a full sweep vs. a `find()` for every shifted item. 107 let raw_capacity = self.indices.buckets(); 108 let shifted_entries = &self.entries[index..]; 109 if shifted_entries.len() > raw_capacity / 2 { 110 // shift all indices greater than `index` 111 unsafe { 112 for bucket in self.indices.iter() { 113 let i = bucket.read(); 114 if i > index { 115 bucket.write(i - 1); 116 } 117 } 118 } 119 } else { 120 // find each following entry to shift its index 121 for (i, entry) in (index + 1..).zip(shifted_entries) { 122 let shifted_bucket = self.find_index(entry.hash, i).unwrap(); 123 unsafe { shifted_bucket.write(i - 1) }; 124 } 125 } 126 127 (index, entry.key, entry.value) 128 } 129 130 /// 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>,131 pub(crate) fn swap_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> 132 where 133 Q: ?Sized + Equivalent<K>, 134 { 135 match self.find_equivalent(hash, key) { 136 Some(raw_bucket) => unsafe { Some(self.swap_remove_bucket(raw_bucket)) }, 137 None => None, 138 } 139 } 140 141 /// Remove an entry by swapping it with the last swap_remove_index(&mut self, index: usize) -> Option<(K, V)>142 pub(crate) fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> { 143 let raw_bucket = match self.entries.get(index) { 144 Some(entry) => self.find_index(entry.hash, index).unwrap(), 145 None => return None, 146 }; 147 unsafe { 148 let (_, key, value) = self.swap_remove_bucket(raw_bucket); 149 Some((key, value)) 150 } 151 } 152 153 /// Remove an entry by swapping it with the last 154 /// 155 /// Safety: The caller must pass a live `raw_bucket`. 156 #[allow(unused_unsafe)] swap_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V)157 unsafe fn swap_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V) { 158 // use swap_remove, but then we need to update the index that points 159 // to the other entry that has to move 160 let index = unsafe { self.indices.remove(raw_bucket) }; 161 let entry = self.entries.swap_remove(index); 162 163 // correct index that points to the entry that had to swap places 164 if let Some(entry) = self.entries.get(index) { 165 // was not last element 166 // examine new element in `index` and find it in indices 167 let last = self.entries.len(); 168 let swapped_bucket = self.find_index(entry.hash, last).unwrap(); 169 unsafe { swapped_bucket.write(index) }; 170 } 171 172 (index, entry.key, entry.value) 173 } 174 reverse(&mut self)175 pub(crate) fn reverse(&mut self) { 176 self.entries.reverse(); 177 178 // No need to save hash indices, can easily calculate what they should 179 // be, given that this is an in-place reversal. 180 let len = self.entries.len(); 181 unsafe { 182 for raw_bucket in self.indices.iter() { 183 let i = raw_bucket.read(); 184 raw_bucket.write(len - i - 1); 185 } 186 } 187 } 188 } 189 190 /// A view into an occupied entry in a `IndexMap`. 191 /// It is part of the [`Entry`] enum. 192 /// 193 /// [`Entry`]: enum.Entry.html 194 // SAFETY: The lifetime of the map reference also constrains the raw bucket, 195 // which is essentially a raw pointer into the map indices. 196 pub struct OccupiedEntry<'a, K: 'a, V: 'a> { 197 map: &'a mut IndexMapCore<K, V>, 198 raw_bucket: RawBucket, 199 key: K, 200 } 201 202 // `hashbrown::raw::Bucket` is only `Send`, not `Sync`. 203 // SAFETY: `&self` only accesses the bucket to read it. 204 unsafe impl<K: Sync, V: Sync> Sync for OccupiedEntry<'_, K, V> {} 205 206 // The parent module also adds methods that don't threaten the unsafe encapsulation. 207 impl<'a, K, V> OccupiedEntry<'a, K, V> { key(&self) -> &K208 pub fn key(&self) -> &K { 209 &self.key 210 } 211 get(&self) -> &V212 pub fn get(&self) -> &V { 213 &self.map.entries[self.index()].value 214 } 215 get_mut(&mut self) -> &mut V216 pub fn get_mut(&mut self) -> &mut V { 217 let index = self.index(); 218 &mut self.map.entries[index].value 219 } 220 221 /// Put the new key in the occupied entry's key slot replace_key(self) -> K222 pub(crate) fn replace_key(self) -> K { 223 let index = self.index(); 224 let old_key = &mut self.map.entries[index].key; 225 replace(old_key, self.key) 226 } 227 228 /// Return the index of the key-value pair 229 #[inline] index(&self) -> usize230 pub fn index(&self) -> usize { 231 unsafe { self.raw_bucket.read() } 232 } 233 into_mut(self) -> &'a mut V234 pub fn into_mut(self) -> &'a mut V { 235 let index = self.index(); 236 &mut self.map.entries[index].value 237 } 238 239 /// Remove and return the key, value pair stored in the map for this entry 240 /// 241 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the 242 /// last element of the map and popping it off. **This perturbs 243 /// the postion of what used to be the last element!** 244 /// 245 /// Computes in **O(1)** time (average). swap_remove_entry(self) -> (K, V)246 pub fn swap_remove_entry(self) -> (K, V) { 247 // This is safe because it can only happen once (self is consumed) 248 // and map.indices have not been modified since entry construction 249 unsafe { 250 let (_, key, value) = self.map.swap_remove_bucket(self.raw_bucket); 251 (key, value) 252 } 253 } 254 255 /// Remove and return the key, value pair stored in the map for this entry 256 /// 257 /// Like `Vec::remove`, the pair is removed by shifting all of the 258 /// elements that follow it, preserving their relative order. 259 /// **This perturbs the index of all of those elements!** 260 /// 261 /// Computes in **O(n)** time (average). shift_remove_entry(self) -> (K, V)262 pub fn shift_remove_entry(self) -> (K, V) { 263 // This is safe because it can only happen once (self is consumed) 264 // and map.indices have not been modified since entry construction 265 unsafe { 266 let (_, key, value) = self.map.shift_remove_bucket(self.raw_bucket); 267 (key, value) 268 } 269 } 270 } 271