iddqd/tri_hash_map/imp.rs
1use super::{IntoIter, Iter, IterMut, RefMut, tables::TriHashMapTables};
2use crate::{
3 DefaultHashBuilder, TriHashItem,
4 errors::{DuplicateItem, TryReserveError},
5 internal::ValidationError,
6 support::{
7 ItemIndex,
8 alloc::{Allocator, Global, global_alloc},
9 borrow::DormantMutRef,
10 fmt_utils::StrDisplayAsDebug,
11 hash_table,
12 item_set::ItemSet,
13 map_hash::MapHash,
14 },
15};
16use alloc::{collections::BTreeSet, vec::Vec};
17use core::{
18 fmt,
19 hash::{BuildHasher, Hash},
20};
21use equivalent::Equivalent;
22
23#[derive(Debug)]
24#[must_use]
25struct PreparedDuplicate {
26 index: ItemIndex,
27 hashes: [MapHash; 3],
28}
29
30impl PreparedDuplicate {
31 fn from_indexes<const N: usize>(
32 indexes: [Option<ItemIndex>; N],
33 mut prepare: impl FnMut(ItemIndex) -> Self,
34 ) -> Vec<Self> {
35 let mut duplicates = Vec::new();
36
37 for index in indexes.into_iter().flatten() {
38 if duplicates
39 .iter()
40 .any(|duplicate: &PreparedDuplicate| duplicate.index == index)
41 {
42 continue;
43 }
44
45 duplicates.push(prepare(index));
46 }
47
48 duplicates
49 }
50}
51
52#[derive(Debug)]
53#[must_use]
54struct PreparedInsertOverwrite {
55 duplicates: Vec<PreparedDuplicate>,
56 hashes: [MapHash; 3],
57}
58
59impl PreparedInsertOverwrite {
60 #[inline]
61 fn duplicate_count(&self) -> usize {
62 self.duplicates.len()
63 }
64
65 #[inline]
66 fn needs_new_item_slot(&self) -> bool {
67 self.duplicates.is_empty()
68 }
69}
70
71/// A 1:1:1 (trijective) map for three keys and a value.
72///
73/// The storage mechanism is a list of items with an embedded free chain, with
74/// indexes to occupied slots stored in three hash tables. This allows for
75/// efficient lookups by any of the three keys, while preventing duplicates.
76///
77/// # Examples
78///
79/// ```
80/// # #[cfg(feature = "default-hasher")] {
81/// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
82///
83/// #[derive(Debug, PartialEq, Eq)]
84/// struct Person {
85/// id: u32,
86/// email: String,
87/// phone: String,
88/// name: String,
89/// }
90///
91/// // Implement TriHashItem to define the three key types.
92/// impl TriHashItem for Person {
93/// type K1<'a> = u32;
94/// type K2<'a> = &'a str;
95/// type K3<'a> = &'a str;
96///
97/// fn key1(&self) -> Self::K1<'_> {
98/// self.id
99/// }
100///
101/// fn key2(&self) -> Self::K2<'_> {
102/// &self.email
103/// }
104///
105/// fn key3(&self) -> Self::K3<'_> {
106/// &self.phone
107/// }
108///
109/// tri_upcast!();
110/// }
111///
112/// // Create a TriHashMap and insert items.
113/// let mut people = TriHashMap::new();
114/// people
115/// .insert_unique(Person {
116/// id: 1,
117/// email: "alice@example.com".to_string(),
118/// phone: "555-1234".to_string(),
119/// name: "Alice".to_string(),
120/// })
121/// .unwrap();
122///
123/// // Lookup by any of the three keys.
124/// let person = people.get1(&1).unwrap();
125/// assert_eq!(person.name, "Alice");
126///
127/// let person = people.get2("alice@example.com").unwrap();
128/// assert_eq!(person.id, 1);
129///
130/// let person = people.get3("555-1234").unwrap();
131/// assert_eq!(person.email, "alice@example.com");
132/// # }
133/// ```
134#[derive(Clone)]
135pub struct TriHashMap<T, S = DefaultHashBuilder, A: Allocator = Global> {
136 pub(super) items: ItemSet<T, A>,
137 // Invariant: the values (ItemIndex) in these tables are valid indexes into
138 // `items`, and are a 1:1 mapping.
139 tables: TriHashMapTables<S, A>,
140}
141
142impl<T: TriHashItem, S: Default, A: Allocator + Default> Default
143 for TriHashMap<T, S, A>
144{
145 fn default() -> Self {
146 Self {
147 items: ItemSet::with_capacity_in(0, A::default()),
148 tables: TriHashMapTables::default(),
149 }
150 }
151}
152
153#[cfg(feature = "default-hasher")]
154impl<T: TriHashItem> TriHashMap<T> {
155 /// Creates a new, empty `TriHashMap`.
156 ///
157 /// # Examples
158 ///
159 /// ```
160 /// # #[cfg(feature = "default-hasher")] {
161 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
162 ///
163 /// #[derive(Debug, PartialEq, Eq)]
164 /// struct Person {
165 /// id: u32,
166 /// email: String,
167 /// phone: String,
168 /// name: String,
169 /// }
170 ///
171 /// impl TriHashItem for Person {
172 /// type K1<'a> = u32;
173 /// type K2<'a> = &'a str;
174 /// type K3<'a> = &'a str;
175 ///
176 /// fn key1(&self) -> Self::K1<'_> {
177 /// self.id
178 /// }
179 /// fn key2(&self) -> Self::K2<'_> {
180 /// &self.email
181 /// }
182 /// fn key3(&self) -> Self::K3<'_> {
183 /// &self.phone
184 /// }
185 /// tri_upcast!();
186 /// }
187 ///
188 /// let map: TriHashMap<Person> = TriHashMap::new();
189 /// assert!(map.is_empty());
190 /// assert_eq!(map.len(), 0);
191 /// # }
192 /// ```
193 #[inline]
194 pub fn new() -> Self {
195 Self { items: ItemSet::new(), tables: TriHashMapTables::default() }
196 }
197
198 /// Creates a new `TriHashMap` with the given capacity.
199 ///
200 /// # Examples
201 ///
202 /// ```
203 /// # #[cfg(feature = "default-hasher")] {
204 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
205 ///
206 /// #[derive(Debug, PartialEq, Eq)]
207 /// struct Person {
208 /// id: u32,
209 /// email: String,
210 /// phone: String,
211 /// name: String,
212 /// }
213 ///
214 /// impl TriHashItem for Person {
215 /// type K1<'a> = u32;
216 /// type K2<'a> = &'a str;
217 /// type K3<'a> = &'a str;
218 ///
219 /// fn key1(&self) -> Self::K1<'_> {
220 /// self.id
221 /// }
222 /// fn key2(&self) -> Self::K2<'_> {
223 /// &self.email
224 /// }
225 /// fn key3(&self) -> Self::K3<'_> {
226 /// &self.phone
227 /// }
228 /// tri_upcast!();
229 /// }
230 ///
231 /// let map: TriHashMap<Person> = TriHashMap::with_capacity(10);
232 /// assert!(map.capacity() >= 10);
233 /// assert!(map.is_empty());
234 /// # }
235 /// ```
236 pub fn with_capacity(capacity: usize) -> Self {
237 Self {
238 items: ItemSet::with_capacity_in(capacity, global_alloc()),
239 tables: TriHashMapTables::with_capacity_and_hasher_in(
240 capacity,
241 DefaultHashBuilder::default(),
242 global_alloc(),
243 ),
244 }
245 }
246}
247
248impl<T: TriHashItem, S: BuildHasher> TriHashMap<T, S> {
249 /// Creates a new, empty `TriHashMap` with the given hasher.
250 ///
251 /// # Examples
252 ///
253 /// ```
254 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
255 /// use std::collections::hash_map::RandomState;
256 ///
257 /// #[derive(Debug, PartialEq, Eq)]
258 /// struct Person {
259 /// id: u32,
260 /// email: String,
261 /// phone: String,
262 /// name: String,
263 /// }
264 ///
265 /// impl TriHashItem for Person {
266 /// type K1<'a> = u32;
267 /// type K2<'a> = &'a str;
268 /// type K3<'a> = &'a str;
269 ///
270 /// fn key1(&self) -> Self::K1<'_> {
271 /// self.id
272 /// }
273 /// fn key2(&self) -> Self::K2<'_> {
274 /// &self.email
275 /// }
276 /// fn key3(&self) -> Self::K3<'_> {
277 /// &self.phone
278 /// }
279 /// tri_upcast!();
280 /// }
281 ///
282 /// let map: TriHashMap<Person, RandomState> =
283 /// TriHashMap::with_hasher(RandomState::new());
284 /// assert!(map.is_empty());
285 /// ```
286 pub const fn with_hasher(hasher: S) -> Self {
287 Self {
288 items: ItemSet::new(),
289 tables: TriHashMapTables::with_hasher(hasher),
290 }
291 }
292
293 /// Creates a new `TriHashMap` with the given capacity and hasher.
294 ///
295 /// # Examples
296 ///
297 /// ```
298 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
299 /// use std::collections::hash_map::RandomState;
300 ///
301 /// #[derive(Debug, PartialEq, Eq)]
302 /// struct Person {
303 /// id: u32,
304 /// email: String,
305 /// phone: String,
306 /// name: String,
307 /// }
308 ///
309 /// impl TriHashItem for Person {
310 /// type K1<'a> = u32;
311 /// type K2<'a> = &'a str;
312 /// type K3<'a> = &'a str;
313 ///
314 /// fn key1(&self) -> Self::K1<'_> {
315 /// self.id
316 /// }
317 /// fn key2(&self) -> Self::K2<'_> {
318 /// &self.email
319 /// }
320 /// fn key3(&self) -> Self::K3<'_> {
321 /// &self.phone
322 /// }
323 /// tri_upcast!();
324 /// }
325 ///
326 /// let map: TriHashMap<Person, RandomState> =
327 /// TriHashMap::with_capacity_and_hasher(10, RandomState::new());
328 /// assert!(map.capacity() >= 10);
329 /// assert!(map.is_empty());
330 /// ```
331 pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
332 Self {
333 items: ItemSet::with_capacity_in(capacity, global_alloc()),
334 tables: TriHashMapTables::with_capacity_and_hasher_in(
335 capacity,
336 hasher,
337 global_alloc(),
338 ),
339 }
340 }
341}
342
343#[cfg(feature = "default-hasher")]
344impl<T: TriHashItem, A: Clone + Allocator>
345 TriHashMap<T, DefaultHashBuilder, A>
346{
347 /// Creates a new empty `TriHashMap` using the given allocator.
348 ///
349 /// Requires the `allocator-api2` feature to be enabled.
350 ///
351 /// # Examples
352 ///
353 /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
354 ///
355 /// ```
356 /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
357 /// use iddqd::{TriHashMap, TriHashItem, tri_upcast};
358 /// # use iddqd_test_utils::bumpalo;
359 ///
360 /// #[derive(Debug, PartialEq, Eq)]
361 /// struct Person {
362 /// id: u32,
363 /// email: String,
364 /// phone: String,
365 /// name: String,
366 /// }
367 ///
368 /// impl TriHashItem for Person {
369 /// type K1<'a> = u32;
370 /// type K2<'a> = &'a str;
371 /// type K3<'a> = &'a str;
372 ///
373 /// fn key1(&self) -> Self::K1<'_> {
374 /// self.id
375 /// }
376 /// fn key2(&self) -> Self::K2<'_> {
377 /// &self.email
378 /// }
379 /// fn key3(&self) -> Self::K3<'_> {
380 /// &self.phone
381 /// }
382 /// tri_upcast!();
383 /// }
384 ///
385 /// // Define a new allocator.
386 /// let bump = bumpalo::Bump::new();
387 /// // Create a new TriHashMap using the allocator.
388 /// let map: TriHashMap<Person, _, &bumpalo::Bump> = TriHashMap::new_in(&bump);
389 /// assert!(map.is_empty());
390 /// # }
391 /// ```
392 pub fn new_in(alloc: A) -> Self {
393 Self {
394 items: ItemSet::with_capacity_in(0, alloc.clone()),
395 tables: TriHashMapTables::with_capacity_and_hasher_in(
396 0,
397 DefaultHashBuilder::default(),
398 alloc,
399 ),
400 }
401 }
402
403 /// Creates an empty `TriHashMap` with the specified capacity using the given
404 /// allocator.
405 ///
406 /// Requires the `allocator-api2` feature to be enabled.
407 ///
408 /// # Examples
409 ///
410 /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
411 ///
412 /// ```
413 /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
414 /// use iddqd::{TriHashMap, TriHashItem, tri_upcast};
415 /// # use iddqd_test_utils::bumpalo;
416 ///
417 /// #[derive(Debug, PartialEq, Eq)]
418 /// struct Person {
419 /// id: u32,
420 /// email: String,
421 /// phone: String,
422 /// name: String,
423 /// }
424 ///
425 /// impl TriHashItem for Person {
426 /// type K1<'a> = u32;
427 /// type K2<'a> = &'a str;
428 /// type K3<'a> = &'a str;
429 ///
430 /// fn key1(&self) -> Self::K1<'_> {
431 /// self.id
432 /// }
433 /// fn key2(&self) -> Self::K2<'_> {
434 /// &self.email
435 /// }
436 /// fn key3(&self) -> Self::K3<'_> {
437 /// &self.phone
438 /// }
439 /// tri_upcast!();
440 /// }
441 ///
442 /// // Define a new allocator.
443 /// let bump = bumpalo::Bump::new();
444 /// // Create a new TriHashMap with capacity using the allocator.
445 /// let map: TriHashMap<Person, _, &bumpalo::Bump> = TriHashMap::with_capacity_in(10, &bump);
446 /// assert!(map.capacity() >= 10);
447 /// assert!(map.is_empty());
448 /// # }
449 /// ```
450 pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
451 Self {
452 items: ItemSet::with_capacity_in(capacity, alloc.clone()),
453 tables: TriHashMapTables::with_capacity_and_hasher_in(
454 capacity,
455 DefaultHashBuilder::default(),
456 alloc,
457 ),
458 }
459 }
460}
461
462impl<T: TriHashItem, S: Clone + BuildHasher, A: Clone + Allocator>
463 TriHashMap<T, S, A>
464{
465 /// Creates a new, empty `TriHashMap` with the given hasher and allocator.
466 ///
467 /// Requires the `allocator-api2` feature to be enabled.
468 ///
469 /// # Examples
470 ///
471 /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
472 ///
473 /// ```
474 /// # #[cfg(feature = "allocator-api2")] {
475 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
476 /// use std::collections::hash_map::RandomState;
477 /// # use iddqd_test_utils::bumpalo;
478 ///
479 /// #[derive(Debug, PartialEq, Eq)]
480 /// struct Person {
481 /// id: u32,
482 /// email: String,
483 /// phone: String,
484 /// name: String,
485 /// }
486 ///
487 /// impl TriHashItem for Person {
488 /// type K1<'a> = u32;
489 /// type K2<'a> = &'a str;
490 /// type K3<'a> = &'a str;
491 ///
492 /// fn key1(&self) -> Self::K1<'_> {
493 /// self.id
494 /// }
495 /// fn key2(&self) -> Self::K2<'_> {
496 /// &self.email
497 /// }
498 /// fn key3(&self) -> Self::K3<'_> {
499 /// &self.phone
500 /// }
501 /// tri_upcast!();
502 /// }
503 ///
504 /// // Define a new allocator.
505 /// let bump = bumpalo::Bump::new();
506 /// let hasher = RandomState::new();
507 /// // Create a new TriHashMap with hasher using the allocator.
508 /// let map: TriHashMap<Person, _, &bumpalo::Bump> =
509 /// TriHashMap::with_hasher_in(hasher, &bump);
510 /// assert!(map.is_empty());
511 /// # }
512 /// ```
513 pub fn with_hasher_in(hasher: S, alloc: A) -> Self {
514 Self {
515 items: ItemSet::with_capacity_in(0, alloc.clone()),
516 tables: TriHashMapTables::with_capacity_and_hasher_in(
517 0,
518 hasher.clone(),
519 alloc,
520 ),
521 }
522 }
523
524 /// Creates a new `TriHashMap` with the given capacity, hasher, and
525 /// allocator.
526 ///
527 /// Requires the `allocator-api2` feature to be enabled.
528 ///
529 /// # Examples
530 ///
531 /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
532 ///
533 /// ```
534 /// # #[cfg(feature = "allocator-api2")] {
535 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
536 /// use std::collections::hash_map::RandomState;
537 /// # use iddqd_test_utils::bumpalo;
538 ///
539 /// #[derive(Debug, PartialEq, Eq)]
540 /// struct Person {
541 /// id: u32,
542 /// email: String,
543 /// phone: String,
544 /// name: String,
545 /// }
546 ///
547 /// impl TriHashItem for Person {
548 /// type K1<'a> = u32;
549 /// type K2<'a> = &'a str;
550 /// type K3<'a> = &'a str;
551 ///
552 /// fn key1(&self) -> Self::K1<'_> {
553 /// self.id
554 /// }
555 /// fn key2(&self) -> Self::K2<'_> {
556 /// &self.email
557 /// }
558 /// fn key3(&self) -> Self::K3<'_> {
559 /// &self.phone
560 /// }
561 /// tri_upcast!();
562 /// }
563 ///
564 /// // Define a new allocator.
565 /// let bump = bumpalo::Bump::new();
566 /// let hasher = RandomState::new();
567 /// // Create a new TriHashMap with capacity and hasher using the allocator.
568 /// let map: TriHashMap<Person, _, &bumpalo::Bump> =
569 /// TriHashMap::with_capacity_and_hasher_in(10, hasher, &bump);
570 /// assert!(map.capacity() >= 10);
571 /// assert!(map.is_empty());
572 /// # }
573 /// ```
574 pub fn with_capacity_and_hasher_in(
575 capacity: usize,
576 hasher: S,
577 alloc: A,
578 ) -> Self {
579 Self {
580 items: ItemSet::with_capacity_in(capacity, alloc.clone()),
581 tables: TriHashMapTables::with_capacity_and_hasher_in(
582 capacity, hasher, alloc,
583 ),
584 }
585 }
586}
587
588impl<T: TriHashItem, S: Default + Clone + BuildHasher, A: Allocator + Default>
589 TriHashMap<T, S, A>
590{
591 /// Creates a new `TriHashMap` from an iterator of values, rejecting
592 /// duplicates.
593 ///
594 /// A value conflicts when any of its keys matches an already-inserted
595 /// item, so a single value can collide with up to three distinct
596 /// existing items (one per key). On the first conflict, this returns a
597 /// [`DuplicateItem`] error containing the new value and every
598 /// conflicting item.
599 ///
600 /// To overwrite duplicates instead, use [`TriHashMap::from_iter`].
601 ///
602 /// # Examples
603 ///
604 /// ```
605 /// # #[cfg(feature = "default-hasher")] {
606 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
607 ///
608 /// #[derive(Debug, PartialEq, Eq)]
609 /// struct Item {
610 /// id: u32,
611 /// name: String,
612 /// email: String,
613 /// }
614 ///
615 /// impl TriHashItem for Item {
616 /// type K1<'a> = u32;
617 /// type K2<'a> = &'a str;
618 /// type K3<'a> = &'a str;
619 /// fn key1(&self) -> Self::K1<'_> {
620 /// self.id
621 /// }
622 /// fn key2(&self) -> Self::K2<'_> {
623 /// &self.name
624 /// }
625 /// fn key3(&self) -> Self::K3<'_> {
626 /// &self.email
627 /// }
628 /// tri_upcast!();
629 /// }
630 ///
631 /// let items = vec![
632 /// Item {
633 /// id: 1,
634 /// name: "foo".to_string(),
635 /// email: "foo@example.com".to_string(),
636 /// },
637 /// Item {
638 /// id: 2,
639 /// name: "bar".to_string(),
640 /// email: "bar@example.com".to_string(),
641 /// },
642 /// ];
643 ///
644 /// // Successful creation with unique keys.
645 /// let map: TriHashMap<Item> = TriHashMap::from_iter_unique(items).unwrap();
646 /// assert_eq!(map.len(), 2);
647 /// assert_eq!(map.get1(&1).unwrap().name, "foo");
648 ///
649 /// // Error with a duplicate key3.
650 /// let duplicate_items = vec![
651 /// Item {
652 /// id: 1,
653 /// name: "foo".to_string(),
654 /// email: "dup@example.com".to_string(),
655 /// },
656 /// Item {
657 /// id: 2,
658 /// name: "bar".to_string(),
659 /// email: "dup@example.com".to_string(),
660 /// },
661 /// ];
662 /// assert!(TriHashMap::<Item>::from_iter_unique(duplicate_items).is_err());
663 /// # }
664 /// ```
665 pub fn from_iter_unique<I: IntoIterator<Item = T>>(
666 iter: I,
667 ) -> Result<Self, DuplicateItem<T>> {
668 let iter = iter.into_iter();
669 let mut map = Self::default();
670 map.reserve(iter.size_hint().0);
671 for value in iter {
672 if let Err((value, indexes)) =
673 map.insert_unique_or_dup_indexes(value)
674 {
675 // Removal produces owned duplicates, so that we don't need to
676 // specify `T: Clone` here.
677 let duplicates = indexes
678 .iter()
679 .map(|ix| {
680 map.remove_by_index(*ix)
681 .expect("duplicate index is present")
682 })
683 .collect();
684 return Err(DuplicateItem::__internal_new(value, duplicates));
685 }
686 }
687
688 Ok(map)
689 }
690}
691
692impl<T: TriHashItem, S: Clone + BuildHasher, A: Allocator> TriHashMap<T, S, A> {
693 /// Returns the hasher.
694 #[cfg(feature = "daft")]
695 #[inline]
696 pub(crate) fn hasher(&self) -> &S {
697 self.tables.hasher()
698 }
699
700 /// Returns the allocator.
701 ///
702 /// Requires the `allocator-api2` feature to be enabled.
703 ///
704 /// # Examples
705 ///
706 /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
707 ///
708 /// ```
709 /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
710 /// use iddqd::{TriHashMap, TriHashItem, tri_upcast};
711 /// # use iddqd_test_utils::bumpalo;
712 ///
713 /// #[derive(Debug, PartialEq, Eq)]
714 /// struct Person {
715 /// id: u32,
716 /// email: String,
717 /// phone: String,
718 /// name: String,
719 /// }
720 ///
721 /// impl TriHashItem for Person {
722 /// type K1<'a> = u32;
723 /// type K2<'a> = &'a str;
724 /// type K3<'a> = &'a str;
725 ///
726 /// fn key1(&self) -> Self::K1<'_> {
727 /// self.id
728 /// }
729 /// fn key2(&self) -> Self::K2<'_> {
730 /// &self.email
731 /// }
732 /// fn key3(&self) -> Self::K3<'_> {
733 /// &self.phone
734 /// }
735 /// tri_upcast!();
736 /// }
737 ///
738 /// // Define a new allocator.
739 /// let bump = bumpalo::Bump::new();
740 /// // Create a new TriHashMap using the allocator.
741 /// let map: TriHashMap<Person, _, &bumpalo::Bump> = TriHashMap::new_in(&bump);
742 /// // Access the allocator.
743 /// let allocator = map.allocator();
744 /// # }
745 /// ```
746 #[inline]
747 pub fn allocator(&self) -> &A {
748 self.items.allocator()
749 }
750
751 /// Returns the currently allocated capacity of the map.
752 ///
753 /// # Examples
754 ///
755 /// ```
756 /// # #[cfg(feature = "default-hasher")] {
757 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
758 ///
759 /// #[derive(Debug, PartialEq, Eq)]
760 /// struct Person {
761 /// id: u32,
762 /// email: String,
763 /// phone: String,
764 /// name: String,
765 /// }
766 ///
767 /// impl TriHashItem for Person {
768 /// type K1<'a> = u32;
769 /// type K2<'a> = &'a str;
770 /// type K3<'a> = &'a str;
771 ///
772 /// fn key1(&self) -> Self::K1<'_> {
773 /// self.id
774 /// }
775 /// fn key2(&self) -> Self::K2<'_> {
776 /// &self.email
777 /// }
778 /// fn key3(&self) -> Self::K3<'_> {
779 /// &self.phone
780 /// }
781 /// tri_upcast!();
782 /// }
783 ///
784 /// let map: TriHashMap<Person> = TriHashMap::with_capacity(10);
785 /// assert!(map.capacity() >= 10);
786 /// # }
787 /// ```
788 pub fn capacity(&self) -> usize {
789 // items and tables.capacity might theoretically diverge: use
790 // items.capacity.
791 self.items.capacity()
792 }
793
794 /// Returns true if the map is empty.
795 ///
796 /// # Examples
797 ///
798 /// ```
799 /// # #[cfg(feature = "default-hasher")] {
800 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
801 ///
802 /// #[derive(Debug, PartialEq, Eq)]
803 /// struct Person {
804 /// id: u32,
805 /// email: String,
806 /// phone: String,
807 /// name: String,
808 /// }
809 ///
810 /// impl TriHashItem for Person {
811 /// type K1<'a> = u32;
812 /// type K2<'a> = &'a str;
813 /// type K3<'a> = &'a str;
814 ///
815 /// fn key1(&self) -> Self::K1<'_> {
816 /// self.id
817 /// }
818 /// fn key2(&self) -> Self::K2<'_> {
819 /// &self.email
820 /// }
821 /// fn key3(&self) -> Self::K3<'_> {
822 /// &self.phone
823 /// }
824 /// tri_upcast!();
825 /// }
826 ///
827 /// let mut map = TriHashMap::new();
828 /// assert!(map.is_empty());
829 ///
830 /// map.insert_unique(Person {
831 /// id: 1,
832 /// email: "alice@example.com".to_string(),
833 /// phone: "555-1234".to_string(),
834 /// name: "Alice".to_string(),
835 /// })
836 /// .unwrap();
837 /// assert!(!map.is_empty());
838 /// # }
839 /// ```
840 #[inline]
841 pub fn is_empty(&self) -> bool {
842 self.items.is_empty()
843 }
844
845 /// Returns the number of items in the map.
846 ///
847 /// # Examples
848 ///
849 /// ```
850 /// # #[cfg(feature = "default-hasher")] {
851 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
852 ///
853 /// #[derive(Debug, PartialEq, Eq)]
854 /// struct Person {
855 /// id: u32,
856 /// email: String,
857 /// phone: String,
858 /// name: String,
859 /// }
860 ///
861 /// impl TriHashItem for Person {
862 /// type K1<'a> = u32;
863 /// type K2<'a> = &'a str;
864 /// type K3<'a> = &'a str;
865 ///
866 /// fn key1(&self) -> Self::K1<'_> {
867 /// self.id
868 /// }
869 /// fn key2(&self) -> Self::K2<'_> {
870 /// &self.email
871 /// }
872 /// fn key3(&self) -> Self::K3<'_> {
873 /// &self.phone
874 /// }
875 /// tri_upcast!();
876 /// }
877 ///
878 /// let mut map = TriHashMap::new();
879 /// assert_eq!(map.len(), 0);
880 ///
881 /// map.insert_unique(Person {
882 /// id: 1,
883 /// email: "alice@example.com".to_string(),
884 /// phone: "555-1234".to_string(),
885 /// name: "Alice".to_string(),
886 /// })
887 /// .unwrap();
888 /// map.insert_unique(Person {
889 /// id: 2,
890 /// email: "bob@example.com".to_string(),
891 /// phone: "555-5678".to_string(),
892 /// name: "Bob".to_string(),
893 /// })
894 /// .unwrap();
895 /// assert_eq!(map.len(), 2);
896 /// # }
897 /// ```
898 #[inline]
899 pub fn len(&self) -> usize {
900 self.items.len()
901 }
902
903 /// Clears the map, removing all items.
904 ///
905 /// # Examples
906 ///
907 /// ```
908 /// # #[cfg(feature = "default-hasher")] {
909 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
910 ///
911 /// #[derive(Debug, PartialEq, Eq)]
912 /// struct Person {
913 /// id: u32,
914 /// email: String,
915 /// phone: String,
916 /// name: String,
917 /// }
918 ///
919 /// impl TriHashItem for Person {
920 /// type K1<'a> = u32;
921 /// type K2<'a> = &'a str;
922 /// type K3<'a> = &'a str;
923 ///
924 /// fn key1(&self) -> Self::K1<'_> {
925 /// self.id
926 /// }
927 /// fn key2(&self) -> Self::K2<'_> {
928 /// &self.email
929 /// }
930 /// fn key3(&self) -> Self::K3<'_> {
931 /// &self.phone
932 /// }
933 /// tri_upcast!();
934 /// }
935 ///
936 /// let mut map = TriHashMap::new();
937 /// map.insert_unique(Person {
938 /// id: 1,
939 /// email: "alice@example.com".to_string(),
940 /// phone: "555-1234".to_string(),
941 /// name: "Alice".to_string(),
942 /// })
943 /// .unwrap();
944 /// assert_eq!(map.len(), 1);
945 ///
946 /// map.clear();
947 /// assert!(map.is_empty());
948 /// assert_eq!(map.len(), 0);
949 /// # }
950 /// ```
951 pub fn clear(&mut self) {
952 // Clear the internal indexes before dropping items. This way, if a user
953 // `Drop` panics during `self.items.clear()`, the tables cannot retain
954 // indexes pointing to removed item slots.
955 self.tables.k1_to_item.clear();
956 self.tables.k2_to_item.clear();
957 self.tables.k3_to_item.clear();
958 self.items.clear();
959 }
960
961 /// Reserves capacity for at least `additional` more elements to be inserted
962 /// in the `TriHashMap`. The collection may reserve more space to
963 /// speculatively avoid frequent reallocations. After calling `reserve`,
964 /// capacity will be greater than or equal to `self.len() + additional`.
965 /// Does nothing if capacity is already sufficient.
966 ///
967 /// # Panics
968 ///
969 /// Panics if the new capacity overflows [`isize::MAX`] bytes, and
970 /// [`abort`]s the program in case of an allocation error. Use
971 /// [`try_reserve`](Self::try_reserve) instead if you want to handle memory
972 /// allocation failure.
973 ///
974 /// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html
975 /// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html
976 ///
977 /// # Examples
978 ///
979 /// ```
980 /// # #[cfg(feature = "default-hasher")] {
981 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
982 ///
983 /// #[derive(Debug, PartialEq, Eq, Hash)]
984 /// struct Item {
985 /// id: u32,
986 /// name: String,
987 /// email: String,
988 /// }
989 ///
990 /// impl TriHashItem for Item {
991 /// type K1<'a> = u32;
992 /// type K2<'a> = &'a str;
993 /// type K3<'a> = &'a str;
994 /// fn key1(&self) -> Self::K1<'_> {
995 /// self.id
996 /// }
997 /// fn key2(&self) -> Self::K2<'_> {
998 /// &self.name
999 /// }
1000 /// fn key3(&self) -> Self::K3<'_> {
1001 /// &self.email
1002 /// }
1003 /// tri_upcast!();
1004 /// }
1005 ///
1006 /// let mut map: TriHashMap<Item> = TriHashMap::new();
1007 /// map.reserve(100);
1008 /// assert!(map.capacity() >= 100);
1009 /// # }
1010 /// ```
1011 pub fn reserve(&mut self, additional: usize) {
1012 self.items.reserve(additional);
1013 self.tables.k1_to_item.reserve(additional);
1014 self.tables.k2_to_item.reserve(additional);
1015 self.tables.k3_to_item.reserve(additional);
1016 }
1017
1018 /// Tries to reserve capacity for at least `additional` more elements to be
1019 /// inserted in the `TriHashMap`. The collection may reserve more space to
1020 /// speculatively avoid frequent reallocations. After calling `try_reserve`,
1021 /// capacity will be greater than or equal to `self.len() + additional` if
1022 /// it returns `Ok(())`. Does nothing if capacity is already sufficient.
1023 ///
1024 /// # Errors
1025 ///
1026 /// If the capacity overflows, or the allocator reports a failure, then an
1027 /// error is returned.
1028 ///
1029 /// # Notes
1030 ///
1031 /// If reservation fails partway through, some internal structures may have
1032 /// already increased their capacity. The map remains in a valid state but
1033 /// may have uneven capacities across its internal structures.
1034 ///
1035 /// # Examples
1036 ///
1037 /// ```
1038 /// # #[cfg(feature = "default-hasher")] {
1039 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1040 ///
1041 /// #[derive(Debug, PartialEq, Eq, Hash)]
1042 /// struct Item {
1043 /// id: u32,
1044 /// name: String,
1045 /// email: String,
1046 /// }
1047 ///
1048 /// impl TriHashItem for Item {
1049 /// type K1<'a> = u32;
1050 /// type K2<'a> = &'a str;
1051 /// type K3<'a> = &'a str;
1052 /// fn key1(&self) -> Self::K1<'_> {
1053 /// self.id
1054 /// }
1055 /// fn key2(&self) -> Self::K2<'_> {
1056 /// &self.name
1057 /// }
1058 /// fn key3(&self) -> Self::K3<'_> {
1059 /// &self.email
1060 /// }
1061 /// tri_upcast!();
1062 /// }
1063 ///
1064 /// let mut map: TriHashMap<Item> = TriHashMap::new();
1065 /// map.try_reserve(100).expect("allocation should succeed");
1066 /// assert!(map.capacity() >= 100);
1067 /// # }
1068 /// ```
1069 pub fn try_reserve(
1070 &mut self,
1071 additional: usize,
1072 ) -> Result<(), crate::errors::TryReserveError> {
1073 self.items.try_reserve(additional)?;
1074 self.tables
1075 .k1_to_item
1076 .try_reserve(additional)
1077 .map_err(crate::errors::TryReserveError::from_hashbrown)?;
1078 self.tables
1079 .k2_to_item
1080 .try_reserve(additional)
1081 .map_err(crate::errors::TryReserveError::from_hashbrown)?;
1082 self.tables
1083 .k3_to_item
1084 .try_reserve(additional)
1085 .map_err(crate::errors::TryReserveError::from_hashbrown)?;
1086 Ok(())
1087 }
1088
1089 /// Shrinks the capacity of the map as much as possible. It will drop
1090 /// down as much as possible while maintaining the internal rules
1091 /// and possibly leaving some space in accordance with the resize policy.
1092 ///
1093 /// # Examples
1094 ///
1095 /// ```
1096 /// # #[cfg(feature = "default-hasher")] {
1097 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1098 ///
1099 /// #[derive(Debug, PartialEq, Eq, Hash)]
1100 /// struct Item {
1101 /// id: u32,
1102 /// name: String,
1103 /// email: String,
1104 /// }
1105 ///
1106 /// impl TriHashItem for Item {
1107 /// type K1<'a> = u32;
1108 /// type K2<'a> = &'a str;
1109 /// type K3<'a> = &'a str;
1110 /// fn key1(&self) -> Self::K1<'_> {
1111 /// self.id
1112 /// }
1113 /// fn key2(&self) -> Self::K2<'_> {
1114 /// &self.name
1115 /// }
1116 /// fn key3(&self) -> Self::K3<'_> {
1117 /// &self.email
1118 /// }
1119 /// tri_upcast!();
1120 /// }
1121 ///
1122 /// let mut map: TriHashMap<Item> = TriHashMap::with_capacity(100);
1123 /// map.insert_unique(Item {
1124 /// id: 1,
1125 /// name: "foo".to_string(),
1126 /// email: "foo@example.com".to_string(),
1127 /// })
1128 /// .unwrap();
1129 /// map.insert_unique(Item {
1130 /// id: 2,
1131 /// name: "bar".to_string(),
1132 /// email: "bar@example.com".to_string(),
1133 /// })
1134 /// .unwrap();
1135 /// assert!(map.capacity() >= 100);
1136 /// map.shrink_to_fit();
1137 /// assert!(map.capacity() >= 2);
1138 /// # }
1139 /// ```
1140 pub fn shrink_to_fit(&mut self) {
1141 // Sequence this carefully.
1142 //
1143 // * First, compact the item set. This does not allocate through A
1144 // (it allocates a small remap buffer through the global allocator),
1145 // and returns a remapper.
1146 // * Then, remap the tables using the remapper.
1147 // * Finally, shrink the capacities of the tables and items.
1148 //
1149 // An allocator panic during either capacity shrink leaves the tables
1150 // and items already in sync, because remap has already been committed.
1151 let remap = self.items.compact();
1152 if !remap.is_identity() {
1153 self.tables.k1_to_item.remap_indexes(&remap);
1154 self.tables.k2_to_item.remap_indexes(&remap);
1155 self.tables.k3_to_item.remap_indexes(&remap);
1156 }
1157 self.items.shrink_capacity_to_fit();
1158 self.tables.k1_to_item.shrink_to_fit();
1159 self.tables.k2_to_item.shrink_to_fit();
1160 self.tables.k3_to_item.shrink_to_fit();
1161 }
1162
1163 /// Shrinks the capacity of the map with a lower limit. It will drop
1164 /// down no lower than the supplied limit while maintaining the internal
1165 /// rules and possibly leaving some space in accordance with the resize
1166 /// policy.
1167 ///
1168 /// If the current capacity is less than the lower limit, this is a no-op.
1169 ///
1170 /// # Examples
1171 ///
1172 /// ```
1173 /// # #[cfg(feature = "default-hasher")] {
1174 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1175 ///
1176 /// #[derive(Debug, PartialEq, Eq, Hash)]
1177 /// struct Item {
1178 /// id: u32,
1179 /// name: String,
1180 /// email: String,
1181 /// }
1182 ///
1183 /// impl TriHashItem for Item {
1184 /// type K1<'a> = u32;
1185 /// type K2<'a> = &'a str;
1186 /// type K3<'a> = &'a str;
1187 /// fn key1(&self) -> Self::K1<'_> {
1188 /// self.id
1189 /// }
1190 /// fn key2(&self) -> Self::K2<'_> {
1191 /// &self.name
1192 /// }
1193 /// fn key3(&self) -> Self::K3<'_> {
1194 /// &self.email
1195 /// }
1196 /// tri_upcast!();
1197 /// }
1198 ///
1199 /// let mut map: TriHashMap<Item> = TriHashMap::with_capacity(100);
1200 /// map.insert_unique(Item {
1201 /// id: 1,
1202 /// name: "foo".to_string(),
1203 /// email: "foo@example.com".to_string(),
1204 /// })
1205 /// .unwrap();
1206 /// map.insert_unique(Item {
1207 /// id: 2,
1208 /// name: "bar".to_string(),
1209 /// email: "bar@example.com".to_string(),
1210 /// })
1211 /// .unwrap();
1212 /// assert!(map.capacity() >= 100);
1213 /// map.shrink_to(10);
1214 /// assert!(map.capacity() >= 10);
1215 /// map.shrink_to(0);
1216 /// assert!(map.capacity() >= 2);
1217 /// # }
1218 /// ```
1219 pub fn shrink_to(&mut self, min_capacity: usize) {
1220 // See `shrink_to_fit` for the rationale behind the sequence.
1221 let remap = self.items.compact();
1222 if !remap.is_identity() {
1223 self.tables.k1_to_item.remap_indexes(&remap);
1224 self.tables.k2_to_item.remap_indexes(&remap);
1225 self.tables.k3_to_item.remap_indexes(&remap);
1226 }
1227 self.items.shrink_capacity_to(min_capacity);
1228 self.tables.k1_to_item.shrink_to(min_capacity);
1229 self.tables.k2_to_item.shrink_to(min_capacity);
1230 self.tables.k3_to_item.shrink_to(min_capacity);
1231 }
1232
1233 /// Iterates over the items in the map.
1234 ///
1235 /// Similar to [`HashMap`], the iteration order is arbitrary and not
1236 /// guaranteed to be stable.
1237 ///
1238 /// # Examples
1239 ///
1240 /// ```
1241 /// # #[cfg(feature = "default-hasher")] {
1242 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1243 ///
1244 /// #[derive(Debug, PartialEq, Eq)]
1245 /// struct Person {
1246 /// id: u32,
1247 /// email: String,
1248 /// phone: String,
1249 /// name: String,
1250 /// }
1251 ///
1252 /// impl TriHashItem for Person {
1253 /// type K1<'a> = u32;
1254 /// type K2<'a> = &'a str;
1255 /// type K3<'a> = &'a str;
1256 ///
1257 /// fn key1(&self) -> Self::K1<'_> {
1258 /// self.id
1259 /// }
1260 /// fn key2(&self) -> Self::K2<'_> {
1261 /// &self.email
1262 /// }
1263 /// fn key3(&self) -> Self::K3<'_> {
1264 /// &self.phone
1265 /// }
1266 /// tri_upcast!();
1267 /// }
1268 ///
1269 /// let mut map = TriHashMap::new();
1270 /// map.insert_unique(Person {
1271 /// id: 1,
1272 /// email: "alice@example.com".to_string(),
1273 /// phone: "555-1234".to_string(),
1274 /// name: "Alice".to_string(),
1275 /// })
1276 /// .unwrap();
1277 /// map.insert_unique(Person {
1278 /// id: 2,
1279 /// email: "bob@example.com".to_string(),
1280 /// phone: "555-5678".to_string(),
1281 /// name: "Bob".to_string(),
1282 /// })
1283 /// .unwrap();
1284 ///
1285 /// let mut count = 0;
1286 /// for person in map.iter() {
1287 /// assert!(person.id == 1 || person.id == 2);
1288 /// count += 1;
1289 /// }
1290 /// assert_eq!(count, 2);
1291 /// # }
1292 /// ```
1293 ///
1294 /// [`HashMap`]: std::collections::HashMap
1295 #[inline]
1296 pub fn iter(&self) -> Iter<'_, T> {
1297 Iter::new(&self.items)
1298 }
1299
1300 /// Iterates over the items in the map, allowing for mutation.
1301 ///
1302 /// Similar to [`HashMap`], the iteration order is arbitrary and not
1303 /// guaranteed to be stable.
1304 ///
1305 /// # Examples
1306 ///
1307 /// ```
1308 /// # #[cfg(feature = "default-hasher")] {
1309 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1310 ///
1311 /// #[derive(Debug, PartialEq, Eq)]
1312 /// struct Person {
1313 /// id: u32,
1314 /// email: String,
1315 /// phone: String,
1316 /// name: String,
1317 /// }
1318 ///
1319 /// impl TriHashItem for Person {
1320 /// type K1<'a> = u32;
1321 /// type K2<'a> = &'a str;
1322 /// type K3<'a> = &'a str;
1323 ///
1324 /// fn key1(&self) -> Self::K1<'_> {
1325 /// self.id
1326 /// }
1327 /// fn key2(&self) -> Self::K2<'_> {
1328 /// &self.email
1329 /// }
1330 /// fn key3(&self) -> Self::K3<'_> {
1331 /// &self.phone
1332 /// }
1333 /// tri_upcast!();
1334 /// }
1335 ///
1336 /// let mut map = TriHashMap::new();
1337 /// map.insert_unique(Person {
1338 /// id: 1,
1339 /// email: "alice@example.com".to_string(),
1340 /// phone: "555-1234".to_string(),
1341 /// name: "Alice".to_string(),
1342 /// })
1343 /// .unwrap();
1344 ///
1345 /// for mut person in map.iter_mut() {
1346 /// person.name.push_str(" Updated");
1347 /// }
1348 ///
1349 /// let person = map.get1(&1).unwrap();
1350 /// assert_eq!(person.name, "Alice Updated");
1351 /// # }
1352 /// ```
1353 ///
1354 /// [`HashMap`]: std::collections::HashMap
1355 #[inline]
1356 pub fn iter_mut(&mut self) -> IterMut<'_, T, S, A> {
1357 IterMut::new(&self.tables, &mut self.items)
1358 }
1359
1360 /// Checks general invariants of the map.
1361 ///
1362 /// The code below always upholds these invariants, but it's useful to have
1363 /// an explicit check for tests.
1364 #[doc(hidden)]
1365 pub fn validate(
1366 &self,
1367 compactness: crate::internal::ValidateCompact,
1368 ) -> Result<(), ValidationError>
1369 where
1370 T: fmt::Debug,
1371 {
1372 self.validate_structural(compactness)?;
1373
1374 // Check that the indexes are all correct.
1375 //
1376 // Unlike the structural checks, this re-looks up each key through the
1377 // user `Hash`, so it only holds when that `Hash` is lawful.
1378 for (ix, item) in self.items.iter() {
1379 let key1 = item.key1();
1380 let key2 = item.key2();
1381 let key3 = item.key3();
1382
1383 let Some(ix1) = self.find1_index(&key1) else {
1384 return Err(ValidationError::general(format!(
1385 "item at index {ix} has no key1 index"
1386 )));
1387 };
1388 let Some(ix2) = self.find2_index(&key2) else {
1389 return Err(ValidationError::general(format!(
1390 "item at index {ix} has no key2 index"
1391 )));
1392 };
1393 let Some(ix3) = self.find3_index(&key3) else {
1394 return Err(ValidationError::general(format!(
1395 "item at index {ix} has no key3 index"
1396 )));
1397 };
1398
1399 if ix1 != ix || ix2 != ix || ix3 != ix {
1400 return Err(ValidationError::general(format!(
1401 "item at index {ix} has inconsistent indexes: {ix1}/{ix2}/{ix3}"
1402 )));
1403 }
1404 }
1405
1406 Ok(())
1407 }
1408
1409 /// Checks the structural invariants of the map:
1410 ///
1411 /// * The item set is well-formed.
1412 /// * Each per-key hash table holds exactly one entry per live item, with no
1413 /// duplicate `ItemIndex`es.
1414 ///
1415 /// Unlike [`validate`](Self::validate), this does not re-look-up keys
1416 /// through the user `Hash`, so it holds regardless of whether that `Hash`
1417 /// is lawful. A buggy hasher can desync the logical key→item mapping, but
1418 /// it must never break these structural invariants! Doing so would be
1419 /// unsoundness, e.g. duplicate indexes enabling mutable aliasing.
1420 #[doc(hidden)]
1421 pub fn validate_structural(
1422 &self,
1423 compactness: crate::internal::ValidateCompact,
1424 ) -> Result<(), ValidationError> {
1425 self.items.validate(compactness)?;
1426 self.tables.validate(self.len(), compactness)?;
1427 Ok(())
1428 }
1429
1430 /// Inserts a value into the map, removing any conflicting items and
1431 /// returning a list of those items.
1432 ///
1433 /// # Examples
1434 ///
1435 /// ```
1436 /// # #[cfg(feature = "default-hasher")] {
1437 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1438 ///
1439 /// #[derive(Debug, PartialEq, Eq)]
1440 /// struct Person {
1441 /// id: u32,
1442 /// email: String,
1443 /// phone: String,
1444 /// name: String,
1445 /// }
1446 ///
1447 /// impl TriHashItem for Person {
1448 /// type K1<'a> = u32;
1449 /// type K2<'a> = &'a str;
1450 /// type K3<'a> = &'a str;
1451 ///
1452 /// fn key1(&self) -> Self::K1<'_> {
1453 /// self.id
1454 /// }
1455 /// fn key2(&self) -> Self::K2<'_> {
1456 /// &self.email
1457 /// }
1458 /// fn key3(&self) -> Self::K3<'_> {
1459 /// &self.phone
1460 /// }
1461 /// tri_upcast!();
1462 /// }
1463 ///
1464 /// let mut map = TriHashMap::new();
1465 ///
1466 /// // First insertion - no conflicts
1467 /// let overwritten = map.insert_overwrite(Person {
1468 /// id: 1,
1469 /// email: "alice@example.com".to_string(),
1470 /// phone: "555-1234".to_string(),
1471 /// name: "Alice".to_string(),
1472 /// });
1473 /// assert!(overwritten.is_empty());
1474 ///
1475 /// // Overwrite with same id - returns the old item
1476 /// let overwritten = map.insert_overwrite(Person {
1477 /// id: 1,
1478 /// email: "alice.new@example.com".to_string(),
1479 /// phone: "555-9999".to_string(),
1480 /// name: "Alice New".to_string(),
1481 /// });
1482 /// assert_eq!(overwritten.len(), 1);
1483 /// assert_eq!(overwritten[0].name, "Alice");
1484 /// # }
1485 /// ```
1486 #[doc(alias = "insert")]
1487 pub fn insert_overwrite(&mut self, value: T) -> Vec<T> {
1488 let prepared = self.prepare_insert_overwrite(&value);
1489
1490 let mut duplicates = Vec::with_capacity(prepared.duplicate_count());
1491
1492 self.try_reserve_insert_overwrite_commit(
1493 prepared.needs_new_item_slot(),
1494 )
1495 .expect("reserved space successfully");
1496
1497 self.commit_insert_overwrite(value, prepared, &mut duplicates);
1498
1499 duplicates
1500 }
1501
1502 /// Inserts a value into the set, returning an error if any duplicates were
1503 /// added.
1504 ///
1505 /// # Examples
1506 ///
1507 /// ```
1508 /// # #[cfg(feature = "default-hasher")] {
1509 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1510 ///
1511 /// #[derive(Debug, PartialEq, Eq)]
1512 /// struct Person {
1513 /// id: u32,
1514 /// email: String,
1515 /// phone: String,
1516 /// name: String,
1517 /// }
1518 ///
1519 /// impl TriHashItem for Person {
1520 /// type K1<'a> = u32;
1521 /// type K2<'a> = &'a str;
1522 /// type K3<'a> = &'a str;
1523 ///
1524 /// fn key1(&self) -> Self::K1<'_> {
1525 /// self.id
1526 /// }
1527 /// fn key2(&self) -> Self::K2<'_> {
1528 /// &self.email
1529 /// }
1530 /// fn key3(&self) -> Self::K3<'_> {
1531 /// &self.phone
1532 /// }
1533 /// tri_upcast!();
1534 /// }
1535 ///
1536 /// let mut map = TriHashMap::new();
1537 ///
1538 /// // Successful insertion
1539 /// assert!(
1540 /// map.insert_unique(Person {
1541 /// id: 1,
1542 /// email: "alice@example.com".to_string(),
1543 /// phone: "555-1234".to_string(),
1544 /// name: "Alice".to_string(),
1545 /// })
1546 /// .is_ok()
1547 /// );
1548 /// assert!(
1549 /// map.insert_unique(Person {
1550 /// id: 2,
1551 /// email: "bob@example.com".to_string(),
1552 /// phone: "555-5678".to_string(),
1553 /// name: "Bob".to_string(),
1554 /// })
1555 /// .is_ok()
1556 /// );
1557 ///
1558 /// // Duplicate key1
1559 /// assert!(
1560 /// map.insert_unique(Person {
1561 /// id: 1,
1562 /// email: "charlie@example.com".to_string(),
1563 /// phone: "555-9999".to_string(),
1564 /// name: "Charlie".to_string(),
1565 /// })
1566 /// .is_err()
1567 /// );
1568 ///
1569 /// // Duplicate key2
1570 /// assert!(
1571 /// map.insert_unique(Person {
1572 /// id: 3,
1573 /// email: "alice@example.com".to_string(),
1574 /// phone: "555-7777".to_string(),
1575 /// name: "Alice2".to_string(),
1576 /// })
1577 /// .is_err()
1578 /// );
1579 ///
1580 /// // Duplicate key3
1581 /// assert!(
1582 /// map.insert_unique(Person {
1583 /// id: 4,
1584 /// email: "dave@example.com".to_string(),
1585 /// phone: "555-1234".to_string(),
1586 /// name: "Dave".to_string(),
1587 /// })
1588 /// .is_err()
1589 /// );
1590 /// # }
1591 /// ```
1592 pub fn insert_unique(
1593 &mut self,
1594 value: T,
1595 ) -> Result<(), DuplicateItem<T, &T>> {
1596 match self.insert_unique_or_dup_indexes(value) {
1597 Ok(_) => Ok(()),
1598 Err((value, duplicates)) => Err(DuplicateItem::__internal_new(
1599 value,
1600 duplicates.iter().map(|ix| &self.items[*ix]).collect(),
1601 )),
1602 }
1603 }
1604
1605 fn insert_unique_or_dup_indexes(
1606 &mut self,
1607 value: T,
1608 ) -> Result<ItemIndex, (T, BTreeSet<ItemIndex>)> {
1609 let mut duplicates = BTreeSet::new();
1610
1611 // Check for duplicates *before* inserting the new item, because we
1612 // don't want to partially insert the new item and then have to roll
1613 // back.
1614 let state = &self.tables.state;
1615 let (e1, e2, e3) = {
1616 let k1 = value.key1();
1617 let k2 = value.key2();
1618 let k3 = value.key3();
1619
1620 let e1 = detect_dup_or_insert(
1621 self.tables
1622 .k1_to_item
1623 .entry(state, k1, |index| self.items[index].key1()),
1624 &mut duplicates,
1625 );
1626 let e2 = detect_dup_or_insert(
1627 self.tables
1628 .k2_to_item
1629 .entry(state, k2, |index| self.items[index].key2()),
1630 &mut duplicates,
1631 );
1632 let e3 = detect_dup_or_insert(
1633 self.tables
1634 .k3_to_item
1635 .entry(state, k3, |index| self.items[index].key3()),
1636 &mut duplicates,
1637 );
1638 (e1, e2, e3)
1639 };
1640
1641 if !duplicates.is_empty() {
1642 return Err((value, duplicates));
1643 }
1644
1645 let next_index = self.items.assert_can_grow().insert(value);
1646 // e1, e2 and e3 are all Some because if they were None, duplicates
1647 // would be non-empty, and we'd have bailed out earlier.
1648 e1.unwrap().insert(next_index);
1649 e2.unwrap().insert(next_index);
1650 e3.unwrap().insert(next_index);
1651
1652 Ok(next_index)
1653 }
1654
1655 /// Returns true if the map contains a single item that matches all three
1656 /// keys.
1657 ///
1658 /// # Examples
1659 ///
1660 /// ```
1661 /// # #[cfg(feature = "default-hasher")] {
1662 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1663 ///
1664 /// #[derive(Debug, PartialEq, Eq)]
1665 /// struct Person {
1666 /// id: u32,
1667 /// email: String,
1668 /// phone: String,
1669 /// name: String,
1670 /// }
1671 ///
1672 /// impl TriHashItem for Person {
1673 /// type K1<'a> = u32;
1674 /// type K2<'a> = &'a str;
1675 /// type K3<'a> = &'a str;
1676 ///
1677 /// fn key1(&self) -> Self::K1<'_> {
1678 /// self.id
1679 /// }
1680 /// fn key2(&self) -> Self::K2<'_> {
1681 /// &self.email
1682 /// }
1683 /// fn key3(&self) -> Self::K3<'_> {
1684 /// &self.phone
1685 /// }
1686 /// tri_upcast!();
1687 /// }
1688 ///
1689 /// let mut map = TriHashMap::new();
1690 /// map.insert_unique(Person {
1691 /// id: 1,
1692 /// email: "alice@example.com".to_string(),
1693 /// phone: "555-1234".to_string(),
1694 /// name: "Alice".to_string(),
1695 /// }).unwrap();
1696 /// map.insert_unique(Person {
1697 /// id: 2,
1698 /// email: "bob@example.com".to_string(),
1699 /// phone: "555-5678".to_string(),
1700 /// name: "Bob".to_string(),
1701 /// }).unwrap();
1702 ///
1703 /// assert!(map.contains_key_unique(&1, &"alice@example.com", &"555-1234"));
1704 /// assert!(map.contains_key_unique(&2, &"bob@example.com", &"555-5678"));
1705 /// assert!(!map.contains_key_unique(&1, &"bob@example.com", &"555-1234")); // key1 exists but key2 doesn't match
1706 /// assert!(!map.contains_key_unique(&3, &"charlie@example.com", &"555-9999")); // none of the keys exist
1707 /// # }
1708 /// ```
1709 pub fn contains_key_unique<'a, Q1, Q2, Q3>(
1710 &'a self,
1711 key1: &Q1,
1712 key2: &Q2,
1713 key3: &Q3,
1714 ) -> bool
1715 where
1716 Q1: Hash + Equivalent<T::K1<'a>> + ?Sized,
1717 Q2: Hash + Equivalent<T::K2<'a>> + ?Sized,
1718 Q3: Hash + Equivalent<T::K3<'a>> + ?Sized,
1719 {
1720 self.get_unique(key1, key2, key3).is_some()
1721 }
1722
1723 /// Gets a reference to the unique item associated with the given `key1`,
1724 /// `key2`, and `key3`, if it exists.
1725 ///
1726 /// # Examples
1727 ///
1728 /// ```
1729 /// # #[cfg(feature = "default-hasher")] {
1730 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1731 ///
1732 /// #[derive(Debug, PartialEq, Eq)]
1733 /// struct Person {
1734 /// id: u32,
1735 /// email: String,
1736 /// phone: String,
1737 /// name: String,
1738 /// }
1739 ///
1740 /// impl TriHashItem for Person {
1741 /// type K1<'a> = u32;
1742 /// type K2<'a> = &'a str;
1743 /// type K3<'a> = &'a str;
1744 ///
1745 /// fn key1(&self) -> Self::K1<'_> {
1746 /// self.id
1747 /// }
1748 /// fn key2(&self) -> Self::K2<'_> {
1749 /// &self.email
1750 /// }
1751 /// fn key3(&self) -> Self::K3<'_> {
1752 /// &self.phone
1753 /// }
1754 /// tri_upcast!();
1755 /// }
1756 ///
1757 /// let mut map = TriHashMap::new();
1758 /// map.insert_unique(Person {
1759 /// id: 1,
1760 /// email: "alice@example.com".to_string(),
1761 /// phone: "555-1234".to_string(),
1762 /// name: "Alice".to_string(),
1763 /// })
1764 /// .unwrap();
1765 ///
1766 /// // All three keys must match
1767 /// assert_eq!(
1768 /// map.get_unique(&1, &"alice@example.com", &"555-1234").unwrap().name,
1769 /// "Alice"
1770 /// );
1771 ///
1772 /// // If any key doesn't match, returns None
1773 /// assert!(map.get_unique(&1, &"wrong@example.com", &"555-1234").is_none());
1774 /// assert!(map.get_unique(&2, &"alice@example.com", &"555-1234").is_none());
1775 /// # }
1776 /// ```
1777 pub fn get_unique<'a, Q1, Q2, Q3>(
1778 &'a self,
1779 key1: &Q1,
1780 key2: &Q2,
1781 key3: &Q3,
1782 ) -> Option<&'a T>
1783 where
1784 Q1: Hash + Equivalent<T::K1<'a>> + ?Sized,
1785 Q2: Hash + Equivalent<T::K2<'a>> + ?Sized,
1786 Q3: Hash + Equivalent<T::K3<'a>> + ?Sized,
1787 {
1788 let index = self.find1_index(key1)?;
1789 let item = &self.items[index];
1790 if key2.equivalent(&item.key2()) && key3.equivalent(&item.key3()) {
1791 Some(item)
1792 } else {
1793 None
1794 }
1795 }
1796
1797 /// Gets a mutable reference to the unique item associated with the given
1798 /// `key1`, `key2`, and `key3`, if it exists.
1799 ///
1800 /// # Examples
1801 ///
1802 /// ```
1803 /// # #[cfg(feature = "default-hasher")] {
1804 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1805 ///
1806 /// #[derive(Debug, PartialEq, Eq)]
1807 /// struct Person {
1808 /// id: u32,
1809 /// email: String,
1810 /// phone: String,
1811 /// name: String,
1812 /// }
1813 ///
1814 /// impl TriHashItem for Person {
1815 /// type K1<'a> = u32;
1816 /// type K2<'a> = &'a str;
1817 /// type K3<'a> = &'a str;
1818 ///
1819 /// fn key1(&self) -> Self::K1<'_> {
1820 /// self.id
1821 /// }
1822 /// fn key2(&self) -> Self::K2<'_> {
1823 /// &self.email
1824 /// }
1825 /// fn key3(&self) -> Self::K3<'_> {
1826 /// &self.phone
1827 /// }
1828 /// tri_upcast!();
1829 /// }
1830 ///
1831 /// let mut map = TriHashMap::new();
1832 /// map.insert_unique(Person {
1833 /// id: 1,
1834 /// email: "alice@example.com".to_string(),
1835 /// phone: "555-1234".to_string(),
1836 /// name: "Alice".to_string(),
1837 /// })
1838 /// .unwrap();
1839 ///
1840 /// // Modify the item through the mutable reference
1841 /// if let Some(mut person) =
1842 /// map.get_mut_unique(&1, &"alice@example.com", &"555-1234")
1843 /// {
1844 /// person.name = "Alice Updated".to_string();
1845 /// }
1846 ///
1847 /// // Verify the change
1848 /// assert_eq!(map.get1(&1).unwrap().name, "Alice Updated");
1849 /// # }
1850 /// ```
1851 pub fn get_mut_unique<'a, Q1, Q2, Q3>(
1852 &'a mut self,
1853 key1: &Q1,
1854 key2: &Q2,
1855 key3: &Q3,
1856 ) -> Option<RefMut<'a, T, S>>
1857 where
1858 Q1: Hash + Equivalent<T::K1<'a>> + ?Sized,
1859 Q2: Hash + Equivalent<T::K2<'a>> + ?Sized,
1860 Q3: Hash + Equivalent<T::K3<'a>> + ?Sized,
1861 {
1862 let (dormant_map, index) = {
1863 let (map, dormant_map) = DormantMutRef::new(self);
1864 let index = map.find1_index(key1)?;
1865 let item = &map.items[index];
1866 if !key2.equivalent(&item.key2()) || !key3.equivalent(&item.key3())
1867 {
1868 return None;
1869 }
1870 (dormant_map, index)
1871 };
1872
1873 // SAFETY: `map` is not used after this point.
1874 let awakened_map = unsafe { dormant_map.awaken() };
1875 let item = &mut awakened_map.items[index];
1876 let state = awakened_map.tables.state.clone();
1877 let hashes = awakened_map.tables.make_hashes(&item);
1878 Some(RefMut::new(state, hashes, item))
1879 }
1880
1881 /// Removes the item uniquely identified by `key1`, `key2`, and `key3`, if
1882 /// it exists.
1883 ///
1884 /// # Examples
1885 ///
1886 /// ```
1887 /// # #[cfg(feature = "default-hasher")] {
1888 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1889 ///
1890 /// #[derive(Debug, PartialEq, Eq)]
1891 /// struct Person {
1892 /// id: u32,
1893 /// email: String,
1894 /// phone: String,
1895 /// name: String,
1896 /// }
1897 ///
1898 /// impl TriHashItem for Person {
1899 /// type K1<'a> = u32;
1900 /// type K2<'a> = &'a str;
1901 /// type K3<'a> = &'a str;
1902 ///
1903 /// fn key1(&self) -> Self::K1<'_> {
1904 /// self.id
1905 /// }
1906 /// fn key2(&self) -> Self::K2<'_> {
1907 /// &self.email
1908 /// }
1909 /// fn key3(&self) -> Self::K3<'_> {
1910 /// &self.phone
1911 /// }
1912 /// tri_upcast!();
1913 /// }
1914 ///
1915 /// let mut map = TriHashMap::new();
1916 /// map.insert_unique(Person {
1917 /// id: 1,
1918 /// email: "alice@example.com".to_string(),
1919 /// phone: "555-1234".to_string(),
1920 /// name: "Alice".to_string(),
1921 /// })
1922 /// .unwrap();
1923 ///
1924 /// // Remove the item using all three keys
1925 /// let removed = map.remove_unique(&1, &"alice@example.com", &"555-1234");
1926 /// assert!(removed.is_some());
1927 /// assert_eq!(removed.unwrap().name, "Alice");
1928 ///
1929 /// // Map is now empty
1930 /// assert!(map.is_empty());
1931 ///
1932 /// // Trying to remove again returns None
1933 /// assert!(map.remove_unique(&1, &"alice@example.com", &"555-1234").is_none());
1934 /// # }
1935 /// ```
1936 pub fn remove_unique<'a, Q1, Q2, Q3>(
1937 &'a mut self,
1938 key1: &Q1,
1939 key2: &Q2,
1940 key3: &Q3,
1941 ) -> Option<T>
1942 where
1943 Q1: Hash + Equivalent<T::K1<'a>> + ?Sized,
1944 Q2: Hash + Equivalent<T::K2<'a>> + ?Sized,
1945 Q3: Hash + Equivalent<T::K3<'a>> + ?Sized,
1946 {
1947 let (dormant_map, remove_index) = {
1948 let (map, dormant_map) = DormantMutRef::new(self);
1949 let remove_index = map.find1_index(key1)?;
1950 let item = &map.items[remove_index];
1951 if !key2.equivalent(&item.key2()) || !key3.equivalent(&item.key3())
1952 {
1953 return None;
1954 }
1955 (dormant_map, remove_index)
1956 };
1957
1958 // SAFETY: `map` is not used after this point.
1959 let awakened_map = unsafe { dormant_map.awaken() };
1960
1961 awakened_map.remove_by_index(remove_index)
1962 }
1963
1964 /// Returns true if the map contains the given `key1`.
1965 ///
1966 /// # Examples
1967 ///
1968 /// ```
1969 /// # #[cfg(feature = "default-hasher")] {
1970 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
1971 ///
1972 /// #[derive(Debug, PartialEq, Eq)]
1973 /// struct Person {
1974 /// id: u32,
1975 /// email: String,
1976 /// phone: String,
1977 /// name: String,
1978 /// }
1979 ///
1980 /// impl TriHashItem for Person {
1981 /// type K1<'a> = u32;
1982 /// type K2<'a> = &'a str;
1983 /// type K3<'a> = &'a str;
1984 ///
1985 /// fn key1(&self) -> Self::K1<'_> {
1986 /// self.id
1987 /// }
1988 /// fn key2(&self) -> Self::K2<'_> {
1989 /// &self.email
1990 /// }
1991 /// fn key3(&self) -> Self::K3<'_> {
1992 /// &self.phone
1993 /// }
1994 /// tri_upcast!();
1995 /// }
1996 ///
1997 /// let mut map = TriHashMap::new();
1998 /// map.insert_unique(Person {
1999 /// id: 1,
2000 /// email: "alice@example.com".to_string(),
2001 /// phone: "555-1234".to_string(),
2002 /// name: "Alice".to_string(),
2003 /// })
2004 /// .unwrap();
2005 ///
2006 /// assert!(map.contains_key1(&1));
2007 /// assert!(!map.contains_key1(&2));
2008 /// # }
2009 /// ```
2010 pub fn contains_key1<'a, Q>(&'a self, key1: &Q) -> bool
2011 where
2012 Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
2013 {
2014 self.find1_index(key1).is_some()
2015 }
2016
2017 /// Gets a reference to the value associated with the given `key1`.
2018 ///
2019 /// # Examples
2020 ///
2021 /// ```
2022 /// # #[cfg(feature = "default-hasher")] {
2023 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2024 ///
2025 /// #[derive(Debug, PartialEq, Eq)]
2026 /// struct Person {
2027 /// id: u32,
2028 /// email: String,
2029 /// phone: String,
2030 /// name: String,
2031 /// }
2032 ///
2033 /// impl TriHashItem for Person {
2034 /// type K1<'a> = u32;
2035 /// type K2<'a> = &'a str;
2036 /// type K3<'a> = &'a str;
2037 ///
2038 /// fn key1(&self) -> Self::K1<'_> {
2039 /// self.id
2040 /// }
2041 /// fn key2(&self) -> Self::K2<'_> {
2042 /// &self.email
2043 /// }
2044 /// fn key3(&self) -> Self::K3<'_> {
2045 /// &self.phone
2046 /// }
2047 /// tri_upcast!();
2048 /// }
2049 ///
2050 /// let mut map = TriHashMap::new();
2051 /// map.insert_unique(Person {
2052 /// id: 1,
2053 /// email: "alice@example.com".to_string(),
2054 /// phone: "555-1234".to_string(),
2055 /// name: "Alice".to_string(),
2056 /// })
2057 /// .unwrap();
2058 ///
2059 /// assert_eq!(map.get1(&1).unwrap().name, "Alice");
2060 /// assert!(map.get1(&2).is_none());
2061 /// # }
2062 /// ```
2063 pub fn get1<'a, Q>(&'a self, key1: &Q) -> Option<&'a T>
2064 where
2065 Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
2066 {
2067 self.find1(key1)
2068 }
2069
2070 /// Gets a mutable reference to the value associated with the given `key1`.
2071 ///
2072 /// # Examples
2073 ///
2074 /// ```
2075 /// # #[cfg(feature = "default-hasher")] {
2076 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2077 ///
2078 /// #[derive(Debug, PartialEq, Eq)]
2079 /// struct Person {
2080 /// id: u32,
2081 /// email: String,
2082 /// phone: String,
2083 /// name: String,
2084 /// }
2085 ///
2086 /// impl TriHashItem for Person {
2087 /// type K1<'a> = u32;
2088 /// type K2<'a> = &'a str;
2089 /// type K3<'a> = &'a str;
2090 ///
2091 /// fn key1(&self) -> Self::K1<'_> {
2092 /// self.id
2093 /// }
2094 /// fn key2(&self) -> Self::K2<'_> {
2095 /// &self.email
2096 /// }
2097 /// fn key3(&self) -> Self::K3<'_> {
2098 /// &self.phone
2099 /// }
2100 /// tri_upcast!();
2101 /// }
2102 ///
2103 /// let mut map = TriHashMap::new();
2104 /// map.insert_unique(Person {
2105 /// id: 1,
2106 /// email: "alice@example.com".to_string(),
2107 /// phone: "555-1234".to_string(),
2108 /// name: "Alice".to_string(),
2109 /// })
2110 /// .unwrap();
2111 ///
2112 /// if let Some(mut person) = map.get1_mut(&1) {
2113 /// person.name = "Alice Updated".to_string();
2114 /// }
2115 ///
2116 /// assert_eq!(map.get1(&1).unwrap().name, "Alice Updated");
2117 /// # }
2118 /// ```
2119 pub fn get1_mut<'a, Q>(&'a mut self, key1: &Q) -> Option<RefMut<'a, T, S>>
2120 where
2121 Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
2122 {
2123 let (dormant_map, index) = {
2124 let (map, dormant_map) = DormantMutRef::new(self);
2125 let index = map.find1_index(key1)?;
2126 (dormant_map, index)
2127 };
2128
2129 // SAFETY: `map` is not used after this point.
2130 let awakened_map = unsafe { dormant_map.awaken() };
2131 let item = &mut awakened_map.items[index];
2132 let state = awakened_map.tables.state.clone();
2133 let hashes = awakened_map.tables.make_hashes(&item);
2134 Some(RefMut::new(state, hashes, item))
2135 }
2136
2137 /// Removes an item from the map by its `key1`.
2138 ///
2139 /// # Examples
2140 ///
2141 /// ```
2142 /// # #[cfg(feature = "default-hasher")] {
2143 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2144 ///
2145 /// #[derive(Debug, PartialEq, Eq)]
2146 /// struct Person {
2147 /// id: u32,
2148 /// email: String,
2149 /// phone: String,
2150 /// name: String,
2151 /// }
2152 ///
2153 /// impl TriHashItem for Person {
2154 /// type K1<'a> = u32;
2155 /// type K2<'a> = &'a str;
2156 /// type K3<'a> = &'a str;
2157 ///
2158 /// fn key1(&self) -> Self::K1<'_> {
2159 /// self.id
2160 /// }
2161 /// fn key2(&self) -> Self::K2<'_> {
2162 /// &self.email
2163 /// }
2164 /// fn key3(&self) -> Self::K3<'_> {
2165 /// &self.phone
2166 /// }
2167 /// tri_upcast!();
2168 /// }
2169 ///
2170 /// let mut map = TriHashMap::new();
2171 /// map.insert_unique(Person {
2172 /// id: 1,
2173 /// email: "alice@example.com".to_string(),
2174 /// phone: "555-1234".to_string(),
2175 /// name: "Alice".to_string(),
2176 /// })
2177 /// .unwrap();
2178 ///
2179 /// let removed = map.remove1(&1);
2180 /// assert!(removed.is_some());
2181 /// assert_eq!(removed.unwrap().name, "Alice");
2182 /// assert!(map.is_empty());
2183 /// # }
2184 /// ```
2185 pub fn remove1<'a, Q>(&'a mut self, key1: &Q) -> Option<T>
2186 where
2187 Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
2188 {
2189 let (dormant_map, remove_index) = {
2190 let (map, dormant_map) = DormantMutRef::new(self);
2191 let remove_index = map.find1_index(key1)?;
2192 (dormant_map, remove_index)
2193 };
2194
2195 // SAFETY: `map` is not used after this point.
2196 let awakened_map = unsafe { dormant_map.awaken() };
2197
2198 awakened_map.remove_by_index(remove_index)
2199 }
2200
2201 /// Returns true if the map contains the given `key2`.
2202 ///
2203 /// # Examples
2204 ///
2205 /// ```
2206 /// # #[cfg(feature = "default-hasher")] {
2207 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2208 ///
2209 /// #[derive(Debug, PartialEq, Eq)]
2210 /// struct Person {
2211 /// id: u32,
2212 /// email: String,
2213 /// phone: String,
2214 /// name: String,
2215 /// }
2216 ///
2217 /// impl TriHashItem for Person {
2218 /// type K1<'a> = u32;
2219 /// type K2<'a> = &'a str;
2220 /// type K3<'a> = &'a str;
2221 ///
2222 /// fn key1(&self) -> Self::K1<'_> {
2223 /// self.id
2224 /// }
2225 /// fn key2(&self) -> Self::K2<'_> {
2226 /// &self.email
2227 /// }
2228 /// fn key3(&self) -> Self::K3<'_> {
2229 /// &self.phone
2230 /// }
2231 /// tri_upcast!();
2232 /// }
2233 ///
2234 /// let mut map = TriHashMap::new();
2235 /// map.insert_unique(Person {
2236 /// id: 1,
2237 /// email: "alice@example.com".to_string(),
2238 /// phone: "555-1234".to_string(),
2239 /// name: "Alice".to_string(),
2240 /// })
2241 /// .unwrap();
2242 ///
2243 /// assert!(map.contains_key2("alice@example.com"));
2244 /// assert!(!map.contains_key2("bob@example.com"));
2245 /// # }
2246 /// ```
2247 pub fn contains_key2<'a, Q>(&'a self, key2: &Q) -> bool
2248 where
2249 Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
2250 {
2251 self.find2_index(key2).is_some()
2252 }
2253
2254 /// Gets a reference to the value associated with the given `key2`.
2255 ///
2256 /// # Examples
2257 ///
2258 /// ```
2259 /// # #[cfg(feature = "default-hasher")] {
2260 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2261 ///
2262 /// #[derive(Debug, PartialEq, Eq)]
2263 /// struct Person {
2264 /// id: u32,
2265 /// email: String,
2266 /// phone: String,
2267 /// name: String,
2268 /// }
2269 ///
2270 /// impl TriHashItem for Person {
2271 /// type K1<'a> = u32;
2272 /// type K2<'a> = &'a str;
2273 /// type K3<'a> = &'a str;
2274 ///
2275 /// fn key1(&self) -> Self::K1<'_> {
2276 /// self.id
2277 /// }
2278 /// fn key2(&self) -> Self::K2<'_> {
2279 /// &self.email
2280 /// }
2281 /// fn key3(&self) -> Self::K3<'_> {
2282 /// &self.phone
2283 /// }
2284 /// tri_upcast!();
2285 /// }
2286 ///
2287 /// let mut map = TriHashMap::new();
2288 /// map.insert_unique(Person {
2289 /// id: 1,
2290 /// email: "alice@example.com".to_string(),
2291 /// phone: "555-1234".to_string(),
2292 /// name: "Alice".to_string(),
2293 /// })
2294 /// .unwrap();
2295 ///
2296 /// assert_eq!(map.get2("alice@example.com").unwrap().name, "Alice");
2297 /// assert!(map.get2("bob@example.com").is_none());
2298 /// # }
2299 /// ```
2300 pub fn get2<'a, Q>(&'a self, key2: &Q) -> Option<&'a T>
2301 where
2302 Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
2303 {
2304 self.find2(key2)
2305 }
2306
2307 /// Gets a mutable reference to the value associated with the given `key2`.
2308 ///
2309 /// # Examples
2310 ///
2311 /// ```
2312 /// # #[cfg(feature = "default-hasher")] {
2313 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2314 ///
2315 /// #[derive(Debug, PartialEq, Eq)]
2316 /// struct Person {
2317 /// id: u32,
2318 /// email: String,
2319 /// phone: String,
2320 /// name: String,
2321 /// }
2322 ///
2323 /// impl TriHashItem for Person {
2324 /// type K1<'a> = u32;
2325 /// type K2<'a> = &'a str;
2326 /// type K3<'a> = &'a str;
2327 ///
2328 /// fn key1(&self) -> Self::K1<'_> {
2329 /// self.id
2330 /// }
2331 /// fn key2(&self) -> Self::K2<'_> {
2332 /// &self.email
2333 /// }
2334 /// fn key3(&self) -> Self::K3<'_> {
2335 /// &self.phone
2336 /// }
2337 /// tri_upcast!();
2338 /// }
2339 ///
2340 /// let mut map = TriHashMap::new();
2341 /// map.insert_unique(Person {
2342 /// id: 1,
2343 /// email: "alice@example.com".to_string(),
2344 /// phone: "555-1234".to_string(),
2345 /// name: "Alice".to_string(),
2346 /// })
2347 /// .unwrap();
2348 ///
2349 /// if let Some(mut person) = map.get2_mut("alice@example.com") {
2350 /// person.name = "Alice Updated".to_string();
2351 /// }
2352 ///
2353 /// assert_eq!(map.get2("alice@example.com").unwrap().name, "Alice Updated");
2354 /// # }
2355 /// ```
2356 pub fn get2_mut<'a, Q>(&'a mut self, key2: &Q) -> Option<RefMut<'a, T, S>>
2357 where
2358 Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
2359 {
2360 let (dormant_map, index) = {
2361 let (map, dormant_map) = DormantMutRef::new(self);
2362 let index = map.find2_index(key2)?;
2363 (dormant_map, index)
2364 };
2365
2366 // SAFETY: `map` is not used after this point.
2367 let awakened_map = unsafe { dormant_map.awaken() };
2368 let item = &mut awakened_map.items[index];
2369 let state = awakened_map.tables.state.clone();
2370 let hashes = awakened_map.tables.make_hashes(&item);
2371 Some(RefMut::new(state, hashes, item))
2372 }
2373
2374 /// Removes an item from the map by its `key2`.
2375 ///
2376 /// # Examples
2377 ///
2378 /// ```
2379 /// # #[cfg(feature = "default-hasher")] {
2380 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2381 ///
2382 /// #[derive(Debug, PartialEq, Eq)]
2383 /// struct Person {
2384 /// id: u32,
2385 /// email: String,
2386 /// phone: String,
2387 /// name: String,
2388 /// }
2389 ///
2390 /// impl TriHashItem for Person {
2391 /// type K1<'a> = u32;
2392 /// type K2<'a> = &'a str;
2393 /// type K3<'a> = &'a str;
2394 ///
2395 /// fn key1(&self) -> Self::K1<'_> {
2396 /// self.id
2397 /// }
2398 /// fn key2(&self) -> Self::K2<'_> {
2399 /// &self.email
2400 /// }
2401 /// fn key3(&self) -> Self::K3<'_> {
2402 /// &self.phone
2403 /// }
2404 /// tri_upcast!();
2405 /// }
2406 ///
2407 /// let mut map = TriHashMap::new();
2408 /// map.insert_unique(Person {
2409 /// id: 1,
2410 /// email: "alice@example.com".to_string(),
2411 /// phone: "555-1234".to_string(),
2412 /// name: "Alice".to_string(),
2413 /// })
2414 /// .unwrap();
2415 ///
2416 /// let removed = map.remove2("alice@example.com");
2417 /// assert!(removed.is_some());
2418 /// assert_eq!(removed.unwrap().name, "Alice");
2419 /// assert!(map.is_empty());
2420 /// # }
2421 /// ```
2422 pub fn remove2<'a, Q>(&'a mut self, key2: &Q) -> Option<T>
2423 where
2424 Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
2425 {
2426 let (dormant_map, remove_index) = {
2427 let (map, dormant_map) = DormantMutRef::new(self);
2428 let remove_index = map.find2_index(key2)?;
2429 (dormant_map, remove_index)
2430 };
2431
2432 // SAFETY: `map` is not used after this point.
2433 let awakened_map = unsafe { dormant_map.awaken() };
2434
2435 awakened_map.remove_by_index(remove_index)
2436 }
2437
2438 /// Returns true if the map contains the given `key3`.
2439 ///
2440 /// # Examples
2441 ///
2442 /// ```
2443 /// # #[cfg(feature = "default-hasher")] {
2444 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2445 ///
2446 /// #[derive(Debug, PartialEq, Eq)]
2447 /// struct Person {
2448 /// id: u32,
2449 /// email: String,
2450 /// phone: String,
2451 /// name: String,
2452 /// }
2453 ///
2454 /// impl TriHashItem for Person {
2455 /// type K1<'a> = u32;
2456 /// type K2<'a> = &'a str;
2457 /// type K3<'a> = &'a str;
2458 ///
2459 /// fn key1(&self) -> Self::K1<'_> {
2460 /// self.id
2461 /// }
2462 /// fn key2(&self) -> Self::K2<'_> {
2463 /// &self.email
2464 /// }
2465 /// fn key3(&self) -> Self::K3<'_> {
2466 /// &self.phone
2467 /// }
2468 /// tri_upcast!();
2469 /// }
2470 ///
2471 /// let mut map = TriHashMap::new();
2472 /// map.insert_unique(Person {
2473 /// id: 1,
2474 /// email: "alice@example.com".to_string(),
2475 /// phone: "555-1234".to_string(),
2476 /// name: "Alice".to_string(),
2477 /// })
2478 /// .unwrap();
2479 ///
2480 /// assert!(map.contains_key3("555-1234"));
2481 /// assert!(!map.contains_key3("555-5678"));
2482 /// # }
2483 /// ```
2484 pub fn contains_key3<'a, Q>(&'a self, key3: &Q) -> bool
2485 where
2486 Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
2487 {
2488 self.find3_index(key3).is_some()
2489 }
2490
2491 /// Gets a reference to the value associated with the given `key3`.
2492 ///
2493 /// # Examples
2494 ///
2495 /// ```
2496 /// # #[cfg(feature = "default-hasher")] {
2497 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2498 ///
2499 /// #[derive(Debug, PartialEq, Eq)]
2500 /// struct Person {
2501 /// id: u32,
2502 /// email: String,
2503 /// phone: String,
2504 /// name: String,
2505 /// }
2506 ///
2507 /// impl TriHashItem for Person {
2508 /// type K1<'a> = u32;
2509 /// type K2<'a> = &'a str;
2510 /// type K3<'a> = &'a str;
2511 ///
2512 /// fn key1(&self) -> Self::K1<'_> {
2513 /// self.id
2514 /// }
2515 /// fn key2(&self) -> Self::K2<'_> {
2516 /// &self.email
2517 /// }
2518 /// fn key3(&self) -> Self::K3<'_> {
2519 /// &self.phone
2520 /// }
2521 /// tri_upcast!();
2522 /// }
2523 ///
2524 /// let mut map = TriHashMap::new();
2525 /// map.insert_unique(Person {
2526 /// id: 1,
2527 /// email: "alice@example.com".to_string(),
2528 /// phone: "555-1234".to_string(),
2529 /// name: "Alice".to_string(),
2530 /// })
2531 /// .unwrap();
2532 ///
2533 /// assert_eq!(map.get3("555-1234").unwrap().name, "Alice");
2534 /// assert!(map.get3("555-5678").is_none());
2535 /// # }
2536 /// ```
2537 pub fn get3<'a, Q>(&'a self, key3: &Q) -> Option<&'a T>
2538 where
2539 Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
2540 {
2541 self.find3(key3)
2542 }
2543
2544 /// Gets a mutable reference to the value associated with the given `key3`.
2545 ///
2546 /// # Examples
2547 ///
2548 /// ```
2549 /// # #[cfg(feature = "default-hasher")] {
2550 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2551 ///
2552 /// #[derive(Debug, PartialEq, Eq)]
2553 /// struct Person {
2554 /// id: u32,
2555 /// email: String,
2556 /// phone: String,
2557 /// name: String,
2558 /// }
2559 ///
2560 /// impl TriHashItem for Person {
2561 /// type K1<'a> = u32;
2562 /// type K2<'a> = &'a str;
2563 /// type K3<'a> = &'a str;
2564 ///
2565 /// fn key1(&self) -> Self::K1<'_> {
2566 /// self.id
2567 /// }
2568 /// fn key2(&self) -> Self::K2<'_> {
2569 /// &self.email
2570 /// }
2571 /// fn key3(&self) -> Self::K3<'_> {
2572 /// &self.phone
2573 /// }
2574 /// tri_upcast!();
2575 /// }
2576 ///
2577 /// let mut map = TriHashMap::new();
2578 /// map.insert_unique(Person {
2579 /// id: 1,
2580 /// email: "alice@example.com".to_string(),
2581 /// phone: "555-1234".to_string(),
2582 /// name: "Alice".to_string(),
2583 /// })
2584 /// .unwrap();
2585 ///
2586 /// if let Some(mut person) = map.get3_mut("555-1234") {
2587 /// person.name = "Alice Updated".to_string();
2588 /// }
2589 ///
2590 /// assert_eq!(map.get3("555-1234").unwrap().name, "Alice Updated");
2591 /// # }
2592 /// ```
2593 pub fn get3_mut<'a, Q>(&'a mut self, key3: &Q) -> Option<RefMut<'a, T, S>>
2594 where
2595 Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
2596 {
2597 let (dormant_map, index) = {
2598 let (map, dormant_map) = DormantMutRef::new(self);
2599 let index = map.find3_index(key3)?;
2600 (dormant_map, index)
2601 };
2602
2603 // SAFETY: `map` is not used after this point.
2604 let awakened_map = unsafe { dormant_map.awaken() };
2605 let item = &mut awakened_map.items[index];
2606 let state = awakened_map.tables.state.clone();
2607 let hashes = awakened_map.tables.make_hashes(&item);
2608 Some(RefMut::new(state, hashes, item))
2609 }
2610
2611 /// Removes an item from the map by its `key3`.
2612 ///
2613 /// # Examples
2614 ///
2615 /// ```
2616 /// # #[cfg(feature = "default-hasher")] {
2617 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2618 ///
2619 /// #[derive(Debug, PartialEq, Eq)]
2620 /// struct Person {
2621 /// id: u32,
2622 /// email: String,
2623 /// phone: String,
2624 /// name: String,
2625 /// }
2626 ///
2627 /// impl TriHashItem for Person {
2628 /// type K1<'a> = u32;
2629 /// type K2<'a> = &'a str;
2630 /// type K3<'a> = &'a str;
2631 ///
2632 /// fn key1(&self) -> Self::K1<'_> {
2633 /// self.id
2634 /// }
2635 /// fn key2(&self) -> Self::K2<'_> {
2636 /// &self.email
2637 /// }
2638 /// fn key3(&self) -> Self::K3<'_> {
2639 /// &self.phone
2640 /// }
2641 /// tri_upcast!();
2642 /// }
2643 ///
2644 /// let mut map = TriHashMap::new();
2645 /// map.insert_unique(Person {
2646 /// id: 1,
2647 /// email: "alice@example.com".to_string(),
2648 /// phone: "555-1234".to_string(),
2649 /// name: "Alice".to_string(),
2650 /// })
2651 /// .unwrap();
2652 ///
2653 /// let removed = map.remove3("555-1234");
2654 /// assert!(removed.is_some());
2655 /// assert_eq!(removed.unwrap().name, "Alice");
2656 /// assert!(map.is_empty());
2657 /// # }
2658 /// ```
2659 pub fn remove3<'a, Q>(&'a mut self, key3: &Q) -> Option<T>
2660 where
2661 Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
2662 {
2663 let (dormant_map, remove_index) = {
2664 let (map, dormant_map) = DormantMutRef::new(self);
2665 let remove_index = map.find3_index(key3)?;
2666 (dormant_map, remove_index)
2667 };
2668
2669 // SAFETY: `map` is not used after this point.
2670 let awakened_map = unsafe { dormant_map.awaken() };
2671
2672 awakened_map.remove_by_index(remove_index)
2673 }
2674
2675 /// Retains only the elements specified by the predicate.
2676 ///
2677 /// In other words, remove all items `T` for which `f(RefMut<T>)` returns
2678 /// false. The elements are visited in an arbitrary order.
2679 ///
2680 /// The `RefMut<T, S>` wrapper allows mutable access to the item while
2681 /// enforcing that the three keys (`K1`, `K2`, `K3`) remain unchanged. If
2682 /// a key is modified during iteration, the method will panic.
2683 ///
2684 /// # Performance considerations
2685 ///
2686 /// This method may leave the internal storage fragmented. If you need
2687 /// compact storage afterward, call `make_compact()`.
2688 ///
2689 /// # Examples
2690 ///
2691 /// ```
2692 /// # #[cfg(feature = "default-hasher")] {
2693 /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
2694 ///
2695 /// #[derive(Debug, PartialEq, Eq, Hash)]
2696 /// struct Item {
2697 /// id: u32,
2698 /// name: String,
2699 /// code: String,
2700 /// value: u32,
2701 /// }
2702 ///
2703 /// impl TriHashItem for Item {
2704 /// type K1<'a> = u32;
2705 /// type K2<'a> = &'a str;
2706 /// type K3<'a> = &'a str;
2707 ///
2708 /// fn key1(&self) -> Self::K1<'_> {
2709 /// self.id
2710 /// }
2711 /// fn key2(&self) -> Self::K2<'_> {
2712 /// &self.name
2713 /// }
2714 /// fn key3(&self) -> Self::K3<'_> {
2715 /// &self.code
2716 /// }
2717 ///
2718 /// tri_upcast!();
2719 /// }
2720 ///
2721 /// let mut map = TriHashMap::new();
2722 /// map.insert_unique(Item {
2723 /// id: 1,
2724 /// name: "foo".to_string(),
2725 /// code: "x".to_string(),
2726 /// value: 42,
2727 /// })
2728 /// .unwrap();
2729 /// map.insert_unique(Item {
2730 /// id: 2,
2731 /// name: "bar".to_string(),
2732 /// code: "y".to_string(),
2733 /// value: 20,
2734 /// })
2735 /// .unwrap();
2736 /// map.insert_unique(Item {
2737 /// id: 3,
2738 /// name: "baz".to_string(),
2739 /// code: "z".to_string(),
2740 /// value: 99,
2741 /// })
2742 /// .unwrap();
2743 ///
2744 /// // Retain only items where value is greater than 30
2745 /// map.retain(|item| item.value > 30);
2746 ///
2747 /// assert_eq!(map.len(), 2);
2748 /// assert_eq!(map.get1(&1).unwrap().value, 42);
2749 /// assert_eq!(map.get1(&3).unwrap().value, 99);
2750 /// assert!(map.get1(&2).is_none());
2751 /// # }
2752 /// ```
2753 pub fn retain<'a, F>(&'a mut self, mut f: F)
2754 where
2755 F: for<'b> FnMut(RefMut<'b, T, S>) -> bool,
2756 {
2757 let hash_state = self.tables.state.clone();
2758 let (_, mut dormant_items) = DormantMutRef::new(&mut self.items);
2759 let mut removed_item = None;
2760
2761 self.tables.k1_to_item.retain(|index| {
2762 // Drop the previously-removed item here, at the top of the next
2763 // iteration.
2764 //
2765 // By now, the prior `k1_to_item` entry has been erased, so if
2766 // `drop` below panics, `k1_to_item`, `k2_to_item`, `k3_to_item`,
2767 // and `items` remain in sync. Dropping the item at the end of the
2768 // prior iteration would unwind before the table erased the entry,
2769 // leaving `k1_to_item` pointing at a slot we already removed from
2770 // `items`, `k2_to_item`, and `k3_to_item`.
2771 drop(removed_item.take());
2772
2773 let (item, dormant_items) = {
2774 // SAFETY: All uses of `items` ended in the previous iteration.
2775 let items = unsafe { dormant_items.reborrow() };
2776 let (items, dormant_items) = DormantMutRef::new(items);
2777 let item: &'a mut T = items
2778 .get_mut(index)
2779 .expect("all indexes are present in self.items");
2780 (item, dormant_items)
2781 };
2782
2783 let (hashes, dormant_item) = {
2784 let (item, dormant_item): (&'a mut T, _) =
2785 DormantMutRef::new(item);
2786 // Use T::k1(item) rather than item.key() to force the key
2787 // trait function to be called for T rather than &mut T.
2788 let key1 = T::key1(item);
2789 let key2 = T::key2(item);
2790 let key3 = T::key3(item);
2791 let hash1 = hash_state.hash_one(key1);
2792 let hash2 = hash_state.hash_one(key2);
2793 let hash3 = hash_state.hash_one(key3);
2794 (
2795 [
2796 MapHash::new(hash1),
2797 MapHash::new(hash2),
2798 MapHash::new(hash3),
2799 ],
2800 dormant_item,
2801 )
2802 };
2803
2804 let hash2 = hashes[1].hash();
2805 let hash3 = hashes[2].hash();
2806 let retain = {
2807 // SAFETY: The original item is no longer used after the second
2808 // block above. dormant_items, from which item is derived, is
2809 // currently dormant.
2810 let item = unsafe { dormant_item.awaken() };
2811
2812 let ref_mut = RefMut::new(hash_state.clone(), hashes, item);
2813 f(ref_mut)
2814 };
2815
2816 if retain {
2817 true
2818 } else {
2819 let k2_entry = self
2820 .tables
2821 .k2_to_item
2822 .find_entry_by_hash(hash2, |map2_index| {
2823 map2_index == index
2824 });
2825 let k3_entry = self
2826 .tables
2827 .k3_to_item
2828 .find_entry_by_hash(hash3, |map3_index| {
2829 map3_index == index
2830 });
2831
2832 if let Ok(k2_entry) = k2_entry {
2833 k2_entry.remove();
2834 } else {
2835 self.tables.k2_to_item.remove_by_index(index);
2836 }
2837 if let Ok(k3_entry) = k3_entry {
2838 k3_entry.remove();
2839 } else {
2840 self.tables.k3_to_item.remove_by_index(index);
2841 }
2842
2843 // SAFETY: The original items is no longer used after the first
2844 // block above, and item + dormant_item have been dropped after
2845 // being used above. The k2/k3 work between them borrows only
2846 // `self.tables.k2_to_item` and `self.tables.k3_to_item`,
2847 // which are disjoint from `self.items`.
2848 let items = unsafe { dormant_items.awaken() };
2849 removed_item = Some(
2850 items
2851 .remove(index)
2852 .expect("all indexes are present in self.items"),
2853 );
2854
2855 false
2856 }
2857 });
2858
2859 // Anything in `removed_item` is implicitly dropped now.
2860 }
2861
2862 fn find1<'a, Q>(&'a self, k: &Q) -> Option<&'a T>
2863 where
2864 Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
2865 {
2866 self.find1_index(k).map(|ix| &self.items[ix])
2867 }
2868
2869 fn find1_index<'a, Q>(&'a self, k: &Q) -> Option<ItemIndex>
2870 where
2871 Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
2872 {
2873 self.tables
2874 .k1_to_item
2875 .find_index(&self.tables.state, k, |index| self.items[index].key1())
2876 }
2877
2878 fn find2<'a, Q>(&'a self, k: &Q) -> Option<&'a T>
2879 where
2880 Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
2881 {
2882 self.find2_index(k).map(|ix| &self.items[ix])
2883 }
2884
2885 fn find2_index<'a, Q>(&'a self, k: &Q) -> Option<ItemIndex>
2886 where
2887 Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
2888 {
2889 self.tables
2890 .k2_to_item
2891 .find_index(&self.tables.state, k, |index| self.items[index].key2())
2892 }
2893
2894 fn find3<'a, Q>(&'a self, k: &Q) -> Option<&'a T>
2895 where
2896 Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
2897 {
2898 self.find3_index(k).map(|ix| &self.items[ix])
2899 }
2900
2901 fn find3_index<'a, Q>(&'a self, k: &Q) -> Option<ItemIndex>
2902 where
2903 Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
2904 {
2905 self.tables
2906 .k3_to_item
2907 .find_index(&self.tables.state, k, |index| self.items[index].key3())
2908 }
2909
2910 fn prepare_insert_overwrite(&self, value: &T) -> PreparedInsertOverwrite {
2911 let key1 = value.key1();
2912 let key2 = value.key2();
2913 let key3 = value.key3();
2914
2915 let index1 = self.find1_index(&key1);
2916 let index2 = self.find2_index(&key2);
2917 let index3 = self.find3_index(&key3);
2918 let hashes = self.tables.make_hashes_for_keys::<T>(&key1, &key2, &key3);
2919
2920 let duplicates = PreparedDuplicate::from_indexes(
2921 [index1, index2, index3],
2922 |index| self.prepare_duplicate(index),
2923 );
2924
2925 PreparedInsertOverwrite { duplicates, hashes }
2926 }
2927
2928 fn prepare_duplicate(&self, index: ItemIndex) -> PreparedDuplicate {
2929 let item = &self.items[index];
2930 let hashes = self.tables.make_hashes::<T>(item);
2931
2932 PreparedDuplicate { index, hashes }
2933 }
2934
2935 fn try_reserve_insert_overwrite_commit(
2936 &mut self,
2937 needs_new_item_slot: bool,
2938 ) -> Result<(), TryReserveError> {
2939 if needs_new_item_slot {
2940 self.items.try_reserve(1)?;
2941 }
2942
2943 self.tables
2944 .k1_to_item
2945 .try_reserve(1)
2946 .map_err(TryReserveError::from_hashbrown)?;
2947
2948 self.tables
2949 .k2_to_item
2950 .try_reserve(1)
2951 .map_err(TryReserveError::from_hashbrown)?;
2952
2953 self.tables
2954 .k3_to_item
2955 .try_reserve(1)
2956 .map_err(TryReserveError::from_hashbrown)?;
2957
2958 Ok(())
2959 }
2960
2961 fn commit_insert_overwrite(
2962 &mut self,
2963 value: T,
2964 prepared: PreparedInsertOverwrite,
2965 duplicates: &mut Vec<T>,
2966 ) -> ItemIndex {
2967 // From here until insertion completes, do not call user code or
2968 // allocate. The caller prepared hashes/indexes and reserved capacity.
2969 for duplicate in prepared.duplicates {
2970 duplicates.push(
2971 self.remove_duplicate(duplicate)
2972 .expect("duplicate index was prepared"),
2973 );
2974 }
2975
2976 self.insert_unique_with_prepared_hashes(value, prepared.hashes)
2977 }
2978
2979 fn insert_unique_with_prepared_hashes(
2980 &mut self,
2981 value: T,
2982 hashes: [MapHash; 3],
2983 ) -> ItemIndex {
2984 let [hash1, hash2, hash3] = hashes;
2985 let next_index = self.items.assert_can_grow().insert(value);
2986
2987 self.tables.k1_to_item.insert_prehashed_unchecked(hash1, next_index);
2988 self.tables.k2_to_item.insert_prehashed_unchecked(hash2, next_index);
2989 self.tables.k3_to_item.insert_prehashed_unchecked(hash3, next_index);
2990
2991 next_index
2992 }
2993
2994 pub(super) fn remove_by_index(
2995 &mut self,
2996 remove_index: ItemIndex,
2997 ) -> Option<T> {
2998 // For panic safety, compute all three key hashes and look up all three
2999 // table entries while `self.items` still holds the value, then remove
3000 // from all three tables and items in sequence. These lookups
3001 // deliberately match by `ItemIndex` rather than by user `Eq`: at this
3002 // point we already know which item is being removed, and user `Eq`
3003 // might be pathological. hashbrown's `find_entry_by_hash` is
3004 // panic-safe because the table is not mutated until
3005 // `OccupiedEntry::remove` is called, so a panic while hashing leaves
3006 // items and all three tables unmodified. (Unlike the IdOrdMap path,
3007 // no separate two-phase commit is needed: the BTreeMap analog has to
3008 // guard against a user-`Ord` panic during the tree walk, but the
3009 // hash walk here never invokes user code.)
3010 //
3011 // If any hash lookup misses — which happens when a `mem::forget` on
3012 // a `RefMut` bypassed the drop-time hash check and one of the item's
3013 // keys now hashes to a different bucket than its entry sits in —
3014 // fall back to a linear scan by `ItemIndex` for that table. The
3015 // fallback never invokes user `Hash`, so cleanup remains panic-safe.
3016 let item = self.items.get(remove_index)?;
3017 let state = &self.tables.state;
3018 let hash1 = state.hash_one(item.key1());
3019 let hash2 = state.hash_one(item.key2());
3020 let hash3 = state.hash_one(item.key3());
3021 match self
3022 .tables
3023 .k1_to_item
3024 .find_entry_by_hash(hash1, |index| index == remove_index)
3025 {
3026 Ok(entry) => entry.remove(),
3027 Err(()) => self.tables.k1_to_item.remove_by_index(remove_index),
3028 }
3029 match self
3030 .tables
3031 .k2_to_item
3032 .find_entry_by_hash(hash2, |index| index == remove_index)
3033 {
3034 Ok(entry) => entry.remove(),
3035 Err(()) => self.tables.k2_to_item.remove_by_index(remove_index),
3036 }
3037 match self
3038 .tables
3039 .k3_to_item
3040 .find_entry_by_hash(hash3, |index| index == remove_index)
3041 {
3042 Ok(entry) => entry.remove(),
3043 Err(()) => self.tables.k3_to_item.remove_by_index(remove_index),
3044 }
3045 Some(
3046 self.items
3047 .remove(remove_index)
3048 .expect("items[remove_index] was Occupied above"),
3049 )
3050 }
3051
3052 /// Removes the item at `duplicate`, using already-computed key hashes when
3053 /// possible.
3054 ///
3055 /// The caller must ensure:
3056 ///
3057 /// * all user-controlled key extraction and hashing for the item at
3058 /// `duplicate.index` has already completed;
3059 /// * the item at `duplicate.index` has not changed since those hashes were
3060 /// computed;
3061 /// * removing this index from the item store and key tables preserves the
3062 /// map/table invariants.
3063 ///
3064 /// The provided `duplicate.hashes` allow the normal commit path to remove
3065 /// key-table entries without recomputing user-controlled hashes. If a
3066 /// prehashed lookup misses, this falls back to removing by `ItemIndex`,
3067 /// which performs a linear scan over cached indexes and does not re-enter
3068 /// user code.
3069 fn remove_duplicate(&mut self, duplicate: PreparedDuplicate) -> Option<T> {
3070 let _ = self.items.get(duplicate.index)?;
3071
3072 let [hash1, hash2, hash3] = duplicate.hashes;
3073
3074 match self
3075 .tables
3076 .k1_to_item
3077 .find_entry_by_hash(hash1.hash(), |index| index == duplicate.index)
3078 {
3079 Ok(entry) => entry.remove(),
3080 Err(()) => self.tables.k1_to_item.remove_by_index(duplicate.index),
3081 }
3082
3083 match self
3084 .tables
3085 .k2_to_item
3086 .find_entry_by_hash(hash2.hash(), |index| index == duplicate.index)
3087 {
3088 Ok(entry) => entry.remove(),
3089 Err(()) => self.tables.k2_to_item.remove_by_index(duplicate.index),
3090 }
3091
3092 match self
3093 .tables
3094 .k3_to_item
3095 .find_entry_by_hash(hash3.hash(), |index| index == duplicate.index)
3096 {
3097 Ok(entry) => entry.remove(),
3098 Err(()) => self.tables.k3_to_item.remove_by_index(duplicate.index),
3099 }
3100
3101 Some(
3102 self.items
3103 .remove(duplicate.index)
3104 .expect("items[duplicate.index] was Occupied above"),
3105 )
3106 }
3107}
3108
3109impl<'a, T, S, A: Allocator> fmt::Debug for TriHashMap<T, S, A>
3110where
3111 T: TriHashItem + fmt::Debug,
3112 T::K1<'a>: fmt::Debug,
3113 T::K2<'a>: fmt::Debug,
3114 T::K3<'a>: fmt::Debug,
3115 T: 'a,
3116{
3117 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3118 let mut map = f.debug_map();
3119 for item in self.items.values() {
3120 let key: KeyMap<'_, T> = KeyMap {
3121 key1: item.key1(),
3122 key2: item.key2(),
3123 key3: item.key3(),
3124 };
3125
3126 // SAFETY:
3127 //
3128 // * Lifetime extension: for a type T and two lifetime params 'a and
3129 // 'b, T<'a> and T<'b> aren't guaranteed to have the same layout,
3130 // but (a) that is true today and (b) it would be shocking and
3131 // break half the Rust ecosystem if that were to change in the
3132 // future.
3133 // * We only use key within the scope of this block before immediately
3134 // dropping it. In particular, map.entry calls key.fmt() without
3135 // holding a reference to it.
3136 let key: KeyMap<'a, T> = unsafe {
3137 core::mem::transmute::<KeyMap<'_, T>, KeyMap<'a, T>>(key)
3138 };
3139
3140 map.entry(&key, item);
3141 }
3142 map.finish()
3143 }
3144}
3145
3146struct KeyMap<'a, T: TriHashItem + 'a> {
3147 key1: T::K1<'a>,
3148 key2: T::K2<'a>,
3149 key3: T::K3<'a>,
3150}
3151
3152impl<'a, T: TriHashItem> fmt::Debug for KeyMap<'a, T>
3153where
3154 T::K1<'a>: fmt::Debug,
3155 T::K2<'a>: fmt::Debug,
3156 T::K3<'a>: fmt::Debug,
3157{
3158 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3159 // We don't want to show key1 and key2 as a tuple since it's
3160 // misleading (suggests maps of tuples). The best we can do
3161 // instead is to show "{k1: abc, k2: xyz, k3: def}"
3162 f.debug_map()
3163 .entry(&StrDisplayAsDebug("k1"), &self.key1)
3164 .entry(&StrDisplayAsDebug("k2"), &self.key2)
3165 .entry(&StrDisplayAsDebug("k3"), &self.key3)
3166 .finish()
3167 }
3168}
3169
3170impl<T: TriHashItem + PartialEq, S: Clone + BuildHasher, A: Allocator> PartialEq
3171 for TriHashMap<T, S, A>
3172{
3173 fn eq(&self, other: &Self) -> bool {
3174 // Implementing PartialEq for TriHashMap is tricky because TriHashMap is
3175 // not semantically like an IndexMap: two maps are equivalent even if
3176 // their items are in a different order. In other words, any permutation
3177 // of items is equivalent.
3178 //
3179 // We also can't sort the items because they're not necessarily Ord.
3180 //
3181 // So we write a custom equality check that checks that each key in one
3182 // map points to the same item as in the other map.
3183
3184 if self.items.len() != other.items.len() {
3185 return false;
3186 }
3187
3188 // Walk over all the items in the first map and check that they point to
3189 // the same item in the second map.
3190 for item in self.items.values() {
3191 let k1 = item.key1();
3192 let k2 = item.key2();
3193 let k3 = item.key3();
3194
3195 // Check that the indexes are the same in the other map.
3196 let Some(other_ix1) = other.find1_index(&k1) else {
3197 return false;
3198 };
3199 let Some(other_ix2) = other.find2_index(&k2) else {
3200 return false;
3201 };
3202 let Some(other_ix3) = other.find3_index(&k3) else {
3203 return false;
3204 };
3205
3206 if other_ix1 != other_ix2 || other_ix1 != other_ix3 {
3207 // All the keys were present but they didn't point to the same
3208 // item.
3209 return false;
3210 }
3211
3212 // Check that the other map's item is the same as this map's
3213 // item. (This is what we use the `PartialEq` bound on T for.)
3214 //
3215 // Because we've checked that other_ix1, other_ix2 and other_ix3 are
3216 // Some, we know that it is valid and points to the expected item.
3217 let other_item = &other.items[other_ix1];
3218 if item != other_item {
3219 return false;
3220 }
3221 }
3222
3223 true
3224 }
3225}
3226
3227// The Eq bound on T ensures that the TriHashMap forms an equivalence class.
3228impl<T: TriHashItem + Eq, S: Clone + BuildHasher, A: Allocator> Eq
3229 for TriHashMap<T, S, A>
3230{
3231}
3232
3233/// The `Extend` implementation overwrites duplicates. In the future, there will
3234/// also be an `extend_unique` method that will return an error.
3235impl<T: TriHashItem, S: Clone + BuildHasher, A: Allocator> Extend<T>
3236 for TriHashMap<T, S, A>
3237{
3238 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
3239 // Keys may already be present in the map, or multiple times in the
3240 // iterator. Reserve the entire hint lower bound if the map is empty.
3241 // Otherwise reserve half the hint (rounded up), so the map will only
3242 // resize twice in the worst case.
3243 let iter = iter.into_iter();
3244 let reserve = if self.is_empty() {
3245 iter.size_hint().0
3246 } else {
3247 iter.size_hint().0.div_ceil(2)
3248 };
3249 self.reserve(reserve);
3250 for item in iter {
3251 self.insert_overwrite(item);
3252 }
3253 }
3254}
3255
3256fn detect_dup_or_insert<'a, A: Allocator>(
3257 item: hash_table::Entry<'a, A>,
3258 duplicates: &mut BTreeSet<ItemIndex>,
3259) -> Option<hash_table::VacantEntry<'a, A>> {
3260 match item {
3261 hash_table::Entry::Vacant(slot) => Some(slot),
3262 hash_table::Entry::Occupied(slot) => {
3263 duplicates.insert(slot.get());
3264 None
3265 }
3266 }
3267}
3268
3269impl<'a, T: TriHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
3270 for &'a TriHashMap<T, S, A>
3271{
3272 type Item = &'a T;
3273 type IntoIter = Iter<'a, T>;
3274
3275 #[inline]
3276 fn into_iter(self) -> Self::IntoIter {
3277 self.iter()
3278 }
3279}
3280
3281impl<'a, T: TriHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
3282 for &'a mut TriHashMap<T, S, A>
3283{
3284 type Item = RefMut<'a, T, S>;
3285 type IntoIter = IterMut<'a, T, S, A>;
3286
3287 #[inline]
3288 fn into_iter(self) -> Self::IntoIter {
3289 self.iter_mut()
3290 }
3291}
3292
3293impl<T: TriHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
3294 for TriHashMap<T, S, A>
3295{
3296 type Item = T;
3297 type IntoIter = IntoIter<T, A>;
3298
3299 #[inline]
3300 fn into_iter(self) -> Self::IntoIter {
3301 IntoIter::new(self.items)
3302 }
3303}
3304
3305/// The `FromIterator` implementation for `TriHashMap` overwrites duplicate
3306/// items.
3307///
3308/// To reject duplicates, use [`TriHashMap::from_iter_unique`].
3309///
3310/// # Examples
3311///
3312/// ```
3313/// # #[cfg(feature = "default-hasher")] {
3314/// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
3315///
3316/// #[derive(Debug, PartialEq, Eq)]
3317/// struct Item {
3318/// id: u32,
3319/// name: String,
3320/// email: String,
3321/// }
3322///
3323/// impl TriHashItem for Item {
3324/// type K1<'a> = u32;
3325/// type K2<'a> = &'a str;
3326/// type K3<'a> = &'a str;
3327/// fn key1(&self) -> Self::K1<'_> {
3328/// self.id
3329/// }
3330/// fn key2(&self) -> Self::K2<'_> {
3331/// &self.name
3332/// }
3333/// fn key3(&self) -> Self::K3<'_> {
3334/// &self.email
3335/// }
3336/// tri_upcast!();
3337/// }
3338///
3339/// let items = vec![
3340/// Item {
3341/// id: 1,
3342/// name: "foo".to_string(),
3343/// email: "foo@example.com".to_string(),
3344/// },
3345/// Item {
3346/// id: 2,
3347/// name: "bar".to_string(),
3348/// email: "bar@example.com".to_string(),
3349/// },
3350/// Item {
3351/// id: 1,
3352/// name: "baz".to_string(),
3353/// email: "baz@example.com".to_string(),
3354/// }, // overwrites first item
3355/// ];
3356///
3357/// let map: TriHashMap<Item> = items.into_iter().collect();
3358/// assert_eq!(map.len(), 2);
3359/// assert_eq!(map.get1(&1).unwrap().name, "baz"); // overwritten
3360/// assert_eq!(map.get1(&1).unwrap().email, "baz@example.com");
3361/// assert_eq!(map.get1(&2).unwrap().name, "bar");
3362/// # }
3363/// ```
3364impl<T: TriHashItem, S: Default + Clone + BuildHasher, A: Default + Allocator>
3365 FromIterator<T> for TriHashMap<T, S, A>
3366{
3367 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
3368 let mut map = TriHashMap::default();
3369 map.extend(iter);
3370 map
3371 }
3372}