1use core::{
2 borrow::Borrow,
3 fmt,
4 hash::{BuildHasher, Hash, Hasher as _},
5 iter::FromIterator,
6 mem,
7 num::NonZeroU32,
8 ops, slice,
9};
10
11use hash32::{BuildHasherDefault, FnvHasher};
12
13use crate::Vec;
14
15/// A [`IndexMap`] using the default FNV hasher
16///
17/// A list of all Methods and Traits available for `FnvIndexMap` can be found in
18/// the [`IndexMap`] documentation.
19///
20/// # Examples
21/// ```
22/// use heapless::FnvIndexMap;
23///
24/// // A hash map with a capacity of 16 key-value pairs allocated on the stack
25/// let mut book_reviews = FnvIndexMap::<_, _, 16>::new();
26///
27/// // review some books.
28/// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.").unwrap();
29/// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.").unwrap();
30/// book_reviews.insert("Pride and Prejudice", "Very enjoyable.").unwrap();
31/// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.").unwrap();
32///
33/// // check for a specific one.
34/// if !book_reviews.contains_key("Les Misérables") {
35/// println!("We've got {} reviews, but Les Misérables ain't one.",
36/// book_reviews.len());
37/// }
38///
39/// // oops, this review has a lot of spelling mistakes, let's delete it.
40/// book_reviews.remove("The Adventures of Sherlock Holmes");
41///
42/// // look up the values associated with some keys.
43/// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
44/// for book in &to_find {
45/// match book_reviews.get(book) {
46/// Some(review) => println!("{}: {}", book, review),
47/// None => println!("{} is unreviewed.", book)
48/// }
49/// }
50///
51/// // iterate over everything.
52/// for (book, review) in &book_reviews {
53/// println!("{}: \"{}\"", book, review);
54/// }
55/// ```
56pub type FnvIndexMap<K, V, const N: usize> = IndexMap<K, V, BuildHasherDefault<FnvHasher>, N>;
57
58#[derive(Clone, Copy, Eq, PartialEq)]
59struct HashValue(u16);
60
61impl HashValue {
62 fn desired_pos(&self, mask: usize) -> usize {
63 usize::from(self.0) & mask
64 }
65
66 fn probe_distance(&self, mask: usize, current: usize) -> usize {
67 current.wrapping_sub(self.desired_pos(mask) as usize) & mask
68 }
69}
70
71#[doc(hidden)]
72#[derive(Clone)]
73pub struct Bucket<K, V> {
74 hash: HashValue,
75 key: K,
76 value: V,
77}
78
79#[doc(hidden)]
80#[derive(Clone, Copy, PartialEq)]
81pub struct Pos {
82 // compact representation of `{ hash_value: u16, index: u16 }`
83 // To get the most from `NonZero` we store the *value minus 1*. This way `None::Option<Pos>`
84 // is equivalent to the very unlikely value of `{ hash_value: 0xffff, index: 0xffff }` instead
85 // the more likely of `{ hash_value: 0x00, index: 0x00 }`
86 nz: NonZeroU32,
87}
88
89impl Pos {
90 fn new(index: usize, hash: HashValue) -> Self {
91 Pos {
92 nz: unsafe {
93 NonZeroU32::new_unchecked(
94 ((u32::from(hash.0) << 16) + index as u32).wrapping_add(1),
95 )
96 },
97 }
98 }
99
100 fn hash(&self) -> HashValue {
101 HashValue((self.nz.get().wrapping_sub(1) >> 16) as u16)
102 }
103
104 fn index(&self) -> usize {
105 self.nz.get().wrapping_sub(1) as u16 as usize
106 }
107}
108
109enum Insert<K, V> {
110 Success(Inserted<V>),
111 Full((K, V)),
112}
113struct Inserted<V> {
114 index: usize,
115 old_value: Option<V>,
116}
117
118macro_rules! probe_loop {
119 ($probe_var: ident < $len: expr, $body: expr) => {
120 loop {
121 if $probe_var < $len {
122 $body
123 $probe_var += 1;
124 } else {
125 $probe_var = 0;
126 }
127 }
128 }
129}
130
131struct CoreMap<K, V, const N: usize> {
132 entries: Vec<Bucket<K, V>, N>,
133 indices: [Option<Pos>; N],
134}
135
136impl<K, V, const N: usize> CoreMap<K, V, N> {
137 const fn new() -> Self {
138 const INIT: Option<Pos> = None;
139
140 CoreMap {
141 entries: Vec::new(),
142 indices: [INIT; N],
143 }
144 }
145}
146
147impl<K, V, const N: usize> CoreMap<K, V, N>
148where
149 K: Eq + Hash,
150{
151 fn capacity() -> usize {
152 N
153 }
154
155 fn mask() -> usize {
156 Self::capacity() - 1
157 }
158
159 fn find<Q>(&self, hash: HashValue, query: &Q) -> Option<(usize, usize)>
160 where
161 K: Borrow<Q>,
162 Q: ?Sized + Eq,
163 {
164 let mut probe = hash.desired_pos(Self::mask());
165 let mut dist = 0;
166
167 probe_loop!(probe < self.indices.len(), {
168 if let Some(pos) = self.indices[probe] {
169 let entry_hash = pos.hash();
170 // NOTE(i) we use unchecked indexing below
171 let i = pos.index();
172 debug_assert!(i < self.entries.len());
173
174 if dist > entry_hash.probe_distance(Self::mask(), probe) {
175 // give up when probe distance is too long
176 return None;
177 } else if entry_hash == hash
178 && unsafe { self.entries.get_unchecked(i).key.borrow() == query }
179 {
180 return Some((probe, i));
181 }
182 } else {
183 return None;
184 }
185
186 dist += 1;
187 });
188 }
189
190 fn insert(&mut self, hash: HashValue, key: K, value: V) -> Insert<K, V> {
191 let mut probe = hash.desired_pos(Self::mask());
192 let mut dist = 0;
193
194 probe_loop!(probe < self.indices.len(), {
195 let pos = &mut self.indices[probe];
196
197 if let Some(pos) = *pos {
198 let entry_hash = pos.hash();
199 // NOTE(i) we use unchecked indexing below
200 let i = pos.index();
201 debug_assert!(i < self.entries.len());
202
203 let their_dist = entry_hash.probe_distance(Self::mask(), probe);
204
205 if their_dist < dist {
206 if self.entries.is_full() {
207 return Insert::Full((key, value));
208 }
209 // robin hood: steal the spot if it's better for us
210 let index = self.entries.len();
211 unsafe { self.entries.push_unchecked(Bucket { hash, key, value }) };
212 Self::insert_phase_2(&mut self.indices, probe, Pos::new(index, hash));
213 return Insert::Success(Inserted {
214 index,
215 old_value: None,
216 });
217 } else if entry_hash == hash && unsafe { self.entries.get_unchecked(i).key == key }
218 {
219 return Insert::Success(Inserted {
220 index: i,
221 old_value: Some(mem::replace(
222 unsafe { &mut self.entries.get_unchecked_mut(i).value },
223 value,
224 )),
225 });
226 }
227 } else {
228 if self.entries.is_full() {
229 return Insert::Full((key, value));
230 }
231 // empty bucket, insert here
232 let index = self.entries.len();
233 *pos = Some(Pos::new(index, hash));
234 unsafe { self.entries.push_unchecked(Bucket { hash, key, value }) };
235 return Insert::Success(Inserted {
236 index,
237 old_value: None,
238 });
239 }
240 dist += 1;
241 });
242 }
243
244 // phase 2 is post-insert where we forward-shift `Pos` in the indices.
245 fn insert_phase_2(indices: &mut [Option<Pos>; N], mut probe: usize, mut old_pos: Pos) -> usize {
246 probe_loop!(probe < indices.len(), {
247 let pos = unsafe { indices.get_unchecked_mut(probe) };
248
249 let mut is_none = true; // work around lack of NLL
250 if let Some(pos) = pos.as_mut() {
251 old_pos = mem::replace(pos, old_pos);
252 is_none = false;
253 }
254
255 if is_none {
256 *pos = Some(old_pos);
257 return probe;
258 }
259 });
260 }
261
262 fn remove_found(&mut self, probe: usize, found: usize) -> (K, V) {
263 // index `probe` and entry `found` is to be removed
264 // use swap_remove, but then we need to update the index that points
265 // to the other entry that has to move
266 self.indices[probe] = None;
267 let entry = unsafe { self.entries.swap_remove_unchecked(found) };
268
269 // correct index that points to the entry that had to swap places
270 if let Some(entry) = self.entries.get(found) {
271 // was not last element
272 // examine new element in `found` and find it in indices
273 let mut probe = entry.hash.desired_pos(Self::mask());
274
275 probe_loop!(probe < self.indices.len(), {
276 if let Some(pos) = self.indices[probe] {
277 if pos.index() >= self.entries.len() {
278 // found it
279 self.indices[probe] = Some(Pos::new(found, entry.hash));
280 break;
281 }
282 }
283 });
284 }
285
286 self.backward_shift_after_removal(probe);
287
288 (entry.key, entry.value)
289 }
290
291 fn retain_in_order<F>(&mut self, mut keep: F)
292 where
293 F: FnMut(&mut K, &mut V) -> bool,
294 {
295 const INIT: Option<Pos> = None;
296
297 self.entries
298 .retain_mut(|entry| keep(&mut entry.key, &mut entry.value));
299
300 if self.entries.len() < self.indices.len() {
301 for index in self.indices.iter_mut() {
302 *index = INIT;
303 }
304
305 for (index, entry) in self.entries.iter().enumerate() {
306 let mut probe = entry.hash.desired_pos(Self::mask());
307 let mut dist = 0;
308
309 probe_loop!(probe < self.indices.len(), {
310 let pos = &mut self.indices[probe];
311
312 if let Some(pos) = *pos {
313 let entry_hash = pos.hash();
314
315 // robin hood: steal the spot if it's better for us
316 let their_dist = entry_hash.probe_distance(Self::mask(), probe);
317 if their_dist < dist {
318 Self::insert_phase_2(
319 &mut self.indices,
320 probe,
321 Pos::new(index, entry.hash),
322 );
323 break;
324 }
325 } else {
326 *pos = Some(Pos::new(index, entry.hash));
327 break;
328 }
329 dist += 1;
330 });
331 }
332 }
333 }
334
335 fn backward_shift_after_removal(&mut self, probe_at_remove: usize) {
336 // backward shift deletion in self.indices
337 // after probe, shift all non-ideally placed indices backward
338 let mut last_probe = probe_at_remove;
339 let mut probe = probe_at_remove + 1;
340
341 probe_loop!(probe < self.indices.len(), {
342 if let Some(pos) = self.indices[probe] {
343 let entry_hash = pos.hash();
344
345 if entry_hash.probe_distance(Self::mask(), probe) > 0 {
346 unsafe { *self.indices.get_unchecked_mut(last_probe) = self.indices[probe] }
347 self.indices[probe] = None;
348 } else {
349 break;
350 }
351 } else {
352 break;
353 }
354 last_probe = probe;
355 });
356 }
357}
358
359impl<K, V, const N: usize> Clone for CoreMap<K, V, N>
360where
361 K: Clone,
362 V: Clone,
363{
364 fn clone(&self) -> Self {
365 Self {
366 entries: self.entries.clone(),
367 indices: self.indices.clone(),
368 }
369 }
370}
371
372/// A view into an entry in the map
373pub enum Entry<'a, K, V, const N: usize> {
374 /// The entry corresponding to the key `K` exists in the map
375 Occupied(OccupiedEntry<'a, K, V, N>),
376 /// The entry corresponding to the key `K` does not exist in the map
377 Vacant(VacantEntry<'a, K, V, N>),
378}
379
380/// An occupied entry which can be manipulated
381pub struct OccupiedEntry<'a, K, V, const N: usize> {
382 key: K,
383 probe: usize,
384 pos: usize,
385 core: &'a mut CoreMap<K, V, N>,
386}
387
388impl<'a, K, V, const N: usize> OccupiedEntry<'a, K, V, N>
389where
390 K: Eq + Hash,
391{
392 /// Gets a reference to the key that this entity corresponds to
393 pub fn key(&self) -> &K {
394 &self.key
395 }
396
397 /// Removes this entry from the map and yields its corresponding key and value
398 pub fn remove_entry(self) -> (K, V) {
399 self.core.remove_found(self.probe, self.pos)
400 }
401
402 /// Gets a reference to the value associated with this entry
403 pub fn get(&self) -> &V {
404 // SAFETY: Already checked existence at instantiation and the only mutable reference
405 // to the map is internally held.
406 unsafe { &self.core.entries.get_unchecked(self.pos).value }
407 }
408
409 /// Gets a mutable reference to the value associated with this entry
410 pub fn get_mut(&mut self) -> &mut V {
411 // SAFETY: Already checked existence at instantiation and the only mutable reference
412 // to the map is internally held.
413 unsafe { &mut self.core.entries.get_unchecked_mut(self.pos).value }
414 }
415
416 /// Consumes this entry and yields a reference to the underlying value
417 pub fn into_mut(self) -> &'a mut V {
418 // SAFETY: Already checked existence at instantiation and the only mutable reference
419 // to the map is internally held.
420 unsafe { &mut self.core.entries.get_unchecked_mut(self.pos).value }
421 }
422
423 /// Overwrites the underlying map's value with this entry's value
424 pub fn insert(self, value: V) -> V {
425 // SAFETY: Already checked existence at instantiation and the only mutable reference
426 // to the map is internally held.
427 unsafe {
428 mem::replace(
429 &mut self.core.entries.get_unchecked_mut(self.pos).value,
430 value,
431 )
432 }
433 }
434
435 /// Removes this entry from the map and yields its value
436 pub fn remove(self) -> V {
437 self.remove_entry().1
438 }
439}
440
441/// A view into an empty slot in the underlying map
442pub struct VacantEntry<'a, K, V, const N: usize> {
443 key: K,
444 hash_val: HashValue,
445 core: &'a mut CoreMap<K, V, N>,
446}
447impl<'a, K, V, const N: usize> VacantEntry<'a, K, V, N>
448where
449 K: Eq + Hash,
450{
451 /// Get the key associated with this entry
452 pub fn key(&self) -> &K {
453 &self.key
454 }
455
456 /// Consumes this entry to yield to key associated with it
457 pub fn into_key(self) -> K {
458 self.key
459 }
460
461 /// Inserts this entry into to underlying map, yields a mutable reference to the inserted value.
462 /// If the map is at capacity the value is returned instead.
463 pub fn insert(self, value: V) -> Result<&'a mut V, V> {
464 if self.core.entries.is_full() {
465 Err(value)
466 } else {
467 match self.core.insert(self.hash_val, self.key, value) {
468 Insert::Success(inserted) => {
469 unsafe {
470 // SAFETY: Already checked existence at instantiation and the only mutable reference
471 // to the map is internally held.
472 Ok(&mut (*self.core.entries.as_mut_ptr().add(inserted.index)).value)
473 }
474 }
475 Insert::Full((_, v)) => Err(v),
476 }
477 }
478 }
479}
480
481/// Fixed capacity [`IndexMap`](https://docs.rs/indexmap/2/indexmap/map/struct.IndexMap.html)
482///
483/// Note that you cannot use `IndexMap` directly, since it is generic around the hashing algorithm
484/// in use. Pick a concrete instantiation like [`FnvIndexMap`] instead
485/// or create your own.
486///
487/// Note that the capacity of the `IndexMap` must be a power of 2.
488///
489/// # Examples
490///
491/// Since `IndexMap` cannot be used directly, we're using its `FnvIndexMap` instantiation
492/// for this example.
493///
494/// ```
495/// use heapless::FnvIndexMap;
496///
497/// // A hash map with a capacity of 16 key-value pairs allocated on the stack
498/// let mut book_reviews = FnvIndexMap::<_, _, 16>::new();
499///
500/// // review some books.
501/// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.").unwrap();
502/// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.").unwrap();
503/// book_reviews.insert("Pride and Prejudice", "Very enjoyable.").unwrap();
504/// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.").unwrap();
505///
506/// // check for a specific one.
507/// if !book_reviews.contains_key("Les Misérables") {
508/// println!("We've got {} reviews, but Les Misérables ain't one.",
509/// book_reviews.len());
510/// }
511///
512/// // oops, this review has a lot of spelling mistakes, let's delete it.
513/// book_reviews.remove("The Adventures of Sherlock Holmes");
514///
515/// // look up the values associated with some keys.
516/// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
517/// for book in &to_find {
518/// match book_reviews.get(book) {
519/// Some(review) => println!("{}: {}", book, review),
520/// None => println!("{} is unreviewed.", book)
521/// }
522/// }
523///
524/// // iterate over everything.
525/// for (book, review) in &book_reviews {
526/// println!("{}: \"{}\"", book, review);
527/// }
528/// ```
529pub struct IndexMap<K, V, S, const N: usize> {
530 core: CoreMap<K, V, N>,
531 build_hasher: S,
532}
533
534impl<K, V, S, const N: usize> IndexMap<K, V, BuildHasherDefault<S>, N> {
535 /// Creates an empty `IndexMap`.
536 pub const fn new() -> Self {
537 // Const assert
538 crate::sealed::greater_than_1::<N>();
539 crate::sealed::power_of_two::<N>();
540
541 IndexMap {
542 build_hasher: BuildHasherDefault::new(),
543 core: CoreMap::new(),
544 }
545 }
546}
547
548impl<K, V, S, const N: usize> IndexMap<K, V, S, N> {
549 /// Returns the number of elements the map can hold
550 pub fn capacity(&self) -> usize {
551 N
552 }
553
554 /// Return an iterator over the keys of the map, in insertion order
555 ///
556 /// ```
557 /// use heapless::FnvIndexMap;
558 ///
559 /// let mut map = FnvIndexMap::<_, _, 16>::new();
560 /// map.insert("a", 1).unwrap();
561 /// map.insert("b", 2).unwrap();
562 /// map.insert("c", 3).unwrap();
563 ///
564 /// for key in map.keys() {
565 /// println!("{}", key);
566 /// }
567 /// ```
568 pub fn keys(&self) -> Keys<'_, K, V> {
569 Keys {
570 iter: self.core.entries.iter(),
571 }
572 }
573
574 /// Return an iterator over the values of the map, in insertion order
575 ///
576 /// ```
577 /// use heapless::FnvIndexMap;
578 ///
579 /// let mut map = FnvIndexMap::<_, _, 16>::new();
580 /// map.insert("a", 1).unwrap();
581 /// map.insert("b", 2).unwrap();
582 /// map.insert("c", 3).unwrap();
583 ///
584 /// for val in map.values() {
585 /// println!("{}", val);
586 /// }
587 /// ```
588 pub fn values(&self) -> Values<'_, K, V> {
589 Values {
590 iter: self.core.entries.iter(),
591 }
592 }
593
594 /// Return an iterator over mutable references to the the values of the map, in insertion order
595 ///
596 /// ```
597 /// use heapless::FnvIndexMap;
598 ///
599 /// let mut map = FnvIndexMap::<_, _, 16>::new();
600 /// map.insert("a", 1).unwrap();
601 /// map.insert("b", 2).unwrap();
602 /// map.insert("c", 3).unwrap();
603 ///
604 /// for val in map.values_mut() {
605 /// *val += 10;
606 /// }
607 ///
608 /// for val in map.values() {
609 /// println!("{}", val);
610 /// }
611 /// ```
612 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
613 ValuesMut {
614 iter: self.core.entries.iter_mut(),
615 }
616 }
617
618 /// Return an iterator over the key-value pairs of the map, in insertion order
619 ///
620 /// ```
621 /// use heapless::FnvIndexMap;
622 ///
623 /// let mut map = FnvIndexMap::<_, _, 16>::new();
624 /// map.insert("a", 1).unwrap();
625 /// map.insert("b", 2).unwrap();
626 /// map.insert("c", 3).unwrap();
627 ///
628 /// for (key, val) in map.iter() {
629 /// println!("key: {} val: {}", key, val);
630 /// }
631 /// ```
632 pub fn iter(&self) -> Iter<'_, K, V> {
633 Iter {
634 iter: self.core.entries.iter(),
635 }
636 }
637
638 /// Return an iterator over the key-value pairs of the map, in insertion order
639 ///
640 /// ```
641 /// use heapless::FnvIndexMap;
642 ///
643 /// let mut map = FnvIndexMap::<_, _, 16>::new();
644 /// map.insert("a", 1).unwrap();
645 /// map.insert("b", 2).unwrap();
646 /// map.insert("c", 3).unwrap();
647 ///
648 /// for (_, val) in map.iter_mut() {
649 /// *val = 2;
650 /// }
651 ///
652 /// for (key, val) in &map {
653 /// println!("key: {} val: {}", key, val);
654 /// }
655 /// ```
656 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
657 IterMut {
658 iter: self.core.entries.iter_mut(),
659 }
660 }
661
662 /// Get the first key-value pair
663 ///
664 /// Computes in **O(1)** time
665 pub fn first(&self) -> Option<(&K, &V)> {
666 self.core
667 .entries
668 .first()
669 .map(|bucket| (&bucket.key, &bucket.value))
670 }
671
672 /// Get the first key-value pair, with mutable access to the value
673 ///
674 /// Computes in **O(1)** time
675 pub fn first_mut(&mut self) -> Option<(&K, &mut V)> {
676 self.core
677 .entries
678 .first_mut()
679 .map(|bucket| (&bucket.key, &mut bucket.value))
680 }
681
682 /// Get the last key-value pair
683 ///
684 /// Computes in **O(1)** time
685 pub fn last(&self) -> Option<(&K, &V)> {
686 self.core
687 .entries
688 .last()
689 .map(|bucket| (&bucket.key, &bucket.value))
690 }
691
692 /// Get the last key-value pair, with mutable access to the value
693 ///
694 /// Computes in **O(1)** time
695 pub fn last_mut(&mut self) -> Option<(&K, &mut V)> {
696 self.core
697 .entries
698 .last_mut()
699 .map(|bucket| (&bucket.key, &mut bucket.value))
700 }
701
702 /// Return the number of key-value pairs in the map.
703 ///
704 /// Computes in **O(1)** time.
705 ///
706 /// ```
707 /// use heapless::FnvIndexMap;
708 ///
709 /// let mut a = FnvIndexMap::<_, _, 16>::new();
710 /// assert_eq!(a.len(), 0);
711 /// a.insert(1, "a").unwrap();
712 /// assert_eq!(a.len(), 1);
713 /// ```
714 pub fn len(&self) -> usize {
715 self.core.entries.len()
716 }
717
718 /// Returns true if the map contains no elements.
719 ///
720 /// Computes in **O(1)** time.
721 ///
722 /// ```
723 /// use heapless::FnvIndexMap;
724 ///
725 /// let mut a = FnvIndexMap::<_, _, 16>::new();
726 /// assert!(a.is_empty());
727 /// a.insert(1, "a");
728 /// assert!(!a.is_empty());
729 /// ```
730 pub fn is_empty(&self) -> bool {
731 self.len() == 0
732 }
733
734 /// Remove all key-value pairs in the map, while preserving its capacity.
735 ///
736 /// Computes in **O(n)** time.
737 ///
738 /// ```
739 /// use heapless::FnvIndexMap;
740 ///
741 /// let mut a = FnvIndexMap::<_, _, 16>::new();
742 /// a.insert(1, "a");
743 /// a.clear();
744 /// assert!(a.is_empty());
745 /// ```
746 pub fn clear(&mut self) {
747 self.core.entries.clear();
748 for pos in self.core.indices.iter_mut() {
749 *pos = None;
750 }
751 }
752}
753
754impl<K, V, S, const N: usize> IndexMap<K, V, S, N>
755where
756 K: Eq + Hash,
757 S: BuildHasher,
758{
759 /* Public API */
760 /// Returns an entry for the corresponding key
761 /// ```
762 /// use heapless::FnvIndexMap;
763 /// use heapless::Entry;
764 /// let mut map = FnvIndexMap::<_, _, 16>::new();
765 /// if let Entry::Vacant(v) = map.entry("a") {
766 /// v.insert(1).unwrap();
767 /// }
768 /// if let Entry::Occupied(mut o) = map.entry("a") {
769 /// println!("found {}", *o.get()); // Prints 1
770 /// o.insert(2);
771 /// }
772 /// // Prints 2
773 /// println!("val: {}", *map.get("a").unwrap());
774 /// ```
775 pub fn entry(&mut self, key: K) -> Entry<'_, K, V, N> {
776 let hash_val = hash_with(&key, &self.build_hasher);
777 if let Some((probe, pos)) = self.core.find(hash_val, &key) {
778 Entry::Occupied(OccupiedEntry {
779 key,
780 probe,
781 pos,
782 core: &mut self.core,
783 })
784 } else {
785 Entry::Vacant(VacantEntry {
786 key,
787 hash_val,
788 core: &mut self.core,
789 })
790 }
791 }
792
793 /// Returns a reference to the value corresponding to the key.
794 ///
795 /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
796 /// form *must* match those for the key type.
797 ///
798 /// Computes in **O(1)** time (average).
799 ///
800 /// ```
801 /// use heapless::FnvIndexMap;
802 ///
803 /// let mut map = FnvIndexMap::<_, _, 16>::new();
804 /// map.insert(1, "a").unwrap();
805 /// assert_eq!(map.get(&1), Some(&"a"));
806 /// assert_eq!(map.get(&2), None);
807 /// ```
808 pub fn get<Q>(&self, key: &Q) -> Option<&V>
809 where
810 K: Borrow<Q>,
811 Q: ?Sized + Hash + Eq,
812 {
813 self.find(key)
814 .map(|(_, found)| unsafe { &self.core.entries.get_unchecked(found).value })
815 }
816
817 /// Returns true if the map contains a value for the specified key.
818 ///
819 /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
820 /// form *must* match those for the key type.
821 ///
822 /// Computes in **O(1)** time (average).
823 ///
824 /// # Examples
825 ///
826 /// ```
827 /// use heapless::FnvIndexMap;
828 ///
829 /// let mut map = FnvIndexMap::<_, _, 8>::new();
830 /// map.insert(1, "a").unwrap();
831 /// assert_eq!(map.contains_key(&1), true);
832 /// assert_eq!(map.contains_key(&2), false);
833 /// ```
834 pub fn contains_key<Q>(&self, key: &Q) -> bool
835 where
836 K: Borrow<Q>,
837 Q: ?Sized + Eq + Hash,
838 {
839 self.find(key).is_some()
840 }
841
842 /// Returns a mutable reference to the value corresponding to the key.
843 ///
844 /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
845 /// form *must* match those for the key type.
846 ///
847 /// Computes in **O(1)** time (average).
848 ///
849 /// # Examples
850 ///
851 /// ```
852 /// use heapless::FnvIndexMap;
853 ///
854 /// let mut map = FnvIndexMap::<_, _, 8>::new();
855 /// map.insert(1, "a").unwrap();
856 /// if let Some(x) = map.get_mut(&1) {
857 /// *x = "b";
858 /// }
859 /// assert_eq!(map[&1], "b");
860 /// ```
861 pub fn get_mut<'v, Q>(&'v mut self, key: &Q) -> Option<&'v mut V>
862 where
863 K: Borrow<Q>,
864 Q: ?Sized + Hash + Eq,
865 {
866 if let Some((_, found)) = self.find(key) {
867 Some(unsafe { &mut self.core.entries.get_unchecked_mut(found).value })
868 } else {
869 None
870 }
871 }
872
873 /// Inserts a key-value pair into the map.
874 ///
875 /// If an equivalent key already exists in the map: the key remains and retains in its place in
876 /// the order, its corresponding value is updated with `value` and the older value is returned
877 /// inside `Some(_)`.
878 ///
879 /// If no equivalent key existed in the map: the new key-value pair is inserted, last in order,
880 /// and `None` is returned.
881 ///
882 /// Computes in **O(1)** time (average).
883 ///
884 /// See also entry if you you want to insert or modify or if you need to get the index of the
885 /// corresponding key-value pair.
886 ///
887 /// # Examples
888 ///
889 /// ```
890 /// use heapless::FnvIndexMap;
891 ///
892 /// let mut map = FnvIndexMap::<_, _, 8>::new();
893 /// assert_eq!(map.insert(37, "a"), Ok(None));
894 /// assert_eq!(map.is_empty(), false);
895 ///
896 /// map.insert(37, "b");
897 /// assert_eq!(map.insert(37, "c"), Ok(Some("b")));
898 /// assert_eq!(map[&37], "c");
899 /// ```
900 pub fn insert(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)> {
901 let hash = hash_with(&key, &self.build_hasher);
902 match self.core.insert(hash, key, value) {
903 Insert::Success(inserted) => Ok(inserted.old_value),
904 Insert::Full((k, v)) => Err((k, v)),
905 }
906 }
907
908 /// Same as [`swap_remove`](Self::swap_remove)
909 ///
910 /// Computes in **O(1)** time (average).
911 ///
912 /// # Examples
913 ///
914 /// ```
915 /// use heapless::FnvIndexMap;
916 ///
917 /// let mut map = FnvIndexMap::<_, _, 8>::new();
918 /// map.insert(1, "a").unwrap();
919 /// assert_eq!(map.remove(&1), Some("a"));
920 /// assert_eq!(map.remove(&1), None);
921 /// ```
922 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
923 where
924 K: Borrow<Q>,
925 Q: ?Sized + Hash + Eq,
926 {
927 self.swap_remove(key)
928 }
929
930 /// Remove the key-value pair equivalent to `key` and return its value.
931 ///
932 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the last element of the map
933 /// and popping it off. **This perturbs the postion of what used to be the last element!**
934 ///
935 /// Return `None` if `key` is not in map.
936 ///
937 /// Computes in **O(1)** time (average).
938 pub fn swap_remove<Q>(&mut self, key: &Q) -> Option<V>
939 where
940 K: Borrow<Q>,
941 Q: ?Sized + Hash + Eq,
942 {
943 self.find(key)
944 .map(|(probe, found)| self.core.remove_found(probe, found).1)
945 }
946
947 /// Retains only the elements specified by the predicate.
948 ///
949 /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
950 pub fn retain<F>(&mut self, mut f: F)
951 where
952 F: FnMut(&K, &mut V) -> bool,
953 {
954 self.core.retain_in_order(move |k, v| f(k, v));
955 }
956
957 /* Private API */
958 /// Return probe (indices) and position (entries)
959 fn find<Q>(&self, key: &Q) -> Option<(usize, usize)>
960 where
961 K: Borrow<Q>,
962 Q: ?Sized + Hash + Eq,
963 {
964 if self.len() == 0 {
965 return None;
966 }
967 let h = hash_with(key, &self.build_hasher);
968 self.core.find(h, key)
969 }
970}
971
972impl<'a, K, Q, V, S, const N: usize> ops::Index<&'a Q> for IndexMap<K, V, S, N>
973where
974 K: Eq + Hash + Borrow<Q>,
975 Q: ?Sized + Eq + Hash,
976 S: BuildHasher,
977{
978 type Output = V;
979
980 fn index(&self, key: &Q) -> &V {
981 self.get(key).expect(msg:"key not found")
982 }
983}
984
985impl<'a, K, Q, V, S, const N: usize> ops::IndexMut<&'a Q> for IndexMap<K, V, S, N>
986where
987 K: Eq + Hash + Borrow<Q>,
988 Q: ?Sized + Eq + Hash,
989 S: BuildHasher,
990{
991 fn index_mut(&mut self, key: &Q) -> &mut V {
992 self.get_mut(key).expect(msg:"key not found")
993 }
994}
995
996impl<K, V, S, const N: usize> Clone for IndexMap<K, V, S, N>
997where
998 K: Clone,
999 V: Clone,
1000 S: Clone,
1001{
1002 fn clone(&self) -> Self {
1003 Self {
1004 core: self.core.clone(),
1005 build_hasher: self.build_hasher.clone(),
1006 }
1007 }
1008}
1009
1010impl<K, V, S, const N: usize> fmt::Debug for IndexMap<K, V, S, N>
1011where
1012 K: fmt::Debug,
1013 V: fmt::Debug,
1014{
1015 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1016 f.debug_map().entries(self.iter()).finish()
1017 }
1018}
1019
1020impl<K, V, S, const N: usize> Default for IndexMap<K, V, S, N>
1021where
1022 S: Default,
1023{
1024 fn default() -> Self {
1025 // Const assert
1026 crate::sealed::greater_than_1::<N>();
1027 crate::sealed::power_of_two::<N>();
1028
1029 IndexMap {
1030 build_hasher: <_>::default(),
1031 core: CoreMap::new(),
1032 }
1033 }
1034}
1035
1036impl<K, V, S, S2, const N: usize, const N2: usize> PartialEq<IndexMap<K, V, S2, N2>>
1037 for IndexMap<K, V, S, N>
1038where
1039 K: Eq + Hash,
1040 V: Eq,
1041 S: BuildHasher,
1042 S2: BuildHasher,
1043{
1044 fn eq(&self, other: &IndexMap<K, V, S2, N2>) -> bool {
1045 self.len() == other.len()
1046 && self
1047 .iter()
1048 .all(|(key: &K, value: &V)| other.get(key).map_or(default:false, |v: &V| *value == *v))
1049 }
1050}
1051
1052impl<K, V, S, const N: usize> Eq for IndexMap<K, V, S, N>
1053where
1054 K: Eq + Hash,
1055 V: Eq,
1056 S: BuildHasher,
1057{
1058}
1059
1060impl<K, V, S, const N: usize> Extend<(K, V)> for IndexMap<K, V, S, N>
1061where
1062 K: Eq + Hash,
1063 S: BuildHasher,
1064{
1065 fn extend<I>(&mut self, iterable: I)
1066 where
1067 I: IntoIterator<Item = (K, V)>,
1068 {
1069 for (k: K, v: V) in iterable {
1070 self.insert(key:k, value:v).ok().unwrap();
1071 }
1072 }
1073}
1074
1075impl<'a, K, V, S, const N: usize> Extend<(&'a K, &'a V)> for IndexMap<K, V, S, N>
1076where
1077 K: Eq + Hash + Copy,
1078 V: Copy,
1079 S: BuildHasher,
1080{
1081 fn extend<I>(&mut self, iterable: I)
1082 where
1083 I: IntoIterator<Item = (&'a K, &'a V)>,
1084 {
1085 self.extend(iter:iterable.into_iter().map(|(&key: K, &value: V)| (key, value)))
1086 }
1087}
1088
1089impl<K, V, S, const N: usize> FromIterator<(K, V)> for IndexMap<K, V, S, N>
1090where
1091 K: Eq + Hash,
1092 S: BuildHasher + Default,
1093{
1094 fn from_iter<I>(iterable: I) -> Self
1095 where
1096 I: IntoIterator<Item = (K, V)>,
1097 {
1098 let mut map: IndexMap = IndexMap::default();
1099 map.extend(iter:iterable);
1100 map
1101 }
1102}
1103
1104#[derive(Clone)]
1105pub struct IntoIter<K, V, const N: usize> {
1106 entries: Vec<Bucket<K, V>, N>,
1107}
1108
1109impl<K, V, const N: usize> Iterator for IntoIter<K, V, N> {
1110 type Item = (K, V);
1111
1112 fn next(&mut self) -> Option<Self::Item> {
1113 self.entries.pop().map(|bucket: Bucket| (bucket.key, bucket.value))
1114 }
1115}
1116
1117impl<K, V, S, const N: usize> IntoIterator for IndexMap<K, V, S, N> {
1118 type Item = (K, V);
1119 type IntoIter = IntoIter<K, V, N>;
1120
1121 fn into_iter(self) -> Self::IntoIter {
1122 IntoIter {
1123 entries: self.core.entries,
1124 }
1125 }
1126}
1127
1128impl<'a, K, V, S, const N: usize> IntoIterator for &'a IndexMap<K, V, S, N> {
1129 type Item = (&'a K, &'a V);
1130 type IntoIter = Iter<'a, K, V>;
1131
1132 fn into_iter(self) -> Self::IntoIter {
1133 self.iter()
1134 }
1135}
1136
1137impl<'a, K, V, S, const N: usize> IntoIterator for &'a mut IndexMap<K, V, S, N> {
1138 type Item = (&'a K, &'a mut V);
1139 type IntoIter = IterMut<'a, K, V>;
1140
1141 fn into_iter(self) -> Self::IntoIter {
1142 self.iter_mut()
1143 }
1144}
1145
1146/// An iterator over the items of a [`IndexMap`].
1147///
1148/// This `struct` is created by the [`iter`](IndexMap::iter) method on [`IndexMap`]. See its
1149/// documentation for more.
1150pub struct Iter<'a, K, V> {
1151 iter: slice::Iter<'a, Bucket<K, V>>,
1152}
1153
1154impl<'a, K, V> Iterator for Iter<'a, K, V> {
1155 type Item = (&'a K, &'a V);
1156
1157 fn next(&mut self) -> Option<Self::Item> {
1158 self.iter.next().map(|bucket: &'a Bucket| (&bucket.key, &bucket.value))
1159 }
1160}
1161
1162impl<'a, K, V> Clone for Iter<'a, K, V> {
1163 fn clone(&self) -> Self {
1164 Self {
1165 iter: self.iter.clone(),
1166 }
1167 }
1168}
1169
1170/// A mutable iterator over the items of a [`IndexMap`].
1171///
1172/// This `struct` is created by the [`iter_mut`](IndexMap::iter_mut) method on [`IndexMap`]. See its
1173/// documentation for more.
1174pub struct IterMut<'a, K, V> {
1175 iter: slice::IterMut<'a, Bucket<K, V>>,
1176}
1177
1178impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1179 type Item = (&'a K, &'a mut V);
1180
1181 fn next(&mut self) -> Option<Self::Item> {
1182 self.iter
1183 .next()
1184 .map(|bucket: &'a mut Bucket| (&bucket.key, &mut bucket.value))
1185 }
1186}
1187
1188/// An iterator over the keys of a [`IndexMap`].
1189///
1190/// This `struct` is created by the [`keys`](IndexMap::keys) method on [`IndexMap`]. See its
1191/// documentation for more.
1192pub struct Keys<'a, K, V> {
1193 iter: slice::Iter<'a, Bucket<K, V>>,
1194}
1195
1196impl<'a, K, V> Iterator for Keys<'a, K, V> {
1197 type Item = &'a K;
1198
1199 fn next(&mut self) -> Option<Self::Item> {
1200 self.iter.next().map(|bucket: &'a Bucket| &bucket.key)
1201 }
1202}
1203
1204/// An iterator over the values of a [`IndexMap`].
1205///
1206/// This `struct` is created by the [`values`](IndexMap::values) method on [`IndexMap`]. See its
1207/// documentation for more.
1208pub struct Values<'a, K, V> {
1209 iter: slice::Iter<'a, Bucket<K, V>>,
1210}
1211
1212impl<'a, K, V> Iterator for Values<'a, K, V> {
1213 type Item = &'a V;
1214
1215 fn next(&mut self) -> Option<Self::Item> {
1216 self.iter.next().map(|bucket: &'a Bucket| &bucket.value)
1217 }
1218}
1219
1220/// A mutable iterator over the values of a [`IndexMap`].
1221///
1222/// This `struct` is created by the [`values_mut`](IndexMap::values_mut) method on [`IndexMap`]. See its
1223/// documentation for more.
1224pub struct ValuesMut<'a, K, V> {
1225 iter: slice::IterMut<'a, Bucket<K, V>>,
1226}
1227
1228impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1229 type Item = &'a mut V;
1230
1231 fn next(&mut self) -> Option<Self::Item> {
1232 self.iter.next().map(|bucket: &'a mut Bucket| &mut bucket.value)
1233 }
1234}
1235
1236fn hash_with<K, S>(key: &K, build_hasher: &S) -> HashValue
1237where
1238 K: ?Sized + Hash,
1239 S: BuildHasher,
1240{
1241 let mut h: ::Hasher = build_hasher.build_hasher();
1242 key.hash(&mut h);
1243 HashValue(h.finish() as u16)
1244}
1245
1246#[cfg(test)]
1247mod tests {
1248 use crate::{indexmap::Entry, FnvIndexMap};
1249
1250 use core::mem;
1251
1252 #[test]
1253 fn size() {
1254 const CAP: usize = 4;
1255 assert_eq!(
1256 mem::size_of::<FnvIndexMap<i16, u16, CAP>>(),
1257 CAP * mem::size_of::<u32>() + // indices
1258 CAP * (mem::size_of::<i16>() + // key
1259 mem::size_of::<u16>() + // value
1260 mem::size_of::<u16>() // hash
1261 ) + // buckets
1262 mem::size_of::<usize>() // entries.length
1263 )
1264 }
1265
1266 #[test]
1267 fn partial_eq() {
1268 {
1269 let mut a: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
1270 a.insert("k1", "v1").unwrap();
1271
1272 let mut b: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
1273 b.insert("k1", "v1").unwrap();
1274
1275 assert!(a == b);
1276
1277 b.insert("k2", "v2").unwrap();
1278
1279 assert!(a != b);
1280 }
1281
1282 {
1283 let mut a: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
1284 a.insert("k1", "v1").unwrap();
1285 a.insert("k2", "v2").unwrap();
1286
1287 let mut b: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
1288 b.insert("k2", "v2").unwrap();
1289 b.insert("k1", "v1").unwrap();
1290
1291 assert!(a == b);
1292 }
1293 }
1294
1295 #[test]
1296 fn into_iter() {
1297 let mut src: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
1298 src.insert("k1", "v1").unwrap();
1299 src.insert("k2", "v2").unwrap();
1300 src.insert("k3", "v3").unwrap();
1301 src.insert("k4", "v4").unwrap();
1302 let clone = src.clone();
1303 for (k, v) in clone.into_iter() {
1304 assert_eq!(v, *src.get(k).unwrap());
1305 }
1306 }
1307
1308 #[test]
1309 fn insert_replaces_on_full_map() {
1310 let mut a: FnvIndexMap<_, _, 2> = FnvIndexMap::new();
1311 a.insert("k1", "v1").unwrap();
1312 a.insert("k2", "v2").unwrap();
1313 a.insert("k1", "v2").unwrap();
1314 assert_eq!(a.get("k1"), a.get("k2"));
1315 }
1316
1317 // tests that use this constant take too long to run under miri, specially on CI, with a map of
1318 // this size so make the map smaller when using miri
1319 #[cfg(not(miri))]
1320 const MAP_SLOTS: usize = 4096;
1321 #[cfg(miri)]
1322 const MAP_SLOTS: usize = 64;
1323 fn almost_filled_map() -> FnvIndexMap<usize, usize, MAP_SLOTS> {
1324 let mut almost_filled = FnvIndexMap::new();
1325 for i in 1..MAP_SLOTS {
1326 almost_filled.insert(i, i).unwrap();
1327 }
1328 almost_filled
1329 }
1330
1331 #[test]
1332 fn entry_find() {
1333 let key = 0;
1334 let value = 0;
1335 let mut src = almost_filled_map();
1336 let entry = src.entry(key);
1337 match entry {
1338 Entry::Occupied(_) => {
1339 panic!("Found entry without inserting");
1340 }
1341 Entry::Vacant(v) => {
1342 assert_eq!(&key, v.key());
1343 assert_eq!(key, v.into_key());
1344 }
1345 }
1346 src.insert(key, value).unwrap();
1347 let entry = src.entry(key);
1348 match entry {
1349 Entry::Occupied(mut o) => {
1350 assert_eq!(&key, o.key());
1351 assert_eq!(&value, o.get());
1352 assert_eq!(&value, o.get_mut());
1353 assert_eq!(&value, o.into_mut());
1354 }
1355 Entry::Vacant(_) => {
1356 panic!("Entry not found");
1357 }
1358 }
1359 }
1360
1361 #[test]
1362 fn entry_vacant_insert() {
1363 let key = 0;
1364 let value = 0;
1365 let mut src = almost_filled_map();
1366 assert_eq!(MAP_SLOTS - 1, src.len());
1367 let entry = src.entry(key);
1368 match entry {
1369 Entry::Occupied(_) => {
1370 panic!("Entry found when empty");
1371 }
1372 Entry::Vacant(v) => {
1373 assert_eq!(value, *v.insert(value).unwrap());
1374 }
1375 };
1376 assert_eq!(value, *src.get(&key).unwrap())
1377 }
1378
1379 #[test]
1380 fn entry_occupied_insert() {
1381 let key = 0;
1382 let value = 0;
1383 let value2 = 5;
1384 let mut src = almost_filled_map();
1385 assert_eq!(MAP_SLOTS - 1, src.len());
1386 src.insert(key, value).unwrap();
1387 let entry = src.entry(key);
1388 match entry {
1389 Entry::Occupied(o) => {
1390 assert_eq!(value, o.insert(value2));
1391 }
1392 Entry::Vacant(_) => {
1393 panic!("Entry not found");
1394 }
1395 };
1396 assert_eq!(value2, *src.get(&key).unwrap())
1397 }
1398
1399 #[test]
1400 fn entry_remove_entry() {
1401 let key = 0;
1402 let value = 0;
1403 let mut src = almost_filled_map();
1404 src.insert(key, value).unwrap();
1405 assert_eq!(MAP_SLOTS, src.len());
1406 let entry = src.entry(key);
1407 match entry {
1408 Entry::Occupied(o) => {
1409 assert_eq!((key, value), o.remove_entry());
1410 }
1411 Entry::Vacant(_) => {
1412 panic!("Entry not found")
1413 }
1414 };
1415 assert_eq!(MAP_SLOTS - 1, src.len());
1416 }
1417
1418 #[test]
1419 fn entry_remove() {
1420 let key = 0;
1421 let value = 0;
1422 let mut src = almost_filled_map();
1423 src.insert(key, value).unwrap();
1424 assert_eq!(MAP_SLOTS, src.len());
1425 let entry = src.entry(key);
1426 match entry {
1427 Entry::Occupied(o) => {
1428 assert_eq!(value, o.remove());
1429 }
1430 Entry::Vacant(_) => {
1431 panic!("Entry not found");
1432 }
1433 };
1434 assert_eq!(MAP_SLOTS - 1, src.len());
1435 }
1436
1437 #[test]
1438 fn retain() {
1439 let mut none = almost_filled_map();
1440 none.retain(|_, _| false);
1441 assert!(none.is_empty());
1442
1443 let mut all = almost_filled_map();
1444 all.retain(|_, _| true);
1445 assert_eq!(all.len(), MAP_SLOTS - 1);
1446
1447 let mut even = almost_filled_map();
1448 even.retain(|_, &mut v| v % 2 == 0);
1449 assert_eq!(even.len(), (MAP_SLOTS - 1) / 2);
1450 for &v in even.values() {
1451 assert_eq!(v % 2, 0);
1452 }
1453
1454 let mut odd = almost_filled_map();
1455 odd.retain(|_, &mut v| v % 2 != 0);
1456 assert_eq!(odd.len(), MAP_SLOTS / 2);
1457 for &v in odd.values() {
1458 assert_ne!(v % 2, 0);
1459 }
1460 assert_eq!(odd.insert(2, 2), Ok(None));
1461 assert_eq!(odd.len(), (MAP_SLOTS / 2) + 1);
1462 }
1463
1464 #[test]
1465 fn entry_roll_through_all() {
1466 let mut src: FnvIndexMap<usize, usize, MAP_SLOTS> = FnvIndexMap::new();
1467 for i in 0..MAP_SLOTS {
1468 match src.entry(i) {
1469 Entry::Occupied(_) => {
1470 panic!("Entry found before insert");
1471 }
1472 Entry::Vacant(v) => {
1473 assert_eq!(i, *v.insert(i).unwrap());
1474 }
1475 }
1476 }
1477 let add_mod = 99;
1478 for i in 0..MAP_SLOTS {
1479 match src.entry(i) {
1480 Entry::Occupied(o) => {
1481 assert_eq!(i, o.insert(i + add_mod));
1482 }
1483 Entry::Vacant(_) => {
1484 panic!("Entry not found after insert");
1485 }
1486 }
1487 }
1488 for i in 0..MAP_SLOTS {
1489 match src.entry(i) {
1490 Entry::Occupied(o) => {
1491 assert_eq!((i, i + add_mod), o.remove_entry());
1492 }
1493 Entry::Vacant(_) => {
1494 panic!("Entry not found after insert");
1495 }
1496 }
1497 }
1498 for i in 0..MAP_SLOTS {
1499 assert!(matches!(src.entry(i), Entry::Vacant(_)));
1500 }
1501 assert!(src.is_empty());
1502 }
1503
1504 #[test]
1505 fn first_last() {
1506 let mut map = FnvIndexMap::<_, _, 4>::new();
1507
1508 assert_eq!(None, map.first());
1509 assert_eq!(None, map.last());
1510
1511 map.insert(0, 0).unwrap();
1512 map.insert(2, 2).unwrap();
1513
1514 assert_eq!(Some((&0, &0)), map.first());
1515 assert_eq!(Some((&2, &2)), map.last());
1516
1517 map.insert(1, 1).unwrap();
1518
1519 assert_eq!(Some((&1, &1)), map.last());
1520
1521 *map.first_mut().unwrap().1 += 1;
1522 *map.last_mut().unwrap().1 += 1;
1523
1524 assert_eq!(Some((&0, &1)), map.first());
1525 assert_eq!(Some((&1, &2)), map.last());
1526 }
1527
1528 #[test]
1529 fn keys_iter() {
1530 let map = almost_filled_map();
1531 for (&key, i) in map.keys().zip(1..MAP_SLOTS) {
1532 assert_eq!(key, i);
1533 }
1534 }
1535
1536 #[test]
1537 fn values_iter() {
1538 let map = almost_filled_map();
1539 for (&value, i) in map.values().zip(1..MAP_SLOTS) {
1540 assert_eq!(value, i);
1541 }
1542 }
1543
1544 #[test]
1545 fn values_mut_iter() {
1546 let mut map = almost_filled_map();
1547 for value in map.values_mut() {
1548 *value += 1;
1549 }
1550
1551 for (&value, i) in map.values().zip(1..MAP_SLOTS) {
1552 assert_eq!(value, i + 1);
1553 }
1554 }
1555}
1556