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