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, 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: impl Iterator = unsafe { self.0.iter().map(|raw_bucket: Bucket| raw_bucket.read()) };
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.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.
108pub 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.
116unsafe 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.
119impl<'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}
192