1#![allow(unsafe_code)]
2//! This module encapsulates the `unsafe` access to `hashbrown::raw::RawTable`,
3//! mostly in dealing with its bucket "pointers".
4
5use super::{equivalent, get_hash, Bucket, Entry, HashValue, IndexMapCore, VacantEntry};
6use core::fmt;
7use core::mem::replace;
8use hashbrown::raw::RawTable;
9
10type 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.
15pub(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
25pub(super) struct DebugIndices<'a>(pub &'a RawTable<usize>);
26impl 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
34impl<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.
134pub 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.
142unsafe 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.
145impl<'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