1 //! `IndexMap` is a hash table where the iteration order of the key-value
2 //! pairs is independent of the hash values of the keys.
3
4 mod core;
5
6 pub use crate::mutable_keys::MutableKeys;
7
8 #[cfg(feature = "rayon")]
9 pub use crate::rayon::map as rayon;
10
11 use crate::vec::{self, Vec};
12 use ::core::cmp::Ordering;
13 use ::core::fmt;
14 use ::core::hash::{BuildHasher, Hash, Hasher};
15 use ::core::iter::FromIterator;
16 use ::core::ops::{Index, IndexMut, RangeBounds};
17 use ::core::slice::{Iter as SliceIter, IterMut as SliceIterMut};
18
19 #[cfg(has_std)]
20 use std::collections::hash_map::RandomState;
21
22 use self::core::IndexMapCore;
23 use crate::equivalent::Equivalent;
24 use crate::util::third;
25 use crate::{Bucket, Entries, HashValue};
26
27 pub use self::core::{Entry, OccupiedEntry, VacantEntry};
28
29 /// A hash table where the iteration order of the key-value pairs is independent
30 /// of the hash values of the keys.
31 ///
32 /// The interface is closely compatible with the standard `HashMap`, but also
33 /// has additional features.
34 ///
35 /// # Order
36 ///
37 /// The key-value pairs have a consistent order that is determined by
38 /// the sequence of insertion and removal calls on the map. The order does
39 /// not depend on the keys or the hash function at all.
40 ///
41 /// All iterators traverse the map in *the order*.
42 ///
43 /// The insertion order is preserved, with **notable exceptions** like the
44 /// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of
45 /// course result in a new order, depending on the sorting order.
46 ///
47 /// # Indices
48 ///
49 /// The key-value pairs are indexed in a compact range without holes in the
50 /// range `0..self.len()`. For example, the method `.get_full` looks up the
51 /// index for a key, and the method `.get_index` looks up the key-value pair by
52 /// index.
53 ///
54 /// # Examples
55 ///
56 /// ```
57 /// use indexmap::IndexMap;
58 ///
59 /// // count the frequency of each letter in a sentence.
60 /// let mut letters = IndexMap::new();
61 /// for ch in "a short treatise on fungi".chars() {
parse_headers<T>( bytes: &mut BytesMut, ctx: ParseContext<'_>, ) -> ParseResult<T::Incoming> where T: Http1Transaction,62 /// *letters.entry(ch).or_insert(0) += 1;
63 /// }
64 ///
65 /// assert_eq!(letters[&'s'], 2);
66 /// assert_eq!(letters[&'t'], 3);
67 /// assert_eq!(letters[&'u'], 1);
68 /// assert_eq!(letters.get(&'y'), None);
69 /// ```
70 #[cfg(has_std)]
71 pub struct IndexMap<K, V, S = RandomState> {
72 core: IndexMapCore<K, V>,
73 hash_builder: S,
74 }
75 #[cfg(not(has_std))]
76 pub struct IndexMap<K, V, S> {
77 core: IndexMapCore<K, V>,
78 hash_builder: S,
79 }
80
81 impl<K, V, S> Clone for IndexMap<K, V, S>
82 where
83 K: Clone,
84 V: Clone,
85 S: Clone,
86 {
87 fn clone(&self) -> Self {
88 IndexMap {
89 core: self.core.clone(),
90 hash_builder: self.hash_builder.clone(),
91 }
92 }
93
94 fn clone_from(&mut self, other: &Self) {
95 self.core.clone_from(&other.core);
96 self.hash_builder.clone_from(&other.hash_builder);
97 }
encode_headers<T>( enc: Encode<'_, T::Outgoing>, dst: &mut Vec<u8>, ) -> crate::Result<Encoder> where T: Http1Transaction,98 }
99
100 impl<K, V, S> Entries for IndexMap<K, V, S> {
101 type Entry = Bucket<K, V>;
102
103 #[inline]
104 fn into_entries(self) -> Vec<Self::Entry> {
105 self.core.into_entries()
106 }
107
108 #[inline]
109 fn as_entries(&self) -> &[Self::Entry] {
110 self.core.as_entries()
111 }
112
113 #[inline]
114 fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
115 self.core.as_entries_mut()
116 }
117
118 fn with_entries<F>(&mut self, f: F)
119 where
120 F: FnOnce(&mut [Self::Entry]),
121 {
122 self.core.with_entries(f);
123 }
124 }
125
126 impl<K, V, S> fmt::Debug for IndexMap<K, V, S>
127 where
128 K: fmt::Debug,
129 V: fmt::Debug,
130 {
131 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
132 if cfg!(not(feature = "test_debug")) {
133 f.debug_map().entries(self.iter()).finish()
134 } else {
135 // Let the inner `IndexMapCore` print all of its details
136 f.debug_struct("IndexMap")
137 .field("core", &self.core)
138 .finish()
139 }
140 }
141 }
142
143 #[cfg(has_std)]
144 impl<K, V> IndexMap<K, V> {
145 /// Create a new map. (Does not allocate.)
146 #[inline]
147 pub fn new() -> Self {
148 Self::with_capacity(0)
149 }
150
151 /// Create a new map with capacity for `n` key-value pairs. (Does not
152 /// allocate if `n` is zero.)
153 ///
154 /// Computes in **O(n)** time.
155 #[inline]
156 pub fn with_capacity(n: usize) -> Self {
157 Self::with_capacity_and_hasher(n, <_>::default())
158 }
159 }
160
161 impl<K, V, S> IndexMap<K, V, S> {
162 /// Create a new map with capacity for `n` key-value pairs. (Does not
163 /// allocate if `n` is zero.)
164 ///
165 /// Computes in **O(n)** time.
166 #[inline]
167 pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self {
168 if n == 0 {
169 IndexMap {
170 core: IndexMapCore::new(),
171 hash_builder,
172 }
173 } else {
174 IndexMap {
175 core: IndexMapCore::with_capacity(n),
176 hash_builder,
177 }
178 }
179 }
180
181 /// Create a new map with `hash_builder`
182 pub fn with_hasher(hash_builder: S) -> Self {
183 Self::with_capacity_and_hasher(0, hash_builder)
184 }
185
186 /// Computes in **O(1)** time.
187 pub fn capacity(&self) -> usize {
188 self.core.capacity()
189 }
190
191 /// Return a reference to the map's `BuildHasher`.
192 pub fn hasher(&self) -> &S {
193 &self.hash_builder
194 }
195
196 /// Return the number of key-value pairs in the map.
197 ///
198 /// Computes in **O(1)** time.
199 #[inline]
200 pub fn len(&self) -> usize {
201 self.core.len()
202 }
203
204 /// Returns true if the map contains no elements.
205 ///
206 /// Computes in **O(1)** time.
207 #[inline]
208 pub fn is_empty(&self) -> bool {
209 self.len() == 0
210 }
211
212 /// Return an iterator over the key-value pairs of the map, in their order
213 pub fn iter(&self) -> Iter<'_, K, V> {
214 Iter {
215 iter: self.as_entries().iter(),
216 }
217 }
218
219 /// Return an iterator over the key-value pairs of the map, in their order
220 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
221 IterMut {
222 iter: self.as_entries_mut().iter_mut(),
223 }
224 }
225
226 /// Return an iterator over the keys of the map, in their order
227 pub fn keys(&self) -> Keys<'_, K, V> {
228 Keys {
229 iter: self.as_entries().iter(),
230 }
231 }
232
233 /// Return an iterator over the values of the map, in their order
234 pub fn values(&self) -> Values<'_, K, V> {
235 Values {
236 iter: self.as_entries().iter(),
237 }
238 }
239
240 /// Return an iterator over mutable references to the values of the map,
241 /// in their order
242 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
243 ValuesMut {
244 iter: self.as_entries_mut().iter_mut(),
245 }
246 }
247
248 /// Remove all key-value pairs in the map, while preserving its capacity.
249 ///
250 /// Computes in **O(n)** time.
251 pub fn clear(&mut self) {
252 self.core.clear();
253 }
254
255 /// Shortens the map, keeping the first `len` elements and dropping the rest.
256 ///
257 /// If `len` is greater than the map's current length, this has no effect.
258 pub fn truncate(&mut self, len: usize) {
259 self.core.truncate(len);
260 }
261
262 /// Clears the `IndexMap` in the given index range, returning those
263 /// key-value pairs as a drain iterator.
264 ///
265 /// The range may be any type that implements `RangeBounds<usize>`,
266 /// including all of the `std::ops::Range*` types, or even a tuple pair of
267 /// `Bound` start and end values. To drain the map entirely, use `RangeFull`
268 /// like `map.drain(..)`.
269 ///
270 /// This shifts down all entries following the drained range to fill the
271 /// gap, and keeps the allocated memory for reuse.
272 ///
273 /// ***Panics*** if the starting point is greater than the end point or if
274 /// the end point is greater than the length of the map.
275 pub fn drain<R>(&mut self, range: R) -> Drain<'_, K, V>
276 where
277 R: RangeBounds<usize>,
278 {
279 Drain {
280 iter: self.core.drain(range),
281 }
282 }
283
284 /// Splits the collection into two at the given index.
285 ///
286 /// Returns a newly allocated map containing the elements in the range
287 /// `[at, len)`. After the call, the original map will be left containing
288 /// the elements `[0, at)` with its previous capacity unchanged.
289 ///
290 /// ***Panics*** if `at > len`.
291 pub fn split_off(&mut self, at: usize) -> Self
292 where
293 S: Clone,
294 {
295 Self {
296 core: self.core.split_off(at),
297 hash_builder: self.hash_builder.clone(),
298 }
299 }
300 }
301
302 impl<K, V, S> IndexMap<K, V, S>
303 where
304 K: Hash + Eq,
305 S: BuildHasher,
306 {
307 /// Reserve capacity for `additional` more key-value pairs.
308 ///
309 /// Computes in **O(n)** time.
310 pub fn reserve(&mut self, additional: usize) {
311 self.core.reserve(additional);
312 }
313
314 /// Shrink the capacity of the map as much as possible.
315 ///
316 /// Computes in **O(n)** time.
317 pub fn shrink_to_fit(&mut self) {
318 self.core.shrink_to_fit();
319 }
320
321 fn hash<Q: ?Sized + Hash>(&self, key: &Q) -> HashValue {
encode(mut msg: Encode<'_, Self::Outgoing>, dst: &mut Vec<u8>) -> crate::Result<Encoder>322 let mut h = self.hash_builder.build_hasher();
323 key.hash(&mut h);
324 HashValue(h.finish() as usize)
325 }
326
327 /// Insert a key-value pair in the map.
328 ///
329 /// If an equivalent key already exists in the map: the key remains and
330 /// retains in its place in the order, its corresponding value is updated
331 /// with `value` and the older value is returned inside `Some(_)`.
332 ///
333 /// If no equivalent key existed in the map: the new key-value pair is
334 /// inserted, last in order, and `None` is returned.
335 ///
336 /// Computes in **O(1)** time (amortized average).
337 ///
338 /// See also [`entry`](#method.entry) if you you want to insert *or* modify
339 /// or if you need to get the index of the corresponding key-value pair.
340 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
341 self.insert_full(key, value).1
342 }
343
344 /// Insert a key-value pair in the map, and get their index.
345 ///
346 /// If an equivalent key already exists in the map: the key remains and
347 /// retains in its place in the order, its corresponding value is updated
348 /// with `value` and the older value is returned inside `(index, Some(_))`.
349 ///
350 /// If no equivalent key existed in the map: the new key-value pair is
351 /// inserted, last in order, and `(index, None)` is returned.
352 ///
353 /// Computes in **O(1)** time (amortized average).
354 ///
355 /// See also [`entry`](#method.entry) if you you want to insert *or* modify
356 /// or if you need to get the index of the corresponding key-value pair.
357 pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>) {
358 let hash = self.hash(&key);
359 self.core.insert_full(hash, key, value)
360 }
361
362 /// Get the given key’s corresponding entry in the map for insertion and/or
363 /// in-place manipulation.
364 ///
365 /// Computes in **O(1)** time (amortized average).
366 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
367 let hash = self.hash(&key);
368 self.core.entry(hash, key)
369 }
370
371 /// Return `true` if an equivalent to `key` exists in the map.
372 ///
373 /// Computes in **O(1)** time (average).
374 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
375 where
376 Q: Hash + Equivalent<K>,
377 {
378 self.get_index_of(key).is_some()
379 }
380
381 /// Return a reference to the value stored for `key`, if it is present,
382 /// else `None`.
383 ///
384 /// Computes in **O(1)** time (average).
385 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
386 where
387 Q: Hash + Equivalent<K>,
388 {
389 if let Some(i) = self.get_index_of(key) {
390 let entry = &self.as_entries()[i];
391 Some(&entry.value)
392 } else {
393 None
394 }
395 }
396
397 /// Return references to the key-value pair stored for `key`,
398 /// if it is present, else `None`.
399 ///
400 /// Computes in **O(1)** time (average).
401 pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
402 where
403 Q: Hash + Equivalent<K>,
404 {
405 if let Some(i) = self.get_index_of(key) {
406 let entry = &self.as_entries()[i];
407 Some((&entry.key, &entry.value))
408 } else {
409 None
410 }
411 }
on_error(err: &crate::Error) -> Option<MessageHead<Self::Outgoing>>412
413 /// Return item index, key and value
414 pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
415 where
416 Q: Hash + Equivalent<K>,
417 {
418 if let Some(i) = self.get_index_of(key) {
419 let entry = &self.as_entries()[i];
420 Some((i, &entry.key, &entry.value))
421 } else {
422 None
423 }
424 }
425
426 /// Return item index, if it exists in the map
427 ///
428 /// Computes in **O(1)** time (average).
429 pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
is_server() -> bool430 where
431 Q: Hash + Equivalent<K>,
432 {
433 if self.is_empty() {
434 None
435 } else {
436 let hash = self.hash(key);
437 self.core.get_index_of(hash, key)
438 }
439 }
440
can_have_body(method: &Option<Method>, status: StatusCode) -> bool441 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
442 where
443 Q: Hash + Equivalent<K>,
444 {
445 if let Some(i) = self.get_index_of(key) {
446 let entry = &mut self.as_entries_mut()[i];
447 Some(&mut entry.value)
448 } else {
449 None
450 }
451 }
452
453 pub fn get_full_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)>
454 where
455 Q: Hash + Equivalent<K>,
456 {
457 if let Some(i) = self.get_index_of(key) {
458 let entry = &mut self.as_entries_mut()[i];
can_have_content_length(method: &Option<Method>, status: StatusCode) -> bool459 Some((i, &entry.key, &mut entry.value))
460 } else {
461 None
462 }
463 }
464
465 pub(crate) fn get_full_mut2_impl<Q: ?Sized>(
466 &mut self,
467 key: &Q,
468 ) -> Option<(usize, &mut K, &mut V)>
469 where
encode_headers_with_lower_case( msg: Encode<'_, StatusCode>, dst: &mut Vec<u8>, is_last: bool, orig_len: usize, wrote_len: bool, ) -> crate::Result<Encoder>470 Q: Hash + Equivalent<K>,
471 {
472 if let Some(i) = self.get_index_of(key) {
473 let entry = &mut self.as_entries_mut()[i];
474 Some((i, &mut entry.key, &mut entry.value))
475 } else {
476 None
477 }
478 }
479
480 /// Remove the key-value pair equivalent to `key` and return
write_full_header_line( &mut self, dst: &mut Vec<u8>, line: &str, _: (HeaderName, &str), )481 /// its value.
482 ///
483 /// **NOTE:** This is equivalent to `.swap_remove(key)`, if you need to
484 /// preserve the order of the keys in the map, use `.shift_remove(key)`
485 /// instead.
486 ///
487 /// Computes in **O(1)** time (average).
488 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
489 where
490 Q: Hash + Equivalent<K>,
491 {
492 self.swap_remove(key)
493 }
494
495 /// Remove and return the key-value pair equivalent to `key`.
496 ///
497 /// **NOTE:** This is equivalent to `.swap_remove_entry(key)`, if you need to
498 /// preserve the order of the keys in the map, use `.shift_remove_entry(key)`
499 /// instead.
500 ///
write_header_name(&mut self, dst: &mut Vec<u8>, name: &HeaderName)501 /// Computes in **O(1)** time (average).
502 pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
503 where
504 Q: Hash + Equivalent<K>,
505 {
506 self.swap_remove_entry(key)
507 }
508
509 /// Remove the key-value pair equivalent to `key` and return
510 /// its value.
encode_headers_with_original_case( msg: Encode<'_, StatusCode>, dst: &mut Vec<u8>, is_last: bool, orig_len: usize, wrote_len: bool, orig_headers: &HeaderCaseMap, ) -> crate::Result<Encoder>511 ///
512 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
513 /// last element of the map and popping it off. **This perturbs
514 /// the position of what used to be the last element!**
515 ///
516 /// Return `None` if `key` is not in map.
517 ///
518 /// Computes in **O(1)** time (average).
519 pub fn swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
520 where
521 Q: Hash + Equivalent<K>,
522 {
523 self.swap_remove_full(key).map(third)
524 }
525
526 /// Remove and return the key-value pair equivalent to `key`.
write_full_header_line( &mut self, dst: &mut Vec<u8>, _: &str, (name, rest): (HeaderName, &str), )527 ///
528 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
529 /// last element of the map and popping it off. **This perturbs
530 /// the position of what used to be the last element!**
531 ///
532 /// Return `None` if `key` is not in map.
533 ///
534 /// Computes in **O(1)** time (average).
535 pub fn swap_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
536 where
537 Q: Hash + Equivalent<K>,
538 {
539 match self.swap_remove_full(key) {
540 Some((_, key, value)) => Some((key, value)),
541 None => None,
542 }
543 }
544
545 /// Remove the key-value pair equivalent to `key` and return it and
546 /// the index it had.
547 ///
548 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
write_header_name(&mut self, dst: &mut Vec<u8>, name: &HeaderName)549 /// last element of the map and popping it off. **This perturbs
550 /// the position of what used to be the last element!**
551 ///
552 /// Return `None` if `key` is not in map.
553 ///
554 /// Computes in **O(1)** time (average).
555 pub fn swap_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
556 where
557 Q: Hash + Equivalent<K>,
558 {
559 if self.is_empty() {
560 return None;
561 }
562 let hash = self.hash(key);
563 self.core.swap_remove_full(hash, key)
564 }
565
566 /// Remove the key-value pair equivalent to `key` and return
567 /// its value.
568 ///
569 /// Like `Vec::remove`, the pair is removed by shifting all of the
570 /// elements that follow it, preserving their relative order.
571 /// **This perturbs the index of all of those elements!**
572 ///
573 /// Return `None` if `key` is not in map.
574 ///
575 /// Computes in **O(n)** time (average).
576 pub fn shift_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
577 where
578 Q: Hash + Equivalent<K>,
579 {
580 self.shift_remove_full(key).map(third)
encode_headers<W>( msg: Encode<'_, StatusCode>, mut dst: &mut Vec<u8>, mut is_last: bool, orig_len: usize, mut wrote_len: bool, mut header_name_writer: W, ) -> crate::Result<Encoder> where W: HeaderNameWriter,581 }
582
583 /// Remove and return the key-value pair equivalent to `key`.
584 ///
585 /// Like `Vec::remove`, the pair is removed by shifting all of the
586 /// elements that follow it, preserving their relative order.
587 /// **This perturbs the index of all of those elements!**
588 ///
589 /// Return `None` if `key` is not in map.
590 ///
591 /// Computes in **O(n)** time (average).
592 pub fn shift_remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
593 where
594 Q: Hash + Equivalent<K>,
595 {
596 match self.shift_remove_full(key) {
597 Some((_, key, value)) => Some((key, value)),
598 None => None,
599 }
600 }
601
602 /// Remove the key-value pair equivalent to `key` and return it and
603 /// the index it had.
604 ///
605 /// Like `Vec::remove`, the pair is removed by shifting all of the
606 /// elements that follow it, preserving their relative order.
607 /// **This perturbs the index of all of those elements!**
608 ///
609 /// Return `None` if `key` is not in map.
610 ///
611 /// Computes in **O(n)** time (average).
612 pub fn shift_remove_full<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, K, V)>
613 where
614 Q: Hash + Equivalent<K>,
615 {
616 if self.is_empty() {
617 return None;
618 }
619 let hash = self.hash(key);
620 self.core.shift_remove_full(hash, key)
621 }
622
623 /// Remove the last key-value pair
624 ///
625 /// Computes in **O(1)** time (average).
626 pub fn pop(&mut self) -> Option<(K, V)> {
627 self.core.pop()
628 }
629
630 /// Scan through each key-value pair in the map and keep those where the
631 /// closure `keep` returns `true`.
632 ///
633 /// The elements are visited in order, and remaining elements keep their
634 /// order.
635 ///
636 /// Computes in **O(n)** time (average).
637 pub fn retain<F>(&mut self, mut keep: F)
638 where
639 F: FnMut(&K, &mut V) -> bool,
640 {
641 self.core.retain_in_order(move |k, v| keep(k, v));
642 }
643
644 pub(crate) fn retain_mut<F>(&mut self, keep: F)
645 where
646 F: FnMut(&mut K, &mut V) -> bool,
647 {
648 self.core.retain_in_order(keep);
649 }
650
651 /// Sort the map’s key-value pairs by the default ordering of the keys.
652 ///
653 /// See `sort_by` for details.
654 pub fn sort_keys(&mut self)
655 where
656 K: Ord,
657 {
658 self.with_entries(|entries| {
659 entries.sort_by(|a, b| Ord::cmp(&a.key, &b.key));
660 });
661 }
662
663 /// Sort the map’s key-value pairs in place using the comparison
664 /// function `compare`.
665 ///
666 /// The comparison function receives two key and value pairs to compare (you
667 /// can sort by keys or values or their combination as needed).
668 ///
669 /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is
670 /// the length of the map and *c* the capacity. The sort is stable.
671 pub fn sort_by<F>(&mut self, mut cmp: F)
672 where
673 F: FnMut(&K, &V, &K, &V) -> Ordering,
674 {
675 self.with_entries(move |entries| {
676 entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
677 });
678 }
679
680 /// Sort the key-value pairs of the map and return a by value iterator of
681 /// the key-value pairs with the result.
682 ///
683 /// The sort is stable.
684 pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<K, V>
685 where
686 F: FnMut(&K, &V, &K, &V) -> Ordering,
687 {
688 let mut entries = self.into_entries();
689 entries.sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
690 IntoIter {
691 iter: entries.into_iter(),
692 }
693 }
694
695 /// Reverses the order of the map’s key-value pairs in place.
696 ///
697 /// Computes in **O(n)** time and **O(1)** space.
698 pub fn reverse(&mut self) {
699 self.core.reverse()
700 }
701 }
702
703 impl<K, V, S> IndexMap<K, V, S> {
704 /// Get a key-value pair by index
705 ///
706 /// Valid indices are *0 <= index < self.len()*
707 ///
708 /// Computes in **O(1)** time.
709 pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
710 self.as_entries().get(index).map(Bucket::refs)
711 }
712
713 /// Get a key-value pair by index
714 ///
715 /// Valid indices are *0 <= index < self.len()*
716 ///
717 /// Computes in **O(1)** time.
718 pub fn get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)> {
719 self.as_entries_mut().get_mut(index).map(Bucket::muts)
720 }
721
722 /// Get the first key-value pair
723 ///
724 /// Computes in **O(1)** time.
725 pub fn first(&self) -> Option<(&K, &V)> {
726 self.as_entries().first().map(Bucket::refs)
727 }
728
729 /// Get the first key-value pair, with mutable access to the value
730 ///
731 /// Computes in **O(1)** time.
732 pub fn first_mut(&mut self) -> Option<(&K, &mut V)> {
733 self.as_entries_mut().first_mut().map(Bucket::ref_mut)
734 }
735
736 /// Get the last key-value pair
737 ///
738 /// Computes in **O(1)** time.
739 pub fn last(&self) -> Option<(&K, &V)> {
740 self.as_entries().last().map(Bucket::refs)
741 }
742
743 /// Get the last key-value pair, with mutable access to the value
744 ///
745 /// Computes in **O(1)** time.
746 pub fn last_mut(&mut self) -> Option<(&K, &mut V)> {
747 self.as_entries_mut().last_mut().map(Bucket::ref_mut)
748 }
749
750 /// Remove the key-value pair by index
751 ///
752 /// Valid indices are *0 <= index < self.len()*
753 ///
754 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
755 /// last element of the map and popping it off. **This perturbs
756 /// the position of what used to be the last element!**
757 ///
758 /// Computes in **O(1)** time (average).
759 pub fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> {
760 self.core.swap_remove_index(index)
761 }
762
763 /// Remove the key-value pair by index
764 ///
765 /// Valid indices are *0 <= index < self.len()*
766 ///
767 /// Like `Vec::remove`, the pair is removed by shifting all of the
768 /// elements that follow it, preserving their relative order.
769 /// **This perturbs the index of all of those elements!**
770 ///
771 /// Computes in **O(n)** time (average).
772 pub fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> {
773 self.core.shift_remove_index(index)
774 }
775
776 /// Swaps the position of two key-value pairs in the map.
777 ///
778 /// ***Panics*** if `a` or `b` are out of bounds.
779 pub fn swap_indices(&mut self, a: usize, b: usize) {
780 self.core.swap_indices(a, b)
781 }
782 }
783
784 /// An iterator over the keys of a `IndexMap`.
785 ///
786 /// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its
787 /// documentation for more.
788 ///
789 /// [`keys`]: struct.IndexMap.html#method.keys
790 /// [`IndexMap`]: struct.IndexMap.html
791 pub struct Keys<'a, K, V> {
792 pub(crate) iter: SliceIter<'a, Bucket<K, V>>,
793 }
794
795 impl<'a, K, V> Iterator for Keys<'a, K, V> {
796 type Item = &'a K;
797
798 iterator_methods!(Bucket::key_ref);
799 }
800
801 impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
802 fn next_back(&mut self) -> Option<Self::Item> {
803 self.iter.next_back().map(Bucket::key_ref)
804 }
805 }
806
807 impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
808 fn len(&self) -> usize {
809 self.iter.len()
810 }
811 }
812
813 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
814 impl<K, V> Clone for Keys<'_, K, V> {
815 fn clone(&self) -> Self {
816 Keys {
817 iter: self.iter.clone(),
818 }
819 }
820 }
821
822 impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
823 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
824 f.debug_list().entries(self.clone()).finish()
825 }
826 }
827
828 /// An iterator over the values of a `IndexMap`.
829 ///
830 /// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
831 /// documentation for more.
832 ///
833 /// [`values`]: struct.IndexMap.html#method.values
834 /// [`IndexMap`]: struct.IndexMap.html
835 pub struct Values<'a, K, V> {
836 iter: SliceIter<'a, Bucket<K, V>>,
837 }
838
839 impl<'a, K, V> Iterator for Values<'a, K, V> {
840 type Item = &'a V;
841
842 iterator_methods!(Bucket::value_ref);
843 }
844
845 impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
846 fn next_back(&mut self) -> Option<Self::Item> {
847 self.iter.next_back().map(Bucket::value_ref)
848 }
849 }
850
851 impl<K, V> ExactSizeIterator for Values<'_, K, V> {
852 fn len(&self) -> usize {
853 self.iter.len()
854 }
855 }
856
857 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
858 impl<K, V> Clone for Values<'_, K, V> {
859 fn clone(&self) -> Self {
860 Values {
861 iter: self.iter.clone(),
862 }
863 }
864 }
865
866 impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
867 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
868 f.debug_list().entries(self.clone()).finish()
869 }
870 }
871
872 /// A mutable iterator over the values of a `IndexMap`.
write_full_header_line( &mut self, dst: &mut Vec<u8>, line: &str, name_value_pair: (HeaderName, &str), )873 ///
874 /// This `struct` is created by the [`values_mut`] method on [`IndexMap`]. See its
875 /// documentation for more.
876 ///
877 /// [`values_mut`]: struct.IndexMap.html#method.values_mut
878 /// [`IndexMap`]: struct.IndexMap.html
879 pub struct ValuesMut<'a, K, V> {
880 iter: SliceIterMut<'a, Bucket<K, V>>,
881 }
882
883 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
884 type Item = &'a mut V;
write_header_name(&mut self, dst: &mut Vec<u8>, name: &HeaderName)885
886 iterator_methods!(Bucket::value_mut);
887 }
888
889 impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
890 fn next_back(&mut self) -> Option<Self::Item> {
891 self.iter.next_back().map(Bucket::value_mut)
892 }
893 }
parse(buf: &mut BytesMut, ctx: ParseContext<'_>) -> ParseResult<StatusCode>894
895 impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
896 fn len(&self) -> usize {
897 self.iter.len()
898 }
899 }
900
901 /// An iterator over the entries of a `IndexMap`.
902 ///
903 /// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its
904 /// documentation for more.
905 ///
906 /// [`iter`]: struct.IndexMap.html#method.iter
907 /// [`IndexMap`]: struct.IndexMap.html
908 pub struct Iter<'a, K, V> {
909 iter: SliceIter<'a, Bucket<K, V>>,
910 }
911
912 impl<'a, K, V> Iterator for Iter<'a, K, V> {
913 type Item = (&'a K, &'a V);
914
915 iterator_methods!(Bucket::refs);
916 }
917
918 impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
919 fn next_back(&mut self) -> Option<Self::Item> {
920 self.iter.next_back().map(Bucket::refs)
921 }
922 }
923
924 impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
925 fn len(&self) -> usize {
926 self.iter.len()
927 }
928 }
929
930 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
931 impl<K, V> Clone for Iter<'_, K, V> {
932 fn clone(&self) -> Self {
933 Iter {
934 iter: self.iter.clone(),
935 }
936 }
937 }
938
939 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
940 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
941 f.debug_list().entries(self.clone()).finish()
942 }
943 }
944
945 /// A mutable iterator over the entries of a `IndexMap`.
946 ///
947 /// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its
948 /// documentation for more.
949 ///
950 /// [`iter_mut`]: struct.IndexMap.html#method.iter_mut
951 /// [`IndexMap`]: struct.IndexMap.html
952 pub struct IterMut<'a, K, V> {
953 iter: SliceIterMut<'a, Bucket<K, V>>,
954 }
955
956 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
957 type Item = (&'a K, &'a mut V);
958
959 iterator_methods!(Bucket::ref_mut);
960 }
961
962 impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
963 fn next_back(&mut self) -> Option<Self::Item> {
964 self.iter.next_back().map(Bucket::ref_mut)
965 }
966 }
967
968 impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
969 fn len(&self) -> usize {
970 self.iter.len()
971 }
972 }
973
974 /// An owning iterator over the entries of a `IndexMap`.
975 ///
976 /// This `struct` is created by the [`into_iter`] method on [`IndexMap`]
977 /// (provided by the `IntoIterator` trait). See its documentation for more.
978 ///
979 /// [`into_iter`]: struct.IndexMap.html#method.into_iter
980 /// [`IndexMap`]: struct.IndexMap.html
981 pub struct IntoIter<K, V> {
982 pub(crate) iter: vec::IntoIter<Bucket<K, V>>,
983 }
984
985 impl<K, V> Iterator for IntoIter<K, V> {
986 type Item = (K, V);
987
988 iterator_methods!(Bucket::key_value);
989 }
990
991 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
992 fn next_back(&mut self) -> Option<Self::Item> {
993 self.iter.next_back().map(Bucket::key_value)
994 }
995 }
996
997 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
998 fn len(&self) -> usize {
999 self.iter.len()
1000 }
1001 }
1002
1003 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
1004 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1005 let iter = self.iter.as_slice().iter().map(Bucket::refs);
1006 f.debug_list().entries(iter).finish()
1007 }
1008 }
1009
1010 /// A draining iterator over the entries of a `IndexMap`.
1011 ///
1012 /// This `struct` is created by the [`drain`] method on [`IndexMap`]. See its
1013 /// documentation for more.
1014 ///
1015 /// [`drain`]: struct.IndexMap.html#method.drain
1016 /// [`IndexMap`]: struct.IndexMap.html
1017 pub struct Drain<'a, K, V> {
1018 pub(crate) iter: vec::Drain<'a, Bucket<K, V>>,
1019 }
1020
1021 impl<K, V> Iterator for Drain<'_, K, V> {
1022 type Item = (K, V);
1023
1024 iterator_methods!(Bucket::key_value);
1025 }
1026
1027 impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
1028 double_ended_iterator_methods!(Bucket::key_value);
1029 }
1030
1031 impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> {
1032 type Item = (&'a K, &'a V);
1033 type IntoIter = Iter<'a, K, V>;
1034 fn into_iter(self) -> Self::IntoIter {
1035 self.iter()
1036 }
1037 }
1038
1039 impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> {
1040 type Item = (&'a K, &'a mut V);
1041 type IntoIter = IterMut<'a, K, V>;
1042 fn into_iter(self) -> Self::IntoIter {
1043 self.iter_mut()
1044 }
encode(msg: Encode<'_, Self::Outgoing>, dst: &mut Vec<u8>) -> crate::Result<Encoder>1045 }
1046
1047 impl<K, V, S> IntoIterator for IndexMap<K, V, S> {
1048 type Item = (K, V);
1049 type IntoIter = IntoIter<K, V>;
1050 fn into_iter(self) -> Self::IntoIter {
1051 IntoIter {
1052 iter: self.into_entries().into_iter(),
1053 }
1054 }
1055 }
1056
1057 /// Access `IndexMap` values corresponding to a key.
1058 ///
1059 /// # Examples
1060 ///
1061 /// ```
1062 /// use indexmap::IndexMap;
1063 ///
1064 /// let mut map = IndexMap::new();
1065 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1066 /// map.insert(word.to_lowercase(), word.to_uppercase());
1067 /// }
1068 /// assert_eq!(map["lorem"], "LOREM");
1069 /// assert_eq!(map["ipsum"], "IPSUM");
1070 /// ```
1071 ///
1072 /// ```should_panic
1073 /// use indexmap::IndexMap;
1074 ///
1075 /// let mut map = IndexMap::new();
1076 /// map.insert("foo", 1);
1077 /// println!("{:?}", map["bar"]); // panics!
1078 /// ```
1079 impl<K, V, Q: ?Sized, S> Index<&Q> for IndexMap<K, V, S>
1080 where
1081 Q: Hash + Equivalent<K>,
1082 K: Hash + Eq,
1083 S: BuildHasher,
1084 {
1085 type Output = V;
1086
1087 /// Returns a reference to the value corresponding to the supplied `key`.
1088 ///
1089 /// ***Panics*** if `key` is not present in the map.
1090 fn index(&self, key: &Q) -> &V {
1091 self.get(key).expect("IndexMap: key not found")
1092 }
1093 }
on_error(_err: &crate::Error) -> Option<MessageHead<Self::Outgoing>>1094
1095 /// Access `IndexMap` values corresponding to a key.
1096 ///
1097 /// Mutable indexing allows changing / updating values of key-value
1098 /// pairs that are already present.
1099 ///
1100 /// You can **not** insert new pairs with index syntax, use `.insert()`.
1101 ///
1102 /// # Examples
1103 ///
1104 /// ```
1105 /// use indexmap::IndexMap;
1106 ///
1107 /// let mut map = IndexMap::new();
1108 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1109 /// map.insert(word.to_lowercase(), word.to_string());
1110 /// }
1111 /// let lorem = &mut map["lorem"];
1112 /// assert_eq!(lorem, "Lorem");
1113 /// lorem.retain(char::is_lowercase);
1114 /// assert_eq!(map["lorem"], "orem");
1115 /// ```
1116 ///
1117 /// ```should_panic
1118 /// use indexmap::IndexMap;
1119 ///
1120 /// let mut map = IndexMap::new();
1121 /// map.insert("foo", 1);
1122 /// map["bar"] = 1; // panics!
1123 /// ```
1124 impl<K, V, Q: ?Sized, S> IndexMut<&Q> for IndexMap<K, V, S>
1125 where
1126 Q: Hash + Equivalent<K>,
1127 K: Hash + Eq,
1128 S: BuildHasher,
1129 {
1130 /// Returns a mutable reference to the value corresponding to the supplied `key`.
1131 ///
1132 /// ***Panics*** if `key` is not present in the map.
1133 fn index_mut(&mut self, key: &Q) -> &mut V {
1134 self.get_mut(key).expect("IndexMap: key not found")
1135 }
1136 }
1137
1138 /// Access `IndexMap` values at indexed positions.
1139 ///
1140 /// # Examples
1141 ///
1142 /// ```
1143 /// use indexmap::IndexMap;
1144 ///
1145 /// let mut map = IndexMap::new();
1146 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1147 /// map.insert(word.to_lowercase(), word.to_uppercase());
1148 /// }
1149 /// assert_eq!(map[0], "LOREM");
1150 /// assert_eq!(map[1], "IPSUM");
1151 /// map.reverse();
1152 /// assert_eq!(map[0], "AMET");
1153 /// assert_eq!(map[1], "SIT");
1154 /// map.sort_keys();
1155 /// assert_eq!(map[0], "AMET");
1156 /// assert_eq!(map[1], "DOLOR");
1157 /// ```
1158 ///
1159 /// ```should_panic
1160 /// use indexmap::IndexMap;
1161 ///
1162 /// let mut map = IndexMap::new();
1163 /// map.insert("foo", 1);
1164 /// println!("{:?}", map[10]); // panics!
1165 /// ```
1166 impl<K, V, S> Index<usize> for IndexMap<K, V, S> {
1167 type Output = V;
1168
1169 /// Returns a reference to the value at the supplied `index`.
1170 ///
1171 /// ***Panics*** if `index` is out of bounds.
set_length(head: &mut RequestHead, body: Option<BodyLength>) -> Encoder1172 fn index(&self, index: usize) -> &V {
1173 self.get_index(index)
1174 .expect("IndexMap: index out of bounds")
1175 .1
1176 }
1177 }
1178
1179 /// Access `IndexMap` values at indexed positions.
1180 ///
1181 /// Mutable indexing allows changing / updating indexed values
1182 /// that are already present.
1183 ///
1184 /// You can **not** insert new values with index syntax, use `.insert()`.
1185 ///
1186 /// # Examples
1187 ///
1188 /// ```
1189 /// use indexmap::IndexMap;
1190 ///
1191 /// let mut map = IndexMap::new();
1192 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
1193 /// map.insert(word.to_lowercase(), word.to_string());
1194 /// }
1195 /// let lorem = &mut map[0];
1196 /// assert_eq!(lorem, "Lorem");
1197 /// lorem.retain(char::is_lowercase);
1198 /// assert_eq!(map["lorem"], "orem");
1199 /// ```
1200 ///
1201 /// ```should_panic
1202 /// use indexmap::IndexMap;
1203 ///
1204 /// let mut map = IndexMap::new();
1205 /// map.insert("foo", 1);
1206 /// map[10] = 1; // panics!
1207 /// ```
1208 impl<K, V, S> IndexMut<usize> for IndexMap<K, V, S> {
1209 /// Returns a mutable reference to the value at the supplied `index`.
1210 ///
1211 /// ***Panics*** if `index` is out of bounds.
1212 fn index_mut(&mut self, index: usize) -> &mut V {
1213 self.get_index_mut(index)
1214 .expect("IndexMap: index out of bounds")
1215 .1
1216 }
1217 }
1218
1219 impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S>
1220 where
1221 K: Hash + Eq,
1222 S: BuildHasher + Default,
1223 {
1224 /// Create an `IndexMap` from the sequence of key-value pairs in the
1225 /// iterable.
1226 ///
1227 /// `from_iter` uses the same logic as `extend`. See
1228 /// [`extend`](#method.extend) for more details.
1229 fn from_iter<I: IntoIterator<Item = (K, V)>>(iterable: I) -> Self {
1230 let iter = iterable.into_iter();
1231 let (low, _) = iter.size_hint();
1232 let mut map = Self::with_capacity_and_hasher(low, <_>::default());
1233 map.extend(iter);
1234 map
1235 }
1236 }
1237
1238 impl<K, V, S> Extend<(K, V)> for IndexMap<K, V, S>
1239 where
1240 K: Hash + Eq,
1241 S: BuildHasher,
1242 {
1243 /// Extend the map with all key-value pairs in the iterable.
1244 ///
1245 /// This is equivalent to calling [`insert`](#method.insert) for each of
1246 /// them in order, which means that for keys that already existed
1247 /// in the map, their value is updated but it keeps the existing order.
1248 ///
1249 /// New keys are inserted in the order they appear in the sequence. If
1250 /// equivalents of a key occur more than once, the last corresponding value
1251 /// prevails.
1252 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I) {
1253 // (Note: this is a copy of `std`/`hashbrown`'s reservation logic.)
1254 // Keys may be already present or show multiple times in the iterator.
1255 // Reserve the entire hint lower bound if the map is empty.
1256 // Otherwise reserve half the hint (rounded up), so the map
1257 // will only resize twice in the worst case.
1258 let iter = iterable.into_iter();
1259 let reserve = if self.is_empty() {
1260 iter.size_hint().0
1261 } else {
1262 (iter.size_hint().0 + 1) / 2
1263 };
1264 self.reserve(reserve);
1265 iter.for_each(move |(k, v)| {
1266 self.insert(k, v);
1267 });
1268 }
1269 }
1270
1271 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for IndexMap<K, V, S>
1272 where
1273 K: Hash + Eq + Copy,
1274 V: Copy,
1275 S: BuildHasher,
1276 {
1277 /// Extend the map with all key-value pairs in the iterable.
1278 ///
1279 /// See the first extend method for more details.
1280 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iterable: I) {
1281 self.extend(iterable.into_iter().map(|(&key, &value)| (key, value)));
1282 }
1283 }
1284
set_content_length(headers: &mut HeaderMap, len: u64) -> Encoder1285 impl<K, V, S> Default for IndexMap<K, V, S>
1286 where
1287 S: Default,
1288 {
1289 /// Return an empty `IndexMap`
1290 fn default() -> Self {
1291 Self::with_capacity_and_hasher(0, S::default())
1292 }
1293 }
1294
1295 impl<K, V1, S1, V2, S2> PartialEq<IndexMap<K, V2, S2>> for IndexMap<K, V1, S1>
1296 where
1297 K: Hash + Eq,
1298 V1: PartialEq<V2>,
1299 S1: BuildHasher,
1300 S2: BuildHasher,
1301 {
1302 fn eq(&self, other: &IndexMap<K, V2, S2>) -> bool {
1303 if self.len() != other.len() {
1304 return false;
1305 }
1306
1307 self.iter()
1308 .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
1309 }
1310 }
1311
1312 impl<K, V, S> Eq for IndexMap<K, V, S>
1313 where
1314 K: Eq + Hash,
1315 V: Eq,
1316 S: BuildHasher,
1317 {
1318 }
1319
1320 #[cfg(test)]
1321 mod tests {
1322 use super::*;
1323 use crate::util::enumerate;
record_header_indices( bytes: &[u8], headers: &[httparse::Header<'_>], indices: &mut [MaybeUninit<HeaderIndices>], ) -> Result<(), crate::error::Parse>1324 use std::string::String;
1325
1326 #[test]
1327 fn it_works() {
1328 let mut map = IndexMap::new();
1329 assert_eq!(map.is_empty(), true);
1330 map.insert(1, ());
1331 map.insert(1, ());
1332 assert_eq!(map.len(), 1);
1333 assert!(map.get(&1).is_some());
1334 assert_eq!(map.is_empty(), false);
1335 }
1336
1337 #[test]
1338 fn new() {
1339 let map = IndexMap::<String, String>::new();
1340 println!("{:?}", map);
1341 assert_eq!(map.capacity(), 0);
1342 assert_eq!(map.len(), 0);
1343 assert_eq!(map.is_empty(), true);
1344 }
1345
1346 #[test]
1347 fn insert() {
1348 let insert = [0, 4, 2, 12, 8, 7, 11, 5];
1349 let not_present = [1, 3, 6, 9, 10];
1350 let mut map = IndexMap::with_capacity(insert.len());
1351
1352 for (i, &elt) in enumerate(&insert) {
1353 assert_eq!(map.len(), i);
1354 map.insert(elt, elt);
1355 assert_eq!(map.len(), i + 1);
1356 assert_eq!(map.get(&elt), Some(&elt));
title_case(dst: &mut Vec<u8>, name: &[u8])1357 assert_eq!(map[&elt], elt);
1358 }
1359 println!("{:?}", map);
1360
1361 for &elt in ¬_present {
1362 assert!(map.get(&elt).is_none());
1363 }
1364 }
1365
1366 #[test]
1367 fn insert_full() {
1368 let insert = vec![9, 2, 7, 1, 4, 6, 13];
1369 let present = vec![1, 6, 2];
1370 let mut map = IndexMap::with_capacity(insert.len());
write_headers_title_case(headers: &HeaderMap, dst: &mut Vec<u8>)1371
1372 for (i, &elt) in enumerate(&insert) {
1373 assert_eq!(map.len(), i);
1374 let (index, existing) = map.insert_full(elt, elt);
1375 assert_eq!(existing, None);
1376 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0));
1377 assert_eq!(map.len(), i + 1);
1378 }
1379
write_headers(headers: &HeaderMap, dst: &mut Vec<u8>)1380 let len = map.len();
1381 for &elt in &present {
1382 let (index, existing) = map.insert_full(elt, elt);
1383 assert_eq!(existing, Some(elt));
1384 assert_eq!(Some(index), map.get_full(&elt).map(|x| x.0));
1385 assert_eq!(map.len(), len);
1386 }
1387 }
1388
1389 #[test]
write_headers_original_case( headers: &HeaderMap, orig_case: &HeaderCaseMap, dst: &mut Vec<u8>, title_case_headers: bool, )1390 fn insert_2() {
1391 let mut map = IndexMap::with_capacity(16);
1392
1393 let mut keys = vec![];
1394 keys.extend(0..16);
1395 keys.extend(128..267);
1396
1397 for &i in &keys {
1398 let old_map = map.clone();
1399 map.insert(i, ());
1400 for key in old_map.keys() {
1401 if map.get(key).is_none() {
1402 println!("old_map: {:?}", old_map);
1403 println!("map: {:?}", map);
1404 panic!("did not find {} in map", key);
1405 }
1406 }
1407 }
1408
1409 for &i in &keys {
1410 assert!(map.get(&i).is_some(), "did not find {}", i);
1411 }
1412 }
1413
1414 #[test]
1415 fn insert_order() {
1416 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1417 let mut map = IndexMap::new();
1418
1419 for &elt in &insert {
1420 map.insert(elt, ());
1421 }
1422
1423 assert_eq!(map.keys().count(), map.len());
1424 assert_eq!(map.keys().count(), insert.len());
1425 for (a, b) in insert.iter().zip(map.keys()) {
1426 assert_eq!(a, b);
1427 }
1428 for (i, k) in (0..insert.len()).zip(map.keys()) {
write_str(&mut self, s: &str) -> fmt::Result1429 assert_eq!(map.get_index(i).unwrap().0, k);
1430 }
1431 }
1432
1433 #[test]
1434 fn grow() {
write_fmt(&mut self, args: fmt::Arguments<'_>) -> fmt::Result1435 let insert = [0, 4, 2, 12, 8, 7, 11];
1436 let not_present = [1, 3, 6, 9, 10];
1437 let mut map = IndexMap::with_capacity(insert.len());
1438
1439 for (i, &elt) in enumerate(&insert) {
1440 assert_eq!(map.len(), i);
extend(dst: &mut Vec<u8>, data: &[u8])1441 map.insert(elt, elt);
1442 assert_eq!(map.len(), i + 1);
1443 assert_eq!(map.get(&elt), Some(&elt));
1444 assert_eq!(map[&elt], elt);
1445 }
1446
1447 println!("{:?}", map);
1448 for &elt in &insert {
1449 map.insert(elt * 10, elt);
1450 }
1451 for &elt in &insert {
test_parse_request()1452 map.insert(elt * 100, elt);
1453 }
1454 for (i, &elt) in insert.iter().cycle().enumerate().take(100) {
1455 map.insert(elt * 100 + i as i32, elt);
1456 }
1457 println!("{:?}", map);
1458 for &elt in ¬_present {
1459 assert!(map.get(&elt).is_none());
1460 }
1461 }
1462
1463 #[test]
1464 fn reserve() {
1465 let mut map = IndexMap::<usize, usize>::new();
1466 assert_eq!(map.capacity(), 0);
1467 map.reserve(100);
1468 let capacity = map.capacity();
1469 assert!(capacity >= 100);
1470 for i in 0..capacity {
1471 assert_eq!(map.len(), i);
1472 map.insert(i, i * i);
1473 assert_eq!(map.len(), i + 1);
1474 assert_eq!(map.capacity(), capacity);
1475 assert_eq!(map.get(&i), Some(&(i * i)));
1476 }
1477 map.insert(capacity, std::usize::MAX);
1478 assert_eq!(map.len(), capacity + 1);
1479 assert!(map.capacity() > capacity);
1480 assert_eq!(map.get(&capacity), Some(&std::usize::MAX));
1481 }
1482
1483 #[test]
1484 fn shrink_to_fit() {
test_parse_response()1485 let mut map = IndexMap::<usize, usize>::new();
1486 assert_eq!(map.capacity(), 0);
1487 for i in 0..100 {
1488 assert_eq!(map.len(), i);
1489 map.insert(i, i * i);
1490 assert_eq!(map.len(), i + 1);
1491 assert!(map.capacity() >= i + 1);
1492 assert_eq!(map.get(&i), Some(&(i * i)));
1493 map.shrink_to_fit();
1494 assert_eq!(map.len(), i + 1);
1495 assert_eq!(map.capacity(), i + 1);
1496 assert_eq!(map.get(&i), Some(&(i * i)));
1497 }
1498 }
1499
1500 #[test]
1501 fn remove() {
1502 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1503 let mut map = IndexMap::new();
1504
1505 for &elt in &insert {
1506 map.insert(elt, elt);
1507 }
1508
1509 assert_eq!(map.keys().count(), map.len());
1510 assert_eq!(map.keys().count(), insert.len());
test_parse_request_errors()1511 for (a, b) in insert.iter().zip(map.keys()) {
1512 assert_eq!(a, b);
1513 }
1514
1515 let remove_fail = [99, 77];
1516 let remove = [4, 12, 8, 7];
1517
1518 for &key in &remove_fail {
1519 assert!(map.swap_remove_full(&key).is_none());
1520 }
1521 println!("{:?}", map);
1522 for &key in &remove {
1523 //println!("{:?}", map);
1524 let index = map.get_full(&key).unwrap().0;
1525 assert_eq!(map.swap_remove_full(&key), Some((index, key, key)));
1526 }
1527 println!("{:?}", map);
1528
1529 for key in &insert {
1530 assert_eq!(map.get(key).is_some(), !remove.contains(key));
1531 }
1532 assert_eq!(map.len(), insert.len() - remove.len());
test_parse_response_h09_allowed()1533 assert_eq!(map.keys().count(), insert.len() - remove.len());
1534 }
1535
1536 #[test]
1537 fn remove_to_empty() {
1538 let mut map = indexmap! { 0 => 0, 4 => 4, 5 => 5 };
1539 map.swap_remove(&5).unwrap();
1540 map.swap_remove(&4).unwrap();
1541 map.swap_remove(&0).unwrap();
1542 assert!(map.is_empty());
1543 }
1544
1545 #[test]
1546 fn swap_remove_index() {
1547 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
1548 let mut map = IndexMap::new();
1549
1550 for &elt in &insert {
1551 map.insert(elt, elt * 2);
1552 }
1553
1554 let mut vector = insert.to_vec();
1555 let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1];
1556
1557 // check that the same swap remove sequence on vec and map
test_parse_response_h09_rejected()1558 // have the same result.
1559 for &rm in remove_sequence {
1560 let out_vec = vector.swap_remove(rm);
1561 let (out_map, _) = map.swap_remove_index(rm).unwrap();
1562 assert_eq!(out_vec, out_map);
1563 }
1564 assert_eq!(vector.len(), map.len());
1565 for (a, b) in vector.iter().zip(map.keys()) {
1566 assert_eq!(a, b);
1567 }
1568 }
1569
1570 #[test]
1571 fn partial_eq_and_eq() {
1572 let mut map_a = IndexMap::new();
1573 map_a.insert(1, "1");
1574 map_a.insert(2, "2");
1575 let mut map_b = map_a.clone();
1576 assert_eq!(map_a, map_b);
1577 map_b.swap_remove(&1);
1578 assert_ne!(map_a, map_b);
1579
1580 let map_c: IndexMap<_, String> = map_b.into_iter().map(|(k, v)| (k, v.into())).collect();
1581 assert_ne!(map_a, map_c);
1582 assert_ne!(map_c, map_a);
test_parse_allow_response_with_spaces_before_colons()1583 }
1584
1585 #[test]
1586 fn extend() {
1587 let mut map = IndexMap::new();
1588 map.extend(vec![(&1, &2), (&3, &4)]);
1589 map.extend(vec![(5, 6)]);
1590 assert_eq!(
1591 map.into_iter().collect::<Vec<_>>(),
1592 vec![(1, 2), (3, 4), (5, 6)]
1593 );
1594 }
1595
1596 #[test]
1597 fn entry() {
1598 let mut map = IndexMap::new();
1599
1600 map.insert(1, "1");
1601 map.insert(2, "2");
1602 {
1603 let e = map.entry(3);
1604 assert_eq!(e.index(), 2);
1605 let e = e.or_insert("3");
1606 assert_eq!(e, &"3");
1607 }
1608
1609 let e = map.entry(2);
1610 assert_eq!(e.index(), 1);
1611 assert_eq!(e.key(), &2);
1612 match e {
test_parse_reject_response_with_spaces_before_colons()1613 Entry::Occupied(ref e) => assert_eq!(e.get(), &"2"),
1614 Entry::Vacant(_) => panic!(),
1615 }
1616 assert_eq!(e.or_insert("4"), &"2");
1617 }
1618
1619 #[test]
1620 fn entry_and_modify() {
1621 let mut map = IndexMap::new();
1622
1623 map.insert(1, "1");
1624 map.entry(1).and_modify(|x| *x = "2");
1625 assert_eq!(Some(&"2"), map.get(&1));
1626
1627 map.entry(2).and_modify(|x| *x = "doesn't exist");
1628 assert_eq!(None, map.get(&2));
1629 }
1630
1631 #[test]
1632 fn entry_or_default() {
1633 let mut map = IndexMap::new();
test_parse_preserve_header_case_in_request()1634
1635 #[derive(Debug, PartialEq)]
1636 enum TestEnum {
1637 DefaultValue,
1638 NonDefaultValue,
1639 }
1640
1641 impl Default for TestEnum {
1642 fn default() -> Self {
1643 TestEnum::DefaultValue
1644 }
1645 }
1646
1647 map.insert(1, TestEnum::NonDefaultValue);
1648 assert_eq!(&mut TestEnum::NonDefaultValue, map.entry(1).or_default());
1649
1650 assert_eq!(&mut TestEnum::DefaultValue, map.entry(2).or_default());
1651 }
1652
1653 #[test]
1654 fn occupied_entry_key() {
1655 // These keys match hash and equality, but their addresses are distinct.
1656 let (k1, k2) = (&mut 1, &mut 1);
1657 let k1_ptr = k1 as *const i32;
1658 let k2_ptr = k2 as *const i32;
1659 assert_ne!(k1_ptr, k2_ptr);
1660
1661 let mut map = IndexMap::new();
1662 map.insert(k1, "value");
1663 match map.entry(k2) {
1664 Entry::Occupied(ref e) => {
1665 // `OccupiedEntry::key` should reference the key in the map,
1666 // not the key that was used to find the entry.
1667 let ptr = *e.key() as *const i32;
1668 assert_eq!(ptr, k1_ptr);
1669 assert_ne!(ptr, k2_ptr);
1670 }
1671 Entry::Vacant(_) => panic!(),
1672 }
1673 }
test_decoder_request()1674
1675 #[test]
1676 fn keys() {
1677 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1678 let map: IndexMap<_, _> = vec.into_iter().collect();
1679 let keys: Vec<_> = map.keys().copied().collect();
1680 assert_eq!(keys.len(), 3);
1681 assert!(keys.contains(&1));
1682 assert!(keys.contains(&2));
1683 assert!(keys.contains(&3));
1684 }
1685
1686 #[test]
1687 fn values() {
1688 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1689 let map: IndexMap<_, _> = vec.into_iter().collect();
1690 let values: Vec<_> = map.values().copied().collect();
1691 assert_eq!(values.len(), 3);
1692 assert!(values.contains(&'a'));
1693 assert!(values.contains(&'b'));
1694 assert!(values.contains(&'c'));
1695 }
1696
1697 #[test]
parse_err(s: &str, comment: &str) -> crate::error::Parse1698 fn values_mut() {
1699 let vec = vec![(1, 1), (2, 2), (3, 3)];
1700 let mut map: IndexMap<_, _> = vec.into_iter().collect();
1701 for value in map.values_mut() {
1702 *value *= 2
1703 }
1704 let values: Vec<_> = map.values().copied().collect();
1705 assert_eq!(values.len(), 3);
1706 assert!(values.contains(&2));
1707 assert!(values.contains(&4));
1708 assert!(values.contains(&6));
1709 }
1710 }
1711