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