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

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