1 //! This is the core implementation that doesn't depend on the hasher at all.
2 //!
3 //! The methods of `IndexMapCore` don't use any Hash properties of K.
4 //!
5 //! It's cleaner to separate them out, then the compiler checks that we are not
6 //! using Hash at all in these methods.
7 //!
8 //! However, we should probably not let this show in the public API or docs.
9
10 mod raw;
11
12 use hashbrown::raw::RawTable;
13
14 use crate::vec::{Drain, Vec};
15 use core::cmp;
16 use core::fmt;
17 use core::mem::replace;
18 use core::ops::RangeBounds;
19
20 use crate::equivalent::Equivalent;
21 use crate::util::{enumerate, simplify_range};
22 use crate::{Bucket, Entries, HashValue};
23
24 /// Core of the map that does not depend on S
25 pub(crate) struct IndexMapCore<K, V> {
26 /// indices mapping from the entry hash to its index.
27 indices: RawTable<usize>,
28 /// entries is a dense vec of entries in their order.
29 entries: Vec<Bucket<K, V>>,
30 }
31
32 #[inline(always)]
get_hash<K, V>(entries: &[Bucket<K, V>]) -> impl Fn(&usize) -> u64 + '_33 fn get_hash<K, V>(entries: &[Bucket<K, V>]) -> impl Fn(&usize) -> u64 + '_ {
34 move |&i| entries[i].hash.get()
35 }
36
37 impl<K, V> Clone for IndexMapCore<K, V>
38 where
39 K: Clone,
40 V: Clone,
41 {
clone(&self) -> Self42 fn clone(&self) -> Self {
43 let indices = self.indices.clone();
44 let mut entries = Vec::with_capacity(indices.capacity());
45 entries.clone_from(&self.entries);
46 IndexMapCore { indices, entries }
47 }
48
clone_from(&mut self, other: &Self)49 fn clone_from(&mut self, other: &Self) {
50 let hasher = get_hash(&other.entries);
51 self.indices.clone_from_with_hasher(&other.indices, hasher);
52 if self.entries.capacity() < other.entries.len() {
53 // If we must resize, match the indices capacity
54 self.reserve_entries();
55 }
56 self.entries.clone_from(&other.entries);
57 }
58 }
59
60 impl<K, V> fmt::Debug for IndexMapCore<K, V>
61 where
62 K: fmt::Debug,
63 V: fmt::Debug,
64 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result65 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
66 f.debug_struct("IndexMapCore")
67 .field("indices", &raw::DebugIndices(&self.indices))
68 .field("entries", &self.entries)
69 .finish()
70 }
71 }
72
73 impl<K, V> Entries for IndexMapCore<K, V> {
74 type Entry = Bucket<K, V>;
75
76 #[inline]
into_entries(self) -> Vec<Self::Entry>77 fn into_entries(self) -> Vec<Self::Entry> {
78 self.entries
79 }
80
81 #[inline]
as_entries(&self) -> &[Self::Entry]82 fn as_entries(&self) -> &[Self::Entry] {
83 &self.entries
84 }
85
86 #[inline]
as_entries_mut(&mut self) -> &mut [Self::Entry]87 fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
88 &mut self.entries
89 }
90
with_entries<F>(&mut self, f: F) where F: FnOnce(&mut [Self::Entry]),91 fn with_entries<F>(&mut self, f: F)
92 where
93 F: FnOnce(&mut [Self::Entry]),
94 {
95 f(&mut self.entries);
96 self.rebuild_hash_table();
97 }
98 }
99
100 impl<K, V> IndexMapCore<K, V> {
101 #[inline]
new() -> Self102 pub(crate) fn new() -> Self {
103 IndexMapCore {
104 indices: RawTable::new(),
105 entries: Vec::new(),
106 }
107 }
108
109 #[inline]
with_capacity(n: usize) -> Self110 pub(crate) fn with_capacity(n: usize) -> Self {
111 IndexMapCore {
112 indices: RawTable::with_capacity(n),
113 entries: Vec::with_capacity(n),
114 }
115 }
116
117 #[inline]
len(&self) -> usize118 pub(crate) fn len(&self) -> usize {
119 self.indices.len()
120 }
121
122 #[inline]
capacity(&self) -> usize123 pub(crate) fn capacity(&self) -> usize {
124 cmp::min(self.indices.capacity(), self.entries.capacity())
125 }
126
clear(&mut self)127 pub(crate) fn clear(&mut self) {
128 self.indices.clear();
129 self.entries.clear();
130 }
131
drain<R>(&mut self, range: R) -> Drain<'_, Bucket<K, V>> where R: RangeBounds<usize>,132 pub(crate) fn drain<R>(&mut self, range: R) -> Drain<'_, Bucket<K, V>>
133 where
134 R: RangeBounds<usize>,
135 {
136 let range = simplify_range(range, self.entries.len());
137 self.erase_indices(range.start, range.end);
138 self.entries.drain(range)
139 }
140
141 /// Reserve capacity for `additional` more key-value pairs.
reserve(&mut self, additional: usize)142 pub(crate) fn reserve(&mut self, additional: usize) {
143 self.indices.reserve(additional, get_hash(&self.entries));
144 self.reserve_entries();
145 }
146
147 /// Reserve entries capacity to match the indices
reserve_entries(&mut self)148 fn reserve_entries(&mut self) {
149 let additional = self.indices.capacity() - self.entries.len();
150 self.entries.reserve_exact(additional);
151 }
152
153 /// Shrink the capacity of the map as much as possible.
shrink_to_fit(&mut self)154 pub(crate) fn shrink_to_fit(&mut self) {
155 self.indices.shrink_to(0, get_hash(&self.entries));
156 self.entries.shrink_to_fit();
157 }
158
159 /// Remove the last key-value pair
pop(&mut self) -> Option<(K, V)>160 pub(crate) fn pop(&mut self) -> Option<(K, V)> {
161 if let Some(entry) = self.entries.pop() {
162 let last = self.entries.len();
163 self.erase_index(entry.hash, last);
164 Some((entry.key, entry.value))
165 } else {
166 None
167 }
168 }
169
170 /// Append a key-value pair, *without* checking whether it already exists,
171 /// and return the pair's new index.
push(&mut self, hash: HashValue, key: K, value: V) -> usize172 fn push(&mut self, hash: HashValue, key: K, value: V) -> usize {
173 let i = self.entries.len();
174 self.indices.insert(hash.get(), i, get_hash(&self.entries));
175 if i == self.entries.capacity() {
176 // Reserve our own capacity synced to the indices,
177 // rather than letting `Vec::push` just double it.
178 self.reserve_entries();
179 }
180 self.entries.push(Bucket { hash, key, value });
181 i
182 }
183
insert_full(&mut self, hash: HashValue, key: K, value: V) -> (usize, Option<V>) where K: Eq,184 pub(crate) fn insert_full(&mut self, hash: HashValue, key: K, value: V) -> (usize, Option<V>)
185 where
186 K: Eq,
187 {
188 match self.get_index_of(hash, &key) {
189 Some(i) => (i, Some(replace(&mut self.entries[i].value, value))),
190 None => (self.push(hash, key, value), None),
191 }
192 }
193
retain_in_order<F>(&mut self, mut keep: F) where F: FnMut(&mut K, &mut V) -> bool,194 pub(crate) fn retain_in_order<F>(&mut self, mut keep: F)
195 where
196 F: FnMut(&mut K, &mut V) -> bool,
197 {
198 // Like Vec::retain in self.entries, but with mutable K and V.
199 // We swap-shift all the items we want to keep, truncate the rest,
200 // then rebuild the raw hash table with the new indexes.
201 let len = self.entries.len();
202 let mut n_deleted = 0;
203 for i in 0..len {
204 let will_keep = {
205 let entry = &mut self.entries[i];
206 keep(&mut entry.key, &mut entry.value)
207 };
208 if !will_keep {
209 n_deleted += 1;
210 } else if n_deleted > 0 {
211 self.entries.swap(i - n_deleted, i);
212 }
213 }
214 if n_deleted > 0 {
215 self.entries.truncate(len - n_deleted);
216 self.rebuild_hash_table();
217 }
218 }
219
rebuild_hash_table(&mut self)220 fn rebuild_hash_table(&mut self) {
221 self.indices.clear();
222 debug_assert!(self.indices.capacity() >= self.entries.len());
223 for (i, entry) in enumerate(&self.entries) {
224 // We should never have to reallocate, so there's no need for a real hasher.
225 self.indices.insert_no_grow(entry.hash.get(), i);
226 }
227 }
228 }
229
230 /// Entry for an existing key-value pair or a vacant location to
231 /// insert one.
232 pub enum Entry<'a, K, V> {
233 /// Existing slot with equivalent key.
234 Occupied(OccupiedEntry<'a, K, V>),
235 /// Vacant slot (no equivalent key in the map).
236 Vacant(VacantEntry<'a, K, V>),
237 }
238
239 impl<'a, K, V> Entry<'a, K, V> {
240 /// Computes in **O(1)** time (amortized average).
or_insert(self, default: V) -> &'a mut V241 pub fn or_insert(self, default: V) -> &'a mut V {
242 match self {
243 Entry::Occupied(entry) => entry.into_mut(),
244 Entry::Vacant(entry) => entry.insert(default),
245 }
246 }
247
248 /// Computes in **O(1)** time (amortized average).
or_insert_with<F>(self, call: F) -> &'a mut V where F: FnOnce() -> V,249 pub fn or_insert_with<F>(self, call: F) -> &'a mut V
250 where
251 F: FnOnce() -> V,
252 {
253 match self {
254 Entry::Occupied(entry) => entry.into_mut(),
255 Entry::Vacant(entry) => entry.insert(call()),
256 }
257 }
258
key(&self) -> &K259 pub fn key(&self) -> &K {
260 match *self {
261 Entry::Occupied(ref entry) => entry.key(),
262 Entry::Vacant(ref entry) => entry.key(),
263 }
264 }
265
266 /// Return the index where the key-value pair exists or will be inserted.
index(&self) -> usize267 pub fn index(&self) -> usize {
268 match *self {
269 Entry::Occupied(ref entry) => entry.index(),
270 Entry::Vacant(ref entry) => entry.index(),
271 }
272 }
273
274 /// Modifies the entry if it is occupied.
and_modify<F>(self, f: F) -> Self where F: FnOnce(&mut V),275 pub fn and_modify<F>(self, f: F) -> Self
276 where
277 F: FnOnce(&mut V),
278 {
279 match self {
280 Entry::Occupied(mut o) => {
281 f(o.get_mut());
282 Entry::Occupied(o)
283 }
284 x => x,
285 }
286 }
287
288 /// Inserts a default-constructed value in the entry if it is vacant and returns a mutable
289 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
290 ///
291 /// Computes in **O(1)** time (amortized average).
or_default(self) -> &'a mut V where V: Default,292 pub fn or_default(self) -> &'a mut V
293 where
294 V: Default,
295 {
296 match self {
297 Entry::Occupied(entry) => entry.into_mut(),
298 Entry::Vacant(entry) => entry.insert(V::default()),
299 }
300 }
301 }
302
303 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Entry<'_, K, V> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result304 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
305 match *self {
306 Entry::Vacant(ref v) => f.debug_tuple(stringify!(Entry)).field(v).finish(),
307 Entry::Occupied(ref o) => f.debug_tuple(stringify!(Entry)).field(o).finish(),
308 }
309 }
310 }
311
312 pub use self::raw::OccupiedEntry;
313
314 // Extra methods that don't threaten the unsafe encapsulation.
315 impl<K, V> OccupiedEntry<'_, K, V> {
316 /// Sets the value of the entry to `value`, and returns the entry's old value.
insert(&mut self, value: V) -> V317 pub fn insert(&mut self, value: V) -> V {
318 replace(self.get_mut(), value)
319 }
320
321 /// Remove the key, value pair stored in the map for this entry, and return the value.
322 ///
323 /// **NOTE:** This is equivalent to `.swap_remove()`.
remove(self) -> V324 pub fn remove(self) -> V {
325 self.swap_remove()
326 }
327
328 /// Remove the key, value pair stored in the map for this entry, and return the value.
329 ///
330 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
331 /// last element of the map and popping it off. **This perturbs
332 /// the postion of what used to be the last element!**
333 ///
334 /// Computes in **O(1)** time (average).
swap_remove(self) -> V335 pub fn swap_remove(self) -> V {
336 self.swap_remove_entry().1
337 }
338
339 /// Remove the key, value pair stored in the map for this entry, and return the value.
340 ///
341 /// Like `Vec::remove`, the pair is removed by shifting all of the
342 /// elements that follow it, preserving their relative order.
343 /// **This perturbs the index of all of those elements!**
344 ///
345 /// Computes in **O(n)** time (average).
shift_remove(self) -> V346 pub fn shift_remove(self) -> V {
347 self.shift_remove_entry().1
348 }
349
350 /// Remove and return the key, value pair stored in the map for this entry
351 ///
352 /// **NOTE:** This is equivalent to `.swap_remove_entry()`.
remove_entry(self) -> (K, V)353 pub fn remove_entry(self) -> (K, V) {
354 self.swap_remove_entry()
355 }
356 }
357
358 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for OccupiedEntry<'_, K, V> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result359 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
360 f.debug_struct(stringify!(OccupiedEntry))
361 .field("key", self.key())
362 .field("value", self.get())
363 .finish()
364 }
365 }
366
367 /// A view into a vacant entry in a `IndexMap`.
368 /// It is part of the [`Entry`] enum.
369 ///
370 /// [`Entry`]: enum.Entry.html
371 pub struct VacantEntry<'a, K, V> {
372 map: &'a mut IndexMapCore<K, V>,
373 hash: HashValue,
374 key: K,
375 }
376
377 impl<'a, K, V> VacantEntry<'a, K, V> {
key(&self) -> &K378 pub fn key(&self) -> &K {
379 &self.key
380 }
381
into_key(self) -> K382 pub fn into_key(self) -> K {
383 self.key
384 }
385
386 /// Return the index where the key-value pair will be inserted.
index(&self) -> usize387 pub fn index(&self) -> usize {
388 self.map.len()
389 }
390
insert(self, value: V) -> &'a mut V391 pub fn insert(self, value: V) -> &'a mut V {
392 let i = self.map.push(self.hash, self.key, value);
393 &mut self.map.entries[i].value
394 }
395 }
396
397 impl<K: fmt::Debug, V> fmt::Debug for VacantEntry<'_, K, V> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result398 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
399 f.debug_tuple(stringify!(VacantEntry))
400 .field(self.key())
401 .finish()
402 }
403 }
404
405 #[test]
assert_send_sync()406 fn assert_send_sync() {
407 fn assert_send_sync<T: Send + Sync>() {}
408 assert_send_sync::<IndexMapCore<i32, i32>>();
409 assert_send_sync::<Entry<'_, i32, i32>>();
410 }
411