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