Vendor indexmap from heapless crate (#108)
1//! We used to have a dependency on the entirety of the [`heapless`] crate and
2//! therefore all of its dependencies. We only use heapless::FnvIndexMap from
3//! that crate and then only in the config
4//! `#[cfg(all(not(feature = "alloc"), not(feature = "std")))]` so we decided to
5//! vendor the relevant code. The only changes we have made are removing the entry
6//! api because we didn't need it, fixing some of the things clippy complained
7//! about, and migrating some of the doctests to unit tests. We advise future
8//! contributors to use caution if you need to touch this code.
9//! This is vendored well-tested code that we didn't want to modify so we opted to
10//! switch from `#![forbid(unsafe_code)]` to `#![deny(unsafe_code)] in our lib.rs,
11//! and to `#![allow(unsafe_code)]` for this file only for the reasons listed.
12//!
13//! [`heapless`]: https://github.com/japaric/heapless
14//! https://web.archive.org/web/20220609184943/https://github.com/japaric/heapless
15#![allow(unsafe_code)]
16
17// Copyright (c) 2017 Jorge Aparicio
18
19// Permission is hereby granted, free of charge, to any
20// person obtaining a copy of this software and associated
21// documentation files (the "Software"), to deal in the
22// Software without restriction, including without
23// limitation the rights to use, copy, modify, merge,
24// publish, distribute, sublicense, and/or sell copies of
25// the Software, and to permit persons to whom the Software
26// is furnished to do so, subject to the following
27// conditions:
28
29// The above copyright notice and this permission notice
30// shall be included in all copies or substantial portions
31// of the Software.
32
33// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
34// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
35// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
36// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
37// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
38// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
40// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
41// DEALINGS IN THE SOFTWARE.
42
43mod sealed {
44 // copied from
45 // https://github.com/japaric/heapless/blob/39273893deda34fa741f79438134fd4d4d7ac3ae/src/sealed.rs
46 // https://web.archive.org/web/20220609184545/https://github.com/japaric/heapless/blob/39273893deda34fa741f79438134fd4d4d7ac3ae/src/sealed.rs
47
48 #[allow(clippy::no_effect)]
49 #[allow(dead_code)]
50 #[allow(path_statements)]
51 pub(super) const fn smaller_than<const N: usize, const MAX: usize>() {
52 Assert::<N, MAX>::LESS;
53 }
54
55 #[allow(clippy::no_effect)]
56 #[allow(dead_code)]
57 #[allow(path_statements)]
58 pub(super) const fn greater_than_eq_0<const N: usize>() {
59 Assert::<N, 0>::GREATER_EQ;
60 }
61
62 #[allow(clippy::no_effect)]
63 #[allow(dead_code)]
64 #[allow(path_statements)]
65 pub(super) const fn greater_than_0<const N: usize>() {
66 Assert::<N, 0>::GREATER;
67 }
68
69 #[allow(clippy::no_effect)]
70 #[allow(dead_code)]
71 #[allow(path_statements)]
72 pub(super) const fn greater_than_1<const N: usize>() {
73 Assert::<N, 1>::GREATER;
74 }
75
76 #[allow(clippy::no_effect)]
77 #[allow(dead_code)]
78 #[allow(path_statements)]
79 pub(super) const fn power_of_two<const N: usize>() {
80 Assert::<N, 0>::GREATER;
81 Assert::<N, 0>::POWER_OF_TWO;
82 }
83
84 #[allow(clippy::no_effect)]
85 #[allow(dead_code)]
86 /// Const assert hack
87 pub(super) struct Assert<const L: usize, const R: usize>;
88
89 #[allow(dead_code)]
90 impl<const L: usize, const R: usize> Assert<L, R> {
91 /// Const assert hack
92 pub(super) const GREATER_EQ: usize = L - R;
93
94 /// Const assert hack
95 pub(super) const LESS_EQ: usize = R - L;
96
97 #[allow(clippy::erasing_op)]
98 /// Const assert hack
99 pub(super) const NOT_EQ: isize = 0 / (R as isize - L as isize);
100
101 /// Const assert hack
102 pub(super) const EQ: usize = (R - L) + (L - R);
103
104 /// Const assert hack
105 pub(super) const GREATER: usize = L - R - 1;
106
107 /// Const assert hack
108 pub(super) const LESS: usize = R - L - 1;
109
110 /// Const assert hack
111 pub(super) const POWER_OF_TWO: usize = 0 - (L & (L - 1));
112 }
113}
114
115mod vec {
116 // copied from
117 // https://github.com/japaric/heapless/blob/39273893deda34fa741f79438134fd4d4d7ac3ae/src/vec.rs
118 // https://web.archive.org/web/20220609184505/https://github.com/japaric/heapless/blob/39273893deda34fa741f79438134fd4d4d7ac3ae/src/vec.rs
119
120 use core::{cmp::Ordering, convert::TryFrom, fmt, hash, iter::FromIterator, mem::MaybeUninit, ops, ptr, slice};
121
122 /// A fixed capacity [`Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html)
123 pub(super) struct Vec<T, const N: usize> {
124 // NOTE order is important for optimizations. the `len` first layout lets the compiler optimize
125 // `new` to: reserve stack space and zero the first word. With the fields in the reverse order
126 // the compiler optimizes `new` to `memclr`-ing the *entire* stack space, including the `buffer`
127 // field which should be left uninitialized. Optimizations were last checked with Rust 1.60
128 len: usize,
129
130 buffer: [MaybeUninit<T>; N],
131 }
132
133 impl<T, const N: usize> Vec<T, N> {
134 const ELEM: MaybeUninit<T> = MaybeUninit::uninit();
135 const INIT: [MaybeUninit<T>; N] = [Self::ELEM; N]; // important for optimization of `new`
136
137 /// Constructs a new, empty vector with a fixed capacity of `N`
138 /// `Vec` `const` constructor; wrap the returned value in [`Vec`](../struct.Vec.html)
139 pub(super) const fn new() -> Self {
140 // Const assert N >= 0
141 super::sealed::greater_than_eq_0::<N>();
142
143 Self { len: 0, buffer: Self::INIT }
144 }
145
146 /// Constructs a new vector with a fixed capacity of `N` and fills it
147 /// with the provided slice.
148 #[inline]
149 pub(super) fn from_slice(other: &[T]) -> Result<Self, ()>
150 where
151 T: Clone,
152 {
153 let mut v = Vec::new();
154 v.extend_from_slice(other)?;
155 Ok(v)
156 }
157
158 /// Clones a vec into a new vec
159 pub(super) fn clone(&self) -> Self
160 where
161 T: Clone,
162 {
163 let mut new = Self::new();
164 // avoid `extend_from_slice` as that introduces a runtime check / panicking branch
165 for elem in self {
166 unsafe {
167 new.push_unchecked(elem.clone());
168 }
169 }
170 new
171 }
172
173 /// Extracts a slice containing the entire vector.
174 ///
175 /// Equivalent to `&s[..]`.
176 pub(super) fn as_slice(&self) -> &[T] {
177 // NOTE(unsafe) avoid bound checks in the slicing operation
178 // &buffer[..self.len]
179 unsafe { slice::from_raw_parts(self.buffer.as_ptr() as *const T, self.len) }
180 }
181
182 /// Returns the contents of the vector as an array of length `M` if the length
183 /// of the vector is exactly `M`, otherwise returns `Err(self)`.
184 pub(super) fn into_array<const M: usize>(self) -> Result<[T; M], Self> {
185 if self.len() == M {
186 // This is how the unstable `MaybeUninit::array_assume_init` method does it
187 let array = unsafe { (&self.buffer as *const _ as *const [T; M]).read() };
188
189 // We don't want `self`'s destructor to be called because that would drop all the
190 // items in the array
191 core::mem::forget(self);
192
193 Ok(array)
194 } else {
195 Err(self)
196 }
197 }
198
199 /// Extracts a mutable slice containing the entire vector.
200 ///
201 /// Equivalent to `&s[..]`.
202 pub(super) fn as_mut_slice(&mut self) -> &mut [T] {
203 // NOTE(unsafe) avoid bound checks in the slicing operation
204 // &mut buffer[..self.len]
205 unsafe { slice::from_raw_parts_mut(self.buffer.as_mut_ptr() as *mut T, self.len) }
206 }
207
208 /// Returns the maximum number of elements the vector can hold.
209 pub(super) const fn capacity(&self) -> usize {
210 N
211 }
212
213 /// Clears the vector, removing all values.
214 pub(super) fn clear(&mut self) {
215 self.truncate(0);
216 }
217
218 /// Extends the vec from an iterator.
219 ///
220 /// # Panic
221 ///
222 /// Panics if the vec cannot hold all elements of the iterator.
223 pub(super) fn extend<I>(&mut self, iter: I)
224 where
225 I: IntoIterator<Item = T>,
226 {
227 for elem in iter {
228 self.push(elem).ok().unwrap()
229 }
230 }
231
232 /// Clones and appends all elements in a slice to the `Vec`.
233 ///
234 /// Iterates over the slice `other`, clones each element, and then appends
235 /// it to this `Vec`. The `other` vector is traversed in-order.
236 pub(super) fn extend_from_slice(&mut self, other: &[T]) -> Result<(), ()>
237 where
238 T: Clone,
239 {
240 if self.len + other.len() > self.capacity() {
241 // won't fit in the `Vec`; don't modify anything and return an error
242 Err(())
243 } else {
244 for elem in other {
245 unsafe {
246 self.push_unchecked(elem.clone());
247 }
248 }
249 Ok(())
250 }
251 }
252
253 /// Removes the last element from a vector and returns it, or `None` if it's empty
254 pub(super) fn pop(&mut self) -> Option<T> {
255 if self.len != 0 {
256 Some(unsafe { self.pop_unchecked() })
257 } else {
258 None
259 }
260 }
261
262 /// Appends an `item` to the back of the collection
263 ///
264 /// Returns back the `item` if the vector is full
265 pub(super) fn push(&mut self, item: T) -> Result<(), T> {
266 if self.len < self.capacity() {
267 unsafe { self.push_unchecked(item) }
268 Ok(())
269 } else {
270 Err(item)
271 }
272 }
273
274 /// Removes the last element from a vector and returns it
275 ///
276 /// # Safety
277 ///
278 /// This assumes the vec to have at least one element.
279 pub(super) unsafe fn pop_unchecked(&mut self) -> T {
280 debug_assert!(!self.is_empty());
281
282 self.len -= 1;
283 (self.buffer.get_unchecked_mut(self.len).as_ptr() as *const T).read()
284 }
285
286 /// Appends an `item` to the back of the collection
287 ///
288 /// # Safety
289 ///
290 /// This assumes the vec is not full.
291 pub(super) unsafe fn push_unchecked(&mut self, item: T) {
292 // NOTE(ptr::write) the memory slot that we are about to write to is uninitialized. We
293 // use `ptr::write` to avoid running `T`'s destructor on the uninitialized memory
294 debug_assert!(!self.is_full());
295
296 *self.buffer.get_unchecked_mut(self.len) = MaybeUninit::new(item);
297
298 self.len += 1;
299 }
300
301 /// Shortens the vector, keeping the first `len` elements and dropping the rest.
302 pub(super) fn truncate(&mut self, len: usize) {
303 // This is safe because:
304 //
305 // * the slice passed to `drop_in_place` is valid; the `len > self.len`
306 // case avoids creating an invalid slice, and
307 // * the `len` of the vector is shrunk before calling `drop_in_place`,
308 // such that no value will be dropped twice in case `drop_in_place`
309 // were to panic once (if it panics twice, the program aborts).
310 unsafe {
311 // Note: It's intentional that this is `>` and not `>=`.
312 // Changing it to `>=` has negative performance
313 // implications in some cases. See rust-lang/rust#78884 for more.
314 if len > self.len {
315 return;
316 }
317 let remaining_len = self.len - len;
318 let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len);
319 self.len = len;
320 ptr::drop_in_place(s);
321 }
322 }
323
324 /// Resizes the Vec in-place so that len is equal to new_len.
325 ///
326 /// If new_len is greater than len, the Vec is extended by the
327 /// difference, with each additional slot filled with value. If
328 /// new_len is less than len, the Vec is simply truncated.
329 ///
330 /// See also [`resize_default`](struct.Vec.html#method.resize_default).
331 pub(super) fn resize(&mut self, new_len: usize, value: T) -> Result<(), ()>
332 where
333 T: Clone,
334 {
335 if new_len > self.capacity() {
336 return Err(());
337 }
338
339 if new_len > self.len {
340 while self.len < new_len {
341 self.push(value.clone()).ok();
342 }
343 } else {
344 self.truncate(new_len);
345 }
346
347 Ok(())
348 }
349
350 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
351 ///
352 /// If `new_len` is greater than `len`, the `Vec` is extended by the
353 /// difference, with each additional slot filled with `Default::default()`.
354 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
355 ///
356 /// See also [`resize`](struct.Vec.html#method.resize).
357 pub(super) fn resize_default(&mut self, new_len: usize) -> Result<(), ()>
358 where
359 T: Clone + Default,
360 {
361 self.resize(new_len, T::default())
362 }
363
364 /// Forces the length of the vector to `new_len`.
365 ///
366 /// This is a low-level operation that maintains none of the normal
367 /// invariants of the type. Normally changing the length of a vector
368 /// is done using one of the safe operations instead, such as
369 /// [`truncate`], [`resize`], [`extend`], or [`clear`].
370 ///
371 /// [`truncate`]: #method.truncate
372 /// [`resize`]: #method.resize
373 /// [`extend`]: https://doc.rust-lang.org/stable/core/iter/trait.Extend.html#tymethod.extend
374 /// [`clear`]: #method.clear
375 ///
376 /// # Safety
377 ///
378 /// - `new_len` must be less than or equal to [`capacity()`].
379 /// - The elements at `old_len..new_len` must be initialized.
380 ///
381 /// [`capacity()`]: #method.capacity
382 pub(super) unsafe fn set_len(&mut self, new_len: usize) {
383 debug_assert!(new_len <= self.capacity());
384
385 self.len = new_len
386 }
387
388 /// Removes an element from the vector and returns it.
389 ///
390 /// The removed element is replaced by the last element of the vector.
391 ///
392 /// This does not preserve ordering, but is O(1).
393 ///
394 /// # Panics
395 ///
396 /// Panics if `index` is out of bounds.
397 pub(super) fn swap_remove(&mut self, index: usize) -> T {
398 assert!(index < self.len);
399 unsafe { self.swap_remove_unchecked(index) }
400 }
401
402 /// Removes an element from the vector and returns it.
403 ///
404 /// The removed element is replaced by the last element of the vector.
405 ///
406 /// This does not preserve ordering, but is O(1).
407 ///
408 /// # Safety
409 ///
410 /// Assumes `index` within bounds.
411 pub(super) unsafe fn swap_remove_unchecked(&mut self, index: usize) -> T {
412 let length = self.len();
413 debug_assert!(index < length);
414 let value = ptr::read(self.as_ptr().add(index));
415 let base_ptr = self.as_mut_ptr();
416 ptr::copy(base_ptr.add(length - 1), base_ptr.add(index), 1);
417 self.len -= 1;
418 value
419 }
420
421 /// Returns true if the vec is full
422 #[inline]
423 pub(super) fn is_full(&self) -> bool {
424 self.len == self.capacity()
425 }
426
427 /// Returns true if the vec is empty
428 #[inline]
429 pub(super) fn is_empty(&self) -> bool {
430 self.len == 0
431 }
432
433 /// Returns `true` if `needle` is a prefix of the Vec.
434 ///
435 /// Always returns `true` if `needle` is an empty slice.
436 #[inline]
437 pub(super) fn starts_with(&self, needle: &[T]) -> bool
438 where
439 T: PartialEq,
440 {
441 let n = needle.len();
442 self.len >= n && needle == &self[..n]
443 }
444
445 /// Returns `true` if `needle` is a suffix of the Vec.
446 ///
447 /// Always returns `true` if `needle` is an empty slice.
448 #[inline]
449 pub(super) fn ends_with(&self, needle: &[T]) -> bool
450 where
451 T: PartialEq,
452 {
453 let (v, n) = (self.len(), needle.len());
454 v >= n && needle == &self[v - n..]
455 }
456 }
457
458 // Trait implementations
459
460 impl<T, const N: usize> Default for Vec<T, N> {
461 fn default() -> Self {
462 Self::new()
463 }
464 }
465
466 impl<T, const N: usize> fmt::Debug for Vec<T, N>
467 where
468 T: fmt::Debug,
469 {
470 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
471 <[T] as fmt::Debug>::fmt(self, f)
472 }
473 }
474
475 impl<const N: usize> fmt::Write for Vec<u8, N> {
476 fn write_str(&mut self, s: &str) -> fmt::Result {
477 match self.extend_from_slice(s.as_bytes()) {
478 Ok(()) => Ok(()),
479 Err(_) => Err(fmt::Error),
480 }
481 }
482 }
483
484 impl<T, const N: usize> Drop for Vec<T, N> {
485 fn drop(&mut self) {
486 // We drop each element used in the vector by turning into a &mut[T]
487 unsafe {
488 ptr::drop_in_place(self.as_mut_slice());
489 }
490 }
491 }
492
493 impl<'a, T: Clone, const N: usize> TryFrom<&'a [T]> for Vec<T, N> {
494 type Error = ();
495
496 fn try_from(slice: &'a [T]) -> Result<Self, Self::Error> {
497 Vec::from_slice(slice)
498 }
499 }
500
501 impl<T, const N: usize> Extend<T> for Vec<T, N> {
502 fn extend<I>(&mut self, iter: I)
503 where
504 I: IntoIterator<Item = T>,
505 {
506 self.extend(iter)
507 }
508 }
509
510 impl<'a, T, const N: usize> Extend<&'a T> for Vec<T, N>
511 where
512 T: 'a + Copy,
513 {
514 fn extend<I>(&mut self, iter: I)
515 where
516 I: IntoIterator<Item = &'a T>,
517 {
518 self.extend(iter.into_iter().cloned())
519 }
520 }
521
522 impl<T, const N: usize> hash::Hash for Vec<T, N>
523 where
524 T: core::hash::Hash,
525 {
526 fn hash<H: hash::Hasher>(&self, state: &mut H) {
527 <[T] as hash::Hash>::hash(self, state)
528 }
529 }
530
531 impl<T, const N: usize> hash32::Hash for Vec<T, N>
532 where
533 T: hash32::Hash,
534 {
535 fn hash<H: hash32::Hasher>(&self, state: &mut H) {
536 <[T] as hash32::Hash>::hash(self, state)
537 }
538 }
539
540 impl<'a, T, const N: usize> IntoIterator for &'a Vec<T, N> {
541 type Item = &'a T;
542 type IntoIter = slice::Iter<'a, T>;
543
544 fn into_iter(self) -> Self::IntoIter {
545 self.iter()
546 }
547 }
548
549 impl<'a, T, const N: usize> IntoIterator for &'a mut Vec<T, N> {
550 type Item = &'a mut T;
551 type IntoIter = slice::IterMut<'a, T>;
552
553 fn into_iter(self) -> Self::IntoIter {
554 self.iter_mut()
555 }
556 }
557
558 impl<T, const N: usize> FromIterator<T> for Vec<T, N> {
559 fn from_iter<I>(iter: I) -> Self
560 where
561 I: IntoIterator<Item = T>,
562 {
563 let mut vec = Vec::new();
564 for i in iter {
565 vec.push(i).ok().expect("Vec::from_iter overflow");
566 }
567 vec
568 }
569 }
570
571 /// An iterator that moves out of an [`Vec`][`Vec`].
572 ///
573 /// This struct is created by calling the `into_iter` method on [`Vec`][`Vec`].
574 ///
575 /// [`Vec`]: (https://doc.rust-lang.org/std/vec/struct.Vec.html)
576 ///
577 pub(super) struct IntoIter<T, const N: usize> {
578 vec: Vec<T, N>,
579 next: usize,
580 }
581
582 impl<T, const N: usize> Iterator for IntoIter<T, N> {
583 type Item = T;
584 fn next(&mut self) -> Option<Self::Item> {
585 if self.next < self.vec.len() {
586 let item = unsafe { (self.vec.buffer.get_unchecked_mut(self.next).as_ptr() as *const T).read() };
587 self.next += 1;
588 Some(item)
589 } else {
590 None
591 }
592 }
593 }
594
595 impl<T, const N: usize> Clone for IntoIter<T, N>
596 where
597 T: Clone,
598 {
599 fn clone(&self) -> Self {
600 let mut vec = Vec::new();
601
602 if self.next < self.vec.len() {
603 let s = unsafe {
604 slice::from_raw_parts(
605 (self.vec.buffer.as_ptr() as *const T).add(self.next),
606 self.vec.len() - self.next,
607 )
608 };
609 vec.extend_from_slice(s).ok();
610 }
611
612 Self { vec, next: 0 }
613 }
614 }
615
616 impl<T, const N: usize> Drop for IntoIter<T, N> {
617 fn drop(&mut self) {
618 unsafe {
619 // Drop all the elements that have not been moved out of vec
620 ptr::drop_in_place(&mut self.vec.as_mut_slice()[self.next..]);
621 // Prevent dropping of other elements
622 self.vec.len = 0;
623 }
624 }
625 }
626
627 impl<T, const N: usize> IntoIterator for Vec<T, N> {
628 type Item = T;
629 type IntoIter = IntoIter<T, N>;
630
631 fn into_iter(self) -> Self::IntoIter {
632 IntoIter { vec: self, next: 0 }
633 }
634 }
635
636 impl<A, B, const N1: usize, const N2: usize> PartialEq<Vec<B, N2>> for Vec<A, N1>
637 where
638 A: PartialEq<B>,
639 {
640 fn eq(&self, other: &Vec<B, N2>) -> bool {
641 <[A]>::eq(self, &**other)
642 }
643 }
644
645 // Vec<A, N> == [B]
646 impl<A, B, const N: usize> PartialEq<[B]> for Vec<A, N>
647 where
648 A: PartialEq<B>,
649 {
650 fn eq(&self, other: &[B]) -> bool {
651 <[A]>::eq(self, other)
652 }
653 }
654
655 // Vec<A, N> == &[B]
656 impl<A, B, const N: usize> PartialEq<&[B]> for Vec<A, N>
657 where
658 A: PartialEq<B>,
659 {
660 fn eq(&self, other: &&[B]) -> bool {
661 <[A]>::eq(self, &other[..])
662 }
663 }
664
665 // Vec<A, N> == &mut [B]
666 impl<A, B, const N: usize> PartialEq<&mut [B]> for Vec<A, N>
667 where
668 A: PartialEq<B>,
669 {
670 fn eq(&self, other: &&mut [B]) -> bool {
671 <[A]>::eq(self, &other[..])
672 }
673 }
674
675 // Vec<A, N> == [B; M]
676 // Equality does not require equal capacity
677 impl<A, B, const N: usize, const M: usize> PartialEq<[B; M]> for Vec<A, N>
678 where
679 A: PartialEq<B>,
680 {
681 fn eq(&self, other: &[B; M]) -> bool {
682 <[A]>::eq(self, &other[..])
683 }
684 }
685
686 // Vec<A, N> == &[B; M]
687 // Equality does not require equal capacity
688 impl<A, B, const N: usize, const M: usize> PartialEq<&[B; M]> for Vec<A, N>
689 where
690 A: PartialEq<B>,
691 {
692 fn eq(&self, other: &&[B; M]) -> bool {
693 <[A]>::eq(self, &other[..])
694 }
695 }
696
697 // Implements Eq if underlying data is Eq
698 impl<T, const N: usize> Eq for Vec<T, N> where T: Eq {}
699
700 impl<T, const N1: usize, const N2: usize> PartialOrd<Vec<T, N2>> for Vec<T, N1>
701 where
702 T: PartialOrd,
703 {
704 fn partial_cmp(&self, other: &Vec<T, N2>) -> Option<Ordering> {
705 PartialOrd::partial_cmp(&**self, &**other)
706 }
707 }
708
709 impl<T, const N: usize> Ord for Vec<T, N>
710 where
711 T: Ord,
712 {
713 #[inline]
714 fn cmp(&self, other: &Self) -> Ordering {
715 Ord::cmp(&**self, &**other)
716 }
717 }
718
719 impl<T, const N: usize> ops::Deref for Vec<T, N> {
720 type Target = [T];
721
722 fn deref(&self) -> &[T] {
723 self.as_slice()
724 }
725 }
726
727 impl<T, const N: usize> ops::DerefMut for Vec<T, N> {
728 fn deref_mut(&mut self) -> &mut [T] {
729 self.as_mut_slice()
730 }
731 }
732
733 impl<T, const N: usize> AsRef<Vec<T, N>> for Vec<T, N> {
734 #[inline]
735 fn as_ref(&self) -> &Self {
736 self
737 }
738 }
739
740 impl<T, const N: usize> AsMut<Vec<T, N>> for Vec<T, N> {
741 #[inline]
742 fn as_mut(&mut self) -> &mut Self {
743 self
744 }
745 }
746
747 impl<T, const N: usize> AsRef<[T]> for Vec<T, N> {
748 #[inline]
749 fn as_ref(&self) -> &[T] {
750 self
751 }
752 }
753
754 impl<T, const N: usize> AsMut<[T]> for Vec<T, N> {
755 #[inline]
756 fn as_mut(&mut self) -> &mut [T] {
757 self
758 }
759 }
760
761 impl<T, const N: usize> Clone for Vec<T, N>
762 where
763 T: Clone,
764 {
765 fn clone(&self) -> Self {
766 self.clone()
767 }
768 }
769
770 #[cfg(test)]
771 mod tests {
772 use super::Vec;
773 use core::fmt::Write;
774
775 // droppable macro copied from this file
776 // https://github.com/japaric/heapless/blob/39273893deda34fa741f79438134fd4d4d7ac3ae/src/test_helpers.rs
777 // https://web.archive.org/web/20220609184423/https://github.com/japaric/heapless/blob/39273893deda34fa741f79438134fd4d4d7ac3ae/src/test_helpers.rs
778 macro_rules! droppable {
779 () => {
780 static COUNT: core::sync::atomic::AtomicI32 = core::sync::atomic::AtomicI32::new(0);
781
782 #[derive(Eq, Ord, PartialEq, PartialOrd)]
783 struct Droppable(i32);
784 impl Droppable {
785 fn new() -> Self {
786 COUNT.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
787 Droppable(Self::count())
788 }
789
790 fn count() -> i32 {
791 COUNT.load(core::sync::atomic::Ordering::Relaxed)
792 }
793 }
794 impl Drop for Droppable {
795 fn drop(&mut self) {
796 COUNT.fetch_sub(1, core::sync::atomic::Ordering::Relaxed);
797 }
798 }
799 };
800 }
801
802 #[test]
803 fn static_new() {
804 static mut _V: Vec<i32, 4> = Vec::new();
805 }
806
807 #[test]
808 fn stack_new() {
809 let mut _v: Vec<i32, 4> = Vec::new();
810 }
811
812 #[test]
813 fn is_full_empty() {
814 let mut v: Vec<i32, 4> = Vec::new();
815
816 assert!(v.is_empty());
817 assert!(!v.is_full());
818
819 v.push(1).unwrap();
820 assert!(!v.is_empty());
821 assert!(!v.is_full());
822
823 v.push(1).unwrap();
824 assert!(!v.is_empty());
825 assert!(!v.is_full());
826
827 v.push(1).unwrap();
828 assert!(!v.is_empty());
829 assert!(!v.is_full());
830
831 v.push(1).unwrap();
832 assert!(!v.is_empty());
833 assert!(v.is_full());
834 }
835
836 #[test]
837 fn drop() {
838 droppable!();
839
840 {
841 let mut v: Vec<Droppable, 2> = Vec::new();
842 v.push(Droppable::new()).ok().unwrap();
843 v.push(Droppable::new()).ok().unwrap();
844 v.pop().unwrap();
845 }
846
847 assert_eq!(Droppable::count(), 0);
848
849 {
850 let mut v: Vec<Droppable, 2> = Vec::new();
851 v.push(Droppable::new()).ok().unwrap();
852 v.push(Droppable::new()).ok().unwrap();
853 }
854
855 assert_eq!(Droppable::count(), 0);
856 }
857
858 #[test]
859 fn eq() {
860 let mut xs: Vec<i32, 4> = Vec::new();
861 let mut ys: Vec<i32, 8> = Vec::new();
862
863 assert_eq!(xs, ys);
864
865 xs.push(1).unwrap();
866 ys.push(1).unwrap();
867
868 assert_eq!(xs, ys);
869 }
870
871 #[test]
872 fn cmp() {
873 let mut xs: Vec<i32, 4> = Vec::new();
874 let mut ys: Vec<i32, 4> = Vec::new();
875
876 assert_eq!(xs, ys);
877
878 xs.push(1).unwrap();
879 ys.push(2).unwrap();
880
881 assert!(xs < ys);
882 }
883
884 #[test]
885 fn cmp_heterogenous_size() {
886 let mut xs: Vec<i32, 4> = Vec::new();
887 let mut ys: Vec<i32, 8> = Vec::new();
888
889 assert_eq!(xs, ys);
890
891 xs.push(1).unwrap();
892 ys.push(2).unwrap();
893
894 assert!(xs < ys);
895 }
896
897 #[test]
898 fn full() {
899 let mut v: Vec<i32, 4> = Vec::new();
900
901 v.push(0).unwrap();
902 v.push(1).unwrap();
903 v.push(2).unwrap();
904 v.push(3).unwrap();
905
906 assert!(v.push(4).is_err());
907 }
908
909 #[test]
910 fn iter() {
911 let mut v: Vec<i32, 4> = Vec::new();
912
913 v.push(0).unwrap();
914 v.push(1).unwrap();
915 v.push(2).unwrap();
916 v.push(3).unwrap();
917
918 let mut items = v.iter();
919
920 assert_eq!(items.next(), Some(&0));
921 assert_eq!(items.next(), Some(&1));
922 assert_eq!(items.next(), Some(&2));
923 assert_eq!(items.next(), Some(&3));
924 assert_eq!(items.next(), None);
925 }
926
927 #[test]
928 fn iter_mut() {
929 let mut v: Vec<i32, 4> = Vec::new();
930
931 v.push(0).unwrap();
932 v.push(1).unwrap();
933 v.push(2).unwrap();
934 v.push(3).unwrap();
935
936 let mut items = v.iter_mut();
937
938 assert_eq!(items.next(), Some(&mut 0));
939 assert_eq!(items.next(), Some(&mut 1));
940 assert_eq!(items.next(), Some(&mut 2));
941 assert_eq!(items.next(), Some(&mut 3));
942 assert_eq!(items.next(), None);
943 }
944
945 #[test]
946 fn collect_from_iter() {
947 let slice = &[1, 2, 3];
948 let vec: Vec<i32, 4> = slice.iter().cloned().collect();
949 assert_eq!(&vec, slice);
950 }
951
952 #[test]
953 #[should_panic]
954 fn collect_from_iter_overfull() {
955 let slice = &[1, 2, 3];
956 let _vec = slice.iter().cloned().collect::<Vec<_, 2>>();
957 }
958
959 #[test]
960 fn iter_move() {
961 let mut v: Vec<i32, 4> = Vec::new();
962 v.push(0).unwrap();
963 v.push(1).unwrap();
964 v.push(2).unwrap();
965 v.push(3).unwrap();
966
967 let mut items = v.into_iter();
968
969 assert_eq!(items.next(), Some(0));
970 assert_eq!(items.next(), Some(1));
971 assert_eq!(items.next(), Some(2));
972 assert_eq!(items.next(), Some(3));
973 assert_eq!(items.next(), None);
974 }
975
976 #[test]
977 fn iter_move_drop() {
978 droppable!();
979
980 {
981 let mut vec: Vec<Droppable, 2> = Vec::new();
982 vec.push(Droppable::new()).ok().unwrap();
983 vec.push(Droppable::new()).ok().unwrap();
984 let mut items = vec.into_iter();
985 // Move all
986 let _ = items.next();
987 let _ = items.next();
988 }
989
990 assert_eq!(Droppable::count(), 0);
991
992 {
993 let mut vec: Vec<Droppable, 2> = Vec::new();
994 vec.push(Droppable::new()).ok().unwrap();
995 vec.push(Droppable::new()).ok().unwrap();
996 let _items = vec.into_iter();
997 // Move none
998 }
999
1000 assert_eq!(Droppable::count(), 0);
1001
1002 {
1003 let mut vec: Vec<Droppable, 2> = Vec::new();
1004 vec.push(Droppable::new()).ok().unwrap();
1005 vec.push(Droppable::new()).ok().unwrap();
1006 let mut items = vec.into_iter();
1007 let _ = items.next(); // Move partly
1008 }
1009
1010 assert_eq!(Droppable::count(), 0);
1011 }
1012
1013 #[test]
1014 fn push_and_pop() {
1015 let mut v: Vec<i32, 4> = Vec::new();
1016 assert_eq!(v.len(), 0);
1017
1018 assert_eq!(v.pop(), None);
1019 assert_eq!(v.len(), 0);
1020
1021 v.push(0).unwrap();
1022 assert_eq!(v.len(), 1);
1023
1024 assert_eq!(v.pop(), Some(0));
1025 assert_eq!(v.len(), 0);
1026
1027 assert_eq!(v.pop(), None);
1028 assert_eq!(v.len(), 0);
1029 }
1030
1031 #[test]
1032 fn resize_size_limit() {
1033 let mut v: Vec<u8, 4> = Vec::new();
1034
1035 v.resize(0, 0).unwrap();
1036 v.resize(4, 0).unwrap();
1037 v.resize(5, 0).err().expect("full");
1038 }
1039
1040 #[test]
1041 fn resize_length_cases() {
1042 let mut v: Vec<u8, 4> = Vec::new();
1043
1044 assert_eq!(v.len(), 0);
1045
1046 // Grow by 1
1047 v.resize(1, 0).unwrap();
1048 assert_eq!(v.len(), 1);
1049
1050 // Grow by 2
1051 v.resize(3, 0).unwrap();
1052 assert_eq!(v.len(), 3);
1053
1054 // Resize to current size
1055 v.resize(3, 0).unwrap();
1056 assert_eq!(v.len(), 3);
1057
1058 // Shrink by 1
1059 v.resize(2, 0).unwrap();
1060 assert_eq!(v.len(), 2);
1061
1062 // Shrink by 2
1063 v.resize(0, 0).unwrap();
1064 assert_eq!(v.len(), 0);
1065 }
1066
1067 #[test]
1068 fn resize_contents() {
1069 let mut v: Vec<u8, 4> = Vec::new();
1070
1071 // New entries take supplied value when growing
1072 v.resize(1, 17).unwrap();
1073 assert_eq!(v[0], 17);
1074
1075 // Old values aren't changed when growing
1076 v.resize(2, 18).unwrap();
1077 assert_eq!(v[0], 17);
1078 assert_eq!(v[1], 18);
1079
1080 // Old values aren't changed when length unchanged
1081 v.resize(2, 0).unwrap();
1082 assert_eq!(v[0], 17);
1083 assert_eq!(v[1], 18);
1084
1085 // Old values aren't changed when shrinking
1086 v.resize(1, 0).unwrap();
1087 assert_eq!(v[0], 17);
1088 }
1089
1090 #[test]
1091 fn resize_default() {
1092 let mut v: Vec<u8, 4> = Vec::new();
1093
1094 // resize_default is implemented using resize, so just check the
1095 // correct value is being written.
1096 v.resize_default(1).unwrap();
1097 assert_eq!(v[0], 0);
1098 }
1099
1100 #[test]
1101 fn write() {
1102 let mut v: Vec<u8, 4> = Vec::new();
1103 write!(v, "{:x}", 1234).unwrap();
1104 assert_eq!(&v[..], b"4d2");
1105 }
1106
1107 #[test]
1108 fn extend_from_slice() {
1109 let mut v: Vec<u8, 4> = Vec::new();
1110 assert_eq!(v.len(), 0);
1111 v.extend_from_slice(&[1, 2]).unwrap();
1112 assert_eq!(v.len(), 2);
1113 assert_eq!(v.as_slice(), &[1, 2]);
1114 v.extend_from_slice(&[3]).unwrap();
1115 assert_eq!(v.len(), 3);
1116 assert_eq!(v.as_slice(), &[1, 2, 3]);
1117 assert!(v.extend_from_slice(&[4, 5]).is_err());
1118 assert_eq!(v.len(), 3);
1119 assert_eq!(v.as_slice(), &[1, 2, 3]);
1120 }
1121
1122 #[test]
1123 fn from_slice() {
1124 // Successful construction
1125 let v: Vec<u8, 4> = Vec::from_slice(&[1, 2, 3]).unwrap();
1126 assert_eq!(v.len(), 3);
1127 assert_eq!(v.as_slice(), &[1, 2, 3]);
1128
1129 // Slice too large
1130 assert!(Vec::<u8, 2>::from_slice(&[1, 2, 3]).is_err());
1131 }
1132
1133 #[test]
1134 fn starts_with() {
1135 let v: Vec<_, 8> = Vec::from_slice(b"ab").unwrap();
1136 assert!(v.starts_with(&[]));
1137 assert!(v.starts_with(b""));
1138 assert!(v.starts_with(b"a"));
1139 assert!(v.starts_with(b"ab"));
1140 assert!(!v.starts_with(b"abc"));
1141 assert!(!v.starts_with(b"ba"));
1142 assert!(!v.starts_with(b"b"));
1143 }
1144
1145 #[test]
1146 fn ends_with() {
1147 let v: Vec<_, 8> = Vec::from_slice(b"ab").unwrap();
1148 assert!(v.ends_with(&[]));
1149 assert!(v.ends_with(b""));
1150 assert!(v.ends_with(b"b"));
1151 assert!(v.ends_with(b"ab"));
1152 assert!(!v.ends_with(b"abc"));
1153 assert!(!v.ends_with(b"ba"));
1154 assert!(!v.ends_with(b"a"));
1155 }
1156
1157 #[test]
1158 fn zero_capacity() {
1159 let mut v: Vec<u8, 0> = Vec::new();
1160 // Validate capacity
1161 assert_eq!(v.capacity(), 0);
1162
1163 // Make sure there is no capacity
1164 assert!(v.push(1).is_err());
1165
1166 // Validate length
1167 assert_eq!(v.len(), 0);
1168
1169 // Validate pop
1170 assert_eq!(v.pop(), None);
1171
1172 // Validate slice
1173 assert_eq!(v.as_slice(), &[]);
1174
1175 // Validate empty
1176 assert!(v.is_empty());
1177
1178 // Validate full
1179 assert!(v.is_full());
1180 }
1181
1182 #[test]
1183 fn vec() {
1184 // A vector with a fixed capacity of 8 elements allocated on the stack
1185 let mut vec = Vec::<_, 8>::new();
1186 vec.push(1).unwrap();
1187 vec.push(2).unwrap();
1188 assert_eq!(vec.len(), 2);
1189 assert_eq!(vec[0], 1);
1190 assert_eq!(vec.pop(), Some(2));
1191 assert_eq!(vec.len(), 1);
1192 vec[0] = 7;
1193 assert_eq!(vec[0], 7);
1194 vec.extend([1, 2, 3].iter().cloned());
1195 assert_eq!(*vec, [7, 1, 2, 3]);
1196 }
1197
1198 #[test]
1199 fn as_slice() {
1200 let buffer: Vec<u8, 5> = Vec::from_slice(&[1, 2, 3, 5, 8]).unwrap();
1201 assert_eq!(buffer.as_slice(), &[1, 2, 3, 5, 8]);
1202 }
1203
1204 #[test]
1205 fn into_array() {
1206 let buffer: Vec<u8, 42> = Vec::from_slice(&[1, 2, 3, 5, 8]).unwrap();
1207 let array: [u8; 5] = buffer.into_array().unwrap();
1208 assert_eq!(array, [1, 2, 3, 5, 8]);
1209 }
1210
1211 #[test]
1212 fn as_mut_slice() {
1213 let mut buffer: Vec<u8, 5> = Vec::from_slice(&[1, 2, 3, 5, 8]).unwrap();
1214 buffer[0] = 9;
1215 assert_eq!(buffer.as_slice(), &[9, 2, 3, 5, 8]);
1216 }
1217
1218 #[test]
1219 fn swap_remove() {
1220 let mut v: Vec<_, 8> = Vec::new();
1221 v.push("foo").unwrap();
1222 v.push("bar").unwrap();
1223 v.push("baz").unwrap();
1224 v.push("qux").unwrap();
1225 assert_eq!(v.swap_remove(1), "bar");
1226 assert_eq!(&*v, ["foo", "qux", "baz"]);
1227 assert_eq!(v.swap_remove(0), "foo");
1228 assert_eq!(&*v, ["baz", "qux"]);
1229 }
1230
1231 #[test]
1232 fn swap_remove_unchecked() {
1233 let mut v: Vec<_, 8> = Vec::new();
1234 v.push("foo").unwrap();
1235 v.push("bar").unwrap();
1236 v.push("baz").unwrap();
1237 v.push("qux").unwrap();
1238 assert_eq!(unsafe { v.swap_remove_unchecked(1) }, "bar");
1239 assert_eq!(&*v, ["foo", "qux", "baz"]);
1240 assert_eq!(unsafe { v.swap_remove_unchecked(0) }, "foo");
1241 assert_eq!(&*v, ["baz", "qux"]);
1242 }
1243 }
1244}
1245
1246// copied from
1247// https://github.com/japaric/heapless/blob/39273893deda34fa741f79438134fd4d4d7ac3ae/src/indexmap.rs
1248// https://web.archive.org/web/20220609184614/https://github.com/japaric/heapless/blob/39273893deda34fa741f79438134fd4d4d7ac3ae/src/indexmap.rs
1249
1250use core::{borrow::Borrow, fmt, iter::FromIterator, mem, num::NonZeroU32, ops, slice};
1251
1252use hash32::{BuildHasher, BuildHasherDefault, FnvHasher, Hash, Hasher};
1253
1254use vec::Vec;
1255
1256/// A [`sprawl::indexmap::IndexMap`](./struct.IndexMap.html) using the default FNV hasher
1257///
1258/// A list of all Methods and Traits available for `FnvIndexMap` can be found in
1259/// the [`sprawl::indexmap::IndexMap`](./struct.IndexMap.html) documentation.
1260pub type FnvIndexMap<K, V, const N: usize> = IndexMap<K, V, BuildHasherDefault<FnvHasher>, N>;
1261
1262#[derive(Clone, Copy, Eq, PartialEq)]
1263struct HashValue(u16);
1264
1265impl HashValue {
1266 fn desired_pos(&self, mask: usize) -> usize {
1267 usize::from(self.0) & mask
1268 }
1269
1270 fn probe_distance(&self, mask: usize, current: usize) -> usize {
1271 current.wrapping_sub(self.desired_pos(mask) as usize) & mask
1272 }
1273}
1274
1275#[derive(Clone)]
1276struct Bucket<K, V> {
1277 hash: HashValue,
1278 key: K,
1279 value: V,
1280}
1281
1282#[derive(Clone, Copy, PartialEq)]
1283struct Pos {
1284 // compact representation of `{ hash_value: u16, index: u16 }`
1285 // To get the most from `NonZero` we store the *value minus 1*. This way `None::Option<Pos>`
1286 // is equivalent to the very unlikely value of `{ hash_value: 0xffff, index: 0xffff }` instead
1287 // the more likely of `{ hash_value: 0x00, index: 0x00 }`
1288 nz: NonZeroU32,
1289}
1290
1291impl Pos {
1292 fn new(index: usize, hash: HashValue) -> Self {
1293 Pos { nz: unsafe { NonZeroU32::new_unchecked(((u32::from(hash.0) << 16) + index as u32).wrapping_add(1)) } }
1294 }
1295
1296 fn hash(&self) -> HashValue {
1297 HashValue((self.nz.get().wrapping_sub(1) >> 16) as u16)
1298 }
1299
1300 fn index(&self) -> usize {
1301 self.nz.get().wrapping_sub(1) as u16 as usize
1302 }
1303}
1304
1305enum Insert<K, V> {
1306 Success(Inserted<V>),
1307 Full((K, V)),
1308}
1309
1310struct Inserted<V> {
1311 #[allow(unused_code)]
1312 index: usize,
1313 old_value: Option<V>,
1314}
1315
1316macro_rules! probe_loop {
1317 ($probe_var: ident < $len: expr, $body: expr) => {
1318 loop {
1319 if $probe_var < $len {
1320 $body
1321 $probe_var += 1;
1322 } else {
1323 $probe_var = 0;
1324 }
1325 }
1326 }
1327}
1328
1329struct CoreMap<K, V, const N: usize> {
1330 entries: Vec<Bucket<K, V>, N>,
1331 indices: [Option<Pos>; N],
1332}
1333
1334impl<K, V, const N: usize> CoreMap<K, V, N> {
1335 const fn new() -> Self {
1336 const INIT: Option<Pos> = None;
1337
1338 CoreMap { entries: Vec::new(), indices: [INIT; N] }
1339 }
1340}
1341
1342impl<K, V, const N: usize> CoreMap<K, V, N>
1343where
1344 K: Eq + Hash,
1345{
1346 fn capacity() -> usize {
1347 N
1348 }
1349
1350 fn mask() -> usize {
1351 Self::capacity() - 1
1352 }
1353
1354 fn find<Q>(&self, hash: HashValue, query: &Q) -> Option<(usize, usize)>
1355 where
1356 K: Borrow<Q>,
1357 Q: ?Sized + Eq,
1358 {
1359 let mut probe = hash.desired_pos(Self::mask());
1360 let mut dist = 0;
1361
1362 probe_loop!(probe < self.indices.len(), {
1363 if let Some(pos) = self.indices[probe] {
1364 let entry_hash = pos.hash();
1365 // NOTE(i) we use unchecked indexing below
1366 let i = pos.index();
1367 debug_assert!(i < self.entries.len());
1368
1369 if dist > entry_hash.probe_distance(Self::mask(), probe) {
1370 // give up when probe distance is too long
1371 return None;
1372 } else if entry_hash == hash && unsafe { self.entries.get_unchecked(i).key.borrow() == query } {
1373 return Some((probe, i));
1374 }
1375 } else {
1376 return None;
1377 }
1378
1379 dist += 1;
1380 });
1381 }
1382
1383 fn insert(&mut self, hash: HashValue, key: K, value: V) -> Insert<K, V> {
1384 let mut probe = hash.desired_pos(Self::mask());
1385 let mut dist = 0;
1386
1387 probe_loop!(probe < self.indices.len(), {
1388 let pos = &mut self.indices[probe];
1389
1390 if let Some(pos) = *pos {
1391 let entry_hash = pos.hash();
1392 // NOTE(i) we use unchecked indexing below
1393 let i = pos.index();
1394 debug_assert!(i < self.entries.len());
1395
1396 let their_dist = entry_hash.probe_distance(Self::mask(), probe);
1397
1398 if their_dist < dist {
1399 if self.entries.is_full() {
1400 return Insert::Full((key, value));
1401 }
1402 // robin hood: steal the spot if it's better for us
1403 let index = self.entries.len();
1404 unsafe { self.entries.push_unchecked(Bucket { hash, key, value }) };
1405 return Insert::Success(Inserted {
1406 index: self.insert_phase_2(probe, Pos::new(index, hash)),
1407 old_value: None,
1408 });
1409 } else if entry_hash == hash && unsafe { self.entries.get_unchecked(i).key == key } {
1410 return Insert::Success(Inserted {
1411 index: i,
1412 old_value: Some(mem::replace(unsafe { &mut self.entries.get_unchecked_mut(i).value }, value)),
1413 });
1414 }
1415 } else {
1416 if self.entries.is_full() {
1417 return Insert::Full((key, value));
1418 }
1419 // empty bucket, insert here
1420 let index = self.entries.len();
1421 *pos = Some(Pos::new(index, hash));
1422 unsafe { self.entries.push_unchecked(Bucket { hash, key, value }) };
1423 return Insert::Success(Inserted { index, old_value: None });
1424 }
1425 dist += 1;
1426 });
1427 }
1428
1429 // phase 2 is post-insert where we forward-shift `Pos` in the indices.
1430 fn insert_phase_2(&mut self, mut probe: usize, mut old_pos: Pos) -> usize {
1431 probe_loop!(probe < self.indices.len(), {
1432 let pos = unsafe { self.indices.get_unchecked_mut(probe) };
1433
1434 let mut is_none = true; // work around lack of NLL
1435 if let Some(pos) = pos.as_mut() {
1436 old_pos = mem::replace(pos, old_pos);
1437 is_none = false;
1438 }
1439
1440 if is_none {
1441 *pos = Some(old_pos);
1442 return probe;
1443 }
1444 });
1445 }
1446
1447 fn remove_found(&mut self, probe: usize, found: usize) -> (K, V) {
1448 // index `probe` and entry `found` is to be removed
1449 // use swap_remove, but then we need to update the index that points
1450 // to the other entry that has to move
1451 self.indices[probe] = None;
1452 let entry = unsafe { self.entries.swap_remove_unchecked(found) };
1453
1454 // correct index that points to the entry that had to swap places
1455 if let Some(entry) = self.entries.get(found) {
1456 // was not last element
1457 // examine new element in `found` and find it in indices
1458 let mut probe = entry.hash.desired_pos(Self::mask());
1459
1460 probe_loop!(probe < self.indices.len(), {
1461 if let Some(pos) = self.indices[probe] {
1462 if pos.index() >= self.entries.len() {
1463 // found it
1464 self.indices[probe] = Some(Pos::new(found, entry.hash));
1465 break;
1466 }
1467 }
1468 });
1469 }
1470
1471 self.backward_shift_after_removal(probe);
1472
1473 (entry.key, entry.value)
1474 }
1475
1476 fn backward_shift_after_removal(&mut self, probe_at_remove: usize) {
1477 // backward shift deletion in self.indices
1478 // after probe, shift all non-ideally placed indices backward
1479 let mut last_probe = probe_at_remove;
1480 let mut probe = probe_at_remove + 1;
1481
1482 probe_loop!(probe < self.indices.len(), {
1483 if let Some(pos) = self.indices[probe] {
1484 let entry_hash = pos.hash();
1485
1486 if entry_hash.probe_distance(Self::mask(), probe) > 0 {
1487 unsafe { *self.indices.get_unchecked_mut(last_probe) = self.indices[probe] }
1488 self.indices[probe] = None;
1489 } else {
1490 break;
1491 }
1492 } else {
1493 break;
1494 }
1495 last_probe = probe;
1496 });
1497 }
1498}
1499
1500impl<K, V, const N: usize> Clone for CoreMap<K, V, N>
1501where
1502 K: Eq + Hash + Clone,
1503 V: Clone,
1504{
1505 fn clone(&self) -> Self {
1506 Self { entries: self.entries.clone(), indices: self.indices }
1507 }
1508}
1509
1510/// Fixed capacity [`IndexMap`](https://docs.rs/indexmap/1/indexmap/map/struct.IndexMap.html)
1511///
1512/// Note that you cannot use `IndexMap` directly, since it is generic around the hashing algorithm
1513/// in use. Pick a concrete instantiation like [`FnvIndexMap`](./type.FnvIndexMap.html) instead
1514/// or create your own.
1515///
1516/// Note that the capacity of the `IndexMap` must be a power of 2.
1517pub struct IndexMap<K, V, S, const N: usize> {
1518 core: CoreMap<K, V, N>,
1519 build_hasher: S,
1520}
1521
1522impl<K, V, S, const N: usize> IndexMap<K, V, BuildHasherDefault<S>, N> {
1523 /// Creates an empty `IndexMap`.
1524 pub const fn new() -> Self {
1525 // Const assert
1526 sealed::greater_than_1::<N>();
1527 sealed::power_of_two::<N>();
1528
1529 IndexMap { build_hasher: BuildHasherDefault::new(), core: CoreMap::new() }
1530 }
1531}
1532
1533impl<K, V, S, const N: usize> IndexMap<K, V, S, N>
1534where
1535 K: Eq + Hash,
1536 S: BuildHasher,
1537{
1538 /* Public API */
1539 /// Returns the number of elements the map can hold
1540 #[allow(unused_code)]
1541 fn capacity(&self) -> usize {
1542 N
1543 }
1544
1545 /// Return an iterator over the keys of the map, in their order
1546 #[allow(unused_code)]
1547 fn keys(&self) -> impl Iterator<Item = &K> {
1548 self.core.entries.iter().map(|bucket| &bucket.key)
1549 }
1550
1551 /// Return an iterator over the values of the map, in their order
1552 #[allow(unused_code)]
1553 fn values(&self) -> impl Iterator<Item = &V> {
1554 self.core.entries.iter().map(|bucket| &bucket.value)
1555 }
1556
1557 /// Return an iterator over mutable references to the the values of the map, in their order
1558 #[allow(unused_code)]
1559 fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
1560 self.core.entries.iter_mut().map(|bucket| &mut bucket.value)
1561 }
1562
1563 /// Return an iterator over the key-value pairs of the map, in their order
1564 fn iter(&self) -> Iter<'_, K, V> {
1565 Iter { iter: self.core.entries.iter() }
1566 }
1567
1568 /// Return an iterator over the key-value pairs of the map, in their order
1569 fn iter_mut(&mut self) -> IterMut<'_, K, V> {
1570 IterMut { iter: self.core.entries.iter_mut() }
1571 }
1572
1573 /// Get the first key-value pair
1574 ///
1575 /// Computes in **O(1)** time
1576 #[allow(unused_code)]
1577 fn first(&self) -> Option<(&K, &V)> {
1578 self.core.entries.first().map(|bucket| (&bucket.key, &bucket.value))
1579 }
1580
1581 /// Get the first key-value pair, with mutable access to the value
1582 ///
1583 /// Computes in **O(1)** time
1584 #[allow(unused_code)]
1585 fn first_mut(&mut self) -> Option<(&K, &mut V)> {
1586 self.core.entries.first_mut().map(|bucket| (&bucket.key, &mut bucket.value))
1587 }
1588
1589 /// Get the last key-value pair
1590 ///
1591 /// Computes in **O(1)** time
1592 #[allow(unused_code)]
1593 fn last(&self) -> Option<(&K, &V)> {
1594 self.core.entries.last().map(|bucket| (&bucket.key, &bucket.value))
1595 }
1596
1597 /// Get the last key-value pair, with mutable access to the value
1598 ///
1599 /// Computes in **O(1)** time
1600 #[allow(unused_code)]
1601 fn last_mut(&mut self) -> Option<(&K, &mut V)> {
1602 self.core.entries.last_mut().map(|bucket| (&bucket.key, &mut bucket.value))
1603 }
1604
1605 /// Return the number of key-value pairs in the map.
1606 ///
1607 /// Computes in **O(1)** time.
1608 fn len(&self) -> usize {
1609 self.core.entries.len()
1610 }
1611
1612 /// Returns true if the map contains no elements.
1613 ///
1614 /// Computes in **O(1)** time.
1615 fn is_empty(&self) -> bool {
1616 self.len() == 0
1617 }
1618
1619 /// Remove all key-value pairs in the map, while preserving its capacity.
1620 ///
1621 /// Computes in **O(n)** time.
1622 pub(crate) fn clear(&mut self) {
1623 self.core.entries.clear();
1624 for pos in self.core.indices.iter_mut() {
1625 *pos = None;
1626 }
1627 }
1628
1629 /// Returns a reference to the value corresponding to the key.
1630 ///
1631 /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
1632 /// form *must* match those for the key type.
1633 ///
1634 /// Computes in **O(1)** time (average).
1635 pub(crate) fn get<Q>(&self, key: &Q) -> Option<&V>
1636 where
1637 K: Borrow<Q>,
1638 Q: ?Sized + Hash + Eq,
1639 {
1640 self.find(key).map(|(_, found)| unsafe { &self.core.entries.get_unchecked(found).value })
1641 }
1642
1643 /// Returns true if the map contains a value for the specified key.
1644 ///
1645 /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
1646 /// form *must* match those for the key type.
1647 ///
1648 /// Computes in **O(1)** time (average).
1649 #[allow(unused_code)]
1650 fn contains_key<Q>(&self, key: &Q) -> bool
1651 where
1652 K: Borrow<Q>,
1653 Q: ?Sized + Eq + Hash,
1654 {
1655 self.find(key).is_some()
1656 }
1657
1658 /// Returns a mutable reference to the value corresponding to the key.
1659 ///
1660 /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
1661 /// form *must* match those for the key type.
1662 ///
1663 /// Computes in **O(1)** time (average).
1664 fn get_mut<'v, Q>(&'v mut self, key: &Q) -> Option<&'v mut V>
1665 where
1666 K: Borrow<Q>,
1667 Q: ?Sized + Hash + Eq,
1668 {
1669 if let Some((_, found)) = self.find(key) {
1670 Some(unsafe { &mut self.core.entries.get_unchecked_mut(found).value })
1671 } else {
1672 None
1673 }
1674 }
1675
1676 /// Inserts a key-value pair into the map.
1677 ///
1678 /// If an equivalent key already exists in the map: the key remains and retains in its place in
1679 /// the order, its corresponding value is updated with `value` and the older value is returned
1680 /// inside `Some(_)`.
1681 ///
1682 /// If no equivalent key existed in the map: the new key-value pair is inserted, last in order,
1683 /// and `None` is returned.
1684 ///
1685 /// Computes in **O(1)** time (average).
1686 ///
1687 /// See also entry if you you want to insert or modify or if you need to get the index of the
1688 /// corresponding key-value pair.
1689 pub(crate) fn insert(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)> {
1690 let hash = hash_with(&key, &self.build_hasher);
1691 match self.core.insert(hash, key, value) {
1692 Insert::Success(inserted) => Ok(inserted.old_value),
1693 Insert::Full((k, v)) => Err((k, v)),
1694 }
1695 }
1696
1697 /// Same as [`swap_remove`](struct.IndexMap.html#method.swap_remove)
1698 ///
1699 /// Computes in **O(1)** time (average).
1700 pub(crate) fn remove<Q>(&mut self, key: &Q) -> Option<V>
1701 where
1702 K: Borrow<Q>,
1703 Q: ?Sized + Hash + Eq,
1704 {
1705 self.swap_remove(key)
1706 }
1707
1708 /// Remove the key-value pair equivalent to `key` and return its value.
1709 ///
1710 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the last element of the map
1711 /// and popping it off. **This perturbs the postion of what used to be the last element!**
1712 ///
1713 /// Return `None` if `key` is not in map.
1714 ///
1715 /// Computes in **O(1)** time (average).
1716 fn swap_remove<Q>(&mut self, key: &Q) -> Option<V>
1717 where
1718 K: Borrow<Q>,
1719 Q: ?Sized + Hash + Eq,
1720 {
1721 self.find(key).map(|(probe, found)| self.core.remove_found(probe, found).1)
1722 }
1723
1724 /* Private API */
1725 /// Return probe (indices) and position (entries)
1726 fn find<Q>(&self, key: &Q) -> Option<(usize, usize)>
1727 where
1728 K: Borrow<Q>,
1729 Q: ?Sized + Hash + Eq,
1730 {
1731 if self.is_empty() {
1732 return None;
1733 }
1734 let h = hash_with(key, &self.build_hasher);
1735 self.core.find(h, key)
1736 }
1737}
1738
1739impl<'a, K, Q, V, S, const N: usize> ops::Index<&'a Q> for IndexMap<K, V, S, N>
1740where
1741 K: Eq + Hash + Borrow<Q>,
1742 Q: ?Sized + Eq + Hash,
1743 S: BuildHasher,
1744{
1745 type Output = V;
1746
1747 fn index(&self, key: &Q) -> &V {
1748 self.get(key).expect("key not found")
1749 }
1750}
1751
1752impl<'a, K, Q, V, S, const N: usize> ops::IndexMut<&'a Q> for IndexMap<K, V, S, N>
1753where
1754 K: Eq + Hash + Borrow<Q>,
1755 Q: ?Sized + Eq + Hash,
1756 S: BuildHasher,
1757{
1758 fn index_mut(&mut self, key: &Q) -> &mut V {
1759 self.get_mut(key).expect("key not found")
1760 }
1761}
1762
1763impl<K, V, S, const N: usize> Clone for IndexMap<K, V, S, N>
1764where
1765 K: Eq + Hash + Clone,
1766 V: Clone,
1767 S: Clone,
1768{
1769 fn clone(&self) -> Self {
1770 Self { core: self.core.clone(), build_hasher: self.build_hasher.clone() }
1771 }
1772}
1773
1774impl<K, V, S, const N: usize> fmt::Debug for IndexMap<K, V, S, N>
1775where
1776 K: Eq + Hash + fmt::Debug,
1777 V: fmt::Debug,
1778 S: BuildHasher,
1779{
1780 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1781 f.debug_map().entries(self.iter()).finish()
1782 }
1783}
1784
1785impl<K, V, S, const N: usize> Default for IndexMap<K, V, S, N>
1786where
1787 K: Eq + Hash,
1788 S: BuildHasher + Default,
1789{
1790 fn default() -> Self {
1791 IndexMap { build_hasher: <_>::default(), core: CoreMap::new() }
1792 }
1793}
1794
1795impl<K, V, S, S2, const N: usize, const N2: usize> PartialEq<IndexMap<K, V, S2, N2>> for IndexMap<K, V, S, N>
1796where
1797 K: Eq + Hash,
1798 V: Eq,
1799 S: BuildHasher,
1800 S2: BuildHasher,
1801{
1802 fn eq(&self, other: &IndexMap<K, V, S2, N2>) -> bool {
1803 self.len() == other.len() && self.iter().all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
1804 }
1805}
1806
1807impl<K, V, S, const N: usize> Eq for IndexMap<K, V, S, N>
1808where
1809 K: Eq + Hash,
1810 V: Eq,
1811 S: BuildHasher,
1812{
1813}
1814
1815impl<K, V, S, const N: usize> Extend<(K, V)> for IndexMap<K, V, S, N>
1816where
1817 K: Eq + Hash,
1818 S: BuildHasher,
1819{
1820 fn extend<I>(&mut self, iterable: I)
1821 where
1822 I: IntoIterator<Item = (K, V)>,
1823 {
1824 for (k, v) in iterable {
1825 self.insert(k, v).ok().unwrap();
1826 }
1827 }
1828}
1829
1830impl<'a, K, V, S, const N: usize> Extend<(&'a K, &'a V)> for IndexMap<K, V, S, N>
1831where
1832 K: Eq + Hash + Copy,
1833 V: Copy,
1834 S: BuildHasher,
1835{
1836 fn extend<I>(&mut self, iterable: I)
1837 where
1838 I: IntoIterator<Item = (&'a K, &'a V)>,
1839 {
1840 self.extend(iterable.into_iter().map(|(&key, &value)| (key, value)))
1841 }
1842}
1843
1844impl<K, V, S, const N: usize> FromIterator<(K, V)> for IndexMap<K, V, S, N>
1845where
1846 K: Eq + Hash,
1847 S: BuildHasher + Default,
1848{
1849 fn from_iter<I>(iterable: I) -> Self
1850 where
1851 I: IntoIterator<Item = (K, V)>,
1852 {
1853 let mut map = IndexMap::default();
1854 map.extend(iterable);
1855 map
1856 }
1857}
1858
1859#[derive(Clone)]
1860pub struct IntoIter<K, V, const N: usize> {
1861 entries: Vec<Bucket<K, V>, N>,
1862}
1863
1864impl<K, V, const N: usize> Iterator for IntoIter<K, V, N> {
1865 type Item = (K, V);
1866
1867 fn next(&mut self) -> Option<Self::Item> {
1868 self.entries.pop().map(|bucket| (bucket.key, bucket.value))
1869 }
1870}
1871
1872impl<K, V, S, const N: usize> IntoIterator for IndexMap<K, V, S, N>
1873where
1874 K: Eq + Hash,
1875 S: BuildHasher,
1876{
1877 type Item = (K, V);
1878 type IntoIter = IntoIter<K, V, N>;
1879
1880 fn into_iter(self) -> Self::IntoIter {
1881 IntoIter { entries: self.core.entries }
1882 }
1883}
1884
1885impl<'a, K, V, S, const N: usize> IntoIterator for &'a IndexMap<K, V, S, N>
1886where
1887 K: Eq + Hash,
1888 S: BuildHasher,
1889{
1890 type Item = (&'a K, &'a V);
1891 type IntoIter = Iter<'a, K, V>;
1892
1893 fn into_iter(self) -> Self::IntoIter {
1894 self.iter()
1895 }
1896}
1897
1898impl<'a, K, V, S, const N: usize> IntoIterator for &'a mut IndexMap<K, V, S, N>
1899where
1900 K: Eq + Hash,
1901 S: BuildHasher,
1902{
1903 type Item = (&'a K, &'a mut V);
1904 type IntoIter = IterMut<'a, K, V>;
1905
1906 fn into_iter(self) -> Self::IntoIter {
1907 self.iter_mut()
1908 }
1909}
1910
1911pub struct Iter<'a, K, V> {
1912 iter: slice::Iter<'a, Bucket<K, V>>,
1913}
1914
1915impl<'a, K, V> Iterator for Iter<'a, K, V> {
1916 type Item = (&'a K, &'a V);
1917
1918 fn next(&mut self) -> Option<Self::Item> {
1919 self.iter.next().map(|bucket| (&bucket.key, &bucket.value))
1920 }
1921}
1922
1923impl<'a, K, V> Clone for Iter<'a, K, V> {
1924 fn clone(&self) -> Self {
1925 Self { iter: self.iter.clone() }
1926 }
1927}
1928
1929pub struct IterMut<'a, K, V> {
1930 iter: slice::IterMut<'a, Bucket<K, V>>,
1931}
1932
1933impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1934 type Item = (&'a K, &'a mut V);
1935
1936 fn next(&mut self) -> Option<Self::Item> {
1937 self.iter.next().map(|bucket| (&bucket.key, &mut bucket.value))
1938 }
1939}
1940
1941fn hash_with<K, S>(key: &K, build_hasher: &S) -> HashValue
1942where
1943 K: ?Sized + Hash,
1944 S: BuildHasher,
1945{
1946 let mut h = build_hasher.build_hasher();
1947 key.hash(&mut h);
1948 HashValue(h.finish() as u16)
1949}
1950
1951#[cfg(test)]
1952mod tests {
1953 use super::FnvIndexMap;
1954
1955 use core::mem;
1956
1957 #[test]
1958 fn size() {
1959 const CAP: usize = 4;
1960 assert_eq!(
1961 mem::size_of::<FnvIndexMap<i16, u16, CAP>>(),
1962 CAP * mem::size_of::<u32>() + // indices
1963 CAP * (mem::size_of::<i16>() + // key
1964 mem::size_of::<u16>() + // value
1965 mem::size_of::<u16>() // hash
1966 ) + // buckets
1967 mem::size_of::<usize>() // entries.length
1968 )
1969 }
1970
1971 #[test]
1972 fn partial_eq() {
1973 {
1974 let mut a: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
1975 a.insert("k1", "v1").unwrap();
1976
1977 let mut b: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
1978 b.insert("k1", "v1").unwrap();
1979
1980 assert!(a == b);
1981
1982 b.insert("k2", "v2").unwrap();
1983
1984 assert!(a != b);
1985 }
1986
1987 {
1988 let mut a: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
1989 a.insert("k1", "v1").unwrap();
1990 a.insert("k2", "v2").unwrap();
1991
1992 let mut b: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
1993 b.insert("k2", "v2").unwrap();
1994 b.insert("k1", "v1").unwrap();
1995
1996 assert!(a == b);
1997 }
1998 }
1999
2000 #[test]
2001 fn into_iter() {
2002 let mut src: FnvIndexMap<_, _, 4> = FnvIndexMap::new();
2003 src.insert("k1", "v1").unwrap();
2004 src.insert("k2", "v2").unwrap();
2005 src.insert("k3", "v3").unwrap();
2006 src.insert("k4", "v4").unwrap();
2007 let clone = src.clone();
2008 for (k, v) in clone.into_iter() {
2009 assert_eq!(v, *src.get(k).unwrap());
2010 }
2011 }
2012
2013 #[test]
2014 fn insert_replaces_on_full_map() {
2015 let mut a: FnvIndexMap<_, _, 2> = FnvIndexMap::new();
2016 a.insert("k1", "v1").unwrap();
2017 a.insert("k2", "v2").unwrap();
2018 a.insert("k1", "v2").unwrap();
2019 assert_eq!(a.get("k1"), a.get("k2"));
2020 }
2021
2022 #[test]
2023 fn first_last() {
2024 let mut map = FnvIndexMap::<_, _, 4>::new();
2025
2026 assert_eq!(None, map.first());
2027 assert_eq!(None, map.last());
2028
2029 map.insert(0, 0).unwrap();
2030 map.insert(2, 2).unwrap();
2031
2032 assert_eq!(Some((&0, &0)), map.first());
2033 assert_eq!(Some((&2, &2)), map.last());
2034
2035 map.insert(1, 1).unwrap();
2036
2037 assert_eq!(Some((&1, &1)), map.last());
2038
2039 *map.first_mut().unwrap().1 += 1;
2040 *map.last_mut().unwrap().1 += 1;
2041
2042 assert_eq!(Some((&0, &1)), map.first());
2043 assert_eq!(Some((&1, &2)), map.last());
2044 }
2045
2046 #[cfg(feature = "std")]
2047 #[test]
2048 fn fnv_index_map() {
2049 // A hash map with a capacity of 16 key-value pairs allocated on the stack
2050 let mut book_reviews = FnvIndexMap::<_, _, 16>::new();
2051 // review some books.
2052 book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.").unwrap();
2053 book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.").unwrap();
2054 book_reviews.insert("Pride and Prejudice", "Very enjoyable.").unwrap();
2055 book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.").unwrap();
2056 // check for a specific one.
2057 if !book_reviews.contains_key("Les Misérables") {
2058 println!("We've got {} reviews, but Les Misérables ain't one.", book_reviews.len());
2059 }
2060 // oops, this review has a lot of spelling mistakes, let's delete it.
2061 book_reviews.remove("The Adventures of Sherlock Holmes");
2062 // look up the values associated with some keys.
2063 let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
2064 for book in &to_find {
2065 match book_reviews.get(book) {
2066 Some(review) => println!("{}: {}", book, review),
2067 None => println!("{} is unreviewed.", book),
2068 }
2069 }
2070 // iterate over everything.
2071 for (book, review) in &book_reviews {
2072 println!("{}: \"{}\"", book, review);
2073 }
2074 }
2075
2076 #[test]
2077 fn keys() {
2078 let mut map = FnvIndexMap::<_, _, 16>::new();
2079 map.insert("a", 1).unwrap();
2080 map.insert("b", 2).unwrap();
2081 map.insert("c", 3).unwrap();
2082 }
2083
2084 #[test]
2085 fn values() {
2086 let mut map = FnvIndexMap::<_, _, 16>::new();
2087 map.insert("a", 1).unwrap();
2088 map.insert("b", 2).unwrap();
2089 map.insert("c", 3).unwrap();
2090 }
2091
2092 #[test]
2093 fn values_mut() {
2094 let mut map = FnvIndexMap::<_, _, 16>::new();
2095 map.insert("a", 1).unwrap();
2096 map.insert("b", 2).unwrap();
2097 map.insert("c", 3).unwrap();
2098 for val in map.values_mut() {
2099 *val += 10;
2100 }
2101 }
2102
2103 #[cfg(feature = "std")]
2104 #[test]
2105 fn iter() {
2106 let mut map = FnvIndexMap::<_, _, 16>::new();
2107 map.insert("a", 1).unwrap();
2108 map.insert("b", 2).unwrap();
2109 map.insert("c", 3).unwrap();
2110 for (key, val) in map.iter() {
2111 println!("key: {} val: {}", key, val);
2112 }
2113 }
2114
2115 #[test]
2116 fn iter_mut() {
2117 let mut map = FnvIndexMap::<_, _, 16>::new();
2118 map.insert("a", 1).unwrap();
2119 map.insert("b", 2).unwrap();
2120 map.insert("c", 3).unwrap();
2121 for (_, val) in map.iter_mut() {
2122 *val = 2;
2123 }
2124 }
2125
2126 #[test]
2127 fn len() {
2128 let mut a = FnvIndexMap::<_, _, 16>::new();
2129 assert_eq!(a.len(), 0);
2130 a.insert(1, "a").unwrap();
2131 assert_eq!(a.len(), 1);
2132 }
2133
2134 #[test]
2135 fn is_empty() {
2136 let mut a = FnvIndexMap::<_, _, 16>::new();
2137 assert!(a.is_empty());
2138 a.insert(1, "a").unwrap();
2139 assert!(!a.is_empty());
2140 }
2141
2142 #[test]
2143 fn clear() {
2144 let mut a = FnvIndexMap::<_, _, 16>::new();
2145 a.insert(1, "a").unwrap();
2146 a.clear();
2147 assert!(a.is_empty());
2148 }
2149
2150 #[test]
2151 fn get() {
2152 let mut map = FnvIndexMap::<_, _, 16>::new();
2153 map.insert(1, "a").unwrap();
2154 assert_eq!(map.get(&1), Some(&"a"));
2155 assert_eq!(map.get(&2), None);
2156 }
2157
2158 #[test]
2159 fn contains_key() {
2160 let mut map = FnvIndexMap::<_, _, 8>::new();
2161 map.insert(1, "a").unwrap();
2162 assert_eq!(map.contains_key(&1), true);
2163 assert_eq!(map.contains_key(&2), false);
2164 }
2165
2166 #[test]
2167 fn get_mut() {
2168 let mut map = FnvIndexMap::<_, _, 8>::new();
2169 map.insert(1, "a").unwrap();
2170 if let Some(x) = map.get_mut(&1) {
2171 *x = "b";
2172 }
2173 assert_eq!(map[&1], "b");
2174 }
2175
2176 #[test]
2177 fn insert() {
2178 let mut map = FnvIndexMap::<_, _, 8>::new();
2179 assert_eq!(map.insert(37, "a"), Ok(None));
2180 assert_eq!(map.is_empty(), false);
2181 map.insert(37, "b").unwrap();
2182 assert_eq!(map.insert(37, "c"), Ok(Some("b")));
2183 assert_eq!(map[&37], "c");
2184 }
2185
2186 #[test]
2187 fn remove() {
2188 let mut map = FnvIndexMap::<_, _, 8>::new();
2189 map.insert(1, "a").unwrap();
2190 assert_eq!(map.remove(&1), Some("a"));
2191 assert_eq!(map.remove(&1), None);
2192 }
2193}