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

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