1 | use core::{fmt, iter::FusedIterator, marker::PhantomData}; |
2 | |
3 | use crate::{ |
4 | raw::{ |
5 | Allocator, Bucket, Global, InsertSlot, RawDrain, RawExtractIf, RawIntoIter, RawIter, |
6 | RawTable, |
7 | }, |
8 | TryReserveError, |
9 | }; |
10 | |
11 | /// Low-level hash table with explicit hashing. |
12 | /// |
13 | /// The primary use case for this type over [`HashMap`] or [`HashSet`] is to |
14 | /// support types that do not implement the [`Hash`] and [`Eq`] traits, but |
15 | /// instead require additional data not contained in the key itself to compute a |
16 | /// hash and compare two elements for equality. |
17 | /// |
18 | /// Examples of when this can be useful include: |
19 | /// - An `IndexMap` implementation where indices into a `Vec` are stored as |
20 | /// elements in a `HashTable<usize>`. Hashing and comparing the elements |
21 | /// requires indexing the associated `Vec` to get the actual value referred to |
22 | /// by the index. |
23 | /// - Avoiding re-computing a hash when it is already known. |
24 | /// - Mutating the key of an element in a way that doesn't affect its hash. |
25 | /// |
26 | /// To achieve this, `HashTable` methods that search for an element in the table |
27 | /// require a hash value and equality function to be explicitly passed in as |
28 | /// arguments. The method will then iterate over the elements with the given |
29 | /// hash and call the equality function on each of them, until a match is found. |
30 | /// |
31 | /// In most cases, a `HashTable` will not be exposed directly in an API. It will |
32 | /// instead be wrapped in a helper type which handles the work of calculating |
33 | /// hash values and comparing elements. |
34 | /// |
35 | /// Due to its low-level nature, this type provides fewer guarantees than |
36 | /// [`HashMap`] and [`HashSet`]. Specifically, the API allows you to shoot |
37 | /// yourself in the foot by having multiple elements with identical keys in the |
38 | /// table. The table itself will still function correctly and lookups will |
39 | /// arbitrarily return one of the matching elements. However you should avoid |
40 | /// doing this because it changes the runtime of hash table operations from |
41 | /// `O(1)` to `O(k)` where `k` is the number of duplicate entries. |
42 | /// |
43 | /// [`HashMap`]: super::HashMap |
44 | /// [`HashSet`]: super::HashSet |
45 | pub struct HashTable<T, A = Global> |
46 | where |
47 | A: Allocator, |
48 | { |
49 | pub(crate) raw: RawTable<T, A>, |
50 | } |
51 | |
52 | impl<T> HashTable<T, Global> { |
53 | /// Creates an empty `HashTable`. |
54 | /// |
55 | /// The hash table is initially created with a capacity of 0, so it will not allocate until it |
56 | /// is first inserted into. |
57 | /// |
58 | /// # Examples |
59 | /// |
60 | /// ``` |
61 | /// use hashbrown::HashTable; |
62 | /// let mut table: HashTable<&str> = HashTable::new(); |
63 | /// assert_eq!(table.len(), 0); |
64 | /// assert_eq!(table.capacity(), 0); |
65 | /// ``` |
66 | pub const fn new() -> Self { |
67 | Self { |
68 | raw: RawTable::new(), |
69 | } |
70 | } |
71 | |
72 | /// Creates an empty `HashTable` with the specified capacity. |
73 | /// |
74 | /// The hash table will be able to hold at least `capacity` elements without |
75 | /// reallocating. If `capacity` is 0, the hash table will not allocate. |
76 | /// |
77 | /// # Examples |
78 | /// |
79 | /// ``` |
80 | /// use hashbrown::HashTable; |
81 | /// let mut table: HashTable<&str> = HashTable::with_capacity(10); |
82 | /// assert_eq!(table.len(), 0); |
83 | /// assert!(table.capacity() >= 10); |
84 | /// ``` |
85 | pub fn with_capacity(capacity: usize) -> Self { |
86 | Self { |
87 | raw: RawTable::with_capacity(capacity), |
88 | } |
89 | } |
90 | } |
91 | |
92 | impl<T, A> HashTable<T, A> |
93 | where |
94 | A: Allocator, |
95 | { |
96 | /// Creates an empty `HashTable` using the given allocator. |
97 | /// |
98 | /// The hash table is initially created with a capacity of 0, so it will not allocate until it |
99 | /// is first inserted into. |
100 | /// |
101 | /// # Examples |
102 | /// |
103 | /// ``` |
104 | /// # #[cfg (feature = "nightly" )] |
105 | /// # fn test() { |
106 | /// use ahash::AHasher; |
107 | /// use bumpalo::Bump; |
108 | /// use hashbrown::HashTable; |
109 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
110 | /// |
111 | /// let bump = Bump::new(); |
112 | /// let mut table = HashTable::new_in(&bump); |
113 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
114 | /// let hasher = |val: &_| hasher.hash_one(val); |
115 | /// |
116 | /// // The created HashTable holds none elements |
117 | /// assert_eq!(table.len(), 0); |
118 | /// |
119 | /// // The created HashTable also doesn't allocate memory |
120 | /// assert_eq!(table.capacity(), 0); |
121 | /// |
122 | /// // Now we insert element inside created HashTable |
123 | /// table.insert_unique(hasher(&"One" ), "One" , hasher); |
124 | /// // We can see that the HashTable holds 1 element |
125 | /// assert_eq!(table.len(), 1); |
126 | /// // And it also allocates some capacity |
127 | /// assert!(table.capacity() > 1); |
128 | /// # } |
129 | /// # fn main() { |
130 | /// # #[cfg (feature = "nightly" )] |
131 | /// # test() |
132 | /// # } |
133 | /// ``` |
134 | pub const fn new_in(alloc: A) -> Self { |
135 | Self { |
136 | raw: RawTable::new_in(alloc), |
137 | } |
138 | } |
139 | |
140 | /// Creates an empty `HashTable` with the specified capacity using the given allocator. |
141 | /// |
142 | /// The hash table will be able to hold at least `capacity` elements without |
143 | /// reallocating. If `capacity` is 0, the hash table will not allocate. |
144 | /// |
145 | /// # Examples |
146 | /// |
147 | /// ``` |
148 | /// # #[cfg (feature = "nightly" )] |
149 | /// # fn test() { |
150 | /// use ahash::AHasher; |
151 | /// use bumpalo::Bump; |
152 | /// use hashbrown::HashTable; |
153 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
154 | /// |
155 | /// let bump = Bump::new(); |
156 | /// let mut table = HashTable::with_capacity_in(5, &bump); |
157 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
158 | /// let hasher = |val: &_| hasher.hash_one(val); |
159 | /// |
160 | /// // The created HashTable holds none elements |
161 | /// assert_eq!(table.len(), 0); |
162 | /// // But it can hold at least 5 elements without reallocating |
163 | /// let empty_map_capacity = table.capacity(); |
164 | /// assert!(empty_map_capacity >= 5); |
165 | /// |
166 | /// // Now we insert some 5 elements inside created HashTable |
167 | /// table.insert_unique(hasher(&"One" ), "One" , hasher); |
168 | /// table.insert_unique(hasher(&"Two" ), "Two" , hasher); |
169 | /// table.insert_unique(hasher(&"Three" ), "Three" , hasher); |
170 | /// table.insert_unique(hasher(&"Four" ), "Four" , hasher); |
171 | /// table.insert_unique(hasher(&"Five" ), "Five" , hasher); |
172 | /// |
173 | /// // We can see that the HashTable holds 5 elements |
174 | /// assert_eq!(table.len(), 5); |
175 | /// // But its capacity isn't changed |
176 | /// assert_eq!(table.capacity(), empty_map_capacity) |
177 | /// # } |
178 | /// # fn main() { |
179 | /// # #[cfg (feature = "nightly" )] |
180 | /// # test() |
181 | /// # } |
182 | /// ``` |
183 | pub fn with_capacity_in(capacity: usize, alloc: A) -> Self { |
184 | Self { |
185 | raw: RawTable::with_capacity_in(capacity, alloc), |
186 | } |
187 | } |
188 | |
189 | /// Returns a reference to the underlying allocator. |
190 | pub fn allocator(&self) -> &A { |
191 | self.raw.allocator() |
192 | } |
193 | |
194 | /// Returns a reference to an entry in the table with the given hash and |
195 | /// which satisfies the equality function passed. |
196 | /// |
197 | /// This method will call `eq` for all entries with the given hash, but may |
198 | /// also call it for entries with a different hash. `eq` should only return |
199 | /// true for the desired entry, at which point the search is stopped. |
200 | /// |
201 | /// # Examples |
202 | /// |
203 | /// ``` |
204 | /// # #[cfg (feature = "nightly" )] |
205 | /// # fn test() { |
206 | /// use ahash::AHasher; |
207 | /// use hashbrown::HashTable; |
208 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
209 | /// |
210 | /// let mut table = HashTable::new(); |
211 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
212 | /// let hasher = |val: &_| hasher.hash_one(val); |
213 | /// table.insert_unique(hasher(&1), 1, hasher); |
214 | /// table.insert_unique(hasher(&2), 2, hasher); |
215 | /// table.insert_unique(hasher(&3), 3, hasher); |
216 | /// assert_eq!(table.find(hasher(&2), |&val| val == 2), Some(&2)); |
217 | /// assert_eq!(table.find(hasher(&4), |&val| val == 4), None); |
218 | /// # } |
219 | /// # fn main() { |
220 | /// # #[cfg (feature = "nightly" )] |
221 | /// # test() |
222 | /// # } |
223 | /// ``` |
224 | pub fn find(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T> { |
225 | self.raw.get(hash, eq) |
226 | } |
227 | |
228 | /// Returns a mutable reference to an entry in the table with the given hash |
229 | /// and which satisfies the equality function passed. |
230 | /// |
231 | /// This method will call `eq` for all entries with the given hash, but may |
232 | /// also call it for entries with a different hash. `eq` should only return |
233 | /// true for the desired entry, at which point the search is stopped. |
234 | /// |
235 | /// When mutating an entry, you should ensure that it still retains the same |
236 | /// hash value as when it was inserted, otherwise lookups of that entry may |
237 | /// fail to find it. |
238 | /// |
239 | /// # Examples |
240 | /// |
241 | /// ``` |
242 | /// # #[cfg (feature = "nightly" )] |
243 | /// # fn test() { |
244 | /// use ahash::AHasher; |
245 | /// use hashbrown::HashTable; |
246 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
247 | /// |
248 | /// let mut table = HashTable::new(); |
249 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
250 | /// let hasher = |val: &_| hasher.hash_one(val); |
251 | /// table.insert_unique(hasher(&1), (1, "a" ), |val| hasher(&val.0)); |
252 | /// if let Some(val) = table.find_mut(hasher(&1), |val| val.0 == 1) { |
253 | /// val.1 = "b" ; |
254 | /// } |
255 | /// assert_eq!(table.find(hasher(&1), |val| val.0 == 1), Some(&(1, "b" ))); |
256 | /// assert_eq!(table.find(hasher(&2), |val| val.0 == 2), None); |
257 | /// # } |
258 | /// # fn main() { |
259 | /// # #[cfg (feature = "nightly" )] |
260 | /// # test() |
261 | /// # } |
262 | /// ``` |
263 | pub fn find_mut(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&mut T> { |
264 | self.raw.get_mut(hash, eq) |
265 | } |
266 | |
267 | /// Returns an `OccupiedEntry` for an entry in the table with the given hash |
268 | /// and which satisfies the equality function passed. |
269 | /// |
270 | /// This can be used to remove the entry from the table. Call |
271 | /// [`HashTable::entry`] instead if you wish to insert an entry if the |
272 | /// lookup fails. |
273 | /// |
274 | /// This method will call `eq` for all entries with the given hash, but may |
275 | /// also call it for entries with a different hash. `eq` should only return |
276 | /// true for the desired entry, at which point the search is stopped. |
277 | /// |
278 | /// # Examples |
279 | /// |
280 | /// ``` |
281 | /// # #[cfg (feature = "nightly" )] |
282 | /// # fn test() { |
283 | /// use ahash::AHasher; |
284 | /// use hashbrown::HashTable; |
285 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
286 | /// |
287 | /// let mut table = HashTable::new(); |
288 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
289 | /// let hasher = |val: &_| hasher.hash_one(val); |
290 | /// table.insert_unique(hasher(&1), (1, "a" ), |val| hasher(&val.0)); |
291 | /// if let Ok(entry) = table.find_entry(hasher(&1), |val| val.0 == 1) { |
292 | /// entry.remove(); |
293 | /// } |
294 | /// assert_eq!(table.find(hasher(&1), |val| val.0 == 1), None); |
295 | /// # } |
296 | /// # fn main() { |
297 | /// # #[cfg (feature = "nightly" )] |
298 | /// # test() |
299 | /// # } |
300 | /// ``` |
301 | pub fn find_entry( |
302 | &mut self, |
303 | hash: u64, |
304 | eq: impl FnMut(&T) -> bool, |
305 | ) -> Result<OccupiedEntry<'_, T, A>, AbsentEntry<'_, T, A>> { |
306 | match self.raw.find(hash, eq) { |
307 | Some(bucket) => Ok(OccupiedEntry { |
308 | hash, |
309 | bucket, |
310 | table: self, |
311 | }), |
312 | None => Err(AbsentEntry { table: self }), |
313 | } |
314 | } |
315 | |
316 | /// Returns an `Entry` for an entry in the table with the given hash |
317 | /// and which satisfies the equality function passed. |
318 | /// |
319 | /// This can be used to remove the entry from the table, or insert a new |
320 | /// entry with the given hash if one doesn't already exist. |
321 | /// |
322 | /// This method will call `eq` for all entries with the given hash, but may |
323 | /// also call it for entries with a different hash. `eq` should only return |
324 | /// true for the desired entry, at which point the search is stopped. |
325 | /// |
326 | /// This method may grow the table in preparation for an insertion. Call |
327 | /// [`HashTable::find_entry`] if this is undesirable. |
328 | /// |
329 | /// `hasher` is called if entries need to be moved or copied to a new table. |
330 | /// This must return the same hash value that each entry was inserted with. |
331 | /// |
332 | /// # Examples |
333 | /// |
334 | /// ``` |
335 | /// # #[cfg (feature = "nightly" )] |
336 | /// # fn test() { |
337 | /// use ahash::AHasher; |
338 | /// use hashbrown::hash_table::Entry; |
339 | /// use hashbrown::HashTable; |
340 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
341 | /// |
342 | /// let mut table = HashTable::new(); |
343 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
344 | /// let hasher = |val: &_| hasher.hash_one(val); |
345 | /// table.insert_unique(hasher(&1), (1, "a" ), |val| hasher(&val.0)); |
346 | /// if let Entry::Occupied(entry) = table.entry(hasher(&1), |val| val.0 == 1, |val| hasher(&val.0)) |
347 | /// { |
348 | /// entry.remove(); |
349 | /// } |
350 | /// if let Entry::Vacant(entry) = table.entry(hasher(&2), |val| val.0 == 2, |val| hasher(&val.0)) { |
351 | /// entry.insert((2, "b" )); |
352 | /// } |
353 | /// assert_eq!(table.find(hasher(&1), |val| val.0 == 1), None); |
354 | /// assert_eq!(table.find(hasher(&2), |val| val.0 == 2), Some(&(2, "b" ))); |
355 | /// # } |
356 | /// # fn main() { |
357 | /// # #[cfg (feature = "nightly" )] |
358 | /// # test() |
359 | /// # } |
360 | /// ``` |
361 | pub fn entry( |
362 | &mut self, |
363 | hash: u64, |
364 | eq: impl FnMut(&T) -> bool, |
365 | hasher: impl Fn(&T) -> u64, |
366 | ) -> Entry<'_, T, A> { |
367 | match self.raw.find_or_find_insert_slot(hash, eq, hasher) { |
368 | Ok(bucket) => Entry::Occupied(OccupiedEntry { |
369 | hash, |
370 | bucket, |
371 | table: self, |
372 | }), |
373 | Err(insert_slot) => Entry::Vacant(VacantEntry { |
374 | hash, |
375 | insert_slot, |
376 | table: self, |
377 | }), |
378 | } |
379 | } |
380 | |
381 | /// Inserts an element into the `HashTable` with the given hash value, but |
382 | /// without checking whether an equivalent element already exists within the |
383 | /// table. |
384 | /// |
385 | /// `hasher` is called if entries need to be moved or copied to a new table. |
386 | /// This must return the same hash value that each entry was inserted with. |
387 | /// |
388 | /// # Examples |
389 | /// |
390 | /// ``` |
391 | /// # #[cfg (feature = "nightly" )] |
392 | /// # fn test() { |
393 | /// use ahash::AHasher; |
394 | /// use hashbrown::HashTable; |
395 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
396 | /// |
397 | /// let mut v = HashTable::new(); |
398 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
399 | /// let hasher = |val: &_| hasher.hash_one(val); |
400 | /// v.insert_unique(hasher(&1), 1, hasher); |
401 | /// # } |
402 | /// # fn main() { |
403 | /// # #[cfg (feature = "nightly" )] |
404 | /// # test() |
405 | /// # } |
406 | /// ``` |
407 | pub fn insert_unique( |
408 | &mut self, |
409 | hash: u64, |
410 | value: T, |
411 | hasher: impl Fn(&T) -> u64, |
412 | ) -> OccupiedEntry<'_, T, A> { |
413 | let bucket = self.raw.insert(hash, value, hasher); |
414 | OccupiedEntry { |
415 | hash, |
416 | bucket, |
417 | table: self, |
418 | } |
419 | } |
420 | |
421 | /// Clears the table, removing all values. |
422 | /// |
423 | /// # Examples |
424 | /// |
425 | /// ``` |
426 | /// # #[cfg (feature = "nightly" )] |
427 | /// # fn test() { |
428 | /// use ahash::AHasher; |
429 | /// use hashbrown::HashTable; |
430 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
431 | /// |
432 | /// let mut v = HashTable::new(); |
433 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
434 | /// let hasher = |val: &_| hasher.hash_one(val); |
435 | /// v.insert_unique(hasher(&1), 1, hasher); |
436 | /// v.clear(); |
437 | /// assert!(v.is_empty()); |
438 | /// # } |
439 | /// # fn main() { |
440 | /// # #[cfg (feature = "nightly" )] |
441 | /// # test() |
442 | /// # } |
443 | /// ``` |
444 | pub fn clear(&mut self) { |
445 | self.raw.clear(); |
446 | } |
447 | |
448 | /// Shrinks the capacity of the table as much as possible. It will drop |
449 | /// down as much as possible while maintaining the internal rules |
450 | /// and possibly leaving some space in accordance with the resize policy. |
451 | /// |
452 | /// `hasher` is called if entries need to be moved or copied to a new table. |
453 | /// This must return the same hash value that each entry was inserted with. |
454 | /// |
455 | /// # Examples |
456 | /// |
457 | /// ``` |
458 | /// # #[cfg (feature = "nightly" )] |
459 | /// # fn test() { |
460 | /// use ahash::AHasher; |
461 | /// use hashbrown::HashTable; |
462 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
463 | /// |
464 | /// let mut table = HashTable::with_capacity(100); |
465 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
466 | /// let hasher = |val: &_| hasher.hash_one(val); |
467 | /// table.insert_unique(hasher(&1), 1, hasher); |
468 | /// table.insert_unique(hasher(&2), 2, hasher); |
469 | /// assert!(table.capacity() >= 100); |
470 | /// table.shrink_to_fit(hasher); |
471 | /// assert!(table.capacity() >= 2); |
472 | /// # } |
473 | /// # fn main() { |
474 | /// # #[cfg (feature = "nightly" )] |
475 | /// # test() |
476 | /// # } |
477 | /// ``` |
478 | pub fn shrink_to_fit(&mut self, hasher: impl Fn(&T) -> u64) { |
479 | self.raw.shrink_to(self.len(), hasher) |
480 | } |
481 | |
482 | /// Shrinks the capacity of the table with a lower limit. It will drop |
483 | /// down no lower than the supplied limit while maintaining the internal rules |
484 | /// and possibly leaving some space in accordance with the resize policy. |
485 | /// |
486 | /// `hasher` is called if entries need to be moved or copied to a new table. |
487 | /// This must return the same hash value that each entry was inserted with. |
488 | /// |
489 | /// Panics if the current capacity is smaller than the supplied |
490 | /// minimum capacity. |
491 | /// |
492 | /// # Examples |
493 | /// |
494 | /// ``` |
495 | /// # #[cfg (feature = "nightly" )] |
496 | /// # fn test() { |
497 | /// use ahash::AHasher; |
498 | /// use hashbrown::HashTable; |
499 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
500 | /// |
501 | /// let mut table = HashTable::with_capacity(100); |
502 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
503 | /// let hasher = |val: &_| hasher.hash_one(val); |
504 | /// table.insert_unique(hasher(&1), 1, hasher); |
505 | /// table.insert_unique(hasher(&2), 2, hasher); |
506 | /// assert!(table.capacity() >= 100); |
507 | /// table.shrink_to(10, hasher); |
508 | /// assert!(table.capacity() >= 10); |
509 | /// table.shrink_to(0, hasher); |
510 | /// assert!(table.capacity() >= 2); |
511 | /// # } |
512 | /// # fn main() { |
513 | /// # #[cfg (feature = "nightly" )] |
514 | /// # test() |
515 | /// # } |
516 | /// ``` |
517 | pub fn shrink_to(&mut self, min_capacity: usize, hasher: impl Fn(&T) -> u64) { |
518 | self.raw.shrink_to(min_capacity, hasher); |
519 | } |
520 | |
521 | /// Reserves capacity for at least `additional` more elements to be inserted |
522 | /// in the `HashTable`. The collection may reserve more space to avoid |
523 | /// frequent reallocations. |
524 | /// |
525 | /// `hasher` is called if entries need to be moved or copied to a new table. |
526 | /// This must return the same hash value that each entry was inserted with. |
527 | /// |
528 | /// # Panics |
529 | /// |
530 | /// Panics if the new capacity exceeds [`isize::MAX`] bytes and [`abort`] the program |
531 | /// in case of allocation error. Use [`try_reserve`](HashTable::try_reserve) instead |
532 | /// if you want to handle memory allocation failure. |
533 | /// |
534 | /// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html |
535 | /// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html |
536 | /// |
537 | /// # Examples |
538 | /// |
539 | /// ``` |
540 | /// # #[cfg (feature = "nightly" )] |
541 | /// # fn test() { |
542 | /// use ahash::AHasher; |
543 | /// use hashbrown::HashTable; |
544 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
545 | /// |
546 | /// let mut table: HashTable<i32> = HashTable::new(); |
547 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
548 | /// let hasher = |val: &_| hasher.hash_one(val); |
549 | /// table.reserve(10, hasher); |
550 | /// assert!(table.capacity() >= 10); |
551 | /// # } |
552 | /// # fn main() { |
553 | /// # #[cfg (feature = "nightly" )] |
554 | /// # test() |
555 | /// # } |
556 | /// ``` |
557 | pub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64) { |
558 | self.raw.reserve(additional, hasher) |
559 | } |
560 | |
561 | /// Tries to reserve capacity for at least `additional` more elements to be inserted |
562 | /// in the given `HashTable`. The collection may reserve more space to avoid |
563 | /// frequent reallocations. |
564 | /// |
565 | /// `hasher` is called if entries need to be moved or copied to a new table. |
566 | /// This must return the same hash value that each entry was inserted with. |
567 | /// |
568 | /// # Errors |
569 | /// |
570 | /// If the capacity overflows, or the allocator reports a failure, then an error |
571 | /// is returned. |
572 | /// |
573 | /// # Examples |
574 | /// |
575 | /// ``` |
576 | /// # #[cfg (feature = "nightly" )] |
577 | /// # fn test() { |
578 | /// use ahash::AHasher; |
579 | /// use hashbrown::HashTable; |
580 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
581 | /// |
582 | /// let mut table: HashTable<i32> = HashTable::new(); |
583 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
584 | /// let hasher = |val: &_| hasher.hash_one(val); |
585 | /// table |
586 | /// .try_reserve(10, hasher) |
587 | /// .expect("why is the test harness OOMing on 10 bytes?" ); |
588 | /// # } |
589 | /// # fn main() { |
590 | /// # #[cfg (feature = "nightly" )] |
591 | /// # test() |
592 | /// # } |
593 | /// ``` |
594 | pub fn try_reserve( |
595 | &mut self, |
596 | additional: usize, |
597 | hasher: impl Fn(&T) -> u64, |
598 | ) -> Result<(), TryReserveError> { |
599 | self.raw.try_reserve(additional, hasher) |
600 | } |
601 | |
602 | /// Returns the number of elements the table can hold without reallocating. |
603 | /// |
604 | /// # Examples |
605 | /// |
606 | /// ``` |
607 | /// use hashbrown::HashTable; |
608 | /// let table: HashTable<i32> = HashTable::with_capacity(100); |
609 | /// assert!(table.capacity() >= 100); |
610 | /// ``` |
611 | pub fn capacity(&self) -> usize { |
612 | self.raw.capacity() |
613 | } |
614 | |
615 | /// Returns the number of elements in the table. |
616 | /// |
617 | /// # Examples |
618 | /// |
619 | /// ``` |
620 | /// # #[cfg (feature = "nightly" )] |
621 | /// # fn test() { |
622 | /// use ahash::AHasher; |
623 | /// use hashbrown::HashTable; |
624 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
625 | /// |
626 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
627 | /// let hasher = |val: &_| hasher.hash_one(val); |
628 | /// let mut v = HashTable::new(); |
629 | /// assert_eq!(v.len(), 0); |
630 | /// v.insert_unique(hasher(&1), 1, hasher); |
631 | /// assert_eq!(v.len(), 1); |
632 | /// # } |
633 | /// # fn main() { |
634 | /// # #[cfg (feature = "nightly" )] |
635 | /// # test() |
636 | /// # } |
637 | /// ``` |
638 | pub fn len(&self) -> usize { |
639 | self.raw.len() |
640 | } |
641 | |
642 | /// Returns `true` if the set contains no elements. |
643 | /// |
644 | /// # Examples |
645 | /// |
646 | /// ``` |
647 | /// # #[cfg (feature = "nightly" )] |
648 | /// # fn test() { |
649 | /// use ahash::AHasher; |
650 | /// use hashbrown::HashTable; |
651 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
652 | /// |
653 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
654 | /// let hasher = |val: &_| hasher.hash_one(val); |
655 | /// let mut v = HashTable::new(); |
656 | /// assert!(v.is_empty()); |
657 | /// v.insert_unique(hasher(&1), 1, hasher); |
658 | /// assert!(!v.is_empty()); |
659 | /// # } |
660 | /// # fn main() { |
661 | /// # #[cfg (feature = "nightly" )] |
662 | /// # test() |
663 | /// # } |
664 | /// ``` |
665 | pub fn is_empty(&self) -> bool { |
666 | self.raw.is_empty() |
667 | } |
668 | |
669 | /// An iterator visiting all elements in arbitrary order. |
670 | /// The iterator element type is `&'a T`. |
671 | /// |
672 | /// # Examples |
673 | /// |
674 | /// ``` |
675 | /// # #[cfg (feature = "nightly" )] |
676 | /// # fn test() { |
677 | /// use ahash::AHasher; |
678 | /// use hashbrown::HashTable; |
679 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
680 | /// |
681 | /// let mut table = HashTable::new(); |
682 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
683 | /// let hasher = |val: &_| hasher.hash_one(val); |
684 | /// table.insert_unique(hasher(&"a" ), "b" , hasher); |
685 | /// table.insert_unique(hasher(&"b" ), "b" , hasher); |
686 | /// |
687 | /// // Will print in an arbitrary order. |
688 | /// for x in table.iter() { |
689 | /// println!("{}" , x); |
690 | /// } |
691 | /// # } |
692 | /// # fn main() { |
693 | /// # #[cfg (feature = "nightly" )] |
694 | /// # test() |
695 | /// # } |
696 | /// ``` |
697 | pub fn iter(&self) -> Iter<'_, T> { |
698 | Iter { |
699 | inner: unsafe { self.raw.iter() }, |
700 | marker: PhantomData, |
701 | } |
702 | } |
703 | |
704 | /// An iterator visiting all elements in arbitrary order, |
705 | /// with mutable references to the elements. |
706 | /// The iterator element type is `&'a mut T`. |
707 | /// |
708 | /// # Examples |
709 | /// |
710 | /// ``` |
711 | /// # #[cfg (feature = "nightly" )] |
712 | /// # fn test() { |
713 | /// use ahash::AHasher; |
714 | /// use hashbrown::HashTable; |
715 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
716 | /// |
717 | /// let mut table = HashTable::new(); |
718 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
719 | /// let hasher = |val: &_| hasher.hash_one(val); |
720 | /// table.insert_unique(hasher(&1), 1, hasher); |
721 | /// table.insert_unique(hasher(&2), 2, hasher); |
722 | /// table.insert_unique(hasher(&3), 3, hasher); |
723 | /// |
724 | /// // Update all values |
725 | /// for val in table.iter_mut() { |
726 | /// *val *= 2; |
727 | /// } |
728 | /// |
729 | /// assert_eq!(table.len(), 3); |
730 | /// let mut vec: Vec<i32> = Vec::new(); |
731 | /// |
732 | /// for val in &table { |
733 | /// println!("val: {}" , val); |
734 | /// vec.push(*val); |
735 | /// } |
736 | /// |
737 | /// // The `Iter` iterator produces items in arbitrary order, so the |
738 | /// // items must be sorted to test them against a sorted array. |
739 | /// vec.sort_unstable(); |
740 | /// assert_eq!(vec, [2, 4, 6]); |
741 | /// |
742 | /// assert_eq!(table.len(), 3); |
743 | /// # } |
744 | /// # fn main() { |
745 | /// # #[cfg (feature = "nightly" )] |
746 | /// # test() |
747 | /// # } |
748 | /// ``` |
749 | pub fn iter_mut(&mut self) -> IterMut<'_, T> { |
750 | IterMut { |
751 | inner: unsafe { self.raw.iter() }, |
752 | marker: PhantomData, |
753 | } |
754 | } |
755 | |
756 | /// Retains only the elements specified by the predicate. |
757 | /// |
758 | /// In other words, remove all elements `e` such that `f(&e)` returns `false`. |
759 | /// |
760 | /// # Examples |
761 | /// |
762 | /// ``` |
763 | /// # #[cfg (feature = "nightly" )] |
764 | /// # fn test() { |
765 | /// use ahash::AHasher; |
766 | /// use hashbrown::HashTable; |
767 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
768 | /// |
769 | /// let mut table = HashTable::new(); |
770 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
771 | /// let hasher = |val: &_| hasher.hash_one(val); |
772 | /// for x in 1..=6 { |
773 | /// table.insert_unique(hasher(&x), x, hasher); |
774 | /// } |
775 | /// table.retain(|&mut x| x % 2 == 0); |
776 | /// assert_eq!(table.len(), 3); |
777 | /// # } |
778 | /// # fn main() { |
779 | /// # #[cfg (feature = "nightly" )] |
780 | /// # test() |
781 | /// # } |
782 | /// ``` |
783 | pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) { |
784 | // Here we only use `iter` as a temporary, preventing use-after-free |
785 | unsafe { |
786 | for item in self.raw.iter() { |
787 | if !f(item.as_mut()) { |
788 | self.raw.erase(item); |
789 | } |
790 | } |
791 | } |
792 | } |
793 | |
794 | /// Clears the set, returning all elements in an iterator. |
795 | /// |
796 | /// # Examples |
797 | /// |
798 | /// ``` |
799 | /// # #[cfg (feature = "nightly" )] |
800 | /// # fn test() { |
801 | /// use ahash::AHasher; |
802 | /// use hashbrown::HashTable; |
803 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
804 | /// |
805 | /// let mut table = HashTable::new(); |
806 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
807 | /// let hasher = |val: &_| hasher.hash_one(val); |
808 | /// for x in 1..=3 { |
809 | /// table.insert_unique(hasher(&x), x, hasher); |
810 | /// } |
811 | /// assert!(!table.is_empty()); |
812 | /// |
813 | /// // print 1, 2, 3 in an arbitrary order |
814 | /// for i in table.drain() { |
815 | /// println!("{}" , i); |
816 | /// } |
817 | /// |
818 | /// assert!(table.is_empty()); |
819 | /// # } |
820 | /// # fn main() { |
821 | /// # #[cfg (feature = "nightly" )] |
822 | /// # test() |
823 | /// # } |
824 | /// ``` |
825 | pub fn drain(&mut self) -> Drain<'_, T, A> { |
826 | Drain { |
827 | inner: self.raw.drain(), |
828 | } |
829 | } |
830 | |
831 | /// Drains elements which are true under the given predicate, |
832 | /// and returns an iterator over the removed items. |
833 | /// |
834 | /// In other words, move all elements `e` such that `f(&e)` returns `true` out |
835 | /// into another iterator. |
836 | /// |
837 | /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating |
838 | /// or the iteration short-circuits, then the remaining elements will be retained. |
839 | /// Use [`retain()`] with a negated predicate if you do not need the returned iterator. |
840 | /// |
841 | /// [`retain()`]: HashTable::retain |
842 | /// |
843 | /// # Examples |
844 | /// |
845 | /// ``` |
846 | /// # #[cfg (feature = "nightly" )] |
847 | /// # fn test() { |
848 | /// use ahash::AHasher; |
849 | /// use hashbrown::HashTable; |
850 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
851 | /// |
852 | /// let mut table = HashTable::new(); |
853 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
854 | /// let hasher = |val: &_| hasher.hash_one(val); |
855 | /// for x in 0..8 { |
856 | /// table.insert_unique(hasher(&x), x, hasher); |
857 | /// } |
858 | /// let drained: Vec<i32> = table.extract_if(|&mut v| v % 2 == 0).collect(); |
859 | /// |
860 | /// let mut evens = drained.into_iter().collect::<Vec<_>>(); |
861 | /// let mut odds = table.into_iter().collect::<Vec<_>>(); |
862 | /// evens.sort(); |
863 | /// odds.sort(); |
864 | /// |
865 | /// assert_eq!(evens, vec![0, 2, 4, 6]); |
866 | /// assert_eq!(odds, vec![1, 3, 5, 7]); |
867 | /// # } |
868 | /// # fn main() { |
869 | /// # #[cfg (feature = "nightly" )] |
870 | /// # test() |
871 | /// # } |
872 | /// ``` |
873 | pub fn extract_if<F>(&mut self, f: F) -> ExtractIf<'_, T, F, A> |
874 | where |
875 | F: FnMut(&mut T) -> bool, |
876 | { |
877 | ExtractIf { |
878 | f, |
879 | inner: RawExtractIf { |
880 | iter: unsafe { self.raw.iter() }, |
881 | table: &mut self.raw, |
882 | }, |
883 | } |
884 | } |
885 | |
886 | /// Attempts to get mutable references to `N` values in the map at once. |
887 | /// |
888 | /// The `eq` argument should be a closure such that `eq(i, k)` returns true if `k` is equal to |
889 | /// the `i`th key to be looked up. |
890 | /// |
891 | /// Returns an array of length `N` with the results of each query. For soundness, at most one |
892 | /// mutable reference will be returned to any value. `None` will be returned if any of the |
893 | /// keys are duplicates or missing. |
894 | /// |
895 | /// # Examples |
896 | /// |
897 | /// ``` |
898 | /// # #[cfg (feature = "nightly" )] |
899 | /// # fn test() { |
900 | /// use ahash::AHasher; |
901 | /// use hashbrown::hash_table::Entry; |
902 | /// use hashbrown::HashTable; |
903 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
904 | /// |
905 | /// let mut libraries: HashTable<(&str, u32)> = HashTable::new(); |
906 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
907 | /// let hasher = |val: &_| hasher.hash_one(val); |
908 | /// for (k, v) in [ |
909 | /// ("Bodleian Library" , 1602), |
910 | /// ("Athenæum" , 1807), |
911 | /// ("Herzogin-Anna-Amalia-Bibliothek" , 1691), |
912 | /// ("Library of Congress" , 1800), |
913 | /// ] { |
914 | /// libraries.insert_unique(hasher(&k), (k, v), |(k, _)| hasher(&k)); |
915 | /// } |
916 | /// |
917 | /// let keys = ["Athenæum" , "Library of Congress" ]; |
918 | /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0); |
919 | /// assert_eq!( |
920 | /// got, |
921 | /// Some([&mut ("Athenæum" , 1807), &mut ("Library of Congress" , 1800),]), |
922 | /// ); |
923 | /// |
924 | /// // Missing keys result in None |
925 | /// let keys = ["Athenæum" , "New York Public Library" ]; |
926 | /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0); |
927 | /// assert_eq!(got, None); |
928 | /// |
929 | /// // Duplicate keys result in None |
930 | /// let keys = ["Athenæum" , "Athenæum" ]; |
931 | /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0); |
932 | /// assert_eq!(got, None); |
933 | /// # } |
934 | /// # fn main() { |
935 | /// # #[cfg (feature = "nightly" )] |
936 | /// # test() |
937 | /// # } |
938 | /// ``` |
939 | pub fn get_many_mut<const N: usize>( |
940 | &mut self, |
941 | hashes: [u64; N], |
942 | eq: impl FnMut(usize, &T) -> bool, |
943 | ) -> Option<[&'_ mut T; N]> { |
944 | self.raw.get_many_mut(hashes, eq) |
945 | } |
946 | |
947 | /// Attempts to get mutable references to `N` values in the map at once, without validating that |
948 | /// the values are unique. |
949 | /// |
950 | /// The `eq` argument should be a closure such that `eq(i, k)` returns true if `k` is equal to |
951 | /// the `i`th key to be looked up. |
952 | /// |
953 | /// Returns an array of length `N` with the results of each query. `None` will be returned if |
954 | /// any of the keys are missing. |
955 | /// |
956 | /// For a safe alternative see [`get_many_mut`](`HashTable::get_many_mut`). |
957 | /// |
958 | /// # Safety |
959 | /// |
960 | /// Calling this method with overlapping keys is *[undefined behavior]* even if the resulting |
961 | /// references are not used. |
962 | /// |
963 | /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html |
964 | /// |
965 | /// # Examples |
966 | /// |
967 | /// ``` |
968 | /// # #[cfg (feature = "nightly" )] |
969 | /// # fn test() { |
970 | /// use ahash::AHasher; |
971 | /// use hashbrown::hash_table::Entry; |
972 | /// use hashbrown::HashTable; |
973 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
974 | /// |
975 | /// let mut libraries: HashTable<(&str, u32)> = HashTable::new(); |
976 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
977 | /// let hasher = |val: &_| hasher.hash_one(val); |
978 | /// for (k, v) in [ |
979 | /// ("Bodleian Library" , 1602), |
980 | /// ("Athenæum" , 1807), |
981 | /// ("Herzogin-Anna-Amalia-Bibliothek" , 1691), |
982 | /// ("Library of Congress" , 1800), |
983 | /// ] { |
984 | /// libraries.insert_unique(hasher(&k), (k, v), |(k, _)| hasher(&k)); |
985 | /// } |
986 | /// |
987 | /// let keys = ["Athenæum" , "Library of Congress" ]; |
988 | /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0); |
989 | /// assert_eq!( |
990 | /// got, |
991 | /// Some([&mut ("Athenæum" , 1807), &mut ("Library of Congress" , 1800),]), |
992 | /// ); |
993 | /// |
994 | /// // Missing keys result in None |
995 | /// let keys = ["Athenæum" , "New York Public Library" ]; |
996 | /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0); |
997 | /// assert_eq!(got, None); |
998 | /// |
999 | /// // Duplicate keys result in None |
1000 | /// let keys = ["Athenæum" , "Athenæum" ]; |
1001 | /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0); |
1002 | /// assert_eq!(got, None); |
1003 | /// # } |
1004 | /// # fn main() { |
1005 | /// # #[cfg (feature = "nightly" )] |
1006 | /// # test() |
1007 | /// # } |
1008 | /// ``` |
1009 | pub unsafe fn get_many_unchecked_mut<const N: usize>( |
1010 | &mut self, |
1011 | hashes: [u64; N], |
1012 | eq: impl FnMut(usize, &T) -> bool, |
1013 | ) -> Option<[&'_ mut T; N]> { |
1014 | self.raw.get_many_unchecked_mut(hashes, eq) |
1015 | } |
1016 | } |
1017 | |
1018 | impl<T, A> IntoIterator for HashTable<T, A> |
1019 | where |
1020 | A: Allocator, |
1021 | { |
1022 | type Item = T; |
1023 | type IntoIter = IntoIter<T, A>; |
1024 | |
1025 | fn into_iter(self) -> IntoIter<T, A> { |
1026 | IntoIter { |
1027 | inner: self.raw.into_iter(), |
1028 | } |
1029 | } |
1030 | } |
1031 | |
1032 | impl<'a, T, A> IntoIterator for &'a HashTable<T, A> |
1033 | where |
1034 | A: Allocator, |
1035 | { |
1036 | type Item = &'a T; |
1037 | type IntoIter = Iter<'a, T>; |
1038 | |
1039 | fn into_iter(self) -> Iter<'a, T> { |
1040 | self.iter() |
1041 | } |
1042 | } |
1043 | |
1044 | impl<'a, T, A> IntoIterator for &'a mut HashTable<T, A> |
1045 | where |
1046 | A: Allocator, |
1047 | { |
1048 | type Item = &'a mut T; |
1049 | type IntoIter = IterMut<'a, T>; |
1050 | |
1051 | fn into_iter(self) -> IterMut<'a, T> { |
1052 | self.iter_mut() |
1053 | } |
1054 | } |
1055 | |
1056 | impl<T, A> Default for HashTable<T, A> |
1057 | where |
1058 | A: Allocator + Default, |
1059 | { |
1060 | fn default() -> Self { |
1061 | Self { |
1062 | raw: Default::default(), |
1063 | } |
1064 | } |
1065 | } |
1066 | |
1067 | impl<T, A> Clone for HashTable<T, A> |
1068 | where |
1069 | T: Clone, |
1070 | A: Allocator + Clone, |
1071 | { |
1072 | fn clone(&self) -> Self { |
1073 | Self { |
1074 | raw: self.raw.clone(), |
1075 | } |
1076 | } |
1077 | } |
1078 | |
1079 | impl<T, A> fmt::Debug for HashTable<T, A> |
1080 | where |
1081 | T: fmt::Debug, |
1082 | A: Allocator, |
1083 | { |
1084 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1085 | f.debug_set().entries(self.iter()).finish() |
1086 | } |
1087 | } |
1088 | |
1089 | /// A view into a single entry in a table, which may either be vacant or occupied. |
1090 | /// |
1091 | /// This `enum` is constructed from the [`entry`] method on [`HashTable`]. |
1092 | /// |
1093 | /// [`HashTable`]: struct.HashTable.html |
1094 | /// [`entry`]: struct.HashTable.html#method.entry |
1095 | /// |
1096 | /// # Examples |
1097 | /// |
1098 | /// ``` |
1099 | /// # #[cfg (feature = "nightly" )] |
1100 | /// # fn test() { |
1101 | /// use ahash::AHasher; |
1102 | /// use hashbrown::hash_table::{Entry, HashTable, OccupiedEntry}; |
1103 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1104 | /// |
1105 | /// let mut table = HashTable::new(); |
1106 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1107 | /// let hasher = |val: &_| hasher.hash_one(val); |
1108 | /// for x in ["a" , "b" , "c" ] { |
1109 | /// table.insert_unique(hasher(&x), x, hasher); |
1110 | /// } |
1111 | /// assert_eq!(table.len(), 3); |
1112 | /// |
1113 | /// // Existing value (insert) |
1114 | /// let entry: Entry<_> = table.entry(hasher(&"a" ), |&x| x == "a" , hasher); |
1115 | /// let _raw_o: OccupiedEntry<_, _> = entry.insert("a" ); |
1116 | /// assert_eq!(table.len(), 3); |
1117 | /// // Nonexistent value (insert) |
1118 | /// table.entry(hasher(&"d" ), |&x| x == "d" , hasher).insert("d" ); |
1119 | /// |
1120 | /// // Existing value (or_insert) |
1121 | /// table |
1122 | /// .entry(hasher(&"b" ), |&x| x == "b" , hasher) |
1123 | /// .or_insert("b" ); |
1124 | /// // Nonexistent value (or_insert) |
1125 | /// table |
1126 | /// .entry(hasher(&"e" ), |&x| x == "e" , hasher) |
1127 | /// .or_insert("e" ); |
1128 | /// |
1129 | /// println!("Our HashTable: {:?}" , table); |
1130 | /// |
1131 | /// let mut vec: Vec<_> = table.iter().copied().collect(); |
1132 | /// // The `Iter` iterator produces items in arbitrary order, so the |
1133 | /// // items must be sorted to test them against a sorted array. |
1134 | /// vec.sort_unstable(); |
1135 | /// assert_eq!(vec, ["a" , "b" , "c" , "d" , "e" ]); |
1136 | /// # } |
1137 | /// # fn main() { |
1138 | /// # #[cfg (feature = "nightly" )] |
1139 | /// # test() |
1140 | /// # } |
1141 | /// ``` |
1142 | pub enum Entry<'a, T, A = Global> |
1143 | where |
1144 | A: Allocator, |
1145 | { |
1146 | /// An occupied entry. |
1147 | /// |
1148 | /// # Examples |
1149 | /// |
1150 | /// ``` |
1151 | /// # #[cfg (feature = "nightly" )] |
1152 | /// # fn test() { |
1153 | /// use ahash::AHasher; |
1154 | /// use hashbrown::hash_table::{Entry, HashTable, OccupiedEntry}; |
1155 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1156 | /// |
1157 | /// let mut table = HashTable::new(); |
1158 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1159 | /// let hasher = |val: &_| hasher.hash_one(val); |
1160 | /// for x in ["a" , "b" ] { |
1161 | /// table.insert_unique(hasher(&x), x, hasher); |
1162 | /// } |
1163 | /// |
1164 | /// match table.entry(hasher(&"a" ), |&x| x == "a" , hasher) { |
1165 | /// Entry::Vacant(_) => unreachable!(), |
1166 | /// Entry::Occupied(_) => {} |
1167 | /// } |
1168 | /// # } |
1169 | /// # fn main() { |
1170 | /// # #[cfg (feature = "nightly" )] |
1171 | /// # test() |
1172 | /// # } |
1173 | /// ``` |
1174 | Occupied(OccupiedEntry<'a, T, A>), |
1175 | |
1176 | /// A vacant entry. |
1177 | /// |
1178 | /// # Examples |
1179 | /// |
1180 | /// ``` |
1181 | /// # #[cfg (feature = "nightly" )] |
1182 | /// # fn test() { |
1183 | /// use ahash::AHasher; |
1184 | /// use hashbrown::hash_table::{Entry, HashTable, OccupiedEntry}; |
1185 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1186 | /// |
1187 | /// let mut table = HashTable::<&str>::new(); |
1188 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1189 | /// let hasher = |val: &_| hasher.hash_one(val); |
1190 | /// |
1191 | /// match table.entry(hasher(&"a" ), |&x| x == "a" , hasher) { |
1192 | /// Entry::Vacant(_) => {} |
1193 | /// Entry::Occupied(_) => unreachable!(), |
1194 | /// } |
1195 | /// # } |
1196 | /// # fn main() { |
1197 | /// # #[cfg (feature = "nightly" )] |
1198 | /// # test() |
1199 | /// # } |
1200 | /// ``` |
1201 | Vacant(VacantEntry<'a, T, A>), |
1202 | } |
1203 | |
1204 | impl<T: fmt::Debug, A: Allocator> fmt::Debug for Entry<'_, T, A> { |
1205 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1206 | match *self { |
1207 | Entry::Vacant(ref v: &VacantEntry<'_, T, A>) => f.debug_tuple("Entry" ).field(v).finish(), |
1208 | Entry::Occupied(ref o: &OccupiedEntry<'_, T, A>) => f.debug_tuple("Entry" ).field(o).finish(), |
1209 | } |
1210 | } |
1211 | } |
1212 | |
1213 | impl<'a, T, A> Entry<'a, T, A> |
1214 | where |
1215 | A: Allocator, |
1216 | { |
1217 | /// Sets the value of the entry, replacing any existing value if there is |
1218 | /// one, and returns an [`OccupiedEntry`]. |
1219 | /// |
1220 | /// # Examples |
1221 | /// |
1222 | /// ``` |
1223 | /// # #[cfg (feature = "nightly" )] |
1224 | /// # fn test() { |
1225 | /// use ahash::AHasher; |
1226 | /// use hashbrown::HashTable; |
1227 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1228 | /// |
1229 | /// let mut table: HashTable<&str> = HashTable::new(); |
1230 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1231 | /// let hasher = |val: &_| hasher.hash_one(val); |
1232 | /// |
1233 | /// let entry = table |
1234 | /// .entry(hasher(&"horseyland" ), |&x| x == "horseyland" , hasher) |
1235 | /// .insert("horseyland" ); |
1236 | /// |
1237 | /// assert_eq!(entry.get(), &"horseyland" ); |
1238 | /// # } |
1239 | /// # fn main() { |
1240 | /// # #[cfg (feature = "nightly" )] |
1241 | /// # test() |
1242 | /// # } |
1243 | /// ``` |
1244 | pub fn insert(self, value: T) -> OccupiedEntry<'a, T, A> { |
1245 | match self { |
1246 | Entry::Occupied(mut entry) => { |
1247 | *entry.get_mut() = value; |
1248 | entry |
1249 | } |
1250 | Entry::Vacant(entry) => entry.insert(value), |
1251 | } |
1252 | } |
1253 | |
1254 | /// Ensures a value is in the entry by inserting if it was vacant. |
1255 | /// |
1256 | /// Returns an [`OccupiedEntry`] pointing to the now-occupied entry. |
1257 | /// |
1258 | /// # Examples |
1259 | /// |
1260 | /// ``` |
1261 | /// # #[cfg (feature = "nightly" )] |
1262 | /// # fn test() { |
1263 | /// use ahash::AHasher; |
1264 | /// use hashbrown::HashTable; |
1265 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1266 | /// |
1267 | /// let mut table: HashTable<&str> = HashTable::new(); |
1268 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1269 | /// let hasher = |val: &_| hasher.hash_one(val); |
1270 | /// |
1271 | /// // nonexistent key |
1272 | /// table |
1273 | /// .entry(hasher(&"poneyland" ), |&x| x == "poneyland" , hasher) |
1274 | /// .or_insert("poneyland" ); |
1275 | /// assert!(table |
1276 | /// .find(hasher(&"poneyland" ), |&x| x == "poneyland" ) |
1277 | /// .is_some()); |
1278 | /// |
1279 | /// // existing key |
1280 | /// table |
1281 | /// .entry(hasher(&"poneyland" ), |&x| x == "poneyland" , hasher) |
1282 | /// .or_insert("poneyland" ); |
1283 | /// assert!(table |
1284 | /// .find(hasher(&"poneyland" ), |&x| x == "poneyland" ) |
1285 | /// .is_some()); |
1286 | /// assert_eq!(table.len(), 1); |
1287 | /// # } |
1288 | /// # fn main() { |
1289 | /// # #[cfg (feature = "nightly" )] |
1290 | /// # test() |
1291 | /// # } |
1292 | /// ``` |
1293 | pub fn or_insert(self, default: T) -> OccupiedEntry<'a, T, A> { |
1294 | match self { |
1295 | Entry::Occupied(entry) => entry, |
1296 | Entry::Vacant(entry) => entry.insert(default), |
1297 | } |
1298 | } |
1299 | |
1300 | /// Ensures a value is in the entry by inserting the result of the default function if empty.. |
1301 | /// |
1302 | /// Returns an [`OccupiedEntry`] pointing to the now-occupied entry. |
1303 | /// |
1304 | /// # Examples |
1305 | /// |
1306 | /// ``` |
1307 | /// # #[cfg (feature = "nightly" )] |
1308 | /// # fn test() { |
1309 | /// use ahash::AHasher; |
1310 | /// use hashbrown::HashTable; |
1311 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1312 | /// |
1313 | /// let mut table: HashTable<String> = HashTable::new(); |
1314 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1315 | /// let hasher = |val: &_| hasher.hash_one(val); |
1316 | /// |
1317 | /// table |
1318 | /// .entry(hasher("poneyland" ), |x| x == "poneyland" , |val| hasher(val)) |
1319 | /// .or_insert_with(|| "poneyland" .to_string()); |
1320 | /// |
1321 | /// assert!(table |
1322 | /// .find(hasher(&"poneyland" ), |x| x == "poneyland" ) |
1323 | /// .is_some()); |
1324 | /// # } |
1325 | /// # fn main() { |
1326 | /// # #[cfg (feature = "nightly" )] |
1327 | /// # test() |
1328 | /// # } |
1329 | /// ``` |
1330 | pub fn or_insert_with(self, default: impl FnOnce() -> T) -> OccupiedEntry<'a, T, A> { |
1331 | match self { |
1332 | Entry::Occupied(entry) => entry, |
1333 | Entry::Vacant(entry) => entry.insert(default()), |
1334 | } |
1335 | } |
1336 | |
1337 | /// Provides in-place mutable access to an occupied entry before any |
1338 | /// potential inserts into the table. |
1339 | /// |
1340 | /// # Examples |
1341 | /// |
1342 | /// ``` |
1343 | /// # #[cfg (feature = "nightly" )] |
1344 | /// # fn test() { |
1345 | /// use ahash::AHasher; |
1346 | /// use hashbrown::HashTable; |
1347 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1348 | /// |
1349 | /// let mut table: HashTable<(&str, u32)> = HashTable::new(); |
1350 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1351 | /// let hasher = |val: &_| hasher.hash_one(val); |
1352 | /// |
1353 | /// table |
1354 | /// .entry( |
1355 | /// hasher(&"poneyland" ), |
1356 | /// |&(x, _)| x == "poneyland" , |
1357 | /// |(k, _)| hasher(&k), |
1358 | /// ) |
1359 | /// .and_modify(|(_, v)| *v += 1) |
1360 | /// .or_insert(("poneyland" , 42)); |
1361 | /// assert_eq!( |
1362 | /// table.find(hasher(&"poneyland" ), |&(k, _)| k == "poneyland" ), |
1363 | /// Some(&("poneyland" , 42)) |
1364 | /// ); |
1365 | /// |
1366 | /// table |
1367 | /// .entry( |
1368 | /// hasher(&"poneyland" ), |
1369 | /// |&(x, _)| x == "poneyland" , |
1370 | /// |(k, _)| hasher(&k), |
1371 | /// ) |
1372 | /// .and_modify(|(_, v)| *v += 1) |
1373 | /// .or_insert(("poneyland" , 42)); |
1374 | /// assert_eq!( |
1375 | /// table.find(hasher(&"poneyland" ), |&(k, _)| k == "poneyland" ), |
1376 | /// Some(&("poneyland" , 43)) |
1377 | /// ); |
1378 | /// # } |
1379 | /// # fn main() { |
1380 | /// # #[cfg (feature = "nightly" )] |
1381 | /// # test() |
1382 | /// # } |
1383 | /// ``` |
1384 | pub fn and_modify(self, f: impl FnOnce(&mut T)) -> Self { |
1385 | match self { |
1386 | Entry::Occupied(mut entry) => { |
1387 | f(entry.get_mut()); |
1388 | Entry::Occupied(entry) |
1389 | } |
1390 | Entry::Vacant(entry) => Entry::Vacant(entry), |
1391 | } |
1392 | } |
1393 | } |
1394 | |
1395 | /// A view into an occupied entry in a `HashTable`. |
1396 | /// It is part of the [`Entry`] enum. |
1397 | /// |
1398 | /// [`Entry`]: enum.Entry.html |
1399 | /// |
1400 | /// # Examples |
1401 | /// |
1402 | /// ``` |
1403 | /// # #[cfg (feature = "nightly" )] |
1404 | /// # fn test() { |
1405 | /// use ahash::AHasher; |
1406 | /// use hashbrown::hash_table::{Entry, HashTable, OccupiedEntry}; |
1407 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1408 | /// |
1409 | /// let mut table = HashTable::new(); |
1410 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1411 | /// let hasher = |val: &_| hasher.hash_one(val); |
1412 | /// for x in ["a" , "b" , "c" ] { |
1413 | /// table.insert_unique(hasher(&x), x, hasher); |
1414 | /// } |
1415 | /// assert_eq!(table.len(), 3); |
1416 | /// |
1417 | /// let _entry_o: OccupiedEntry<_, _> = table.find_entry(hasher(&"a" ), |&x| x == "a" ).unwrap(); |
1418 | /// assert_eq!(table.len(), 3); |
1419 | /// |
1420 | /// // Existing key |
1421 | /// match table.entry(hasher(&"a" ), |&x| x == "a" , hasher) { |
1422 | /// Entry::Vacant(_) => unreachable!(), |
1423 | /// Entry::Occupied(view) => { |
1424 | /// assert_eq!(view.get(), &"a" ); |
1425 | /// } |
1426 | /// } |
1427 | /// |
1428 | /// assert_eq!(table.len(), 3); |
1429 | /// |
1430 | /// // Existing key (take) |
1431 | /// match table.entry(hasher(&"c" ), |&x| x == "c" , hasher) { |
1432 | /// Entry::Vacant(_) => unreachable!(), |
1433 | /// Entry::Occupied(view) => { |
1434 | /// assert_eq!(view.remove().0, "c" ); |
1435 | /// } |
1436 | /// } |
1437 | /// assert_eq!(table.find(hasher(&"c" ), |&x| x == "c" ), None); |
1438 | /// assert_eq!(table.len(), 2); |
1439 | /// # } |
1440 | /// # fn main() { |
1441 | /// # #[cfg (feature = "nightly" )] |
1442 | /// # test() |
1443 | /// # } |
1444 | /// ``` |
1445 | pub struct OccupiedEntry<'a, T, A = Global> |
1446 | where |
1447 | A: Allocator, |
1448 | { |
1449 | hash: u64, |
1450 | bucket: Bucket<T>, |
1451 | table: &'a mut HashTable<T, A>, |
1452 | } |
1453 | |
1454 | unsafe impl<T, A> Send for OccupiedEntry<'_, T, A> |
1455 | where |
1456 | T: Send, |
1457 | A: Send + Allocator, |
1458 | { |
1459 | } |
1460 | unsafe impl<T, A> Sync for OccupiedEntry<'_, T, A> |
1461 | where |
1462 | T: Sync, |
1463 | A: Sync + Allocator, |
1464 | { |
1465 | } |
1466 | |
1467 | impl<T: fmt::Debug, A: Allocator> fmt::Debug for OccupiedEntry<'_, T, A> { |
1468 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1469 | f.debug_struct("OccupiedEntry" ) |
1470 | .field("value" , self.get()) |
1471 | .finish() |
1472 | } |
1473 | } |
1474 | |
1475 | impl<'a, T, A> OccupiedEntry<'a, T, A> |
1476 | where |
1477 | A: Allocator, |
1478 | { |
1479 | /// Takes the value out of the entry, and returns it along with a |
1480 | /// `VacantEntry` that can be used to insert another value with the same |
1481 | /// hash as the one that was just removed. |
1482 | /// |
1483 | /// # Examples |
1484 | /// |
1485 | /// ``` |
1486 | /// # #[cfg (feature = "nightly" )] |
1487 | /// # fn test() { |
1488 | /// use ahash::AHasher; |
1489 | /// use hashbrown::hash_table::Entry; |
1490 | /// use hashbrown::HashTable; |
1491 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1492 | /// |
1493 | /// let mut table: HashTable<&str> = HashTable::new(); |
1494 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1495 | /// let hasher = |val: &_| hasher.hash_one(val); |
1496 | /// // The table is empty |
1497 | /// assert!(table.is_empty() && table.capacity() == 0); |
1498 | /// |
1499 | /// table.insert_unique(hasher(&"poneyland" ), "poneyland" , hasher); |
1500 | /// let capacity_before_remove = table.capacity(); |
1501 | /// |
1502 | /// if let Entry::Occupied(o) = table.entry(hasher(&"poneyland" ), |&x| x == "poneyland" , hasher) { |
1503 | /// assert_eq!(o.remove().0, "poneyland" ); |
1504 | /// } |
1505 | /// |
1506 | /// assert!(table |
1507 | /// .find(hasher(&"poneyland" ), |&x| x == "poneyland" ) |
1508 | /// .is_none()); |
1509 | /// // Now table hold none elements but capacity is equal to the old one |
1510 | /// assert!(table.len() == 0 && table.capacity() == capacity_before_remove); |
1511 | /// # } |
1512 | /// # fn main() { |
1513 | /// # #[cfg (feature = "nightly" )] |
1514 | /// # test() |
1515 | /// # } |
1516 | /// ``` |
1517 | pub fn remove(self) -> (T, VacantEntry<'a, T, A>) { |
1518 | let (val, slot) = unsafe { self.table.raw.remove(self.bucket) }; |
1519 | ( |
1520 | val, |
1521 | VacantEntry { |
1522 | hash: self.hash, |
1523 | insert_slot: slot, |
1524 | table: self.table, |
1525 | }, |
1526 | ) |
1527 | } |
1528 | |
1529 | /// Gets a reference to the value in the entry. |
1530 | /// |
1531 | /// # Examples |
1532 | /// |
1533 | /// ``` |
1534 | /// # #[cfg (feature = "nightly" )] |
1535 | /// # fn test() { |
1536 | /// use ahash::AHasher; |
1537 | /// use hashbrown::hash_table::Entry; |
1538 | /// use hashbrown::HashTable; |
1539 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1540 | /// |
1541 | /// let mut table: HashTable<&str> = HashTable::new(); |
1542 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1543 | /// let hasher = |val: &_| hasher.hash_one(val); |
1544 | /// table.insert_unique(hasher(&"poneyland" ), "poneyland" , hasher); |
1545 | /// |
1546 | /// match table.entry(hasher(&"poneyland" ), |&x| x == "poneyland" , hasher) { |
1547 | /// Entry::Vacant(_) => panic!(), |
1548 | /// Entry::Occupied(entry) => assert_eq!(entry.get(), &"poneyland" ), |
1549 | /// } |
1550 | /// # } |
1551 | /// # fn main() { |
1552 | /// # #[cfg (feature = "nightly" )] |
1553 | /// # test() |
1554 | /// # } |
1555 | /// ``` |
1556 | pub fn get(&self) -> &T { |
1557 | unsafe { self.bucket.as_ref() } |
1558 | } |
1559 | |
1560 | /// Gets a mutable reference to the value in the entry. |
1561 | /// |
1562 | /// If you need a reference to the `OccupiedEntry` which may outlive the |
1563 | /// destruction of the `Entry` value, see [`into_mut`]. |
1564 | /// |
1565 | /// [`into_mut`]: #method.into_mut |
1566 | /// |
1567 | /// # Examples |
1568 | /// |
1569 | /// ``` |
1570 | /// # #[cfg (feature = "nightly" )] |
1571 | /// # fn test() { |
1572 | /// use ahash::AHasher; |
1573 | /// use hashbrown::hash_table::Entry; |
1574 | /// use hashbrown::HashTable; |
1575 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1576 | /// |
1577 | /// let mut table: HashTable<(&str, u32)> = HashTable::new(); |
1578 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1579 | /// let hasher = |val: &_| hasher.hash_one(val); |
1580 | /// table.insert_unique(hasher(&"poneyland" ), ("poneyland" , 12), |(k, _)| hasher(&k)); |
1581 | /// |
1582 | /// assert_eq!( |
1583 | /// table.find(hasher(&"poneyland" ), |&(x, _)| x == "poneyland" ,), |
1584 | /// Some(&("poneyland" , 12)) |
1585 | /// ); |
1586 | /// |
1587 | /// if let Entry::Occupied(mut o) = table.entry( |
1588 | /// hasher(&"poneyland" ), |
1589 | /// |&(x, _)| x == "poneyland" , |
1590 | /// |(k, _)| hasher(&k), |
1591 | /// ) { |
1592 | /// o.get_mut().1 += 10; |
1593 | /// assert_eq!(o.get().1, 22); |
1594 | /// |
1595 | /// // We can use the same Entry multiple times. |
1596 | /// o.get_mut().1 += 2; |
1597 | /// } |
1598 | /// |
1599 | /// assert_eq!( |
1600 | /// table.find(hasher(&"poneyland" ), |&(x, _)| x == "poneyland" ,), |
1601 | /// Some(&("poneyland" , 24)) |
1602 | /// ); |
1603 | /// # } |
1604 | /// # fn main() { |
1605 | /// # #[cfg (feature = "nightly" )] |
1606 | /// # test() |
1607 | /// # } |
1608 | /// ``` |
1609 | pub fn get_mut(&mut self) -> &mut T { |
1610 | unsafe { self.bucket.as_mut() } |
1611 | } |
1612 | |
1613 | /// Converts the OccupiedEntry into a mutable reference to the value in the entry |
1614 | /// with a lifetime bound to the table itself. |
1615 | /// |
1616 | /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`]. |
1617 | /// |
1618 | /// [`get_mut`]: #method.get_mut |
1619 | /// |
1620 | /// # Examples |
1621 | /// |
1622 | /// ``` |
1623 | /// # #[cfg (feature = "nightly" )] |
1624 | /// # fn test() { |
1625 | /// use ahash::AHasher; |
1626 | /// use hashbrown::hash_table::Entry; |
1627 | /// use hashbrown::HashTable; |
1628 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1629 | /// |
1630 | /// let mut table: HashTable<(&str, u32)> = HashTable::new(); |
1631 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1632 | /// let hasher = |val: &_| hasher.hash_one(val); |
1633 | /// table.insert_unique(hasher(&"poneyland" ), ("poneyland" , 12), |(k, _)| hasher(&k)); |
1634 | /// |
1635 | /// assert_eq!( |
1636 | /// table.find(hasher(&"poneyland" ), |&(x, _)| x == "poneyland" ,), |
1637 | /// Some(&("poneyland" , 12)) |
1638 | /// ); |
1639 | /// |
1640 | /// let value: &mut (&str, u32); |
1641 | /// match table.entry( |
1642 | /// hasher(&"poneyland" ), |
1643 | /// |&(x, _)| x == "poneyland" , |
1644 | /// |(k, _)| hasher(&k), |
1645 | /// ) { |
1646 | /// Entry::Occupied(entry) => value = entry.into_mut(), |
1647 | /// Entry::Vacant(_) => panic!(), |
1648 | /// } |
1649 | /// value.1 += 10; |
1650 | /// |
1651 | /// assert_eq!( |
1652 | /// table.find(hasher(&"poneyland" ), |&(x, _)| x == "poneyland" ,), |
1653 | /// Some(&("poneyland" , 22)) |
1654 | /// ); |
1655 | /// # } |
1656 | /// # fn main() { |
1657 | /// # #[cfg (feature = "nightly" )] |
1658 | /// # test() |
1659 | /// # } |
1660 | /// ``` |
1661 | pub fn into_mut(self) -> &'a mut T { |
1662 | unsafe { self.bucket.as_mut() } |
1663 | } |
1664 | |
1665 | /// Converts the OccupiedEntry into a mutable reference to the underlying |
1666 | /// table. |
1667 | pub fn into_table(self) -> &'a mut HashTable<T, A> { |
1668 | self.table |
1669 | } |
1670 | } |
1671 | |
1672 | /// A view into a vacant entry in a `HashTable`. |
1673 | /// It is part of the [`Entry`] enum. |
1674 | /// |
1675 | /// [`Entry`]: enum.Entry.html |
1676 | /// |
1677 | /// # Examples |
1678 | /// |
1679 | /// ``` |
1680 | /// # #[cfg (feature = "nightly" )] |
1681 | /// # fn test() { |
1682 | /// use ahash::AHasher; |
1683 | /// use hashbrown::hash_table::{Entry, HashTable, VacantEntry}; |
1684 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1685 | /// |
1686 | /// let mut table: HashTable<&str> = HashTable::new(); |
1687 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1688 | /// let hasher = |val: &_| hasher.hash_one(val); |
1689 | /// |
1690 | /// let entry_v: VacantEntry<_, _> = match table.entry(hasher(&"a" ), |&x| x == "a" , hasher) { |
1691 | /// Entry::Vacant(view) => view, |
1692 | /// Entry::Occupied(_) => unreachable!(), |
1693 | /// }; |
1694 | /// entry_v.insert("a" ); |
1695 | /// assert!(table.find(hasher(&"a" ), |&x| x == "a" ).is_some() && table.len() == 1); |
1696 | /// |
1697 | /// // Nonexistent key (insert) |
1698 | /// match table.entry(hasher(&"b" ), |&x| x == "b" , hasher) { |
1699 | /// Entry::Vacant(view) => { |
1700 | /// view.insert("b" ); |
1701 | /// } |
1702 | /// Entry::Occupied(_) => unreachable!(), |
1703 | /// } |
1704 | /// assert!(table.find(hasher(&"b" ), |&x| x == "b" ).is_some() && table.len() == 2); |
1705 | /// # } |
1706 | /// # fn main() { |
1707 | /// # #[cfg (feature = "nightly" )] |
1708 | /// # test() |
1709 | /// # } |
1710 | /// ``` |
1711 | pub struct VacantEntry<'a, T, A = Global> |
1712 | where |
1713 | A: Allocator, |
1714 | { |
1715 | hash: u64, |
1716 | insert_slot: InsertSlot, |
1717 | table: &'a mut HashTable<T, A>, |
1718 | } |
1719 | |
1720 | impl<T: fmt::Debug, A: Allocator> fmt::Debug for VacantEntry<'_, T, A> { |
1721 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1722 | f.write_str("VacantEntry" ) |
1723 | } |
1724 | } |
1725 | |
1726 | impl<'a, T, A> VacantEntry<'a, T, A> |
1727 | where |
1728 | A: Allocator, |
1729 | { |
1730 | /// Inserts a new element into the table with the hash that was used to |
1731 | /// obtain the `VacantEntry`. |
1732 | /// |
1733 | /// An `OccupiedEntry` is returned for the newly inserted element. |
1734 | /// |
1735 | /// # Examples |
1736 | /// |
1737 | /// ``` |
1738 | /// # #[cfg (feature = "nightly" )] |
1739 | /// # fn test() { |
1740 | /// use ahash::AHasher; |
1741 | /// use hashbrown::hash_table::Entry; |
1742 | /// use hashbrown::HashTable; |
1743 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1744 | /// |
1745 | /// let mut table: HashTable<&str> = HashTable::new(); |
1746 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1747 | /// let hasher = |val: &_| hasher.hash_one(val); |
1748 | /// |
1749 | /// if let Entry::Vacant(o) = table.entry(hasher(&"poneyland" ), |&x| x == "poneyland" , hasher) { |
1750 | /// o.insert("poneyland" ); |
1751 | /// } |
1752 | /// assert_eq!( |
1753 | /// table.find(hasher(&"poneyland" ), |&x| x == "poneyland" ), |
1754 | /// Some(&"poneyland" ) |
1755 | /// ); |
1756 | /// # } |
1757 | /// # fn main() { |
1758 | /// # #[cfg (feature = "nightly" )] |
1759 | /// # test() |
1760 | /// # } |
1761 | /// ``` |
1762 | pub fn insert(self, value: T) -> OccupiedEntry<'a, T, A> { |
1763 | let bucket = unsafe { |
1764 | self.table |
1765 | .raw |
1766 | .insert_in_slot(self.hash, self.insert_slot, value) |
1767 | }; |
1768 | OccupiedEntry { |
1769 | hash: self.hash, |
1770 | bucket, |
1771 | table: self.table, |
1772 | } |
1773 | } |
1774 | |
1775 | /// Converts the VacantEntry into a mutable reference to the underlying |
1776 | /// table. |
1777 | pub fn into_table(self) -> &'a mut HashTable<T, A> { |
1778 | self.table |
1779 | } |
1780 | } |
1781 | |
1782 | /// Type representing the absence of an entry, as returned by [`HashTable::find_entry`]. |
1783 | /// |
1784 | /// This type only exists due to [limitations] in Rust's NLL borrow checker. In |
1785 | /// the future, `find_entry` will return an `Option<OccupiedEntry>` and this |
1786 | /// type will be removed. |
1787 | /// |
1788 | /// [limitations]: https://smallcultfollowing.com/babysteps/blog/2018/06/15/mir-based-borrow-check-nll-status-update/#polonius |
1789 | /// |
1790 | /// # Examples |
1791 | /// |
1792 | /// ``` |
1793 | /// # #[cfg (feature = "nightly" )] |
1794 | /// # fn test() { |
1795 | /// use ahash::AHasher; |
1796 | /// use hashbrown::hash_table::{AbsentEntry, Entry, HashTable}; |
1797 | /// use std::hash::{BuildHasher, BuildHasherDefault}; |
1798 | /// |
1799 | /// let mut table: HashTable<&str> = HashTable::new(); |
1800 | /// let hasher = BuildHasherDefault::<AHasher>::default(); |
1801 | /// let hasher = |val: &_| hasher.hash_one(val); |
1802 | /// |
1803 | /// let entry_v: AbsentEntry<_, _> = table.find_entry(hasher(&"a" ), |&x| x == "a" ).unwrap_err(); |
1804 | /// entry_v |
1805 | /// .into_table() |
1806 | /// .insert_unique(hasher(&"a" ), "a" , hasher); |
1807 | /// assert!(table.find(hasher(&"a" ), |&x| x == "a" ).is_some() && table.len() == 1); |
1808 | /// |
1809 | /// // Nonexistent key (insert) |
1810 | /// match table.entry(hasher(&"b" ), |&x| x == "b" , hasher) { |
1811 | /// Entry::Vacant(view) => { |
1812 | /// view.insert("b" ); |
1813 | /// } |
1814 | /// Entry::Occupied(_) => unreachable!(), |
1815 | /// } |
1816 | /// assert!(table.find(hasher(&"b" ), |&x| x == "b" ).is_some() && table.len() == 2); |
1817 | /// # } |
1818 | /// # fn main() { |
1819 | /// # #[cfg (feature = "nightly" )] |
1820 | /// # test() |
1821 | /// # } |
1822 | /// ``` |
1823 | pub struct AbsentEntry<'a, T, A = Global> |
1824 | where |
1825 | A: Allocator, |
1826 | { |
1827 | table: &'a mut HashTable<T, A>, |
1828 | } |
1829 | |
1830 | impl<T: fmt::Debug, A: Allocator> fmt::Debug for AbsentEntry<'_, T, A> { |
1831 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1832 | f.write_str("AbsentEntry" ) |
1833 | } |
1834 | } |
1835 | |
1836 | impl<'a, T, A> AbsentEntry<'a, T, A> |
1837 | where |
1838 | A: Allocator, |
1839 | { |
1840 | /// Converts the AbsentEntry into a mutable reference to the underlying |
1841 | /// table. |
1842 | pub fn into_table(self) -> &'a mut HashTable<T, A> { |
1843 | self.table |
1844 | } |
1845 | } |
1846 | |
1847 | /// An iterator over the entries of a `HashTable` in arbitrary order. |
1848 | /// The iterator element type is `&'a T`. |
1849 | /// |
1850 | /// This `struct` is created by the [`iter`] method on [`HashTable`]. See its |
1851 | /// documentation for more. |
1852 | /// |
1853 | /// [`iter`]: struct.HashTable.html#method.iter |
1854 | /// [`HashTable`]: struct.HashTable.html |
1855 | pub struct Iter<'a, T> { |
1856 | inner: RawIter<T>, |
1857 | marker: PhantomData<&'a T>, |
1858 | } |
1859 | |
1860 | impl<'a, T> Iterator for Iter<'a, T> { |
1861 | type Item = &'a T; |
1862 | |
1863 | fn next(&mut self) -> Option<Self::Item> { |
1864 | // Avoid `Option::map` because it bloats LLVM IR. |
1865 | match self.inner.next() { |
1866 | Some(bucket) => Some(unsafe { bucket.as_ref() }), |
1867 | None => None, |
1868 | } |
1869 | } |
1870 | |
1871 | fn size_hint(&self) -> (usize, Option<usize>) { |
1872 | self.inner.size_hint() |
1873 | } |
1874 | |
1875 | fn fold<B, F>(self, init: B, mut f: F) -> B |
1876 | where |
1877 | Self: Sized, |
1878 | F: FnMut(B, Self::Item) -> B, |
1879 | { |
1880 | self.inner |
1881 | .fold(init, |acc, bucket| unsafe { f(acc, bucket.as_ref()) }) |
1882 | } |
1883 | } |
1884 | |
1885 | impl<T> ExactSizeIterator for Iter<'_, T> { |
1886 | fn len(&self) -> usize { |
1887 | self.inner.len() |
1888 | } |
1889 | } |
1890 | |
1891 | impl<T> FusedIterator for Iter<'_, T> {} |
1892 | |
1893 | /// A mutable iterator over the entries of a `HashTable` in arbitrary order. |
1894 | /// The iterator element type is `&'a mut T`. |
1895 | /// |
1896 | /// This `struct` is created by the [`iter_mut`] method on [`HashTable`]. See its |
1897 | /// documentation for more. |
1898 | /// |
1899 | /// [`iter_mut`]: struct.HashTable.html#method.iter_mut |
1900 | /// [`HashTable`]: struct.HashTable.html |
1901 | pub struct IterMut<'a, T> { |
1902 | inner: RawIter<T>, |
1903 | marker: PhantomData<&'a mut T>, |
1904 | } |
1905 | |
1906 | impl<'a, T> Iterator for IterMut<'a, T> { |
1907 | type Item = &'a mut T; |
1908 | |
1909 | fn next(&mut self) -> Option<Self::Item> { |
1910 | // Avoid `Option::map` because it bloats LLVM IR. |
1911 | match self.inner.next() { |
1912 | Some(bucket) => Some(unsafe { bucket.as_mut() }), |
1913 | None => None, |
1914 | } |
1915 | } |
1916 | |
1917 | fn size_hint(&self) -> (usize, Option<usize>) { |
1918 | self.inner.size_hint() |
1919 | } |
1920 | |
1921 | fn fold<B, F>(self, init: B, mut f: F) -> B |
1922 | where |
1923 | Self: Sized, |
1924 | F: FnMut(B, Self::Item) -> B, |
1925 | { |
1926 | self.inner |
1927 | .fold(init, |acc, bucket| unsafe { f(acc, bucket.as_mut()) }) |
1928 | } |
1929 | } |
1930 | |
1931 | impl<T> ExactSizeIterator for IterMut<'_, T> { |
1932 | fn len(&self) -> usize { |
1933 | self.inner.len() |
1934 | } |
1935 | } |
1936 | |
1937 | impl<T> FusedIterator for IterMut<'_, T> {} |
1938 | |
1939 | /// An owning iterator over the entries of a `HashTable` in arbitrary order. |
1940 | /// The iterator element type is `T`. |
1941 | /// |
1942 | /// This `struct` is created by the [`into_iter`] method on [`HashTable`] |
1943 | /// (provided by the [`IntoIterator`] trait). See its documentation for more. |
1944 | /// The table cannot be used after calling that method. |
1945 | /// |
1946 | /// [`into_iter`]: struct.HashTable.html#method.into_iter |
1947 | /// [`HashTable`]: struct.HashTable.html |
1948 | /// [`IntoIterator`]: https://doc.rust-lang.org/core/iter/trait.IntoIterator.html |
1949 | pub struct IntoIter<T, A = Global> |
1950 | where |
1951 | A: Allocator, |
1952 | { |
1953 | inner: RawIntoIter<T, A>, |
1954 | } |
1955 | |
1956 | impl<T, A> Iterator for IntoIter<T, A> |
1957 | where |
1958 | A: Allocator, |
1959 | { |
1960 | type Item = T; |
1961 | |
1962 | fn next(&mut self) -> Option<Self::Item> { |
1963 | self.inner.next() |
1964 | } |
1965 | |
1966 | fn size_hint(&self) -> (usize, Option<usize>) { |
1967 | self.inner.size_hint() |
1968 | } |
1969 | |
1970 | fn fold<B, F>(self, init: B, f: F) -> B |
1971 | where |
1972 | Self: Sized, |
1973 | F: FnMut(B, Self::Item) -> B, |
1974 | { |
1975 | self.inner.fold(init, f) |
1976 | } |
1977 | } |
1978 | |
1979 | impl<T, A> ExactSizeIterator for IntoIter<T, A> |
1980 | where |
1981 | A: Allocator, |
1982 | { |
1983 | fn len(&self) -> usize { |
1984 | self.inner.len() |
1985 | } |
1986 | } |
1987 | |
1988 | impl<T, A> FusedIterator for IntoIter<T, A> where A: Allocator {} |
1989 | |
1990 | /// A draining iterator over the items of a `HashTable`. |
1991 | /// |
1992 | /// This `struct` is created by the [`drain`] method on [`HashTable`]. |
1993 | /// See its documentation for more. |
1994 | /// |
1995 | /// [`HashTable`]: struct.HashTable.html |
1996 | /// [`drain`]: struct.HashTable.html#method.drain |
1997 | pub struct Drain<'a, T, A: Allocator = Global> { |
1998 | inner: RawDrain<'a, T, A>, |
1999 | } |
2000 | |
2001 | impl<T, A: Allocator> Drain<'_, T, A> { |
2002 | /// Returns a iterator of references over the remaining items. |
2003 | fn iter(&self) -> Iter<'_, T> { |
2004 | Iter { |
2005 | inner: self.inner.iter(), |
2006 | marker: PhantomData, |
2007 | } |
2008 | } |
2009 | } |
2010 | |
2011 | impl<T, A: Allocator> Iterator for Drain<'_, T, A> { |
2012 | type Item = T; |
2013 | |
2014 | fn next(&mut self) -> Option<T> { |
2015 | self.inner.next() |
2016 | } |
2017 | fn size_hint(&self) -> (usize, Option<usize>) { |
2018 | self.inner.size_hint() |
2019 | } |
2020 | } |
2021 | impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> { |
2022 | fn len(&self) -> usize { |
2023 | self.inner.len() |
2024 | } |
2025 | } |
2026 | impl<T, A: Allocator> FusedIterator for Drain<'_, T, A> {} |
2027 | |
2028 | impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> { |
2029 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2030 | f.debug_list().entries(self.iter()).finish() |
2031 | } |
2032 | } |
2033 | |
2034 | /// A draining iterator over entries of a `HashTable` which don't satisfy the predicate `f`. |
2035 | /// |
2036 | /// This `struct` is created by [`HashTable::extract_if`]. See its |
2037 | /// documentation for more. |
2038 | #[must_use = "Iterators are lazy unless consumed" ] |
2039 | pub struct ExtractIf<'a, T, F, A: Allocator = Global> |
2040 | where |
2041 | F: FnMut(&mut T) -> bool, |
2042 | { |
2043 | f: F, |
2044 | inner: RawExtractIf<'a, T, A>, |
2045 | } |
2046 | |
2047 | impl<T, F, A: Allocator> Iterator for ExtractIf<'_, T, F, A> |
2048 | where |
2049 | F: FnMut(&mut T) -> bool, |
2050 | { |
2051 | type Item = T; |
2052 | |
2053 | #[inline ] |
2054 | fn next(&mut self) -> Option<Self::Item> { |
2055 | self.inner.next(|val| (self.f)(val)) |
2056 | } |
2057 | |
2058 | #[inline ] |
2059 | fn size_hint(&self) -> (usize, Option<usize>) { |
2060 | (0, self.inner.iter.size_hint().1) |
2061 | } |
2062 | } |
2063 | |
2064 | impl<T, F, A: Allocator> FusedIterator for ExtractIf<'_, T, F, A> where F: FnMut(&mut T) -> bool {} |
2065 | |