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, get_hash, 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: &Bucket in entries { |
18 | // SAFETY: we asserted that sufficient capacity exists for all entries. |
19 | unsafe { |
20 | indices.insert_no_grow(hash:entry.hash.get(), value: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.as_ref()) }; |
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.as_mut(); |
42 | if *i >= end { |
43 | *i -= offset; |
44 | } else if *i >= start { |
45 | self.indices.erase(bucket); |
46 | } |
47 | } |
48 | } |
49 | } |
50 | |
51 | /// Search for a key in the table and return `Ok(entry_index)` if found. |
52 | /// Otherwise, insert the key and return `Err(new_index)`. |
53 | /// |
54 | /// Note that hashbrown may resize the table to reserve space for insertion, |
55 | /// even before checking if it's already present, so this is somewhat biased |
56 | /// towards new items. |
57 | pub(crate) fn find_or_insert(&mut self, hash: HashValue, key: &K) -> Result<usize, usize> |
58 | where |
59 | K: Eq, |
60 | { |
61 | let hash = hash.get(); |
62 | let eq = equivalent(key, &self.entries); |
63 | let hasher = get_hash(&self.entries); |
64 | // SAFETY: We're not mutating between find and read/insert. |
65 | unsafe { |
66 | match self.indices.find_or_find_insert_slot(hash, eq, hasher) { |
67 | Ok(raw_bucket) => Ok(*raw_bucket.as_ref()), |
68 | Err(slot) => { |
69 | let index = self.indices.len(); |
70 | self.indices.insert_in_slot(hash, slot, index); |
71 | Err(index) |
72 | } |
73 | } |
74 | } |
75 | } |
76 | |
77 | pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V> |
78 | where |
79 | K: Eq, |
80 | { |
81 | let eq = equivalent(&key, &self.entries); |
82 | match self.indices.find(hash.get(), eq) { |
83 | // SAFETY: The entry is created with a live raw bucket, at the same time |
84 | // we have a &mut reference to the map, so it can not be modified further. |
85 | Some(raw_bucket) => Entry::Occupied(OccupiedEntry { |
86 | map: self, |
87 | raw_bucket, |
88 | key, |
89 | }), |
90 | None => Entry::Vacant(VacantEntry { |
91 | map: self, |
92 | hash, |
93 | key, |
94 | }), |
95 | } |
96 | } |
97 | |
98 | pub(super) fn indices_mut(&mut self) -> impl Iterator<Item = &mut usize> { |
99 | // SAFETY: we're not letting any of the buckets escape this function, |
100 | // only the item references that are appropriately bound to `&mut self`. |
101 | unsafe { self.indices.iter().map(|bucket| bucket.as_mut()) } |
102 | } |
103 | |
104 | /// Return the raw bucket for the given index |
105 | fn find_index(&self, index: usize) -> RawBucket { |
106 | // We'll get a "nice" bounds-check from indexing `self.entries`, |
107 | // and then we expect to find it in the table as well. |
108 | let hash = self.entries[index].hash.get(); |
109 | self.indices |
110 | .find(hash, move |&i| i == index) |
111 | .expect("index not found" ) |
112 | } |
113 | |
114 | pub(crate) fn swap_indices(&mut self, a: usize, b: usize) { |
115 | // SAFETY: Can't take two `get_mut` references from one table, so we |
116 | // must use raw buckets to do the swap. This is still safe because we |
117 | // are locally sure they won't dangle, and we write them individually. |
118 | unsafe { |
119 | let raw_bucket_a = self.find_index(a); |
120 | let raw_bucket_b = self.find_index(b); |
121 | *raw_bucket_a.as_mut() = b; |
122 | *raw_bucket_b.as_mut() = a; |
123 | } |
124 | self.entries.swap(a, b); |
125 | } |
126 | } |
127 | |
128 | /// A view into an occupied entry in a `IndexMap`. |
129 | /// It is part of the [`Entry`] enum. |
130 | /// |
131 | /// [`Entry`]: enum.Entry.html |
132 | // SAFETY: The lifetime of the map reference also constrains the raw bucket, |
133 | // which is essentially a raw pointer into the map indices. |
134 | pub struct OccupiedEntry<'a, K, V> { |
135 | map: &'a mut IndexMapCore<K, V>, |
136 | raw_bucket: RawBucket, |
137 | key: K, |
138 | } |
139 | |
140 | // `hashbrown::raw::Bucket` is only `Send`, not `Sync`. |
141 | // SAFETY: `&self` only accesses the bucket to read it. |
142 | unsafe impl<K: Sync, V: Sync> Sync for OccupiedEntry<'_, K, V> {} |
143 | |
144 | // The parent module also adds methods that don't threaten the unsafe encapsulation. |
145 | impl<'a, K, V> OccupiedEntry<'a, K, V> { |
146 | /// Gets a reference to the entry's key in the map. |
147 | /// |
148 | /// Note that this is not the key that was used to find the entry. There may be an observable |
149 | /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like |
150 | /// extra fields or the memory address of an allocation. |
151 | pub fn key(&self) -> &K { |
152 | &self.map.entries[self.index()].key |
153 | } |
154 | |
155 | /// Gets a reference to the entry's value in the map. |
156 | pub fn get(&self) -> &V { |
157 | &self.map.entries[self.index()].value |
158 | } |
159 | |
160 | /// Gets a mutable reference to the entry's value in the map. |
161 | /// |
162 | /// If you need a reference which may outlive the destruction of the |
163 | /// `Entry` value, see `into_mut`. |
164 | pub fn get_mut(&mut self) -> &mut V { |
165 | let index = self.index(); |
166 | &mut self.map.entries[index].value |
167 | } |
168 | |
169 | /// Put the new key in the occupied entry's key slot |
170 | pub(crate) fn replace_key(self) -> K { |
171 | let index = self.index(); |
172 | let old_key = &mut self.map.entries[index].key; |
173 | replace(old_key, self.key) |
174 | } |
175 | |
176 | /// Return the index of the key-value pair |
177 | #[inline ] |
178 | pub fn index(&self) -> usize { |
179 | // SAFETY: we have &mut map keep keeping the bucket stable |
180 | unsafe { *self.raw_bucket.as_ref() } |
181 | } |
182 | |
183 | /// Converts into a mutable reference to the entry's value in the map, |
184 | /// with a lifetime bound to the map itself. |
185 | pub fn into_mut(self) -> &'a mut V { |
186 | let index = self.index(); |
187 | &mut self.map.entries[index].value |
188 | } |
189 | |
190 | /// Remove and return the key, value pair stored in the map for this entry |
191 | /// |
192 | /// Like `Vec::swap_remove`, the pair is removed by swapping it with the |
193 | /// last element of the map and popping it off. **This perturbs |
194 | /// the position of what used to be the last element!** |
195 | /// |
196 | /// Computes in **O(1)** time (average). |
197 | pub fn swap_remove_entry(self) -> (K, V) { |
198 | // SAFETY: This is safe because it can only happen once (self is consumed) |
199 | // and map.indices have not been modified since entry construction |
200 | let (index, _slot) = unsafe { self.map.indices.remove(self.raw_bucket) }; |
201 | self.map.swap_remove_finish(index) |
202 | } |
203 | |
204 | /// Remove and return the key, value pair stored in the map for this entry |
205 | /// |
206 | /// Like `Vec::remove`, the pair is removed by shifting all of the |
207 | /// elements that follow it, preserving their relative order. |
208 | /// **This perturbs the index of all of those elements!** |
209 | /// |
210 | /// Computes in **O(n)** time (average). |
211 | pub fn shift_remove_entry(self) -> (K, V) { |
212 | // SAFETY: This is safe because it can only happen once (self is consumed) |
213 | // and map.indices have not been modified since entry construction |
214 | let (index, _slot) = unsafe { self.map.indices.remove(self.raw_bucket) }; |
215 | self.map.shift_remove_finish(index) |
216 | } |
217 | } |
218 | |