1use std::collections::HashMap;
2use std::collections::hash_map::RandomState;
3use std::convert::TryFrom;
4use std::hash::{BuildHasher, Hash, Hasher};
5use std::iter::{FromIterator, FusedIterator};
6use std::marker::PhantomData;
7use std::{fmt, mem, ops, ptr, vec};
8
9use crate::Error;
10
11use super::HeaderValue;
12use super::name::{HdrName, HeaderName, InvalidHeaderName};
13
14pub use self::as_header_name::AsHeaderName;
15pub use self::into_header_name::IntoHeaderName;
16
17/// A set of HTTP headers
18///
19/// `HeaderMap` is an multimap of [`HeaderName`] to values.
20///
21/// [`HeaderName`]: struct.HeaderName.html
22///
23/// # Examples
24///
25/// Basic usage
26///
27/// ```
28/// # use http::HeaderMap;
29/// # use http::header::{CONTENT_LENGTH, HOST, LOCATION};
30/// let mut headers = HeaderMap::new();
31///
32/// headers.insert(HOST, "example.com".parse().unwrap());
33/// headers.insert(CONTENT_LENGTH, "123".parse().unwrap());
34///
35/// assert!(headers.contains_key(HOST));
36/// assert!(!headers.contains_key(LOCATION));
37///
38/// assert_eq!(headers[HOST], "example.com");
39///
40/// headers.remove(HOST);
41///
42/// assert!(!headers.contains_key(HOST));
43/// ```
44#[derive(Clone)]
45pub struct HeaderMap<T = HeaderValue> {
46 // Used to mask values to get an index
47 mask: Size,
48 indices: Box<[Pos]>,
49 entries: Vec<Bucket<T>>,
50 extra_values: Vec<ExtraValue<T>>,
51 danger: Danger,
52}
53
54// # Implementation notes
55//
56// Below, you will find a fairly large amount of code. Most of this is to
57// provide the necessary functions to efficiently manipulate the header
58// multimap. The core hashing table is based on robin hood hashing [1]. While
59// this is the same hashing algorithm used as part of Rust's `HashMap` in
60// stdlib, many implementation details are different. The two primary reasons
61// for this divergence are that `HeaderMap` is a multimap and the structure has
62// been optimized to take advantage of the characteristics of HTTP headers.
63//
64// ## Structure Layout
65//
66// Most of the data contained by `HeaderMap` is *not* stored in the hash table.
67// Instead, pairs of header name and *first* associated header value are stored
68// in the `entries` vector. If the header name has more than one associated
69// header value, then additional values are stored in `extra_values`. The actual
70// hash table (`indices`) only maps hash codes to indices in `entries`. This
71// means that, when an eviction happens, the actual header name and value stay
72// put and only a tiny amount of memory has to be copied.
73//
74// Extra values associated with a header name are tracked using a linked list.
75// Links are formed with offsets into `extra_values` and not pointers.
76//
77// [1]: https://en.wikipedia.org/wiki/Hash_table#Robin_Hood_hashing
78
79/// `HeaderMap` entry iterator.
80///
81/// Yields `(&HeaderName, &value)` tuples. The same header name may be yielded
82/// more than once if it has more than one associated value.
83#[derive(Debug)]
84pub struct Iter<'a, T> {
85 map: &'a HeaderMap<T>,
86 entry: usize,
87 cursor: Option<Cursor>,
88}
89
90/// `HeaderMap` mutable entry iterator
91///
92/// Yields `(&HeaderName, &mut value)` tuples. The same header name may be
93/// yielded more than once if it has more than one associated value.
94#[derive(Debug)]
95pub struct IterMut<'a, T> {
96 map: *mut HeaderMap<T>,
97 entry: usize,
98 cursor: Option<Cursor>,
99 lt: PhantomData<&'a mut HeaderMap<T>>,
100}
101
102/// An owning iterator over the entries of a `HeaderMap`.
103///
104/// This struct is created by the `into_iter` method on `HeaderMap`.
105#[derive(Debug)]
106pub struct IntoIter<T> {
107 // If None, pull from `entries`
108 next: Option<usize>,
109 entries: vec::IntoIter<Bucket<T>>,
110 extra_values: Vec<ExtraValue<T>>,
111}
112
113/// An iterator over `HeaderMap` keys.
114///
115/// Each header name is yielded only once, even if it has more than one
116/// associated value.
117#[derive(Debug)]
118pub struct Keys<'a, T> {
119 inner: ::std::slice::Iter<'a, Bucket<T>>,
120}
121
122/// `HeaderMap` value iterator.
123///
124/// Each value contained in the `HeaderMap` will be yielded.
125#[derive(Debug)]
126pub struct Values<'a, T> {
127 inner: Iter<'a, T>,
128}
129
130/// `HeaderMap` mutable value iterator
131#[derive(Debug)]
132pub struct ValuesMut<'a, T> {
133 inner: IterMut<'a, T>,
134}
135
136/// A drain iterator for `HeaderMap`.
137#[derive(Debug)]
138pub struct Drain<'a, T> {
139 idx: usize,
140 len: usize,
141 entries: *mut [Bucket<T>],
142 // If None, pull from `entries`
143 next: Option<usize>,
144 extra_values: *mut Vec<ExtraValue<T>>,
145 lt: PhantomData<&'a mut HeaderMap<T>>,
146}
147
148/// A view to all values stored in a single entry.
149///
150/// This struct is returned by `HeaderMap::get_all`.
151#[derive(Debug)]
152pub struct GetAll<'a, T> {
153 map: &'a HeaderMap<T>,
154 index: Option<usize>,
155}
156
157/// A view into a single location in a `HeaderMap`, which may be vacant or occupied.
158#[derive(Debug)]
159pub enum Entry<'a, T: 'a> {
160 /// An occupied entry
161 Occupied(OccupiedEntry<'a, T>),
162
163 /// A vacant entry
164 Vacant(VacantEntry<'a, T>),
165}
166
167/// A view into a single empty location in a `HeaderMap`.
168///
169/// This struct is returned as part of the `Entry` enum.
170#[derive(Debug)]
171pub struct VacantEntry<'a, T> {
172 map: &'a mut HeaderMap<T>,
173 key: HeaderName,
174 hash: HashValue,
175 probe: usize,
176 danger: bool,
177}
178
179/// A view into a single occupied location in a `HeaderMap`.
180///
181/// This struct is returned as part of the `Entry` enum.
182#[derive(Debug)]
183pub struct OccupiedEntry<'a, T> {
184 map: &'a mut HeaderMap<T>,
185 probe: usize,
186 index: usize,
187}
188
189/// An iterator of all values associated with a single header name.
190#[derive(Debug)]
191pub struct ValueIter<'a, T> {
192 map: &'a HeaderMap<T>,
193 index: usize,
194 front: Option<Cursor>,
195 back: Option<Cursor>,
196}
197
198/// A mutable iterator of all values associated with a single header name.
199#[derive(Debug)]
200pub struct ValueIterMut<'a, T> {
201 map: *mut HeaderMap<T>,
202 index: usize,
203 front: Option<Cursor>,
204 back: Option<Cursor>,
205 lt: PhantomData<&'a mut HeaderMap<T>>,
206}
207
208/// An drain iterator of all values associated with a single header name.
209#[derive(Debug)]
210pub struct ValueDrain<'a, T> {
211 first: Option<T>,
212 next: Option<::std::vec::IntoIter<T>>,
213 lt: PhantomData<&'a mut HeaderMap<T>>,
214}
215
216/// Tracks the value iterator state
217#[derive(Debug, Copy, Clone, Eq, PartialEq)]
218enum Cursor {
219 Head,
220 Values(usize),
221}
222
223/// Type used for representing the size of a HeaderMap value.
224///
225/// 32,768 is more than enough entries for a single header map. Setting this
226/// limit enables using `u16` to represent all offsets, which takes 2 bytes
227/// instead of 8 on 64 bit processors.
228///
229/// Setting this limit is especially beneficial for `indices`, making it more
230/// cache friendly. More hash codes can fit in a cache line.
231///
232/// You may notice that `u16` may represent more than 32,768 values. This is
233/// true, but 32,768 should be plenty and it allows us to reserve the top bit
234/// for future usage.
235type Size = u16;
236
237/// This limit falls out from above.
238const MAX_SIZE: usize = 1 << 15;
239
240/// An entry in the hash table. This represents the full hash code for an entry
241/// as well as the position of the entry in the `entries` vector.
242#[derive(Copy, Clone)]
243struct Pos {
244 // Index in the `entries` vec
245 index: Size,
246 // Full hash value for the entry.
247 hash: HashValue,
248}
249
250/// Hash values are limited to u16 as well. While `fast_hash` and `Hasher`
251/// return `usize` hash codes, limiting the effective hash code to the lower 16
252/// bits is fine since we know that the `indices` vector will never grow beyond
253/// that size.
254#[derive(Debug, Copy, Clone, Eq, PartialEq)]
255struct HashValue(u16);
256
257/// Stores the data associated with a `HeaderMap` entry. Only the first value is
258/// included in this struct. If a header name has more than one associated
259/// value, all extra values are stored in the `extra_values` vector. A doubly
260/// linked list of entries is maintained. The doubly linked list is used so that
261/// removing a value is constant time. This also has the nice property of
262/// enabling double ended iteration.
263#[derive(Debug, Clone)]
264struct Bucket<T> {
265 hash: HashValue,
266 key: HeaderName,
267 value: T,
268 links: Option<Links>,
269}
270
271/// The head and tail of the value linked list.
272#[derive(Debug, Copy, Clone)]
273struct Links {
274 next: usize,
275 tail: usize,
276}
277
278/// Access to the `links` value in a slice of buckets.
279///
280/// It's important that no other field is accessed, since it may have been
281/// freed in a `Drain` iterator.
282#[derive(Debug)]
283struct RawLinks<T>(*mut [Bucket<T>]);
284
285/// Node in doubly-linked list of header value entries
286#[derive(Debug, Clone)]
287struct ExtraValue<T> {
288 value: T,
289 prev: Link,
290 next: Link,
291}
292
293/// A header value node is either linked to another node in the `extra_values`
294/// list or it points to an entry in `entries`. The entry in `entries` is the
295/// start of the list and holds the associated header name.
296#[derive(Debug, Copy, Clone, Eq, PartialEq)]
297enum Link {
298 Entry(usize),
299 Extra(usize),
300}
301
302/// Tracks the header map danger level! This relates to the adaptive hashing
303/// algorithm. A HeaderMap starts in the "green" state, when a large number of
304/// collisions are detected, it transitions to the yellow state. At this point,
305/// the header map will either grow and switch back to the green state OR it
306/// will transition to the red state.
307///
308/// When in the red state, a safe hashing algorithm is used and all values in
309/// the header map have to be rehashed.
310#[derive(Clone)]
311enum Danger {
312 Green,
313 Yellow,
314 Red(RandomState),
315}
316
317// Constants related to detecting DOS attacks.
318//
319// Displacement is the number of entries that get shifted when inserting a new
320// value. Forward shift is how far the entry gets stored from the ideal
321// position.
322//
323// The current constant values were picked from another implementation. It could
324// be that there are different values better suited to the header map case.
325const DISPLACEMENT_THRESHOLD: usize = 128;
326const FORWARD_SHIFT_THRESHOLD: usize = 512;
327
328// The default strategy for handling the yellow danger state is to increase the
329// header map capacity in order to (hopefully) reduce the number of collisions.
330// If growing the hash map would cause the load factor to drop bellow this
331// threshold, then instead of growing, the headermap is switched to the red
332// danger state and safe hashing is used instead.
333const LOAD_FACTOR_THRESHOLD: f32 = 0.2;
334
335// Macro used to iterate the hash table starting at a given point, looping when
336// the end is hit.
337macro_rules! probe_loop {
338 ($label:tt: $probe_var: ident < $len: expr, $body: expr) => {
339 debug_assert!($len > 0);
340 $label:
341 loop {
342 if $probe_var < $len {
343 $body
344 $probe_var += 1;
345 } else {
346 $probe_var = 0;
347 }
348 }
349 };
350 ($probe_var: ident < $len: expr, $body: expr) => {
351 debug_assert!($len > 0);
352 loop {
353 if $probe_var < $len {
354 $body
355 $probe_var += 1;
356 } else {
357 $probe_var = 0;
358 }
359 }
360 };
361}
362
363// First part of the robinhood algorithm. Given a key, find the slot in which it
364// will be inserted. This is done by starting at the "ideal" spot. Then scanning
365// until the destination slot is found. A destination slot is either the next
366// empty slot or the next slot that is occupied by an entry that has a lower
367// displacement (displacement is the distance from the ideal spot).
368//
369// This is implemented as a macro instead of a function that takes a closure in
370// order to guarantee that it is "inlined". There is no way to annotate closures
371// to guarantee inlining.
372macro_rules! insert_phase_one {
373 ($map:ident,
374 $key:expr,
375 $probe:ident,
376 $pos:ident,
377 $hash:ident,
378 $danger:ident,
379 $vacant:expr,
380 $occupied:expr,
381 $robinhood:expr) =>
382 {{
383 let $hash = hash_elem_using(&$map.danger, &$key);
384 let mut $probe = desired_pos($map.mask, $hash);
385 let mut dist = 0;
386 let ret;
387
388 // Start at the ideal position, checking all slots
389 probe_loop!('probe: $probe < $map.indices.len(), {
390 if let Some(($pos, entry_hash)) = $map.indices[$probe].resolve() {
391 // The slot is already occupied, but check if it has a lower
392 // displacement.
393 let their_dist = probe_distance($map.mask, entry_hash, $probe);
394
395 if their_dist < dist {
396 // The new key's distance is larger, so claim this spot and
397 // displace the current entry.
398 //
399 // Check if this insertion is above the danger threshold.
400 let $danger =
401 dist >= FORWARD_SHIFT_THRESHOLD && !$map.danger.is_red();
402
403 ret = $robinhood;
404 break 'probe;
405 } else if entry_hash == $hash && $map.entries[$pos].key == $key {
406 // There already is an entry with the same key.
407 ret = $occupied;
408 break 'probe;
409 }
410 } else {
411 // The entry is vacant, use it for this key.
412 let $danger =
413 dist >= FORWARD_SHIFT_THRESHOLD && !$map.danger.is_red();
414
415 ret = $vacant;
416 break 'probe;
417 }
418
419 dist += 1;
420 });
421
422 ret
423 }}
424}
425
426// ===== impl HeaderMap =====
427
428impl HeaderMap {
429 /// Create an empty `HeaderMap`.
430 ///
431 /// The map will be created without any capacity. This function will not
432 /// allocate.
433 ///
434 /// # Examples
435 ///
436 /// ```
437 /// # use http::HeaderMap;
438 /// let map = HeaderMap::new();
439 ///
440 /// assert!(map.is_empty());
441 /// assert_eq!(0, map.capacity());
442 /// ```
443 pub fn new() -> Self {
444 HeaderMap::with_capacity(0)
445 }
446}
447
448impl<T> HeaderMap<T> {
449 /// Create an empty `HeaderMap` with the specified capacity.
450 ///
451 /// The returned map will allocate internal storage in order to hold about
452 /// `capacity` elements without reallocating. However, this is a "best
453 /// effort" as there are usage patterns that could cause additional
454 /// allocations before `capacity` headers are stored in the map.
455 ///
456 /// More capacity than requested may be allocated.
457 ///
458 /// # Panics
459 ///
460 /// Requested capacity too large: would overflow `usize`.
461 ///
462 /// # Examples
463 ///
464 /// ```
465 /// # use http::HeaderMap;
466 /// let map: HeaderMap<u32> = HeaderMap::with_capacity(10);
467 ///
468 /// assert!(map.is_empty());
469 /// assert_eq!(12, map.capacity());
470 /// ```
471 pub fn with_capacity(capacity: usize) -> HeaderMap<T> {
472 if capacity == 0 {
473 HeaderMap {
474 mask: 0,
475 indices: Box::new([]), // as a ZST, this doesn't actually allocate anything
476 entries: Vec::new(),
477 extra_values: Vec::new(),
478 danger: Danger::Green,
479 }
480 } else {
481 let raw_cap = match to_raw_capacity(capacity).checked_next_power_of_two() {
482 Some(c) => c,
483 None => panic!(
484 "requested capacity {} too large: next power of two would overflow `usize`",
485 capacity
486 ),
487 };
488 assert!(raw_cap <= MAX_SIZE, "requested capacity too large");
489 debug_assert!(raw_cap > 0);
490
491 HeaderMap {
492 mask: (raw_cap - 1) as Size,
493 indices: vec![Pos::none(); raw_cap].into_boxed_slice(),
494 entries: Vec::with_capacity(raw_cap),
495 extra_values: Vec::new(),
496 danger: Danger::Green,
497 }
498 }
499 }
500
501 /// Returns the number of headers stored in the map.
502 ///
503 /// This number represents the total number of **values** stored in the map.
504 /// This number can be greater than or equal to the number of **keys**
505 /// stored given that a single key may have more than one associated value.
506 ///
507 /// # Examples
508 ///
509 /// ```
510 /// # use http::HeaderMap;
511 /// # use http::header::{ACCEPT, HOST};
512 /// let mut map = HeaderMap::new();
513 ///
514 /// assert_eq!(0, map.len());
515 ///
516 /// map.insert(ACCEPT, "text/plain".parse().unwrap());
517 /// map.insert(HOST, "localhost".parse().unwrap());
518 ///
519 /// assert_eq!(2, map.len());
520 ///
521 /// map.append(ACCEPT, "text/html".parse().unwrap());
522 ///
523 /// assert_eq!(3, map.len());
524 /// ```
525 pub fn len(&self) -> usize {
526 self.entries.len() + self.extra_values.len()
527 }
528
529 /// Returns the number of keys stored in the map.
530 ///
531 /// This number will be less than or equal to `len()` as each key may have
532 /// more than one associated value.
533 ///
534 /// # Examples
535 ///
536 /// ```
537 /// # use http::HeaderMap;
538 /// # use http::header::{ACCEPT, HOST};
539 /// let mut map = HeaderMap::new();
540 ///
541 /// assert_eq!(0, map.keys_len());
542 ///
543 /// map.insert(ACCEPT, "text/plain".parse().unwrap());
544 /// map.insert(HOST, "localhost".parse().unwrap());
545 ///
546 /// assert_eq!(2, map.keys_len());
547 ///
548 /// map.insert(ACCEPT, "text/html".parse().unwrap());
549 ///
550 /// assert_eq!(2, map.keys_len());
551 /// ```
552 pub fn keys_len(&self) -> usize {
553 self.entries.len()
554 }
555
556 /// Returns true if the map contains no elements.
557 ///
558 /// # Examples
559 ///
560 /// ```
561 /// # use http::HeaderMap;
562 /// # use http::header::HOST;
563 /// let mut map = HeaderMap::new();
564 ///
565 /// assert!(map.is_empty());
566 ///
567 /// map.insert(HOST, "hello.world".parse().unwrap());
568 ///
569 /// assert!(!map.is_empty());
570 /// ```
571 pub fn is_empty(&self) -> bool {
572 self.entries.len() == 0
573 }
574
575 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
576 /// for reuse.
577 ///
578 /// # Examples
579 ///
580 /// ```
581 /// # use http::HeaderMap;
582 /// # use http::header::HOST;
583 /// let mut map = HeaderMap::new();
584 /// map.insert(HOST, "hello.world".parse().unwrap());
585 ///
586 /// map.clear();
587 /// assert!(map.is_empty());
588 /// assert!(map.capacity() > 0);
589 /// ```
590 pub fn clear(&mut self) {
591 self.entries.clear();
592 self.extra_values.clear();
593 self.danger = Danger::Green;
594
595 for e in self.indices.iter_mut() {
596 *e = Pos::none();
597 }
598 }
599
600 /// Returns the number of headers the map can hold without reallocating.
601 ///
602 /// This number is an approximation as certain usage patterns could cause
603 /// additional allocations before the returned capacity is filled.
604 ///
605 /// # Examples
606 ///
607 /// ```
608 /// # use http::HeaderMap;
609 /// # use http::header::HOST;
610 /// let mut map = HeaderMap::new();
611 ///
612 /// assert_eq!(0, map.capacity());
613 ///
614 /// map.insert(HOST, "hello.world".parse().unwrap());
615 /// assert_eq!(6, map.capacity());
616 /// ```
617 pub fn capacity(&self) -> usize {
618 usable_capacity(self.indices.len())
619 }
620
621 /// Reserves capacity for at least `additional` more headers to be inserted
622 /// into the `HeaderMap`.
623 ///
624 /// The header map may reserve more space to avoid frequent reallocations.
625 /// Like with `with_capacity`, this will be a "best effort" to avoid
626 /// allocations until `additional` more headers are inserted. Certain usage
627 /// patterns could cause additional allocations before the number is
628 /// reached.
629 ///
630 /// # Panics
631 ///
632 /// Panics if the new allocation size overflows `usize`.
633 ///
634 /// # Examples
635 ///
636 /// ```
637 /// # use http::HeaderMap;
638 /// # use http::header::HOST;
639 /// let mut map = HeaderMap::new();
640 /// map.reserve(10);
641 /// # map.insert(HOST, "bar".parse().unwrap());
642 /// ```
643 pub fn reserve(&mut self, additional: usize) {
644 // TODO: This can't overflow if done properly... since the max # of
645 // elements is u16::MAX.
646 let cap = self
647 .entries
648 .len()
649 .checked_add(additional)
650 .expect("reserve overflow");
651
652 if cap > self.indices.len() {
653 let cap = cap.next_power_of_two();
654 assert!(cap <= MAX_SIZE, "header map reserve over max capacity");
655 assert!(cap != 0, "header map reserve overflowed");
656
657 if self.entries.len() == 0 {
658 self.mask = cap as Size - 1;
659 self.indices = vec![Pos::none(); cap].into_boxed_slice();
660 self.entries = Vec::with_capacity(usable_capacity(cap));
661 } else {
662 self.grow(cap);
663 }
664 }
665 }
666
667 /// Returns a reference to the value associated with the key.
668 ///
669 /// If there are multiple values associated with the key, then the first one
670 /// is returned. Use `get_all` to get all values associated with a given
671 /// key. Returns `None` if there are no values associated with the key.
672 ///
673 /// # Examples
674 ///
675 /// ```
676 /// # use http::HeaderMap;
677 /// # use http::header::HOST;
678 /// let mut map = HeaderMap::new();
679 /// assert!(map.get("host").is_none());
680 ///
681 /// map.insert(HOST, "hello".parse().unwrap());
682 /// assert_eq!(map.get(HOST).unwrap(), &"hello");
683 /// assert_eq!(map.get("host").unwrap(), &"hello");
684 ///
685 /// map.append(HOST, "world".parse().unwrap());
686 /// assert_eq!(map.get("host").unwrap(), &"hello");
687 /// ```
688 pub fn get<K>(&self, key: K) -> Option<&T>
689 where
690 K: AsHeaderName,
691 {
692 self.get2(&key)
693 }
694
695 fn get2<K>(&self, key: &K) -> Option<&T>
696 where
697 K: AsHeaderName,
698 {
699 match key.find(self) {
700 Some((_, found)) => {
701 let entry = &self.entries[found];
702 Some(&entry.value)
703 }
704 None => None,
705 }
706 }
707
708 /// Returns a mutable reference to the value associated with the key.
709 ///
710 /// If there are multiple values associated with the key, then the first one
711 /// is returned. Use `entry` to get all values associated with a given
712 /// key. Returns `None` if there are no values associated with the key.
713 ///
714 /// # Examples
715 ///
716 /// ```
717 /// # use http::HeaderMap;
718 /// # use http::header::HOST;
719 /// let mut map = HeaderMap::default();
720 /// map.insert(HOST, "hello".to_string());
721 /// map.get_mut("host").unwrap().push_str("-world");
722 ///
723 /// assert_eq!(map.get(HOST).unwrap(), &"hello-world");
724 /// ```
725 pub fn get_mut<K>(&mut self, key: K) -> Option<&mut T>
726 where
727 K: AsHeaderName,
728 {
729 match key.find(self) {
730 Some((_, found)) => {
731 let entry = &mut self.entries[found];
732 Some(&mut entry.value)
733 }
734 None => None,
735 }
736 }
737
738 /// Returns a view of all values associated with a key.
739 ///
740 /// The returned view does not incur any allocations and allows iterating
741 /// the values associated with the key. See [`GetAll`] for more details.
742 /// Returns `None` if there are no values associated with the key.
743 ///
744 /// [`GetAll`]: struct.GetAll.html
745 ///
746 /// # Examples
747 ///
748 /// ```
749 /// # use http::HeaderMap;
750 /// # use http::header::HOST;
751 /// let mut map = HeaderMap::new();
752 ///
753 /// map.insert(HOST, "hello".parse().unwrap());
754 /// map.append(HOST, "goodbye".parse().unwrap());
755 ///
756 /// let view = map.get_all("host");
757 ///
758 /// let mut iter = view.iter();
759 /// assert_eq!(&"hello", iter.next().unwrap());
760 /// assert_eq!(&"goodbye", iter.next().unwrap());
761 /// assert!(iter.next().is_none());
762 /// ```
763 pub fn get_all<K>(&self, key: K) -> GetAll<'_, T>
764 where
765 K: AsHeaderName,
766 {
767 GetAll {
768 map: self,
769 index: key.find(self).map(|(_, i)| i),
770 }
771 }
772
773 /// Returns true if the map contains a value for the specified key.
774 ///
775 /// # Examples
776 ///
777 /// ```
778 /// # use http::HeaderMap;
779 /// # use http::header::HOST;
780 /// let mut map = HeaderMap::new();
781 /// assert!(!map.contains_key(HOST));
782 ///
783 /// map.insert(HOST, "world".parse().unwrap());
784 /// assert!(map.contains_key("host"));
785 /// ```
786 pub fn contains_key<K>(&self, key: K) -> bool
787 where
788 K: AsHeaderName,
789 {
790 key.find(self).is_some()
791 }
792
793 /// An iterator visiting all key-value pairs.
794 ///
795 /// The iteration order is arbitrary, but consistent across platforms for
796 /// the same crate version. Each key will be yielded once per associated
797 /// value. So, if a key has 3 associated values, it will be yielded 3 times.
798 ///
799 /// # Examples
800 ///
801 /// ```
802 /// # use http::HeaderMap;
803 /// # use http::header::{CONTENT_LENGTH, HOST};
804 /// let mut map = HeaderMap::new();
805 ///
806 /// map.insert(HOST, "hello".parse().unwrap());
807 /// map.append(HOST, "goodbye".parse().unwrap());
808 /// map.insert(CONTENT_LENGTH, "123".parse().unwrap());
809 ///
810 /// for (key, value) in map.iter() {
811 /// println!("{:?}: {:?}", key, value);
812 /// }
813 /// ```
814 pub fn iter(&self) -> Iter<'_, T> {
815 Iter {
816 map: self,
817 entry: 0,
818 cursor: self.entries.first().map(|_| Cursor::Head),
819 }
820 }
821
822 /// An iterator visiting all key-value pairs, with mutable value references.
823 ///
824 /// The iterator order is arbitrary, but consistent across platforms for the
825 /// same crate version. Each key will be yielded once per associated value,
826 /// so if a key has 3 associated values, it will be yielded 3 times.
827 ///
828 /// # Examples
829 ///
830 /// ```
831 /// # use http::HeaderMap;
832 /// # use http::header::{CONTENT_LENGTH, HOST};
833 /// let mut map = HeaderMap::default();
834 ///
835 /// map.insert(HOST, "hello".to_string());
836 /// map.append(HOST, "goodbye".to_string());
837 /// map.insert(CONTENT_LENGTH, "123".to_string());
838 ///
839 /// for (key, value) in map.iter_mut() {
840 /// value.push_str("-boop");
841 /// }
842 /// ```
843 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
844 IterMut {
845 map: self as *mut _,
846 entry: 0,
847 cursor: self.entries.first().map(|_| Cursor::Head),
848 lt: PhantomData,
849 }
850 }
851
852 /// An iterator visiting all keys.
853 ///
854 /// The iteration order is arbitrary, but consistent across platforms for
855 /// the same crate version. Each key will be yielded only once even if it
856 /// has multiple associated values.
857 ///
858 /// # Examples
859 ///
860 /// ```
861 /// # use http::HeaderMap;
862 /// # use http::header::{CONTENT_LENGTH, HOST};
863 /// let mut map = HeaderMap::new();
864 ///
865 /// map.insert(HOST, "hello".parse().unwrap());
866 /// map.append(HOST, "goodbye".parse().unwrap());
867 /// map.insert(CONTENT_LENGTH, "123".parse().unwrap());
868 ///
869 /// for key in map.keys() {
870 /// println!("{:?}", key);
871 /// }
872 /// ```
873 pub fn keys(&self) -> Keys<'_, T> {
874 Keys {
875 inner: self.entries.iter(),
876 }
877 }
878
879 /// An iterator visiting all values.
880 ///
881 /// The iteration order is arbitrary, but consistent across platforms for
882 /// the same crate version.
883 ///
884 /// # Examples
885 ///
886 /// ```
887 /// # use http::HeaderMap;
888 /// # use http::header::{CONTENT_LENGTH, HOST};
889 /// let mut map = HeaderMap::new();
890 ///
891 /// map.insert(HOST, "hello".parse().unwrap());
892 /// map.append(HOST, "goodbye".parse().unwrap());
893 /// map.insert(CONTENT_LENGTH, "123".parse().unwrap());
894 ///
895 /// for value in map.values() {
896 /// println!("{:?}", value);
897 /// }
898 /// ```
899 pub fn values(&self) -> Values<'_, T> {
900 Values { inner: self.iter() }
901 }
902
903 /// An iterator visiting all values mutably.
904 ///
905 /// The iteration order is arbitrary, but consistent across platforms for
906 /// the same crate version.
907 ///
908 /// # Examples
909 ///
910 /// ```
911 /// # use http::HeaderMap;
912 /// # use http::header::{CONTENT_LENGTH, HOST};
913 /// let mut map = HeaderMap::default();
914 ///
915 /// map.insert(HOST, "hello".to_string());
916 /// map.append(HOST, "goodbye".to_string());
917 /// map.insert(CONTENT_LENGTH, "123".to_string());
918 ///
919 /// for value in map.values_mut() {
920 /// value.push_str("-boop");
921 /// }
922 /// ```
923 pub fn values_mut(&mut self) -> ValuesMut<'_, T> {
924 ValuesMut {
925 inner: self.iter_mut(),
926 }
927 }
928
929 /// Clears the map, returning all entries as an iterator.
930 ///
931 /// The internal memory is kept for reuse.
932 ///
933 /// For each yielded item that has `None` provided for the `HeaderName`,
934 /// then the associated header name is the same as that of the previously
935 /// yielded item. The first yielded item will have `HeaderName` set.
936 ///
937 /// # Examples
938 ///
939 /// ```
940 /// # use http::HeaderMap;
941 /// # use http::header::{CONTENT_LENGTH, HOST};
942 /// let mut map = HeaderMap::new();
943 ///
944 /// map.insert(HOST, "hello".parse().unwrap());
945 /// map.append(HOST, "goodbye".parse().unwrap());
946 /// map.insert(CONTENT_LENGTH, "123".parse().unwrap());
947 ///
948 /// let mut drain = map.drain();
949 ///
950 ///
951 /// assert_eq!(drain.next(), Some((Some(HOST), "hello".parse().unwrap())));
952 /// assert_eq!(drain.next(), Some((None, "goodbye".parse().unwrap())));
953 ///
954 /// assert_eq!(drain.next(), Some((Some(CONTENT_LENGTH), "123".parse().unwrap())));
955 ///
956 /// assert_eq!(drain.next(), None);
957 /// ```
958 pub fn drain(&mut self) -> Drain<'_, T> {
959 for i in self.indices.iter_mut() {
960 *i = Pos::none();
961 }
962
963 // Memory safety
964 //
965 // When the Drain is first created, it shortens the length of
966 // the source vector to make sure no uninitialized or moved-from
967 // elements are accessible at all if the Drain's destructor never
968 // gets to run.
969
970 let entries = &mut self.entries[..] as *mut _;
971 let extra_values = &mut self.extra_values as *mut _;
972 let len = self.entries.len();
973 unsafe { self.entries.set_len(0); }
974
975 Drain {
976 idx: 0,
977 len,
978 entries,
979 extra_values,
980 next: None,
981 lt: PhantomData,
982 }
983 }
984
985 fn value_iter(&self, idx: Option<usize>) -> ValueIter<'_, T> {
986 use self::Cursor::*;
987
988 if let Some(idx) = idx {
989 let back = {
990 let entry = &self.entries[idx];
991
992 entry.links.map(|l| Values(l.tail)).unwrap_or(Head)
993 };
994
995 ValueIter {
996 map: self,
997 index: idx,
998 front: Some(Head),
999 back: Some(back),
1000 }
1001 } else {
1002 ValueIter {
1003 map: self,
1004 index: ::std::usize::MAX,
1005 front: None,
1006 back: None,
1007 }
1008 }
1009 }
1010
1011 fn value_iter_mut(&mut self, idx: usize) -> ValueIterMut<'_, T> {
1012 use self::Cursor::*;
1013
1014 let back = {
1015 let entry = &self.entries[idx];
1016
1017 entry.links.map(|l| Values(l.tail)).unwrap_or(Head)
1018 };
1019
1020 ValueIterMut {
1021 map: self as *mut _,
1022 index: idx,
1023 front: Some(Head),
1024 back: Some(back),
1025 lt: PhantomData,
1026 }
1027 }
1028
1029 /// Gets the given key's corresponding entry in the map for in-place
1030 /// manipulation.
1031 ///
1032 /// # Examples
1033 ///
1034 /// ```
1035 /// # use http::HeaderMap;
1036 /// let mut map: HeaderMap<u32> = HeaderMap::default();
1037 ///
1038 /// let headers = &[
1039 /// "content-length",
1040 /// "x-hello",
1041 /// "Content-Length",
1042 /// "x-world",
1043 /// ];
1044 ///
1045 /// for &header in headers {
1046 /// let counter = map.entry(header).or_insert(0);
1047 /// *counter += 1;
1048 /// }
1049 ///
1050 /// assert_eq!(map["content-length"], 2);
1051 /// assert_eq!(map["x-hello"], 1);
1052 /// ```
1053 pub fn entry<K>(&mut self, key: K) -> Entry<'_, T>
1054 where
1055 K: IntoHeaderName,
1056 {
1057 key.entry(self)
1058 }
1059
1060 /// Gets the given key's corresponding entry in the map for in-place
1061 /// manipulation.
1062 ///
1063 /// # Errors
1064 ///
1065 /// This method differs from `entry` by allowing types that may not be
1066 /// valid `HeaderName`s to passed as the key (such as `String`). If they
1067 /// do not parse as a valid `HeaderName`, this returns an
1068 /// `InvalidHeaderName` error.
1069 pub fn try_entry<K>(&mut self, key: K) -> Result<Entry<'_, T>, InvalidHeaderName>
1070 where
1071 K: AsHeaderName,
1072 {
1073 key.try_entry(self)
1074 }
1075
1076 fn entry2<K>(&mut self, key: K) -> Entry<'_, T>
1077 where
1078 K: Hash + Into<HeaderName>,
1079 HeaderName: PartialEq<K>,
1080 {
1081 // Ensure that there is space in the map
1082 self.reserve_one();
1083
1084 insert_phase_one!(
1085 self,
1086 key,
1087 probe,
1088 pos,
1089 hash,
1090 danger,
1091 Entry::Vacant(VacantEntry {
1092 map: self,
1093 hash: hash,
1094 key: key.into(),
1095 probe: probe,
1096 danger: danger,
1097 }),
1098 Entry::Occupied(OccupiedEntry {
1099 map: self,
1100 index: pos,
1101 probe: probe,
1102 }),
1103 Entry::Vacant(VacantEntry {
1104 map: self,
1105 hash: hash,
1106 key: key.into(),
1107 probe: probe,
1108 danger: danger,
1109 })
1110 )
1111 }
1112
1113 /// Inserts a key-value pair into the map.
1114 ///
1115 /// If the map did not previously have this key present, then `None` is
1116 /// returned.
1117 ///
1118 /// If the map did have this key present, the new value is associated with
1119 /// the key and all previous values are removed. **Note** that only a single
1120 /// one of the previous values is returned. If there are multiple values
1121 /// that have been previously associated with the key, then the first one is
1122 /// returned. See `insert_mult` on `OccupiedEntry` for an API that returns
1123 /// all values.
1124 ///
1125 /// The key is not updated, though; this matters for types that can be `==`
1126 /// without being identical.
1127 ///
1128 /// # Examples
1129 ///
1130 /// ```
1131 /// # use http::HeaderMap;
1132 /// # use http::header::HOST;
1133 /// let mut map = HeaderMap::new();
1134 /// assert!(map.insert(HOST, "world".parse().unwrap()).is_none());
1135 /// assert!(!map.is_empty());
1136 ///
1137 /// let mut prev = map.insert(HOST, "earth".parse().unwrap()).unwrap();
1138 /// assert_eq!("world", prev);
1139 /// ```
1140 pub fn insert<K>(&mut self, key: K, val: T) -> Option<T>
1141 where
1142 K: IntoHeaderName,
1143 {
1144 key.insert(self, val)
1145 }
1146
1147 #[inline]
1148 fn insert2<K>(&mut self, key: K, value: T) -> Option<T>
1149 where
1150 K: Hash + Into<HeaderName>,
1151 HeaderName: PartialEq<K>,
1152 {
1153 self.reserve_one();
1154
1155 insert_phase_one!(
1156 self,
1157 key,
1158 probe,
1159 pos,
1160 hash,
1161 danger,
1162 // Vacant
1163 {
1164 let _ = danger; // Make lint happy
1165 let index = self.entries.len();
1166 self.insert_entry(hash, key.into(), value);
1167 self.indices[probe] = Pos::new(index, hash);
1168 None
1169 },
1170 // Occupied
1171 Some(self.insert_occupied(pos, value)),
1172 // Robinhood
1173 {
1174 self.insert_phase_two(key.into(), value, hash, probe, danger);
1175 None
1176 }
1177 )
1178 }
1179
1180 /// Set an occupied bucket to the given value
1181 #[inline]
1182 fn insert_occupied(&mut self, index: usize, value: T) -> T {
1183 if let Some(links) = self.entries[index].links {
1184 self.remove_all_extra_values(links.next);
1185 }
1186
1187 let entry = &mut self.entries[index];
1188 mem::replace(&mut entry.value, value)
1189 }
1190
1191 fn insert_occupied_mult(&mut self, index: usize, value: T) -> ValueDrain<'_, T> {
1192 let old;
1193 let links;
1194
1195 {
1196 let entry = &mut self.entries[index];
1197
1198 old = mem::replace(&mut entry.value, value);
1199 links = entry.links.take();
1200 }
1201
1202 let raw_links = self.raw_links();
1203 let extra_values = &mut self.extra_values;
1204
1205 let next = links.map(|l| {
1206 drain_all_extra_values(raw_links, extra_values, l.next)
1207 .into_iter()
1208 });
1209
1210 ValueDrain {
1211 first: Some(old),
1212 next: next,
1213 lt: PhantomData,
1214 }
1215 }
1216
1217 /// Inserts a key-value pair into the map.
1218 ///
1219 /// If the map did not previously have this key present, then `false` is
1220 /// returned.
1221 ///
1222 /// If the map did have this key present, the new value is pushed to the end
1223 /// of the list of values currently associated with the key. The key is not
1224 /// updated, though; this matters for types that can be `==` without being
1225 /// identical.
1226 ///
1227 /// # Examples
1228 ///
1229 /// ```
1230 /// # use http::HeaderMap;
1231 /// # use http::header::HOST;
1232 /// let mut map = HeaderMap::new();
1233 /// assert!(map.insert(HOST, "world".parse().unwrap()).is_none());
1234 /// assert!(!map.is_empty());
1235 ///
1236 /// map.append(HOST, "earth".parse().unwrap());
1237 ///
1238 /// let values = map.get_all("host");
1239 /// let mut i = values.iter();
1240 /// assert_eq!("world", *i.next().unwrap());
1241 /// assert_eq!("earth", *i.next().unwrap());
1242 /// ```
1243 pub fn append<K>(&mut self, key: K, value: T) -> bool
1244 where
1245 K: IntoHeaderName,
1246 {
1247 key.append(self, value)
1248 }
1249
1250 #[inline]
1251 fn append2<K>(&mut self, key: K, value: T) -> bool
1252 where
1253 K: Hash + Into<HeaderName>,
1254 HeaderName: PartialEq<K>,
1255 {
1256 self.reserve_one();
1257
1258 insert_phase_one!(
1259 self,
1260 key,
1261 probe,
1262 pos,
1263 hash,
1264 danger,
1265 // Vacant
1266 {
1267 let _ = danger;
1268 let index = self.entries.len();
1269 self.insert_entry(hash, key.into(), value);
1270 self.indices[probe] = Pos::new(index, hash);
1271 false
1272 },
1273 // Occupied
1274 {
1275 append_value(pos, &mut self.entries[pos], &mut self.extra_values, value);
1276 true
1277 },
1278 // Robinhood
1279 {
1280 self.insert_phase_two(key.into(), value, hash, probe, danger);
1281
1282 false
1283 }
1284 )
1285 }
1286
1287 #[inline]
1288 fn find<K: ?Sized>(&self, key: &K) -> Option<(usize, usize)>
1289 where
1290 K: Hash + Into<HeaderName>,
1291 HeaderName: PartialEq<K>,
1292 {
1293 if self.entries.is_empty() {
1294 return None;
1295 }
1296
1297 let hash = hash_elem_using(&self.danger, key);
1298 let mask = self.mask;
1299 let mut probe = desired_pos(mask, hash);
1300 let mut dist = 0;
1301
1302 probe_loop!(probe < self.indices.len(), {
1303 if let Some((i, entry_hash)) = self.indices[probe].resolve() {
1304 if dist > probe_distance(mask, entry_hash, probe) {
1305 // give up when probe distance is too long
1306 return None;
1307 } else if entry_hash == hash && self.entries[i].key == *key {
1308 return Some((probe, i));
1309 }
1310 } else {
1311 return None;
1312 }
1313
1314 dist += 1;
1315 });
1316 }
1317
1318 /// phase 2 is post-insert where we forward-shift `Pos` in the indices.
1319 #[inline]
1320 fn insert_phase_two(
1321 &mut self,
1322 key: HeaderName,
1323 value: T,
1324 hash: HashValue,
1325 probe: usize,
1326 danger: bool,
1327 ) -> usize {
1328 // Push the value and get the index
1329 let index = self.entries.len();
1330 self.insert_entry(hash, key, value);
1331
1332 let num_displaced = do_insert_phase_two(&mut self.indices, probe, Pos::new(index, hash));
1333
1334 if danger || num_displaced >= DISPLACEMENT_THRESHOLD {
1335 // Increase danger level
1336 self.danger.to_yellow();
1337 }
1338
1339 index
1340 }
1341
1342 /// Removes a key from the map, returning the value associated with the key.
1343 ///
1344 /// Returns `None` if the map does not contain the key. If there are
1345 /// multiple values associated with the key, then the first one is returned.
1346 /// See `remove_entry_mult` on `OccupiedEntry` for an API that yields all
1347 /// values.
1348 ///
1349 /// # Examples
1350 ///
1351 /// ```
1352 /// # use http::HeaderMap;
1353 /// # use http::header::HOST;
1354 /// let mut map = HeaderMap::new();
1355 /// map.insert(HOST, "hello.world".parse().unwrap());
1356 ///
1357 /// let prev = map.remove(HOST).unwrap();
1358 /// assert_eq!("hello.world", prev);
1359 ///
1360 /// assert!(map.remove(HOST).is_none());
1361 /// ```
1362 pub fn remove<K>(&mut self, key: K) -> Option<T>
1363 where
1364 K: AsHeaderName,
1365 {
1366 match key.find(self) {
1367 Some((probe, idx)) => {
1368 if let Some(links) = self.entries[idx].links {
1369 self.remove_all_extra_values(links.next);
1370 }
1371
1372 let entry = self.remove_found(probe, idx);
1373
1374 Some(entry.value)
1375 }
1376 None => None,
1377 }
1378 }
1379
1380 /// Remove an entry from the map.
1381 ///
1382 /// Warning: To avoid inconsistent state, extra values _must_ be removed
1383 /// for the `found` index (via `remove_all_extra_values` or similar)
1384 /// _before_ this method is called.
1385 #[inline]
1386 fn remove_found(&mut self, probe: usize, found: usize) -> Bucket<T> {
1387 // index `probe` and entry `found` is to be removed
1388 // use swap_remove, but then we need to update the index that points
1389 // to the other entry that has to move
1390 self.indices[probe] = Pos::none();
1391 let entry = self.entries.swap_remove(found);
1392
1393 // correct index that points to the entry that had to swap places
1394 if let Some(entry) = self.entries.get(found) {
1395 // was not last element
1396 // examine new element in `found` and find it in indices
1397 let mut probe = desired_pos(self.mask, entry.hash);
1398
1399 probe_loop!(probe < self.indices.len(), {
1400 if let Some((i, _)) = self.indices[probe].resolve() {
1401 if i >= self.entries.len() {
1402 // found it
1403 self.indices[probe] = Pos::new(found, entry.hash);
1404 break;
1405 }
1406 }
1407 });
1408
1409 // Update links
1410 if let Some(links) = entry.links {
1411 self.extra_values[links.next].prev = Link::Entry(found);
1412 self.extra_values[links.tail].next = Link::Entry(found);
1413 }
1414 }
1415
1416 // backward shift deletion in self.indices
1417 // after probe, shift all non-ideally placed indices backward
1418 if self.entries.len() > 0 {
1419 let mut last_probe = probe;
1420 let mut probe = probe + 1;
1421
1422 probe_loop!(probe < self.indices.len(), {
1423 if let Some((_, entry_hash)) = self.indices[probe].resolve() {
1424 if probe_distance(self.mask, entry_hash, probe) > 0 {
1425 self.indices[last_probe] = self.indices[probe];
1426 self.indices[probe] = Pos::none();
1427 } else {
1428 break;
1429 }
1430 } else {
1431 break;
1432 }
1433
1434 last_probe = probe;
1435 });
1436 }
1437
1438 entry
1439 }
1440
1441 /// Removes the `ExtraValue` at the given index.
1442 #[inline]
1443 fn remove_extra_value(&mut self, idx: usize) -> ExtraValue<T> {
1444 let raw_links = self.raw_links();
1445 remove_extra_value(raw_links, &mut self.extra_values, idx)
1446 }
1447
1448 fn remove_all_extra_values(&mut self, mut head: usize) {
1449 loop {
1450 let extra = self.remove_extra_value(head);
1451
1452 if let Link::Extra(idx) = extra.next {
1453 head = idx;
1454 } else {
1455 break;
1456 }
1457 }
1458 }
1459
1460 #[inline]
1461 fn insert_entry(&mut self, hash: HashValue, key: HeaderName, value: T) {
1462 assert!(self.entries.len() < MAX_SIZE, "header map at capacity");
1463
1464 self.entries.push(Bucket {
1465 hash: hash,
1466 key: key,
1467 value: value,
1468 links: None,
1469 });
1470 }
1471
1472 fn rebuild(&mut self) {
1473 // Loop over all entries and re-insert them into the map
1474 'outer: for (index, entry) in self.entries.iter_mut().enumerate() {
1475 let hash = hash_elem_using(&self.danger, &entry.key);
1476 let mut probe = desired_pos(self.mask, hash);
1477 let mut dist = 0;
1478
1479 // Update the entry's hash code
1480 entry.hash = hash;
1481
1482 probe_loop!(probe < self.indices.len(), {
1483 if let Some((_, entry_hash)) = self.indices[probe].resolve() {
1484 // if existing element probed less than us, swap
1485 let their_dist = probe_distance(self.mask, entry_hash, probe);
1486
1487 if their_dist < dist {
1488 // Robinhood
1489 break;
1490 }
1491 } else {
1492 // Vacant slot
1493 self.indices[probe] = Pos::new(index, hash);
1494 continue 'outer;
1495 }
1496
1497 dist += 1;
1498 });
1499
1500 do_insert_phase_two(&mut self.indices, probe, Pos::new(index, hash));
1501 }
1502 }
1503
1504 fn reinsert_entry_in_order(&mut self, pos: Pos) {
1505 if let Some((_, entry_hash)) = pos.resolve() {
1506 // Find first empty bucket and insert there
1507 let mut probe = desired_pos(self.mask, entry_hash);
1508
1509 probe_loop!(probe < self.indices.len(), {
1510 if self.indices[probe].resolve().is_none() {
1511 // empty bucket, insert here
1512 self.indices[probe] = pos;
1513 return;
1514 }
1515 });
1516 }
1517 }
1518
1519 fn reserve_one(&mut self) {
1520 let len = self.entries.len();
1521
1522 if self.danger.is_yellow() {
1523 let load_factor = self.entries.len() as f32 / self.indices.len() as f32;
1524
1525 if load_factor >= LOAD_FACTOR_THRESHOLD {
1526 // Transition back to green danger level
1527 self.danger.to_green();
1528
1529 // Double the capacity
1530 let new_cap = self.indices.len() * 2;
1531
1532 // Grow the capacity
1533 self.grow(new_cap);
1534 } else {
1535 self.danger.to_red();
1536
1537 // Rebuild hash table
1538 for index in self.indices.iter_mut() {
1539 *index = Pos::none();
1540 }
1541
1542 self.rebuild();
1543 }
1544 } else if len == self.capacity() {
1545 if len == 0 {
1546 let new_raw_cap = 8;
1547 self.mask = 8 - 1;
1548 self.indices = vec![Pos::none(); new_raw_cap].into_boxed_slice();
1549 self.entries = Vec::with_capacity(usable_capacity(new_raw_cap));
1550 } else {
1551 let raw_cap = self.indices.len();
1552 self.grow(raw_cap << 1);
1553 }
1554 }
1555 }
1556
1557 #[inline]
1558 fn grow(&mut self, new_raw_cap: usize) {
1559 assert!(new_raw_cap <= MAX_SIZE, "requested capacity too large");
1560 // This path can never be reached when handling the first allocation in
1561 // the map.
1562
1563 // find first ideally placed element -- start of cluster
1564 let mut first_ideal = 0;
1565
1566 for (i, pos) in self.indices.iter().enumerate() {
1567 if let Some((_, entry_hash)) = pos.resolve() {
1568 if 0 == probe_distance(self.mask, entry_hash, i) {
1569 first_ideal = i;
1570 break;
1571 }
1572 }
1573 }
1574
1575 // visit the entries in an order where we can simply reinsert them
1576 // into self.indices without any bucket stealing.
1577 let old_indices = mem::replace(
1578 &mut self.indices,
1579 vec![Pos::none(); new_raw_cap].into_boxed_slice(),
1580 );
1581 self.mask = new_raw_cap.wrapping_sub(1) as Size;
1582
1583 for &pos in &old_indices[first_ideal..] {
1584 self.reinsert_entry_in_order(pos);
1585 }
1586
1587 for &pos in &old_indices[..first_ideal] {
1588 self.reinsert_entry_in_order(pos);
1589 }
1590
1591 // Reserve additional entry slots
1592 let more = self.capacity() - self.entries.len();
1593 self.entries.reserve_exact(more);
1594 }
1595
1596 #[inline]
1597 fn raw_links(&mut self) -> RawLinks<T> {
1598 RawLinks(&mut self.entries[..] as *mut _)
1599 }
1600}
1601
1602/// Removes the `ExtraValue` at the given index.
1603#[inline]
1604fn remove_extra_value<T>(
1605 mut raw_links: RawLinks<T>,
1606 extra_values: &mut Vec<ExtraValue<T>>,
1607 idx: usize)
1608 -> ExtraValue<T>
1609{
1610 let prev;
1611 let next;
1612
1613 {
1614 debug_assert!(extra_values.len() > idx);
1615 let extra = &extra_values[idx];
1616 prev = extra.prev;
1617 next = extra.next;
1618 }
1619
1620 // First unlink the extra value
1621 match (prev, next) {
1622 (Link::Entry(prev), Link::Entry(next)) => {
1623 debug_assert_eq!(prev, next);
1624
1625 raw_links[prev] = None;
1626 }
1627 (Link::Entry(prev), Link::Extra(next)) => {
1628 debug_assert!(raw_links[prev].is_some());
1629
1630 raw_links[prev].as_mut().unwrap()
1631 .next = next;
1632
1633 debug_assert!(extra_values.len() > next);
1634 extra_values[next].prev = Link::Entry(prev);
1635 }
1636 (Link::Extra(prev), Link::Entry(next)) => {
1637 debug_assert!(raw_links[next].is_some());
1638
1639 raw_links[next].as_mut().unwrap()
1640 .tail = prev;
1641
1642 debug_assert!(extra_values.len() > prev);
1643 extra_values[prev].next = Link::Entry(next);
1644 }
1645 (Link::Extra(prev), Link::Extra(next)) => {
1646 debug_assert!(extra_values.len() > next);
1647 debug_assert!(extra_values.len() > prev);
1648
1649 extra_values[prev].next = Link::Extra(next);
1650 extra_values[next].prev = Link::Extra(prev);
1651 }
1652 }
1653
1654 // Remove the extra value
1655 let mut extra = extra_values.swap_remove(idx);
1656
1657 // This is the index of the value that was moved (possibly `extra`)
1658 let old_idx = extra_values.len();
1659
1660 // Update the links
1661 if extra.prev == Link::Extra(old_idx) {
1662 extra.prev = Link::Extra(idx);
1663 }
1664
1665 if extra.next == Link::Extra(old_idx) {
1666 extra.next = Link::Extra(idx);
1667 }
1668
1669 // Check if another entry was displaced. If it was, then the links
1670 // need to be fixed.
1671 if idx != old_idx {
1672 let next;
1673 let prev;
1674
1675 {
1676 debug_assert!(extra_values.len() > idx);
1677 let moved = &extra_values[idx];
1678 next = moved.next;
1679 prev = moved.prev;
1680 }
1681
1682 // An entry was moved, we have to the links
1683 match prev {
1684 Link::Entry(entry_idx) => {
1685 // It is critical that we do not attempt to read the
1686 // header name or value as that memory may have been
1687 // "released" already.
1688 debug_assert!(raw_links[entry_idx].is_some());
1689
1690 let links = raw_links[entry_idx].as_mut().unwrap();
1691 links.next = idx;
1692 }
1693 Link::Extra(extra_idx) => {
1694 debug_assert!(extra_values.len() > extra_idx);
1695 extra_values[extra_idx].next = Link::Extra(idx);
1696 }
1697 }
1698
1699 match next {
1700 Link::Entry(entry_idx) => {
1701 debug_assert!(raw_links[entry_idx].is_some());
1702
1703 let links = raw_links[entry_idx].as_mut().unwrap();
1704 links.tail = idx;
1705 }
1706 Link::Extra(extra_idx) => {
1707 debug_assert!(extra_values.len() > extra_idx);
1708 extra_values[extra_idx].prev = Link::Extra(idx);
1709 }
1710 }
1711 }
1712
1713 debug_assert!({
1714 for v in &*extra_values {
1715 assert!(v.next != Link::Extra(old_idx));
1716 assert!(v.prev != Link::Extra(old_idx));
1717 }
1718
1719 true
1720 });
1721
1722 extra
1723}
1724
1725fn drain_all_extra_values<T>(
1726 raw_links: RawLinks<T>,
1727 extra_values: &mut Vec<ExtraValue<T>>,
1728 mut head: usize)
1729 -> Vec<T>
1730{
1731 let mut vec = Vec::new();
1732 loop {
1733 let extra = remove_extra_value(raw_links, extra_values, head);
1734 vec.push(extra.value);
1735
1736 if let Link::Extra(idx) = extra.next {
1737 head = idx;
1738 } else {
1739 break;
1740 }
1741 }
1742 vec
1743}
1744
1745impl<'a, T> IntoIterator for &'a HeaderMap<T> {
1746 type Item = (&'a HeaderName, &'a T);
1747 type IntoIter = Iter<'a, T>;
1748
1749 fn into_iter(self) -> Iter<'a, T> {
1750 self.iter()
1751 }
1752}
1753
1754impl<'a, T> IntoIterator for &'a mut HeaderMap<T> {
1755 type Item = (&'a HeaderName, &'a mut T);
1756 type IntoIter = IterMut<'a, T>;
1757
1758 fn into_iter(self) -> IterMut<'a, T> {
1759 self.iter_mut()
1760 }
1761}
1762
1763impl<T> IntoIterator for HeaderMap<T> {
1764 type Item = (Option<HeaderName>, T);
1765 type IntoIter = IntoIter<T>;
1766
1767 /// Creates a consuming iterator, that is, one that moves keys and values
1768 /// out of the map in arbitrary order. The map cannot be used after calling
1769 /// this.
1770 ///
1771 /// For each yielded item that has `None` provided for the `HeaderName`,
1772 /// then the associated header name is the same as that of the previously
1773 /// yielded item. The first yielded item will have `HeaderName` set.
1774 ///
1775 /// # Examples
1776 ///
1777 /// Basic usage.
1778 ///
1779 /// ```
1780 /// # use http::header;
1781 /// # use http::header::*;
1782 /// let mut map = HeaderMap::new();
1783 /// map.insert(header::CONTENT_LENGTH, "123".parse().unwrap());
1784 /// map.insert(header::CONTENT_TYPE, "json".parse().unwrap());
1785 ///
1786 /// let mut iter = map.into_iter();
1787 /// assert_eq!(iter.next(), Some((Some(header::CONTENT_LENGTH), "123".parse().unwrap())));
1788 /// assert_eq!(iter.next(), Some((Some(header::CONTENT_TYPE), "json".parse().unwrap())));
1789 /// assert!(iter.next().is_none());
1790 /// ```
1791 ///
1792 /// Multiple values per key.
1793 ///
1794 /// ```
1795 /// # use http::header;
1796 /// # use http::header::*;
1797 /// let mut map = HeaderMap::new();
1798 ///
1799 /// map.append(header::CONTENT_LENGTH, "123".parse().unwrap());
1800 /// map.append(header::CONTENT_LENGTH, "456".parse().unwrap());
1801 ///
1802 /// map.append(header::CONTENT_TYPE, "json".parse().unwrap());
1803 /// map.append(header::CONTENT_TYPE, "html".parse().unwrap());
1804 /// map.append(header::CONTENT_TYPE, "xml".parse().unwrap());
1805 ///
1806 /// let mut iter = map.into_iter();
1807 ///
1808 /// assert_eq!(iter.next(), Some((Some(header::CONTENT_LENGTH), "123".parse().unwrap())));
1809 /// assert_eq!(iter.next(), Some((None, "456".parse().unwrap())));
1810 ///
1811 /// assert_eq!(iter.next(), Some((Some(header::CONTENT_TYPE), "json".parse().unwrap())));
1812 /// assert_eq!(iter.next(), Some((None, "html".parse().unwrap())));
1813 /// assert_eq!(iter.next(), Some((None, "xml".parse().unwrap())));
1814 /// assert!(iter.next().is_none());
1815 /// ```
1816 fn into_iter(self) -> IntoIter<T> {
1817 IntoIter {
1818 next: None,
1819 entries: self.entries.into_iter(),
1820 extra_values: self.extra_values,
1821 }
1822 }
1823}
1824
1825impl<T> FromIterator<(HeaderName, T)> for HeaderMap<T> {
1826 fn from_iter<I>(iter: I) -> Self
1827 where
1828 I: IntoIterator<Item = (HeaderName, T)>,
1829 {
1830 let mut map = HeaderMap::default();
1831 map.extend(iter);
1832 map
1833 }
1834}
1835
1836/// Try to convert a `HashMap` into a `HeaderMap`.
1837///
1838/// # Examples
1839///
1840/// ```
1841/// use std::collections::HashMap;
1842/// use std::convert::TryInto;
1843/// use http::HeaderMap;
1844///
1845/// let mut map = HashMap::new();
1846/// map.insert("X-Custom-Header".to_string(), "my value".to_string());
1847///
1848/// let headers: HeaderMap = (&map).try_into().expect("valid headers");
1849/// assert_eq!(headers["X-Custom-Header"], "my value");
1850/// ```
1851impl<'a, K, V, T> TryFrom<&'a HashMap<K, V>> for HeaderMap<T>
1852 where
1853 K: Eq + Hash,
1854 HeaderName: TryFrom<&'a K>,
1855 <HeaderName as TryFrom<&'a K>>::Error: Into<crate::Error>,
1856 T: TryFrom<&'a V>,
1857 T::Error: Into<crate::Error>,
1858{
1859 type Error = Error;
1860
1861 fn try_from(c: &'a HashMap<K, V>) -> Result<Self, Self::Error> {
1862 c.into_iter()
1863 .map(|(k, v)| -> crate::Result<(HeaderName, T)> {
1864 let name = TryFrom::try_from(k).map_err(Into::into)?;
1865 let value = TryFrom::try_from(v).map_err(Into::into)?;
1866 Ok((name, value))
1867 })
1868 .collect()
1869 }
1870}
1871
1872impl<T> Extend<(Option<HeaderName>, T)> for HeaderMap<T> {
1873 /// Extend a `HeaderMap` with the contents of another `HeaderMap`.
1874 ///
1875 /// This function expects the yielded items to follow the same structure as
1876 /// `IntoIter`.
1877 ///
1878 /// # Panics
1879 ///
1880 /// This panics if the first yielded item does not have a `HeaderName`.
1881 ///
1882 /// # Examples
1883 ///
1884 /// ```
1885 /// # use http::header::*;
1886 /// let mut map = HeaderMap::new();
1887 ///
1888 /// map.insert(ACCEPT, "text/plain".parse().unwrap());
1889 /// map.insert(HOST, "hello.world".parse().unwrap());
1890 ///
1891 /// let mut extra = HeaderMap::new();
1892 ///
1893 /// extra.insert(HOST, "foo.bar".parse().unwrap());
1894 /// extra.insert(COOKIE, "hello".parse().unwrap());
1895 /// extra.append(COOKIE, "world".parse().unwrap());
1896 ///
1897 /// map.extend(extra);
1898 ///
1899 /// assert_eq!(map["host"], "foo.bar");
1900 /// assert_eq!(map["accept"], "text/plain");
1901 /// assert_eq!(map["cookie"], "hello");
1902 ///
1903 /// let v = map.get_all("host");
1904 /// assert_eq!(1, v.iter().count());
1905 ///
1906 /// let v = map.get_all("cookie");
1907 /// assert_eq!(2, v.iter().count());
1908 /// ```
1909 fn extend<I: IntoIterator<Item = (Option<HeaderName>, T)>>(&mut self, iter: I) {
1910 let mut iter = iter.into_iter();
1911
1912 // The structure of this is a bit weird, but it is mostly to make the
1913 // borrow checker happy.
1914 let (mut key, mut val) = match iter.next() {
1915 Some((Some(key), val)) => (key, val),
1916 Some((None, _)) => panic!("expected a header name, but got None"),
1917 None => return,
1918 };
1919
1920 'outer: loop {
1921 let mut entry = match self.entry2(key) {
1922 Entry::Occupied(mut e) => {
1923 // Replace all previous values while maintaining a handle to
1924 // the entry.
1925 e.insert(val);
1926 e
1927 }
1928 Entry::Vacant(e) => e.insert_entry(val),
1929 };
1930
1931 // As long as `HeaderName` is none, keep inserting the value into
1932 // the current entry
1933 loop {
1934 match iter.next() {
1935 Some((Some(k), v)) => {
1936 key = k;
1937 val = v;
1938 continue 'outer;
1939 }
1940 Some((None, v)) => {
1941 entry.append(v);
1942 }
1943 None => {
1944 return;
1945 }
1946 }
1947 }
1948 }
1949 }
1950}
1951
1952impl<T> Extend<(HeaderName, T)> for HeaderMap<T> {
1953 fn extend<I: IntoIterator<Item = (HeaderName, T)>>(&mut self, iter: I) {
1954 // Keys may be already present or show multiple times in the iterator.
1955 // Reserve the entire hint lower bound if the map is empty.
1956 // Otherwise reserve half the hint (rounded up), so the map
1957 // will only resize twice in the worst case.
1958 let iter = iter.into_iter();
1959
1960 let reserve = if self.is_empty() {
1961 iter.size_hint().0
1962 } else {
1963 (iter.size_hint().0 + 1) / 2
1964 };
1965
1966 self.reserve(reserve);
1967
1968 for (k, v) in iter {
1969 self.append(k, v);
1970 }
1971 }
1972}
1973
1974impl<T: PartialEq> PartialEq for HeaderMap<T> {
1975 fn eq(&self, other: &HeaderMap<T>) -> bool {
1976 if self.len() != other.len() {
1977 return false;
1978 }
1979
1980 self.keys()
1981 .all(|key| self.get_all(key) == other.get_all(key))
1982 }
1983}
1984
1985impl<T: Eq> Eq for HeaderMap<T> {}
1986
1987impl<T: fmt::Debug> fmt::Debug for HeaderMap<T> {
1988 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1989 f.debug_map().entries(self.iter()).finish()
1990 }
1991}
1992
1993impl<T> Default for HeaderMap<T> {
1994 fn default() -> Self {
1995 HeaderMap::with_capacity(0)
1996 }
1997}
1998
1999impl<'a, K, T> ops::Index<K> for HeaderMap<T>
2000where
2001 K: AsHeaderName,
2002{
2003 type Output = T;
2004
2005 /// # Panics
2006 /// Using the index operator will cause a panic if the header you're querying isn't set.
2007 #[inline]
2008 fn index(&self, index: K) -> &T {
2009 match self.get2(&index) {
2010 Some(val) => val,
2011 None => panic!("no entry found for key {:?}", index.as_str()),
2012 }
2013 }
2014}
2015
2016/// phase 2 is post-insert where we forward-shift `Pos` in the indices.
2017///
2018/// returns the number of displaced elements
2019#[inline]
2020fn do_insert_phase_two(indices: &mut [Pos], mut probe: usize, mut old_pos: Pos) -> usize {
2021 let mut num_displaced = 0;
2022
2023 probe_loop!(probe < indices.len(), {
2024 let pos = &mut indices[probe];
2025
2026 if pos.is_none() {
2027 *pos = old_pos;
2028 break;
2029 } else {
2030 num_displaced += 1;
2031 old_pos = mem::replace(pos, old_pos);
2032 }
2033 });
2034
2035 num_displaced
2036}
2037
2038#[inline]
2039fn append_value<T>(
2040 entry_idx: usize,
2041 entry: &mut Bucket<T>,
2042 extra: &mut Vec<ExtraValue<T>>,
2043 value: T,
2044) {
2045 match entry.links {
2046 Some(links) => {
2047 let idx = extra.len();
2048 extra.push(ExtraValue {
2049 value: value,
2050 prev: Link::Extra(links.tail),
2051 next: Link::Entry(entry_idx),
2052 });
2053
2054 extra[links.tail].next = Link::Extra(idx);
2055
2056 entry.links = Some(Links { tail: idx, ..links });
2057 }
2058 None => {
2059 let idx = extra.len();
2060 extra.push(ExtraValue {
2061 value: value,
2062 prev: Link::Entry(entry_idx),
2063 next: Link::Entry(entry_idx),
2064 });
2065
2066 entry.links = Some(Links {
2067 next: idx,
2068 tail: idx,
2069 });
2070 }
2071 }
2072}
2073
2074// ===== impl Iter =====
2075
2076impl<'a, T> Iterator for Iter<'a, T> {
2077 type Item = (&'a HeaderName, &'a T);
2078
2079 fn next(&mut self) -> Option<Self::Item> {
2080 use self::Cursor::*;
2081
2082 if self.cursor.is_none() {
2083 if (self.entry + 1) >= self.map.entries.len() {
2084 return None;
2085 }
2086
2087 self.entry += 1;
2088 self.cursor = Some(Cursor::Head);
2089 }
2090
2091 let entry = &self.map.entries[self.entry];
2092
2093 match self.cursor.unwrap() {
2094 Head => {
2095 self.cursor = entry.links.map(|l| Values(l.next));
2096 Some((&entry.key, &entry.value))
2097 }
2098 Values(idx) => {
2099 let extra = &self.map.extra_values[idx];
2100
2101 match extra.next {
2102 Link::Entry(_) => self.cursor = None,
2103 Link::Extra(i) => self.cursor = Some(Values(i)),
2104 }
2105
2106 Some((&entry.key, &extra.value))
2107 }
2108 }
2109 }
2110
2111 fn size_hint(&self) -> (usize, Option<usize>) {
2112 let map = self.map;
2113 debug_assert!(map.entries.len() >= self.entry);
2114
2115 let lower = map.entries.len() - self.entry;
2116 // We could pessimistically guess at the upper bound, saying
2117 // that its lower + map.extra_values.len(). That could be
2118 // way over though, such as if we're near the end, and have
2119 // already gone through several extra values...
2120 (lower, None)
2121 }
2122}
2123
2124impl<'a, T> FusedIterator for Iter<'a, T> {}
2125
2126unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
2127unsafe impl<'a, T: Sync> Send for Iter<'a, T> {}
2128
2129// ===== impl IterMut =====
2130
2131impl<'a, T> IterMut<'a, T> {
2132 fn next_unsafe(&mut self) -> Option<(&'a HeaderName, *mut T)> {
2133 use self::Cursor::*;
2134
2135 if self.cursor.is_none() {
2136 if (self.entry + 1) >= unsafe { &*self.map }.entries.len() {
2137 return None;
2138 }
2139
2140 self.entry += 1;
2141 self.cursor = Some(Cursor::Head);
2142 }
2143
2144 let entry = unsafe { &mut (*self.map).entries[self.entry] };
2145
2146 match self.cursor.unwrap() {
2147 Head => {
2148 self.cursor = entry.links.map(|l| Values(l.next));
2149 Some((&entry.key, &mut entry.value as *mut _))
2150 }
2151 Values(idx) => {
2152 let extra = unsafe { &mut (*self.map).extra_values[idx] };
2153
2154 match extra.next {
2155 Link::Entry(_) => self.cursor = None,
2156 Link::Extra(i) => self.cursor = Some(Values(i)),
2157 }
2158
2159 Some((&entry.key, &mut extra.value as *mut _))
2160 }
2161 }
2162 }
2163}
2164
2165impl<'a, T> Iterator for IterMut<'a, T> {
2166 type Item = (&'a HeaderName, &'a mut T);
2167
2168 fn next(&mut self) -> Option<Self::Item> {
2169 self.next_unsafe()
2170 .map(|(key, ptr)| (key, unsafe { &mut *ptr }))
2171 }
2172
2173 fn size_hint(&self) -> (usize, Option<usize>) {
2174 let map = unsafe { &*self.map };
2175 debug_assert!(map.entries.len() >= self.entry);
2176
2177 let lower = map.entries.len() - self.entry;
2178 // We could pessimistically guess at the upper bound, saying
2179 // that its lower + map.extra_values.len(). That could be
2180 // way over though, such as if we're near the end, and have
2181 // already gone through several extra values...
2182 (lower, None)
2183 }
2184}
2185
2186impl<'a, T> FusedIterator for IterMut<'a, T> {}
2187
2188unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
2189unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
2190
2191// ===== impl Keys =====
2192
2193impl<'a, T> Iterator for Keys<'a, T> {
2194 type Item = &'a HeaderName;
2195
2196 fn next(&mut self) -> Option<Self::Item> {
2197 self.inner.next().map(|b| &b.key)
2198 }
2199
2200 fn size_hint(&self) -> (usize, Option<usize>) {
2201 self.inner.size_hint()
2202 }
2203}
2204
2205impl<'a, T> ExactSizeIterator for Keys<'a, T> {}
2206impl<'a, T> FusedIterator for Keys<'a, T> {}
2207
2208// ===== impl Values ====
2209
2210impl<'a, T> Iterator for Values<'a, T> {
2211 type Item = &'a T;
2212
2213 fn next(&mut self) -> Option<Self::Item> {
2214 self.inner.next().map(|(_, v)| v)
2215 }
2216
2217 fn size_hint(&self) -> (usize, Option<usize>) {
2218 self.inner.size_hint()
2219 }
2220}
2221
2222impl<'a, T> FusedIterator for Values<'a, T> {}
2223
2224// ===== impl ValuesMut ====
2225
2226impl<'a, T> Iterator for ValuesMut<'a, T> {
2227 type Item = &'a mut T;
2228
2229 fn next(&mut self) -> Option<Self::Item> {
2230 self.inner.next().map(|(_, v)| v)
2231 }
2232
2233 fn size_hint(&self) -> (usize, Option<usize>) {
2234 self.inner.size_hint()
2235 }
2236}
2237
2238impl<'a, T> FusedIterator for ValuesMut<'a, T> {}
2239
2240// ===== impl Drain =====
2241
2242impl<'a, T> Iterator for Drain<'a, T> {
2243 type Item = (Option<HeaderName>, T);
2244
2245 fn next(&mut self) -> Option<Self::Item> {
2246 if let Some(next) = self.next {
2247 // Remove the extra value
2248
2249 let raw_links = RawLinks(self.entries);
2250 let extra = unsafe {
2251 remove_extra_value(raw_links, &mut *self.extra_values, next)
2252 };
2253
2254 match extra.next {
2255 Link::Extra(idx) => self.next = Some(idx),
2256 Link::Entry(_) => self.next = None,
2257 }
2258
2259 return Some((None, extra.value));
2260 }
2261
2262 let idx = self.idx;
2263
2264 if idx == self.len {
2265 return None;
2266 }
2267
2268 self.idx += 1;
2269
2270 unsafe {
2271 let entry = &(*self.entries)[idx];
2272
2273 // Read the header name
2274 let key = ptr::read(&entry.key as *const _);
2275 let value = ptr::read(&entry.value as *const _);
2276 self.next = entry.links.map(|l| l.next);
2277
2278 Some((Some(key), value))
2279 }
2280 }
2281
2282 fn size_hint(&self) -> (usize, Option<usize>) {
2283 // At least this many names... It's unknown if the user wants
2284 // to count the extra_values on top.
2285 //
2286 // For instance, extending a new `HeaderMap` wouldn't need to
2287 // reserve the upper-bound in `entries`, only the lower-bound.
2288 let lower = self.len - self.idx;
2289 let upper = unsafe { (*self.extra_values).len() } + lower;
2290 (lower, Some(upper))
2291 }
2292}
2293
2294impl<'a, T> FusedIterator for Drain<'a, T> {}
2295
2296impl<'a, T> Drop for Drain<'a, T> {
2297 fn drop(&mut self) {
2298 for _ in self {}
2299 }
2300}
2301
2302unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
2303unsafe impl<'a, T: Send> Send for Drain<'a, T> {}
2304
2305// ===== impl Entry =====
2306
2307impl<'a, T> Entry<'a, T> {
2308 /// Ensures a value is in the entry by inserting the default if empty.
2309 ///
2310 /// Returns a mutable reference to the **first** value in the entry.
2311 ///
2312 /// # Examples
2313 ///
2314 /// ```
2315 /// # use http::HeaderMap;
2316 /// let mut map: HeaderMap<u32> = HeaderMap::default();
2317 ///
2318 /// let headers = &[
2319 /// "content-length",
2320 /// "x-hello",
2321 /// "Content-Length",
2322 /// "x-world",
2323 /// ];
2324 ///
2325 /// for &header in headers {
2326 /// let counter = map.entry(header)
2327 /// .or_insert(0);
2328 /// *counter += 1;
2329 /// }
2330 ///
2331 /// assert_eq!(map["content-length"], 2);
2332 /// assert_eq!(map["x-hello"], 1);
2333 /// ```
2334 pub fn or_insert(self, default: T) -> &'a mut T {
2335 use self::Entry::*;
2336
2337 match self {
2338 Occupied(e) => e.into_mut(),
2339 Vacant(e) => e.insert(default),
2340 }
2341 }
2342
2343 /// Ensures a value is in the entry by inserting the result of the default
2344 /// function if empty.
2345 ///
2346 /// The default function is not called if the entry exists in the map.
2347 /// Returns a mutable reference to the **first** value in the entry.
2348 ///
2349 /// # Examples
2350 ///
2351 /// Basic usage.
2352 ///
2353 /// ```
2354 /// # use http::HeaderMap;
2355 /// let mut map = HeaderMap::new();
2356 ///
2357 /// let res = map.entry("x-hello")
2358 /// .or_insert_with(|| "world".parse().unwrap());
2359 ///
2360 /// assert_eq!(res, "world");
2361 /// ```
2362 ///
2363 /// The default function is not called if the entry exists in the map.
2364 ///
2365 /// ```
2366 /// # use http::HeaderMap;
2367 /// # use http::header::HOST;
2368 /// let mut map = HeaderMap::new();
2369 /// map.insert(HOST, "world".parse().unwrap());
2370 ///
2371 /// let res = map.entry("host")
2372 /// .or_insert_with(|| unreachable!());
2373 ///
2374 ///
2375 /// assert_eq!(res, "world");
2376 /// ```
2377 pub fn or_insert_with<F: FnOnce() -> T>(self, default: F) -> &'a mut T {
2378 use self::Entry::*;
2379
2380 match self {
2381 Occupied(e) => e.into_mut(),
2382 Vacant(e) => e.insert(default()),
2383 }
2384 }
2385
2386 /// Returns a reference to the entry's key
2387 ///
2388 /// # Examples
2389 ///
2390 /// ```
2391 /// # use http::HeaderMap;
2392 /// let mut map = HeaderMap::new();
2393 ///
2394 /// assert_eq!(map.entry("x-hello").key(), "x-hello");
2395 /// ```
2396 pub fn key(&self) -> &HeaderName {
2397 use self::Entry::*;
2398
2399 match *self {
2400 Vacant(ref e) => e.key(),
2401 Occupied(ref e) => e.key(),
2402 }
2403 }
2404}
2405
2406// ===== impl VacantEntry =====
2407
2408impl<'a, T> VacantEntry<'a, T> {
2409 /// Returns a reference to the entry's key
2410 ///
2411 /// # Examples
2412 ///
2413 /// ```
2414 /// # use http::HeaderMap;
2415 /// let mut map = HeaderMap::new();
2416 ///
2417 /// assert_eq!(map.entry("x-hello").key().as_str(), "x-hello");
2418 /// ```
2419 pub fn key(&self) -> &HeaderName {
2420 &self.key
2421 }
2422
2423 /// Take ownership of the key
2424 ///
2425 /// # Examples
2426 ///
2427 /// ```
2428 /// # use http::header::{HeaderMap, Entry};
2429 /// let mut map = HeaderMap::new();
2430 ///
2431 /// if let Entry::Vacant(v) = map.entry("x-hello") {
2432 /// assert_eq!(v.into_key().as_str(), "x-hello");
2433 /// }
2434 /// ```
2435 pub fn into_key(self) -> HeaderName {
2436 self.key
2437 }
2438
2439 /// Insert the value into the entry.
2440 ///
2441 /// The value will be associated with this entry's key. A mutable reference
2442 /// to the inserted value will be returned.
2443 ///
2444 /// # Examples
2445 ///
2446 /// ```
2447 /// # use http::header::{HeaderMap, Entry};
2448 /// let mut map = HeaderMap::new();
2449 ///
2450 /// if let Entry::Vacant(v) = map.entry("x-hello") {
2451 /// v.insert("world".parse().unwrap());
2452 /// }
2453 ///
2454 /// assert_eq!(map["x-hello"], "world");
2455 /// ```
2456 pub fn insert(self, value: T) -> &'a mut T {
2457 // Ensure that there is space in the map
2458 let index =
2459 self.map
2460 .insert_phase_two(self.key, value.into(), self.hash, self.probe, self.danger);
2461
2462 &mut self.map.entries[index].value
2463 }
2464
2465 /// Insert the value into the entry.
2466 ///
2467 /// The value will be associated with this entry's key. The new
2468 /// `OccupiedEntry` is returned, allowing for further manipulation.
2469 ///
2470 /// # Examples
2471 ///
2472 /// ```
2473 /// # use http::header::*;
2474 /// let mut map = HeaderMap::new();
2475 ///
2476 /// if let Entry::Vacant(v) = map.entry("x-hello") {
2477 /// let mut e = v.insert_entry("world".parse().unwrap());
2478 /// e.insert("world2".parse().unwrap());
2479 /// }
2480 ///
2481 /// assert_eq!(map["x-hello"], "world2");
2482 /// ```
2483 pub fn insert_entry(self, value: T) -> OccupiedEntry<'a, T> {
2484 // Ensure that there is space in the map
2485 let index =
2486 self.map
2487 .insert_phase_two(self.key, value.into(), self.hash, self.probe, self.danger);
2488
2489 OccupiedEntry {
2490 map: self.map,
2491 index: index,
2492 probe: self.probe,
2493 }
2494 }
2495}
2496
2497// ===== impl GetAll =====
2498
2499impl<'a, T: 'a> GetAll<'a, T> {
2500 /// Returns an iterator visiting all values associated with the entry.
2501 ///
2502 /// Values are iterated in insertion order.
2503 ///
2504 /// # Examples
2505 ///
2506 /// ```
2507 /// # use http::HeaderMap;
2508 /// # use http::header::HOST;
2509 /// let mut map = HeaderMap::new();
2510 /// map.insert(HOST, "hello.world".parse().unwrap());
2511 /// map.append(HOST, "hello.earth".parse().unwrap());
2512 ///
2513 /// let values = map.get_all("host");
2514 /// let mut iter = values.iter();
2515 /// assert_eq!(&"hello.world", iter.next().unwrap());
2516 /// assert_eq!(&"hello.earth", iter.next().unwrap());
2517 /// assert!(iter.next().is_none());
2518 /// ```
2519 pub fn iter(&self) -> ValueIter<'a, T> {
2520 // This creates a new GetAll struct so that the lifetime
2521 // isn't bound to &self.
2522 GetAll {
2523 map: self.map,
2524 index: self.index,
2525 }
2526 .into_iter()
2527 }
2528}
2529
2530impl<'a, T: PartialEq> PartialEq for GetAll<'a, T> {
2531 fn eq(&self, other: &Self) -> bool {
2532 self.iter().eq(other.iter())
2533 }
2534}
2535
2536impl<'a, T> IntoIterator for GetAll<'a, T> {
2537 type Item = &'a T;
2538 type IntoIter = ValueIter<'a, T>;
2539
2540 fn into_iter(self) -> ValueIter<'a, T> {
2541 self.map.value_iter(self.index)
2542 }
2543}
2544
2545impl<'a, 'b: 'a, T> IntoIterator for &'b GetAll<'a, T> {
2546 type Item = &'a T;
2547 type IntoIter = ValueIter<'a, T>;
2548
2549 fn into_iter(self) -> ValueIter<'a, T> {
2550 self.map.value_iter(self.index)
2551 }
2552}
2553
2554// ===== impl ValueIter =====
2555
2556impl<'a, T: 'a> Iterator for ValueIter<'a, T> {
2557 type Item = &'a T;
2558
2559 fn next(&mut self) -> Option<Self::Item> {
2560 use self::Cursor::*;
2561
2562 match self.front {
2563 Some(Head) => {
2564 let entry = &self.map.entries[self.index];
2565
2566 if self.back == Some(Head) {
2567 self.front = None;
2568 self.back = None;
2569 } else {
2570 // Update the iterator state
2571 match entry.links {
2572 Some(links) => {
2573 self.front = Some(Values(links.next));
2574 }
2575 None => unreachable!(),
2576 }
2577 }
2578
2579 Some(&entry.value)
2580 }
2581 Some(Values(idx)) => {
2582 let extra = &self.map.extra_values[idx];
2583
2584 if self.front == self.back {
2585 self.front = None;
2586 self.back = None;
2587 } else {
2588 match extra.next {
2589 Link::Entry(_) => self.front = None,
2590 Link::Extra(i) => self.front = Some(Values(i)),
2591 }
2592 }
2593
2594 Some(&extra.value)
2595 }
2596 None => None,
2597 }
2598 }
2599
2600 fn size_hint(&self) -> (usize, Option<usize>) {
2601 match (self.front, self.back) {
2602 // Exactly 1 value...
2603 (Some(Cursor::Head), Some(Cursor::Head)) => (1, Some(1)),
2604 // At least 1...
2605 (Some(_), _) => (1, None),
2606 // No more values...
2607 (None, _) => (0, Some(0)),
2608 }
2609 }
2610}
2611
2612impl<'a, T: 'a> DoubleEndedIterator for ValueIter<'a, T> {
2613 fn next_back(&mut self) -> Option<Self::Item> {
2614 use self::Cursor::*;
2615
2616 match self.back {
2617 Some(Head) => {
2618 self.front = None;
2619 self.back = None;
2620 Some(&self.map.entries[self.index].value)
2621 }
2622 Some(Values(idx)) => {
2623 let extra = &self.map.extra_values[idx];
2624
2625 if self.front == self.back {
2626 self.front = None;
2627 self.back = None;
2628 } else {
2629 match extra.prev {
2630 Link::Entry(_) => self.back = Some(Head),
2631 Link::Extra(idx) => self.back = Some(Values(idx)),
2632 }
2633 }
2634
2635 Some(&extra.value)
2636 }
2637 None => None,
2638 }
2639 }
2640}
2641
2642impl<'a, T> FusedIterator for ValueIter<'a, T> {}
2643
2644// ===== impl ValueIterMut =====
2645
2646impl<'a, T: 'a> Iterator for ValueIterMut<'a, T> {
2647 type Item = &'a mut T;
2648
2649 fn next(&mut self) -> Option<Self::Item> {
2650 use self::Cursor::*;
2651
2652 let entry = unsafe { &mut (*self.map).entries[self.index] };
2653
2654 match self.front {
2655 Some(Head) => {
2656 if self.back == Some(Head) {
2657 self.front = None;
2658 self.back = None;
2659 } else {
2660 // Update the iterator state
2661 match entry.links {
2662 Some(links) => {
2663 self.front = Some(Values(links.next));
2664 }
2665 None => unreachable!(),
2666 }
2667 }
2668
2669 Some(&mut entry.value)
2670 }
2671 Some(Values(idx)) => {
2672 let extra = unsafe { &mut (*self.map).extra_values[idx] };
2673
2674 if self.front == self.back {
2675 self.front = None;
2676 self.back = None;
2677 } else {
2678 match extra.next {
2679 Link::Entry(_) => self.front = None,
2680 Link::Extra(i) => self.front = Some(Values(i)),
2681 }
2682 }
2683
2684 Some(&mut extra.value)
2685 }
2686 None => None,
2687 }
2688 }
2689}
2690
2691impl<'a, T: 'a> DoubleEndedIterator for ValueIterMut<'a, T> {
2692 fn next_back(&mut self) -> Option<Self::Item> {
2693 use self::Cursor::*;
2694
2695 let entry = unsafe { &mut (*self.map).entries[self.index] };
2696
2697 match self.back {
2698 Some(Head) => {
2699 self.front = None;
2700 self.back = None;
2701 Some(&mut entry.value)
2702 }
2703 Some(Values(idx)) => {
2704 let extra = unsafe { &mut (*self.map).extra_values[idx] };
2705
2706 if self.front == self.back {
2707 self.front = None;
2708 self.back = None;
2709 } else {
2710 match extra.prev {
2711 Link::Entry(_) => self.back = Some(Head),
2712 Link::Extra(idx) => self.back = Some(Values(idx)),
2713 }
2714 }
2715
2716 Some(&mut extra.value)
2717 }
2718 None => None,
2719 }
2720 }
2721}
2722
2723impl<'a, T> FusedIterator for ValueIterMut<'a, T> {}
2724
2725unsafe impl<'a, T: Sync> Sync for ValueIterMut<'a, T> {}
2726unsafe impl<'a, T: Send> Send for ValueIterMut<'a, T> {}
2727
2728// ===== impl IntoIter =====
2729
2730impl<T> Iterator for IntoIter<T> {
2731 type Item = (Option<HeaderName>, T);
2732
2733 fn next(&mut self) -> Option<Self::Item> {
2734 if let Some(next) = self.next {
2735 self.next = match self.extra_values[next].next {
2736 Link::Entry(_) => None,
2737 Link::Extra(v) => Some(v),
2738 };
2739
2740 let value = unsafe { ptr::read(&self.extra_values[next].value) };
2741
2742 return Some((None, value));
2743 }
2744
2745 if let Some(bucket) = self.entries.next() {
2746 self.next = bucket.links.map(|l| l.next);
2747 let name = Some(bucket.key);
2748 let value = bucket.value;
2749
2750 return Some((name, value));
2751 }
2752
2753 None
2754 }
2755
2756 fn size_hint(&self) -> (usize, Option<usize>) {
2757 let (lower, _) = self.entries.size_hint();
2758 // There could be more than just the entries upper, as there
2759 // could be items in the `extra_values`. We could guess, saying
2760 // `upper + extra_values.len()`, but that could overestimate by a lot.
2761 (lower, None)
2762 }
2763}
2764
2765impl<T> FusedIterator for IntoIter<T> {}
2766
2767impl<T> Drop for IntoIter<T> {
2768 fn drop(&mut self) {
2769 // Ensure the iterator is consumed
2770 for _ in self.by_ref() {}
2771
2772 // All the values have already been yielded out.
2773 unsafe {
2774 self.extra_values.set_len(0);
2775 }
2776 }
2777}
2778
2779// ===== impl OccupiedEntry =====
2780
2781impl<'a, T> OccupiedEntry<'a, T> {
2782 /// Returns a reference to the entry's key.
2783 ///
2784 /// # Examples
2785 ///
2786 /// ```
2787 /// # use http::header::{HeaderMap, Entry, HOST};
2788 /// let mut map = HeaderMap::new();
2789 /// map.insert(HOST, "world".parse().unwrap());
2790 ///
2791 /// if let Entry::Occupied(e) = map.entry("host") {
2792 /// assert_eq!("host", e.key());
2793 /// }
2794 /// ```
2795 pub fn key(&self) -> &HeaderName {
2796 &self.map.entries[self.index].key
2797 }
2798
2799 /// Get a reference to the first value in the entry.
2800 ///
2801 /// Values are stored in insertion order.
2802 ///
2803 /// # Panics
2804 ///
2805 /// `get` panics if there are no values associated with the entry.
2806 ///
2807 /// # Examples
2808 ///
2809 /// ```
2810 /// # use http::header::{HeaderMap, Entry, HOST};
2811 /// let mut map = HeaderMap::new();
2812 /// map.insert(HOST, "hello.world".parse().unwrap());
2813 ///
2814 /// if let Entry::Occupied(mut e) = map.entry("host") {
2815 /// assert_eq!(e.get(), &"hello.world");
2816 ///
2817 /// e.append("hello.earth".parse().unwrap());
2818 ///
2819 /// assert_eq!(e.get(), &"hello.world");
2820 /// }
2821 /// ```
2822 pub fn get(&self) -> &T {
2823 &self.map.entries[self.index].value
2824 }
2825
2826 /// Get a mutable reference to the first value in the entry.
2827 ///
2828 /// Values are stored in insertion order.
2829 ///
2830 /// # Panics
2831 ///
2832 /// `get_mut` panics if there are no values associated with the entry.
2833 ///
2834 /// # Examples
2835 ///
2836 /// ```
2837 /// # use http::header::{HeaderMap, Entry, HOST};
2838 /// let mut map = HeaderMap::default();
2839 /// map.insert(HOST, "hello.world".to_string());
2840 ///
2841 /// if let Entry::Occupied(mut e) = map.entry("host") {
2842 /// e.get_mut().push_str("-2");
2843 /// assert_eq!(e.get(), &"hello.world-2");
2844 /// }
2845 /// ```
2846 pub fn get_mut(&mut self) -> &mut T {
2847 &mut self.map.entries[self.index].value
2848 }
2849
2850 /// Converts the `OccupiedEntry` into a mutable reference to the **first**
2851 /// value.
2852 ///
2853 /// The lifetime of the returned reference is bound to the original map.
2854 ///
2855 /// # Panics
2856 ///
2857 /// `into_mut` panics if there are no values associated with the entry.
2858 ///
2859 /// # Examples
2860 ///
2861 /// ```
2862 /// # use http::header::{HeaderMap, Entry, HOST};
2863 /// let mut map = HeaderMap::default();
2864 /// map.insert(HOST, "hello.world".to_string());
2865 /// map.append(HOST, "hello.earth".to_string());
2866 ///
2867 /// if let Entry::Occupied(e) = map.entry("host") {
2868 /// e.into_mut().push_str("-2");
2869 /// }
2870 ///
2871 /// assert_eq!("hello.world-2", map["host"]);
2872 /// ```
2873 pub fn into_mut(self) -> &'a mut T {
2874 &mut self.map.entries[self.index].value
2875 }
2876
2877 /// Sets the value of the entry.
2878 ///
2879 /// All previous values associated with the entry are removed and the first
2880 /// one is returned. See `insert_mult` for an API that returns all values.
2881 ///
2882 /// # Examples
2883 ///
2884 /// ```
2885 /// # use http::header::{HeaderMap, Entry, HOST};
2886 /// let mut map = HeaderMap::new();
2887 /// map.insert(HOST, "hello.world".parse().unwrap());
2888 ///
2889 /// if let Entry::Occupied(mut e) = map.entry("host") {
2890 /// let mut prev = e.insert("earth".parse().unwrap());
2891 /// assert_eq!("hello.world", prev);
2892 /// }
2893 ///
2894 /// assert_eq!("earth", map["host"]);
2895 /// ```
2896 pub fn insert(&mut self, value: T) -> T {
2897 self.map.insert_occupied(self.index, value.into())
2898 }
2899
2900 /// Sets the value of the entry.
2901 ///
2902 /// This function does the same as `insert` except it returns an iterator
2903 /// that yields all values previously associated with the key.
2904 ///
2905 /// # Examples
2906 ///
2907 /// ```
2908 /// # use http::header::{HeaderMap, Entry, HOST};
2909 /// let mut map = HeaderMap::new();
2910 /// map.insert(HOST, "world".parse().unwrap());
2911 /// map.append(HOST, "world2".parse().unwrap());
2912 ///
2913 /// if let Entry::Occupied(mut e) = map.entry("host") {
2914 /// let mut prev = e.insert_mult("earth".parse().unwrap());
2915 /// assert_eq!("world", prev.next().unwrap());
2916 /// assert_eq!("world2", prev.next().unwrap());
2917 /// assert!(prev.next().is_none());
2918 /// }
2919 ///
2920 /// assert_eq!("earth", map["host"]);
2921 /// ```
2922 pub fn insert_mult(&mut self, value: T) -> ValueDrain<'_, T> {
2923 self.map.insert_occupied_mult(self.index, value.into())
2924 }
2925
2926 /// Insert the value into the entry.
2927 ///
2928 /// The new value is appended to the end of the entry's value list. All
2929 /// previous values associated with the entry are retained.
2930 ///
2931 /// # Examples
2932 ///
2933 /// ```
2934 /// # use http::header::{HeaderMap, Entry, HOST};
2935 /// let mut map = HeaderMap::new();
2936 /// map.insert(HOST, "world".parse().unwrap());
2937 ///
2938 /// if let Entry::Occupied(mut e) = map.entry("host") {
2939 /// e.append("earth".parse().unwrap());
2940 /// }
2941 ///
2942 /// let values = map.get_all("host");
2943 /// let mut i = values.iter();
2944 /// assert_eq!("world", *i.next().unwrap());
2945 /// assert_eq!("earth", *i.next().unwrap());
2946 /// ```
2947 pub fn append(&mut self, value: T) {
2948 let idx = self.index;
2949 let entry = &mut self.map.entries[idx];
2950 append_value(idx, entry, &mut self.map.extra_values, value.into());
2951 }
2952
2953 /// Remove the entry from the map.
2954 ///
2955 /// All values associated with the entry are removed and the first one is
2956 /// returned. See `remove_entry_mult` for an API that returns all values.
2957 ///
2958 /// # Examples
2959 ///
2960 /// ```
2961 /// # use http::header::{HeaderMap, Entry, HOST};
2962 /// let mut map = HeaderMap::new();
2963 /// map.insert(HOST, "world".parse().unwrap());
2964 ///
2965 /// if let Entry::Occupied(e) = map.entry("host") {
2966 /// let mut prev = e.remove();
2967 /// assert_eq!("world", prev);
2968 /// }
2969 ///
2970 /// assert!(!map.contains_key("host"));
2971 /// ```
2972 pub fn remove(self) -> T {
2973 self.remove_entry().1
2974 }
2975
2976 /// Remove the entry from the map.
2977 ///
2978 /// The key and all values associated with the entry are removed and the
2979 /// first one is returned. See `remove_entry_mult` for an API that returns
2980 /// all values.
2981 ///
2982 /// # Examples
2983 ///
2984 /// ```
2985 /// # use http::header::{HeaderMap, Entry, HOST};
2986 /// let mut map = HeaderMap::new();
2987 /// map.insert(HOST, "world".parse().unwrap());
2988 ///
2989 /// if let Entry::Occupied(e) = map.entry("host") {
2990 /// let (key, mut prev) = e.remove_entry();
2991 /// assert_eq!("host", key.as_str());
2992 /// assert_eq!("world", prev);
2993 /// }
2994 ///
2995 /// assert!(!map.contains_key("host"));
2996 /// ```
2997 pub fn remove_entry(self) -> (HeaderName, T) {
2998 if let Some(links) = self.map.entries[self.index].links {
2999 self.map.remove_all_extra_values(links.next);
3000 }
3001
3002 let entry = self.map.remove_found(self.probe, self.index);
3003
3004 (entry.key, entry.value)
3005 }
3006
3007 /// Remove the entry from the map.
3008 ///
3009 /// The key and all values associated with the entry are removed and
3010 /// returned.
3011 pub fn remove_entry_mult(self) -> (HeaderName, ValueDrain<'a, T>) {
3012 let raw_links = self.map.raw_links();
3013 let extra_values = &mut self.map.extra_values;
3014
3015 let next = self.map.entries[self.index].links.map(|l| {
3016 drain_all_extra_values(raw_links, extra_values, l.next)
3017 .into_iter()
3018 });
3019
3020 let entry = self.map.remove_found(self.probe, self.index);
3021
3022 let drain = ValueDrain {
3023 first: Some(entry.value),
3024 next,
3025 lt: PhantomData,
3026 };
3027 (entry.key, drain)
3028 }
3029
3030 /// Returns an iterator visiting all values associated with the entry.
3031 ///
3032 /// Values are iterated in insertion order.
3033 ///
3034 /// # Examples
3035 ///
3036 /// ```
3037 /// # use http::header::{HeaderMap, Entry, HOST};
3038 /// let mut map = HeaderMap::new();
3039 /// map.insert(HOST, "world".parse().unwrap());
3040 /// map.append(HOST, "earth".parse().unwrap());
3041 ///
3042 /// if let Entry::Occupied(e) = map.entry("host") {
3043 /// let mut iter = e.iter();
3044 /// assert_eq!(&"world", iter.next().unwrap());
3045 /// assert_eq!(&"earth", iter.next().unwrap());
3046 /// assert!(iter.next().is_none());
3047 /// }
3048 /// ```
3049 pub fn iter(&self) -> ValueIter<'_, T> {
3050 self.map.value_iter(Some(self.index))
3051 }
3052
3053 /// Returns an iterator mutably visiting all values associated with the
3054 /// entry.
3055 ///
3056 /// Values are iterated in insertion order.
3057 ///
3058 /// # Examples
3059 ///
3060 /// ```
3061 /// # use http::header::{HeaderMap, Entry, HOST};
3062 /// let mut map = HeaderMap::default();
3063 /// map.insert(HOST, "world".to_string());
3064 /// map.append(HOST, "earth".to_string());
3065 ///
3066 /// if let Entry::Occupied(mut e) = map.entry("host") {
3067 /// for e in e.iter_mut() {
3068 /// e.push_str("-boop");
3069 /// }
3070 /// }
3071 ///
3072 /// let mut values = map.get_all("host");
3073 /// let mut i = values.iter();
3074 /// assert_eq!(&"world-boop", i.next().unwrap());
3075 /// assert_eq!(&"earth-boop", i.next().unwrap());
3076 /// ```
3077 pub fn iter_mut(&mut self) -> ValueIterMut<'_, T> {
3078 self.map.value_iter_mut(self.index)
3079 }
3080}
3081
3082impl<'a, T> IntoIterator for OccupiedEntry<'a, T> {
3083 type Item = &'a mut T;
3084 type IntoIter = ValueIterMut<'a, T>;
3085
3086 fn into_iter(self) -> ValueIterMut<'a, T> {
3087 self.map.value_iter_mut(self.index)
3088 }
3089}
3090
3091impl<'a, 'b: 'a, T> IntoIterator for &'b OccupiedEntry<'a, T> {
3092 type Item = &'a T;
3093 type IntoIter = ValueIter<'a, T>;
3094
3095 fn into_iter(self) -> ValueIter<'a, T> {
3096 self.iter()
3097 }
3098}
3099
3100impl<'a, 'b: 'a, T> IntoIterator for &'b mut OccupiedEntry<'a, T> {
3101 type Item = &'a mut T;
3102 type IntoIter = ValueIterMut<'a, T>;
3103
3104 fn into_iter(self) -> ValueIterMut<'a, T> {
3105 self.iter_mut()
3106 }
3107}
3108
3109// ===== impl ValueDrain =====
3110
3111impl<'a, T> Iterator for ValueDrain<'a, T> {
3112 type Item = T;
3113
3114 fn next(&mut self) -> Option<T> {
3115 if self.first.is_some() {
3116 self.first.take()
3117 } else if let Some(ref mut extras) = self.next {
3118 extras.next()
3119 } else {
3120 None
3121 }
3122 }
3123
3124 fn size_hint(&self) -> (usize, Option<usize>) {
3125 match (&self.first, &self.next) {
3126 // Exactly 1
3127 (&Some(_), &None) => (1, Some(1)),
3128 // 1 + extras
3129 (&Some(_), &Some(ref extras)) => {
3130 let (l, u) = extras.size_hint();
3131 (l + 1, u.map(|u| u + 1))
3132 },
3133 // Extras only
3134 (&None, &Some(ref extras)) => extras.size_hint(),
3135 // No more
3136 (&None, &None) => (0, Some(0)),
3137 }
3138 }
3139}
3140
3141impl<'a, T> FusedIterator for ValueDrain<'a, T> {}
3142
3143impl<'a, T> Drop for ValueDrain<'a, T> {
3144 fn drop(&mut self) {
3145 while let Some(_) = self.next() {}
3146 }
3147}
3148
3149unsafe impl<'a, T: Sync> Sync for ValueDrain<'a, T> {}
3150unsafe impl<'a, T: Send> Send for ValueDrain<'a, T> {}
3151
3152// ===== impl RawLinks =====
3153
3154impl<T> Clone for RawLinks<T> {
3155 fn clone(&self) -> RawLinks<T> {
3156 *self
3157 }
3158}
3159
3160impl<T> Copy for RawLinks<T> {}
3161
3162impl<T> ops::Index<usize> for RawLinks<T> {
3163 type Output = Option<Links>;
3164
3165 fn index(&self, idx: usize) -> &Self::Output {
3166 unsafe {
3167 &(*self.0)[idx].links
3168 }
3169 }
3170}
3171
3172impl<T> ops::IndexMut<usize> for RawLinks<T> {
3173 fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
3174 unsafe {
3175 &mut (*self.0)[idx].links
3176 }
3177 }
3178}
3179
3180// ===== impl Pos =====
3181
3182impl Pos {
3183 #[inline]
3184 fn new(index: usize, hash: HashValue) -> Self {
3185 debug_assert!(index < MAX_SIZE);
3186 Pos {
3187 index: index as Size,
3188 hash: hash,
3189 }
3190 }
3191
3192 #[inline]
3193 fn none() -> Self {
3194 Pos {
3195 index: !0,
3196 hash: HashValue(0),
3197 }
3198 }
3199
3200 #[inline]
3201 fn is_some(&self) -> bool {
3202 !self.is_none()
3203 }
3204
3205 #[inline]
3206 fn is_none(&self) -> bool {
3207 self.index == !0
3208 }
3209
3210 #[inline]
3211 fn resolve(&self) -> Option<(usize, HashValue)> {
3212 if self.is_some() {
3213 Some((self.index as usize, self.hash))
3214 } else {
3215 None
3216 }
3217 }
3218}
3219
3220impl Danger {
3221 fn is_red(&self) -> bool {
3222 match *self {
3223 Danger::Red(_) => true,
3224 _ => false,
3225 }
3226 }
3227
3228 fn to_red(&mut self) {
3229 debug_assert!(self.is_yellow());
3230 *self = Danger::Red(RandomState::new());
3231 }
3232
3233 fn is_yellow(&self) -> bool {
3234 match *self {
3235 Danger::Yellow => true,
3236 _ => false,
3237 }
3238 }
3239
3240 fn to_yellow(&mut self) {
3241 match *self {
3242 Danger::Green => {
3243 *self = Danger::Yellow;
3244 }
3245 _ => {}
3246 }
3247 }
3248
3249 fn to_green(&mut self) {
3250 debug_assert!(self.is_yellow());
3251 *self = Danger::Green;
3252 }
3253}
3254
3255// ===== impl Utils =====
3256
3257#[inline]
3258fn usable_capacity(cap: usize) -> usize {
3259 cap - cap / 4
3260}
3261
3262#[inline]
3263fn to_raw_capacity(n: usize) -> usize {
3264 match n.checked_add(n / 3) {
3265 Some(n) => n,
3266 None => panic!(
3267 "requested capacity {} too large: overflow while converting to raw capacity",
3268 n
3269 ),
3270 }
3271}
3272
3273#[inline]
3274fn desired_pos(mask: Size, hash: HashValue) -> usize {
3275 (hash.0 & mask) as usize
3276}
3277
3278/// The number of steps that `current` is forward of the desired position for hash
3279#[inline]
3280fn probe_distance(mask: Size, hash: HashValue, current: usize) -> usize {
3281 current.wrapping_sub(desired_pos(mask, hash)) & mask as usize
3282}
3283
3284fn hash_elem_using<K: ?Sized>(danger: &Danger, k: &K) -> HashValue
3285where
3286 K: Hash,
3287{
3288 use fnv::FnvHasher;
3289
3290 const MASK: u64 = (MAX_SIZE as u64) - 1;
3291
3292 let hash = match *danger {
3293 // Safe hash
3294 Danger::Red(ref hasher) => {
3295 let mut h = hasher.build_hasher();
3296 k.hash(&mut h);
3297 h.finish()
3298 }
3299 // Fast hash
3300 _ => {
3301 let mut h = FnvHasher::default();
3302 k.hash(&mut h);
3303 h.finish()
3304 }
3305 };
3306
3307 HashValue((hash & MASK) as u16)
3308}
3309
3310/*
3311 *
3312 * ===== impl IntoHeaderName / AsHeaderName =====
3313 *
3314 */
3315
3316mod into_header_name {
3317 use super::{Entry, HdrName, HeaderMap, HeaderName};
3318
3319 /// A marker trait used to identify values that can be used as insert keys
3320 /// to a `HeaderMap`.
3321 pub trait IntoHeaderName: Sealed {}
3322
3323 // All methods are on this pub(super) trait, instead of `IntoHeaderName`,
3324 // so that they aren't publicly exposed to the world.
3325 //
3326 // Being on the `IntoHeaderName` trait would mean users could call
3327 // `"host".insert(&mut map, "localhost")`.
3328 //
3329 // Ultimately, this allows us to adjust the signatures of these methods
3330 // without breaking any external crate.
3331 pub trait Sealed {
3332 #[doc(hidden)]
3333 fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T>;
3334
3335 #[doc(hidden)]
3336 fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool;
3337
3338 #[doc(hidden)]
3339 fn entry<T>(self, map: &mut HeaderMap<T>) -> Entry<'_, T>;
3340 }
3341
3342 // ==== impls ====
3343
3344 impl Sealed for HeaderName {
3345 #[inline]
3346 fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T> {
3347 map.insert2(self, val)
3348 }
3349
3350 #[inline]
3351 fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool {
3352 map.append2(self, val)
3353 }
3354
3355 #[inline]
3356 fn entry<T>(self, map: &mut HeaderMap<T>) -> Entry<'_, T> {
3357 map.entry2(self)
3358 }
3359 }
3360
3361 impl IntoHeaderName for HeaderName {}
3362
3363 impl<'a> Sealed for &'a HeaderName {
3364 #[inline]
3365 fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T> {
3366 map.insert2(self, val)
3367 }
3368 #[inline]
3369 fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool {
3370 map.append2(self, val)
3371 }
3372
3373 #[inline]
3374 fn entry<T>(self, map: &mut HeaderMap<T>) -> Entry<'_, T> {
3375 map.entry2(self)
3376 }
3377 }
3378
3379 impl<'a> IntoHeaderName for &'a HeaderName {}
3380
3381 impl Sealed for &'static str {
3382 #[inline]
3383 fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T> {
3384 HdrName::from_static(self, move |hdr| map.insert2(hdr, val))
3385 }
3386 #[inline]
3387 fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool {
3388 HdrName::from_static(self, move |hdr| map.append2(hdr, val))
3389 }
3390
3391 #[inline]
3392 fn entry<T>(self, map: &mut HeaderMap<T>) -> Entry<'_, T> {
3393 HdrName::from_static(self, move |hdr| map.entry2(hdr))
3394 }
3395 }
3396
3397 impl IntoHeaderName for &'static str {}
3398}
3399
3400mod as_header_name {
3401 use super::{Entry, HdrName, HeaderMap, HeaderName, InvalidHeaderName};
3402
3403 /// A marker trait used to identify values that can be used as search keys
3404 /// to a `HeaderMap`.
3405 pub trait AsHeaderName: Sealed {}
3406
3407 // All methods are on this pub(super) trait, instead of `AsHeaderName`,
3408 // so that they aren't publicly exposed to the world.
3409 //
3410 // Being on the `AsHeaderName` trait would mean users could call
3411 // `"host".find(&map)`.
3412 //
3413 // Ultimately, this allows us to adjust the signatures of these methods
3414 // without breaking any external crate.
3415 pub trait Sealed {
3416 #[doc(hidden)]
3417 fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName>;
3418
3419 #[doc(hidden)]
3420 fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)>;
3421
3422 #[doc(hidden)]
3423 fn as_str(&self) -> &str;
3424 }
3425
3426 // ==== impls ====
3427
3428 impl Sealed for HeaderName {
3429 #[inline]
3430 fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3431 Ok(map.entry2(self))
3432 }
3433
3434 #[inline]
3435 fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3436 map.find(self)
3437 }
3438
3439 fn as_str(&self) -> &str {
3440 <HeaderName>::as_str(self)
3441 }
3442 }
3443
3444 impl AsHeaderName for HeaderName {}
3445
3446 impl<'a> Sealed for &'a HeaderName {
3447 #[inline]
3448 fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3449 Ok(map.entry2(self))
3450 }
3451
3452 #[inline]
3453 fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3454 map.find(*self)
3455 }
3456
3457 fn as_str(&self) -> &str {
3458 <HeaderName>::as_str(*self)
3459 }
3460 }
3461
3462 impl<'a> AsHeaderName for &'a HeaderName {}
3463
3464 impl<'a> Sealed for &'a str {
3465 #[inline]
3466 fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3467 HdrName::from_bytes(self.as_bytes(), move |hdr| map.entry2(hdr))
3468 }
3469
3470 #[inline]
3471 fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3472 HdrName::from_bytes(self.as_bytes(), move |hdr| map.find(&hdr)).unwrap_or(None)
3473 }
3474
3475 fn as_str(&self) -> &str {
3476 self
3477 }
3478 }
3479
3480 impl<'a> AsHeaderName for &'a str {}
3481
3482 impl Sealed for String {
3483 #[inline]
3484 fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3485 self.as_str().try_entry(map)
3486 }
3487
3488 #[inline]
3489 fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3490 Sealed::find(&self.as_str(), map)
3491 }
3492
3493 fn as_str(&self) -> &str {
3494 self
3495 }
3496 }
3497
3498 impl AsHeaderName for String {}
3499
3500 impl<'a> Sealed for &'a String {
3501 #[inline]
3502 fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3503 self.as_str().try_entry(map)
3504 }
3505
3506 #[inline]
3507 fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3508 Sealed::find(*self, map)
3509 }
3510
3511 fn as_str(&self) -> &str {
3512 *self
3513 }
3514 }
3515
3516 impl<'a> AsHeaderName for &'a String {}
3517}
3518
3519#[test]
3520fn test_bounds() {
3521 fn check_bounds<T: Send + Send>() {}
3522
3523 check_bounds::<HeaderMap<()>>();
3524 check_bounds::<Iter<'static, ()>>();
3525 check_bounds::<IterMut<'static, ()>>();
3526 check_bounds::<Keys<'static, ()>>();
3527 check_bounds::<Values<'static, ()>>();
3528 check_bounds::<ValuesMut<'static, ()>>();
3529 check_bounds::<Drain<'static, ()>>();
3530 check_bounds::<GetAll<'static, ()>>();
3531 check_bounds::<Entry<'static, ()>>();
3532 check_bounds::<VacantEntry<'static, ()>>();
3533 check_bounds::<OccupiedEntry<'static, ()>>();
3534 check_bounds::<ValueIter<'static, ()>>();
3535 check_bounds::<ValueIterMut<'static, ()>>();
3536 check_bounds::<ValueDrain<'static, ()>>();
3537}
3538
3539#[test]
3540fn skip_duplicates_during_key_iteration() {
3541 let mut map = HeaderMap::new();
3542 map.append("a", HeaderValue::from_static("a"));
3543 map.append("a", HeaderValue::from_static("b"));
3544 assert_eq!(map.keys().count(), map.keys_len());
3545}
3546