map.rs source code [crates/http/src/header/map.rs]

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	/// ```
441	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	/// ```
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	/// ```
513	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	/// ```
540	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	/// ```
559	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	/// ```
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	/// ```
605	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	/// ```
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	/// ```
676	pub fn get<K>(&self, key: K) -> Option<&T>
677	where
678	K: AsHeaderName,
679	{
680	self.get2(&key)
681	}
682
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	/// ```
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	/// ```
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	/// ```
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	/// ```
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	/// ```
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	/// ```
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	/// ```
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	/// ```
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	/// ```
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
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
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	/// ```
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.
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
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	/// ```
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]
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]
1173	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
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	/// ```
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]
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]
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]
1311	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	/// ```
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]
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]
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
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]
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
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
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
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]
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]
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]
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
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 = Vec::new();
1723	loop {
1724	let extra: ExtraValue = remove_extra_value(raw_links, extra_values, idx:head);
1725	vec.push(extra.value);
1726
1727	if let Link::Extra(idx: usize) = 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
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
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	/// ```
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> {
1817	fn from_iter<I>(iter: I) -> Self
1818	where
1819	I: IntoIterator<Item = (HeaderName, T)>,
1820	{
1821	let mut map: HeaderMap = 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
1852	fn try_from(c: &'a HashMap<K, V>) -> Result<Self, Self::Error> {
1853	cimpl Iterator>.into_iter()
1854	.map(\|(k: &K, v: &V)\| -> crate::Result<(HeaderName, T)> {
1855	let name: HeaderName = TryFrom::try_from(k).map_err(op:Into::into)?;
1856	let value: T = TryFrom::try_from(v).map_err(op: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	/// ```
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> {
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: ::IntoIter = iter.into_iter();
1950
1951	let reserve: usize = if self.is_empty() {
1952	iter.size_hint().0
1953	} else {
1954	(iter.size_hint().0 + `1`) / `2`
1955	};
1956
1957	self.reserve(additional:reserve);
1958
1959	for (k: HeaderName, v: T) in iter {
1960	self.append(key:k, value:v);
1961	}
1962	}
1963	}
1964
1965	impl<T: PartialEq> PartialEq for HeaderMap<T> {
1966	fn eq(&self, other: &HeaderMap<T>) -> bool {
1967	if self.len() != other.len() {
1968	return `false`;
1969	}
1970
1971	self.keys()
1972	.all(\|key: &HeaderName\| 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> {
1979	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> {
1985	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]
1999	fn index(&self, index: K) -> &T {
2000	match self.get2(&index) {
2001	Some(val: &T) => 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]
2011	fn do_insert_phase_two(indices: &mut [Pos], mut probe: usize, mut old_pos: Pos) -> usize {
2012	let mut num_displaced: usize = `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]
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
2070	fn next(&mut self) -> Option<Self::Item> {
2071	self.inner
2072	.next_unsafe()
2073	.map(\|(key: &HeaderName, ptr: mut T)\| (key, unsafe* { &*ptr }))
2074	}
2075
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> {
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
2125	fn next(&mut self) -> Option<Self::Item> {
2126	self.next_unsafe()
2127	.map(\|(key: &HeaderName, ptr: mut T)\| (key, unsafe* { &mut *ptr }))
2128	}
2129
2130	fn size_hint(&self) -> (usize, Option<usize>) {
2131	let map: &HeaderMap = unsafe { &*self.map };
2132	debug_assert!(map.entries.len() >= self.entry);
2133
2134	let lower: usize = 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
2153	fn next(&mut self) -> Option<Self::Item> {
2154	self.inner.next().map(\|b: &Bucket\| &b.key)
2155	}
2156
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
2170	fn next(&mut self) -> Option<Self::Item> {
2171	self.inner.next().map(\|(_, v: &T)\| v)
2172	}
2173
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
2186	fn next(&mut self) -> Option<Self::Item> {
2187	self.inner.next().map(\|(_, v: &mut T)\| v)
2188	}
2189
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
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
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> {
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	/// ```
2291	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	/// ```
2334	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	/// ```
2353	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	/// ```
2376	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	/// ```
2392	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	/// ```
2413	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	/// ```
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	/// ```
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> {
2488	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
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
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
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
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> {
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
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> {
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
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
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> {
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(new_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	/// ```
2752	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	/// ```
2779	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	/// ```
2803	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	/// ```
2830	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	/// ```
2853	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	/// ```
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	/// ```
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	/// ```
2929	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	/// ```
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.
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	/// ```
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	/// ```
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
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
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
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
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
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> {
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> {
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
3122	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> {
3130	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]
3141	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]
3150	fn none() -> Self {
3151	Pos {
3152	index: !`0`,
3153	hash: HashValue(`0`),
3154	}
3155	}
3156
3157	#[inline]
3158	fn is_some(&self) -> bool {
3159	!self.is_none()
3160	}
3161
3162	#[inline]
3163	fn is_none(&self) -> bool {
3164	self.index == !`0`
3165	}
3166
3167	#[inline]
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 {
3178	fn is_red(&self) -> bool {
3179	match *self {
3180	Danger::Red(_) => `true`,
3181	_ => `false`,
3182	}
3183	}
3184
3185	fn to_red(&mut self) {
3186	debug_assert!(self.is_yellow());
3187	*self = Danger::Red(RandomState::new());
3188	}
3189
3190	fn is_yellow(&self) -> bool {
3191	match *self {
3192	Danger::Yellow => `true`,
3193	_ => `false`,
3194	}
3195	}
3196
3197	fn to_yellow(&mut self) {
3198	match *self {
3199	Danger::Green => {
3200	*self = Danger::Yellow;
3201	}
3202	_ => {}
3203	}
3204	}
3205
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]
3215	fn usable_capacity(cap: usize) -> usize {
3216	cap - cap / `4`
3217	}
3218
3219	#[inline]
3220	fn to_raw_capacity(n: usize) -> usize {
3221	n + n / `3`
3222	}
3223
3224	#[inline]
3225	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]
3231	fn probe_distance(mask: Size, hash: HashValue, current: usize) -> usize {
3232	current.wrapping_sub(desired_pos(mask, hash)) & mask as usize
3233	}
3234
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: u64 = match *danger {
3244	// Safe hash
3245	Danger::Red(ref hasher: &RandomState) => {
3246	let mut h: DefaultHasher = hasher.build_hasher();
3247	k.hash(&mut h);
3248	h.finish()
3249	}
3250	// Fast hash
3251	_ => {
3252	let mut h: FnvHasher = 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)]
3284	fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T>;
3285
3286	#[doc(hidden)]
3287	fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool;
3288
3289	#[doc(hidden)]
3290	fn entry<T>(self, map: &mut HeaderMap<T>) -> Entry<'_, T>;
3291	}
3292
3293	// ==== impls ====
3294
3295	impl Sealed for HeaderName {
3296	#[inline]
3297	fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T> {
3298	map.insert2(self, val)
3299	}
3300
3301	#[inline]
3302	fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool {
3303	map.append2(self, val)
3304	}
3305
3306	#[inline]
3307	fn entry<T>(self, map: &mut HeaderMap<T>) -> Entry<'_, T> {
3308	map.entry2(self)
3309	}
3310	}
3311
3312	impl IntoHeaderName for HeaderName {}
3313
3314	impl<'a> Sealed for &'a HeaderName {
3315	#[inline]
3316	fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T> {
3317	map.insert2(self, val)
3318	}
3319	#[inline]
3320	fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool {
3321	map.append2(self, val)
3322	}
3323
3324	#[inline]
3325	fn entry<T>(self, map: &mut HeaderMap<T>) -> Entry<'_, T> {
3326	map.entry2(self)
3327	}
3328	}
3329
3330	impl<'a> IntoHeaderName for &'a HeaderName {}
3331
3332	impl Sealed for &'static str {
3333	#[inline]
3334	fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T> {
3335	HdrName::from_static(self, move \|hdr\| map.insert2(hdr, val))
3336	}
3337	#[inline]
3338	fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool {
3339	HdrName::from_static(self, move \|hdr\| map.append2(hdr, val))
3340	}
3341
3342	#[inline]
3343	fn entry<T>(self, map: &mut HeaderMap<T>) -> Entry<'_, T> {
3344	HdrName::from_static(self, move \|hdr\| map.entry2(hdr))
3345	}
3346	}
3347
3348	impl IntoHeaderName for &'static str {}
3349	}
3350
3351	mod as_header_name {
3352	use super::{Entry, HdrName, HeaderMap, HeaderName, InvalidHeaderName};
3353
3354	/// A marker trait used to identify values that can be used as search keys
3355	/// to a `HeaderMap`.
3356	pub trait AsHeaderName: Sealed {}
3357
3358	// All methods are on this pub(super) trait, instead of `AsHeaderName`,
3359	// so that they aren't publicly exposed to the world.
3360	//
3361	// Being on the `AsHeaderName` trait would mean users could call
3362	// `"host".find(&map)`.
3363	//
3364	// Ultimately, this allows us to adjust the signatures of these methods
3365	// without breaking any external crate.
3366	pub trait Sealed {
3367	#[doc(hidden)]
3368	fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName>;
3369
3370	#[doc(hidden)]
3371	fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)>;
3372
3373	#[doc(hidden)]
3374	fn as_str(&self) -> &str;
3375	}
3376
3377	// ==== impls ====
3378
3379	impl Sealed for HeaderName {
3380	#[inline]
3381	fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3382	Ok(map.entry2(self))
3383	}
3384
3385	#[inline]
3386	fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3387	map.find(self)
3388	}
3389
3390	fn as_str(&self) -> &str {
3391	<HeaderName>::as_str(self)
3392	}
3393	}
3394
3395	impl AsHeaderName for HeaderName {}
3396
3397	impl<'a> Sealed for &'a HeaderName {
3398	#[inline]
3399	fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3400	Ok(map.entry2(self))
3401	}
3402
3403	#[inline]
3404	fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3405	map.find(*self)
3406	}
3407
3408	fn as_str(&self) -> &str {
3409	<HeaderName>::as_str(*self)
3410	}
3411	}
3412
3413	impl<'a> AsHeaderName for &'a HeaderName {}
3414
3415	impl<'a> Sealed for &'a str {
3416	#[inline]
3417	fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3418	HdrName::from_bytes(self.as_bytes(), move \|hdr\| map.entry2(hdr))
3419	}
3420
3421	#[inline]
3422	fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3423	HdrName::from_bytes(self.as_bytes(), move \|hdr\| map.find(&hdr)).unwrap_or(None)
3424	}
3425
3426	fn as_str(&self) -> &str {
3427	self
3428	}
3429	}
3430
3431	impl<'a> AsHeaderName for &'a str {}
3432
3433	impl Sealed for String {
3434	#[inline]
3435	fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3436	self.as_str().try_entry(map)
3437	}
3438
3439	#[inline]
3440	fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3441	Sealed::find(&self.as_str(), map)
3442	}
3443
3444	fn as_str(&self) -> &str {
3445	self
3446	}
3447	}
3448
3449	impl AsHeaderName for String {}
3450
3451	impl<'a> Sealed for &'a String {
3452	#[inline]
3453	fn try_entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<'_, T>, InvalidHeaderName> {
3454	self.as_str().try_entry(map)
3455	}
3456
3457	#[inline]
3458	fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
3459	Sealed::find(*self, map)
3460	}
3461
3462	fn as_str(&self) -> &str {
3463	*self
3464	}
3465	}
3466
3467	impl<'a> AsHeaderName for &'a String {}
3468	}
3469
3470	#[test]
3471	fn test_bounds() {
3472	fn check_bounds<T: Send + Send>() {}
3473
3474	check_bounds::<HeaderMap<()>>();
3475	check_bounds::<Iter<'static, ()>>();
3476	check_bounds::<IterMut<'static, ()>>();
3477	check_bounds::<Keys<'static, ()>>();
3478	check_bounds::<Values<'static, ()>>();
3479	check_bounds::<ValuesMut<'static, ()>>();
3480	check_bounds::<Drain<'static, ()>>();
3481	check_bounds::<GetAll<'static, ()>>();
3482	check_bounds::<Entry<'static, ()>>();
3483	check_bounds::<VacantEntry<'static, ()>>();
3484	check_bounds::<OccupiedEntry<'static, ()>>();
3485	check_bounds::<ValueIter<'static, ()>>();
3486	check_bounds::<ValueIterMut<'static, ()>>();
3487	check_bounds::<ValueDrain<'static, ()>>();
3488	}
3489
3490	#[test]
3491	fn skip_duplicates_during_key_iteration() {
3492	let mut map: HeaderMap = HeaderMap::new();
3493	map.append(key:"a", value:HeaderValue::from_static(src:"a"));
3494	map.append(key:"a", value:HeaderValue::from_static(src:"b"));
3495	assert_eq!(map.keys().count(), map.keys_len());
3496	}
3497