Google Git
Sign in
apache / incubator-teaclave-sgx-sdk / refs/tags/v1.0.1 / . / third_party / http / src / header / map.rs
blob: 6130ebb9f119dbb626ceb51a6f8d78d690f2183e [file] [log] [blame]
use super::HeaderValue;
use super::name::{HeaderName, HdrName, InvalidHeaderName};
use std::prelude::v1::*;
use std::{fmt, mem, ops, ptr, vec};
use std::collections::hash_map::RandomState;
use std::hash::{BuildHasher, Hasher, Hash};
use std::iter::FromIterator;
use std::marker::PhantomData;
pub use self::as_header_name::AsHeaderName;
pub use self::into_header_name::IntoHeaderName;
/// A set of HTTP headers
///
/// `HeaderMap` is an multimap of `HeaderName` to values.
///
/// # Examples
///
/// Basic usage
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::{CONTENT_LENGTH, HOST, LOCATION};
/// let mut headers = HeaderMap::new();
///
/// headers.insert(HOST, "example.com".parse().unwrap());
/// headers.insert(CONTENT_LENGTH, "123".parse().unwrap());
///
/// assert!(headers.contains_key(HOST));
/// assert!(!headers.contains_key(LOCATION));
///
/// assert_eq!(headers[HOST], "example.com");
///
/// headers.remove(HOST);
///
/// assert!(!headers.contains_key(HOST));
/// ```
#[derive(Clone)]
pub struct HeaderMap<T = HeaderValue> {
// Used to mask values to get an index
mask: Size,
indices: Vec<Pos>,
entries: Vec<Bucket<T>>,
extra_values: Vec<ExtraValue<T>>,
danger: Danger,
}
// # Implementation notes
//
// Below, you will find a fairly large amount of code. Most of this is to
// provide the necessary functions to efficiently manipulate the header
// multimap. The core hashing table is based on robin hood hashing [1]. While
// this is the same hashing algorithm used as part of Rust's `HashMap` in
// stdlib, many implementation details are different. The two primary reasons
// for this divergence are that `HeaderMap` is a multimap and the structure has
// been optimized to take advantage of the characteristics of HTTP headers.
//
// ## Structure Layout
//
// Most of the data contained by `HeaderMap` is *not* stored in the hash table.
// Instead, pairs of header name and *first* associated header value are stored
// in the `entries` vector. If the header name has more than one associated
// header value, then additional values are stored in `extra_values`. The actual
// hash table (`indices`) only maps hash codes to indices in `entries`. This
// means that, when an eviction happens, the actual header name and value stay
// put and only a tiny amount of memory has to be copied.
//
// Extra values associated with a header name are tracked using a linked list.
// Links are formed with offsets into `extra_values` and not pointers.
//
// [1]: https://en.wikipedia.org/wiki/Hash_table#Robin_Hood_hashing
/// `HeaderMap` entry iterator.
///
/// Yields `(&HeaderName, &value)` tuples. The same header name may be yielded
/// more than once if it has more than one associated value.
#[derive(Debug)]
pub struct Iter<'a, T: 'a> {
inner: IterMut<'a, T>,
}
/// `HeaderMap` mutable entry iterator
///
/// Yields `(&HeaderName, &mut value)` tuples. The same header name may be
/// yielded more than once if it has more than one associated value.
#[derive(Debug)]
pub struct IterMut<'a, T: 'a> {
map: *mut HeaderMap<T>,
entry: usize,
cursor: Option<Cursor>,
lt: PhantomData<&'a mut HeaderMap<T>>,
}
/// An owning iterator over the entries of a `HeaderMap`.
///
/// This struct is created by the `into_iter` method on `HeaderMap`.
#[derive(Debug)]
pub struct IntoIter<T> {
// If None, pull from `entries`
next: Option<usize>,
entries: vec::IntoIter<Bucket<T>>,
extra_values: Vec<ExtraValue<T>>,
}
/// An iterator over `HeaderMap` keys.
///
/// Each header name is yielded only once, even if it has more than one
/// associated value.
#[derive(Debug)]
pub struct Keys<'a, T: 'a> {
inner: ::std::slice::Iter<'a, Bucket<T>>,
}
/// `HeaderMap` value iterator.
///
/// Each value contained in the `HeaderMap` will be yielded.
#[derive(Debug)]
pub struct Values<'a, T: 'a> {
inner: Iter<'a, T>,
}
/// `HeaderMap` mutable value iterator
#[derive(Debug)]
pub struct ValuesMut<'a, T: 'a> {
inner: IterMut<'a, T>,
}
/// A drain iterator for `HeaderMap`.
#[derive(Debug)]
pub struct Drain<'a, T: 'a> {
idx: usize,
map: *mut HeaderMap<T>,
lt: PhantomData<&'a mut HeaderMap<T>>,
}
/// A view to all values stored in a single entry.
///
/// This struct is returned by `HeaderMap::get_all`.
#[derive(Debug)]
pub struct GetAll<'a, T: 'a> {
map: &'a HeaderMap<T>,
index: Option<usize>,
}
/// A view into a single location in a `HeaderMap`, which may be vacant or occupied.
#[derive(Debug)]
pub enum Entry<'a, T: 'a> {
/// An occupied entry
Occupied(OccupiedEntry<'a, T>),
/// A vacant entry
Vacant(VacantEntry<'a, T>),
}
/// A view into a single empty location in a `HeaderMap`.
///
/// This struct is returned as part of the `Entry` enum.
#[derive(Debug)]
pub struct VacantEntry<'a, T: 'a> {
map: &'a mut HeaderMap<T>,
key: HeaderName,
hash: HashValue,
probe: usize,
danger: bool,
}
/// A view into a single occupied location in a `HeaderMap`.
///
/// This struct is returned as part of the `Entry` enum.
#[derive(Debug)]
pub struct OccupiedEntry<'a, T: 'a> {
map: &'a mut HeaderMap<T>,
probe: usize,
index: usize,
}
/// An iterator of all values associated with a single header name.
#[derive(Debug)]
pub struct ValueIter<'a, T: 'a> {
map: &'a HeaderMap<T>,
index: usize,
front: Option<Cursor>,
back: Option<Cursor>,
}
/// A mutable iterator of all values associated with a single header name.
#[derive(Debug)]
pub struct ValueIterMut<'a, T: 'a> {
map: *mut HeaderMap<T>,
index: usize,
front: Option<Cursor>,
back: Option<Cursor>,
lt: PhantomData<&'a mut HeaderMap<T>>,
}
/// An drain iterator of all values associated with a single header name.
#[derive(Debug)]
pub struct ValueDrain<'a, T: 'a> {
map: *mut HeaderMap<T>,
first: Option<T>,
next: Option<usize>,
lt: PhantomData<&'a mut HeaderMap<T>>,
}
/// Tracks the value iterator state
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
enum Cursor {
Head,
Values(usize),
}
/// Type used for representing the size of a HeaderMap value.
///
/// 32,768 is more than enough entries for a single header map. Setting this
/// limit enables using `u16` to represent all offsets, which takes 2 bytes
/// instead of 8 on 64 bit processors.
///
/// Setting this limit is especially benificial for `indices`, making it more
/// cache friendly. More hash codes can fit in a cache line.
///
/// You may notice that `u16` may represent more than 32,768 values. This is
/// true, but 32,768 should be plenty and it allows us to reserve the top bit
/// for future usage.
type Size = usize;
/// This limit falls out from above.
const MAX_SIZE: usize = (1 << 15);
/// An entry in the hash table. This represents the full hash code for an entry
/// as well as the position of the entry in the `entries` vector.
#[derive(Copy, Clone)]
struct Pos {
// Index in the `entries` vec
index: Size,
// Full hash value for the entry.
hash: HashValue,
}
/// Hash values are limited to u16 as well. While `fast_hash` and `Hasher`
/// return `usize` hash codes, limiting the effective hash code to the lower 16
/// bits is fine since we know that the `indices` vector will never grow beyond
/// that size.
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
struct HashValue(usize);
/// Stores the data associated with a `HeaderMap` entry. Only the first value is
/// included in this struct. If a header name has more than one associated
/// value, all extra values are stored in the `extra_values` vector. A doubly
/// linked list of entries is maintained. The doubly linked list is used so that
/// removing a value is constant time. This also has the nice property of
/// enabling double ended iteration.
#[derive(Debug, Clone)]
struct Bucket<T> {
hash: HashValue,
key: HeaderName,
value: T,
links: Option<Links>,
}
/// The head and tail of the value linked list.
#[derive(Debug, Copy, Clone)]
struct Links {
next: usize,
tail: usize,
}
/// Node in doubly-linked list of header value entries
#[derive(Debug, Clone)]
struct ExtraValue<T> {
value: T,
prev: Link,
next: Link,
}
/// A header value node is either linked to another node in the `extra_values`
/// list or it points to an entry in `entries`. The entry in `entries` is the
/// start of the list and holds the associated header name.
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
enum Link {
Entry(usize),
Extra(usize),
}
/// Tracks the header map danger level! This relates to the adaptive hashing
/// algorithm. A HeaderMap starts in the "green" state, when a large number of
/// collisions are detected, it transitions to the yellow state. At this point,
/// the header map will either grow and switch back to the green state OR it
/// will transition to the red state.
///
/// When in the red state, a safe hashing algorithm is used and all values in
/// the header map have to be rehashed.
#[derive(Clone)]
enum Danger {
Green,
Yellow,
Red(RandomState),
}
// The HeaderMap will use a sequential search strategy until the size of the map
// exceeds this threshold. This tends to be faster for very small header maps.
// This way all hashing logic can be skipped.
const SEQ_SEARCH_THRESHOLD: usize = 8;
// Constants related to detecting DOS attacks.
//
// Displacement is the number of entries that get shifted when inserting a new
// value. Forward shift is how far the entry gets stored from the ideal
// position.
//
// The current constant values were picked from another implementation. It could
// be that there are different values better suited to the header map case.
const DISPLACEMENT_THRESHOLD: usize = 128;
const FORWARD_SHIFT_THRESHOLD: usize = 512;
// The default strategy for handling the yellow danger state is to increase the
// header map capacity in order to (hopefully) reduce the number of collisions.
// If growing the hash map would cause the load factor to drop bellow this
// threshold, then instead of growing, the headermap is switched to the red
// danger state and safe hashing is used instead.
const LOAD_FACTOR_THRESHOLD: f32 = 0.2;
// Macro used to iterate the hash table starting at a given point, looping when
// the end is hit.
macro_rules! probe_loop {
($label:tt: $probe_var: ident < $len: expr, $body: expr) => {
debug_assert!($len > 0);
$label:
loop {
if $probe_var < $len {
$body
$probe_var += 1;
} else {
$probe_var = 0;
}
}
};
($probe_var: ident < $len: expr, $body: expr) => {
debug_assert!($len > 0);
loop {
if $probe_var < $len {
$body
$probe_var += 1;
} else {
$probe_var = 0;
}
}
};
}
// First part of the robinhood algorithm. Given a key, find the slot in which it
// will be inserted. This is done by starting at the "ideal" spot. Then scanning
// until the destination slot is found. A destination slot is either the next
// empty slot or the next slot that is occupied by an entry that has a lower
// displacement (displacement is the distance from the ideal spot).
//
// This is implemented as a macro instead of a function that takes a closure in
// order to guarantee that it is "inlined". There is no way to annotate closures
// to guarantee inlining.
macro_rules! insert_phase_one {
($map:ident,
$key:expr,
$probe:ident,
$pos:ident,
$hash:ident,
$danger:ident,
$vacant:expr,
$occupied:expr,
$robinhood:expr) =>
{{
let $hash = hash_elem_using(&$map.danger, &$key);
let mut $probe = desired_pos($map.mask, $hash);
let mut dist = 0;
let ret;
// Start at the ideal position, checking all slots
probe_loop!('probe: $probe < $map.indices.len(), {
if let Some(($pos, entry_hash)) = $map.indices[$probe].resolve() {
// The slot is already occupied, but check if it has a lower
// displacement.
let their_dist = probe_distance($map.mask, entry_hash, $probe);
if their_dist < dist {
// The new key's distance is larger, so claim this spot and
// displace the current entry.
//
// Check if this insertion is above the danger threshold.
let $danger =
dist >= FORWARD_SHIFT_THRESHOLD && !$map.danger.is_red();
ret = $robinhood;
break 'probe;
} else if entry_hash == $hash && $map.entries[$pos].key == $key {
// There already is an entry with the same key.
ret = $occupied;
break 'probe;
}
} else {
// The entry is vacant, use it for this key.
let $danger =
dist >= FORWARD_SHIFT_THRESHOLD && !$map.danger.is_red();
ret = $vacant;
break 'probe;
}
dist += 1;
});
ret
}}
}
// ===== impl HeaderMap =====
impl HeaderMap {
/// Create an empty `HeaderMap`.
///
/// The map will be created without any capacity. This function will not
/// allocate.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// let map = HeaderMap::new();
///
/// assert!(map.is_empty());
/// assert_eq!(0, map.capacity());
/// ```
pub fn new() -> Self {
HeaderMap::with_capacity(0)
}
}
impl<T> HeaderMap<T> {
/// Create an empty `HeaderMap` with the specified capacity.
///
/// The returned map will allocate internal storage in order to hold about
/// `capacity` elements without reallocating. However, this is a "best
/// effort" as there are usage patterns that could cause additional
/// allocations before `capacity` headers are stored in the map.
///
/// More capacity than requested may be allocated.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// let map: HeaderMap<u32> = HeaderMap::with_capacity(10);
///
/// assert!(map.is_empty());
/// assert_eq!(12, map.capacity());
/// ```
pub fn with_capacity(capacity: usize) -> HeaderMap<T> {
assert!(capacity <= MAX_SIZE, "requested capacity too large");
if capacity == 0 {
HeaderMap {
mask: 0,
indices: Vec::new(),
entries: Vec::new(),
extra_values: Vec::new(),
danger: Danger::Green,
}
} else {
// Avoid allocating storage for the hash table if the requested
// capacity is below the threshold at which the hash map algorithm
// is used.
let entries_cap = to_raw_capacity(capacity).next_power_of_two();
let indices_cap = if entries_cap > SEQ_SEARCH_THRESHOLD {
entries_cap
} else {
0
};
HeaderMap {
mask: entries_cap.wrapping_sub(1) as Size,
indices: vec![Pos::none(); indices_cap],
entries: Vec::with_capacity(entries_cap),
extra_values: Vec::new(),
danger: Danger::Green,
}
}
}
/// Returns the number of headers stored in the map.
///
/// This number represents the total number of **values** stored in the map.
/// This number can be greater than or equal to the number of **keys**
/// stored given that a single key may have more than one associated value.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::{ACCEPT, HOST};
/// let mut map = HeaderMap::new();
///
/// assert_eq!(0, map.len());
///
/// map.insert(ACCEPT, "text/plain".parse().unwrap());
/// map.insert(HOST, "localhost".parse().unwrap());
///
/// assert_eq!(2, map.len());
///
/// map.append(ACCEPT, "text/html".parse().unwrap());
///
/// assert_eq!(3, map.len());
/// ```
pub fn len(&self) -> usize {
self.entries.len() + self.extra_values.len()
}
/// Returns the number of keys stored in the map.
///
/// This number will be less than or equal to `len()` as each key may have
/// more than one associated value.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::{ACCEPT, HOST};
/// let mut map = HeaderMap::new();
///
/// assert_eq!(0, map.keys_len());
///
/// map.insert(ACCEPT, "text/plain".parse().unwrap());
/// map.insert(HOST, "localhost".parse().unwrap());
///
/// assert_eq!(2, map.keys_len());
///
/// map.insert(ACCEPT, "text/html".parse().unwrap());
///
/// assert_eq!(2, map.keys_len());
/// ```
pub fn keys_len(&self) -> usize {
self.entries.len()
}
/// Returns true if the map contains no elements.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
///
/// assert!(map.is_empty());
///
/// map.insert(HOST, "hello.world".parse().unwrap());
///
/// assert!(!map.is_empty());
/// ```
pub fn is_empty(&self) -> bool {
self.entries.len() == 0
}
/// Clears the map, removing all key-value pairs. Keeps the allocated memory
/// for reuse.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "hello.world".parse().unwrap());
///
/// map.clear();
/// assert!(map.is_empty());
/// assert!(map.capacity() > 0);
/// ```
pub fn clear(&mut self) {
self.entries.clear();
self.extra_values.clear();
self.danger = Danger::Green;
for e in self.indices.iter_mut() {
*e = Pos::none();
}
}
/// Returns the number of headers the map can hold without reallocating.
///
/// This number is an approximation as certain usage patterns could cause
/// additional allocations before the returned capacity is filled.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
///
/// assert_eq!(0, map.capacity());
///
/// map.insert(HOST, "hello.world".parse().unwrap());
/// assert_eq!(6, map.capacity());
/// ```
pub fn capacity(&self) -> usize {
usable_capacity(self.indices.len())
}
/// Reserves capacity for at least `additional` more headers to be inserted
/// into the `HeaderMap`.
///
/// The header map may reserve more space to avoid frequent reallocations.
/// Like with `with_capacity`, this will be a "best effort" to avoid
/// allocations until `additional` more headers are inserted. Certain usage
/// patterns could cause additional allocations before the number is
/// reached.
///
/// # Panics
///
/// Panics if the new allocation size overflows `usize`.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
/// map.reserve(10);
/// # map.insert(HOST, "bar".parse().unwrap());
/// ```
pub fn reserve(&mut self, additional: usize) {
// TODO: This can't overflow if done properly... since the max # of
// elements is u16::MAX.
let cap = self.entries.len()
.checked_add(additional)
.expect("reserve overflow");
if cap > self.indices.len() {
let cap = cap.next_power_of_two();
if self.entries.len() == 0 {
self.mask = cap - 1;
self.indices = vec![Pos::none(); cap];
self.entries = Vec::with_capacity(usable_capacity(cap));
} else {
self.grow(cap);
}
}
}
/// Returns a reference to the value associated with the key.
///
/// If there are multiple values associated with the key, then the first one
/// is returned. Use `get_all` to get all values associated with a given
/// key. Returns `None` if there are no values associated with the key.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
/// assert!(map.get("host").is_none());
///
/// map.insert(HOST, "hello".parse().unwrap());
/// assert_eq!(map.get(HOST).unwrap(), &"hello");
/// assert_eq!(map.get("host").unwrap(), &"hello");
///
/// map.append(HOST, "world".parse().unwrap());
/// assert_eq!(map.get("host").unwrap(), &"hello");
/// ```
pub fn get<K>(&self, key: K) -> Option<&T>
where K: AsHeaderName
{
match key.find(self) {
Some((_, found)) => {
let entry = &self.entries[found];
Some(&entry.value)
}
None => None,
}
}
/// Returns a mutable reference to the value associated with the key.
///
/// If there are multiple values associated with the key, then the first one
/// is returned. Use `entry` to get all values associated with a given
/// key. Returns `None` if there are no values associated with the key.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::default();
/// map.insert(HOST, "hello".to_string());
/// map.get_mut("host").unwrap().push_str("-world");
///
/// assert_eq!(map.get(HOST).unwrap(), &"hello-world");
/// ```
pub fn get_mut<K>(&mut self, key: K) -> Option<&mut T>
where K: AsHeaderName
{
match key.find(self) {
Some((_, found)) => {
let entry = &mut self.entries[found];
Some(&mut entry.value)
}
None => None,
}
}
/// Returns a view of all values associated with a key.
///
/// The returned view does not incur any allocations and allows iterating
/// the values associated with the key. See [`GetAll`] for more details.
/// Returns `None` if there are no values associated with the key.
///
/// [`GetAll`]: struct.GetAll.html
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
///
/// map.insert(HOST, "hello".parse().unwrap());
/// map.append(HOST, "goodbye".parse().unwrap());
///
/// let view = map.get_all("host");
///
/// let mut iter = view.iter();
/// assert_eq!(&"hello", iter.next().unwrap());
/// assert_eq!(&"goodbye", iter.next().unwrap());
/// assert!(iter.next().is_none());
/// ```
pub fn get_all<K>(&self, key: K) -> GetAll<T>
where K: AsHeaderName
{
GetAll {
map: self,
index: key.find(self).map(|(_, i)| i),
}
}
/// Returns true if the map contains a value for the specified key.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
/// assert!(!map.contains_key(HOST));
///
/// map.insert(HOST, "world".parse().unwrap());
/// assert!(map.contains_key("host"));
/// ```
pub fn contains_key<K>(&self, key: K) -> bool
where K: AsHeaderName
{
key.find(self).is_some()
}
/// An iterator visiting all key-value pairs.
///
/// The iteration order is arbitrary, but consistent across platforms for
/// the same crate version. Each key will be yielded once per associated
/// value. So, if a key has 3 associated values, it will be yielded 3 times.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::{CONTENT_LENGTH, HOST};
/// let mut map = HeaderMap::new();
///
/// map.insert(HOST, "hello".parse().unwrap());
/// map.append(HOST, "goodbye".parse().unwrap());
/// map.insert(CONTENT_LENGTH, "123".parse().unwrap());
///
/// for (key, value) in map.iter() {
/// println!("{:?}: {:?}", key, value);
/// }
/// ```
pub fn iter(&self) -> Iter<T> {
Iter {
inner: IterMut {
map: self as *const _ as *mut _,
entry: 0,
cursor: self.entries.first().map(|_| Cursor::Head),
lt: PhantomData,
}
}
}
/// An iterator visiting all key-value pairs, with mutable value references.
///
/// The iterator order is arbitrary, but consistent across platforms for the
/// same crate version. Each key will be yielded once per associated value,
/// so if a key has 3 associated values, it will be yielded 3 times.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::{CONTENT_LENGTH, HOST};
/// let mut map = HeaderMap::default();
///
/// map.insert(HOST, "hello".to_string());
/// map.append(HOST, "goodbye".to_string());
/// map.insert(CONTENT_LENGTH, "123".to_string());
///
/// for (key, value) in map.iter_mut() {
/// value.push_str("-boop");
/// }
/// ```
pub fn iter_mut(&mut self) -> IterMut<T> {
IterMut {
map: self as *mut _,
entry: 0,
cursor: self.entries.first().map(|_| Cursor::Head),
lt: PhantomData,
}
}
/// An iterator visiting all keys.
///
/// The iteration order is arbitrary, but consistent across platforms for
/// the same crate version. Each key will be yielded only once even if it
/// has multiple associated values.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::{CONTENT_LENGTH, HOST};
/// let mut map = HeaderMap::new();
///
/// map.insert(HOST, "hello".parse().unwrap());
/// map.append(HOST, "goodbye".parse().unwrap());
/// map.insert(CONTENT_LENGTH, "123".parse().unwrap());
///
/// for key in map.keys() {
/// println!("{:?}", key);
/// }
/// ```
pub fn keys(&self) -> Keys<T> {
Keys { inner: self.entries.iter() }
}
/// An iterator visiting all values.
///
/// The iteration order is arbitrary, but consistent across platforms for
/// the same crate version.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::{CONTENT_LENGTH, HOST};
/// let mut map = HeaderMap::new();
///
/// map.insert(HOST, "hello".parse().unwrap());
/// map.append(HOST, "goodbye".parse().unwrap());
/// map.insert(CONTENT_LENGTH, "123".parse().unwrap());
///
/// for value in map.values() {
/// println!("{:?}", value);
/// }
/// ```
pub fn values(&self) -> Values<T> {
Values { inner: self.iter() }
}
/// An iterator visiting all values mutably.
///
/// The iteration order is arbitrary, but consistent across platforms for
/// the same crate version.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::{CONTENT_LENGTH, HOST};
/// let mut map = HeaderMap::default();
///
/// map.insert(HOST, "hello".to_string());
/// map.append(HOST, "goodbye".to_string());
/// map.insert(CONTENT_LENGTH, "123".to_string());
///
/// for value in map.values_mut() {
/// value.push_str("-boop");
/// }
/// ```
pub fn values_mut(&mut self) -> ValuesMut<T> {
ValuesMut { inner: self.iter_mut() }
}
/// Clears the map, returning all entries as an iterator.
///
/// The internal memory is kept for reuse.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::{CONTENT_LENGTH, HOST};
/// let mut map = HeaderMap::new();
///
/// map.insert(HOST, "hello".parse().unwrap());
/// map.append(HOST, "goodbye".parse().unwrap());
/// map.insert(CONTENT_LENGTH, "123".parse().unwrap());
///
/// let mut drain = map.drain();
///
/// let (key, mut vals) = drain.next().unwrap();
///
/// assert_eq!("host", key);
/// assert_eq!("hello", vals.next().unwrap());
/// assert_eq!("goodbye", vals.next().unwrap());
/// assert!(vals.next().is_none());
///
/// let (key, mut vals) = drain.next().unwrap();
///
/// assert_eq!("content-length", key);
/// assert_eq!("123", vals.next().unwrap());
/// assert!(vals.next().is_none());
/// ```
pub fn drain(&mut self) -> Drain<T> {
for i in &mut self.indices {
*i = Pos::none();
}
Drain {
idx: 0,
map: self as *mut _,
lt: PhantomData,
}
}
fn value_iter(&self, idx: Option<usize>) -> ValueIter<T> {
use self::Cursor::*;
if let Some(idx) = idx {
let back = {
let entry = &self.entries[idx];
entry.links
.map(|l| Values(l.tail))
.unwrap_or(Head)
};
ValueIter {
map: self,
index: idx,
front: Some(Head),
back: Some(back),
}
} else {
ValueIter {
map: self,
index: ::std::usize::MAX,
front: None,
back: None,
}
}
}
fn value_iter_mut(&mut self, idx: usize) -> ValueIterMut<T> {
use self::Cursor::*;
let back = {
let entry = &self.entries[idx];
entry.links
.map(|l| Values(l.tail))
.unwrap_or(Head)
};
ValueIterMut {
map: self as *mut _,
index: idx,
front: Some(Head),
back: Some(back),
lt: PhantomData,
}
}
/// Gets the given key's corresponding entry in the map for in-place
/// manipulation.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// let mut map: HeaderMap<u32> = HeaderMap::default();
///
/// let headers = &[
/// "content-length",
/// "x-hello",
/// "Content-Length",
/// "x-world",
/// ];
///
/// for &header in headers {
/// let counter = map.entry(header).unwrap().or_insert(0);
/// *counter += 1;
/// }
///
/// assert_eq!(map["content-length"], 2);
/// assert_eq!(map["x-hello"], 1);
/// ```
pub fn entry<K>(&mut self, key: K) -> Result<Entry<T>, InvalidHeaderName>
where K: AsHeaderName,
{
key.entry(self)
}
fn entry2<K>(&mut self, key: K) -> Entry<T>
where K: Hash + Into<HeaderName>,
HeaderName: PartialEq<K>,
{
// Ensure that there is space in the map
self.reserve_one();
insert_phase_one!(
self,
key,
probe,
pos,
hash,
danger,
Entry::Vacant(VacantEntry {
map: self,
hash: hash,
key: key.into(),
probe: probe,
danger: danger,
}),
Entry::Occupied(OccupiedEntry {
map: self,
index: pos,
probe: probe,
}),
Entry::Vacant(VacantEntry {
map: self,
hash: hash,
key: key.into(),
probe: probe,
danger: danger,
}))
}
/// Inserts a key-value pair into the map.
///
/// If the map did not previously have this key present, then `None` is
/// returned.
///
/// If the map did have this key present, the new value is associated with
/// the key and all previous values are removed. **Note** that only a single
/// one of the previous values is returned. If there are multiple values
/// that have been previously associated with the key, then the first one is
/// returned. See `insert_mult` on `OccupiedEntry` for an API that returns
/// all values.
///
/// The key is not updated, though; this matters for types that can be `==`
/// without being identical.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
/// assert!(map.insert(HOST, "world".parse().unwrap()).is_none());
/// assert!(!map.is_empty());
///
/// let mut prev = map.insert(HOST, "earth".parse().unwrap()).unwrap();
/// assert_eq!("world", prev);
/// ```
pub fn insert<K>(&mut self, key: K, val: T) -> Option<T>
where K: IntoHeaderName,
{
key.insert(self, val)
}
#[inline]
fn insert2<K>(&mut self, key: K, value: T) -> Option<T>
where K: Hash + Into<HeaderName>,
HeaderName: PartialEq<K>,
{
self.reserve_one();
insert_phase_one!(
self, key, probe, pos, hash, danger,
// Vacant
{
drop(danger); // Make lint happy
let index = self.entries.len();
self.insert_entry(hash, key.into(), value);
self.indices[probe] = Pos::new(index, hash);
None
},
// Occupied
Some(self.insert_occupied(pos, value)),
// Robinhood
{
self.insert_phase_two(
key.into(),
value,
hash,
probe,
danger);
None
})
}
/// Set an occupied bucket to the given value
#[inline]
fn insert_occupied(&mut self, index: usize, value: T) -> T {
if let Some(links) = self.entries[index].links {
self.remove_all_extra_values(links.next);
}
let entry = &mut self.entries[index];
mem::replace(&mut entry.value, value)
}
fn insert_occupied_mult(&mut self, index: usize, value: T) -> ValueDrain<T> {
let old;
let links;
{
let entry = &mut self.entries[index];
old = mem::replace(&mut entry.value, value);
links = entry.links.take();
}
ValueDrain {
map: self as *mut _,
first: Some(old),
next: links.map(|l| l.next),
lt: PhantomData,
}
}
/// Inserts a key-value pair into the map.
///
/// If the map did not previously have this key present, then `false` is
/// returned.
///
/// If the map did have this key present, the new value is pushed to the end
/// of the list of values currently associated with the key. The key is not
/// updated, though; this matters for types that can be `==` without being
/// identical.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
/// assert!(map.insert(HOST, "world".parse().unwrap()).is_none());
/// assert!(!map.is_empty());
///
/// map.append(HOST, "earth".parse().unwrap());
///
/// let values = map.get_all("host");
/// let mut i = values.iter();
/// assert_eq!("world", *i.next().unwrap());
/// assert_eq!("earth", *i.next().unwrap());
/// ```
pub fn append<K>(&mut self, key: K, value: T) -> bool
where K: IntoHeaderName,
{
key.append(self, value)
}
#[inline]
fn append2<K>(&mut self, key: K, value: T) -> bool
where K: Hash + Into<HeaderName>,
HeaderName: PartialEq<K>,
{
self.reserve_one();
insert_phase_one!(
self, key, probe, pos, hash, danger,
// Vacant
{
drop(danger);
let index = self.entries.len();
self.insert_entry(hash, key.into(), value);
self.indices[probe] = Pos::new(index, hash);
false
},
// Occupied
{
append_value(pos, &mut self.entries[pos], &mut self.extra_values, value);
true
},
// Robinhood
{
self.insert_phase_two(
key.into(),
value,
hash,
probe,
danger);
false
})
}
#[inline]
fn find<K: ?Sized>(&self, key: &K) -> Option<(usize, usize)>
where K: Hash + Into<HeaderName>,
HeaderName: PartialEq<K>,
{
if self.entries.is_empty() {
return None;
}
let hash = hash_elem_using(&self.danger, key);
let mask = self.mask;
let mut probe = desired_pos(mask, hash);
let mut dist = 0;
probe_loop!(probe < self.indices.len(), {
if let Some((i, entry_hash)) = self.indices[probe].resolve() {
if dist > probe_distance(mask, entry_hash, probe) {
// give up when probe distance is too long
return None;
} else if entry_hash == hash && self.entries[i].key == *key {
return Some((probe, i));
}
} else {
return None;
}
dist += 1;
});
}
/// phase 2 is post-insert where we forward-shift `Pos` in the indices.
///
/// This phase only needs to happen if currently in hashed mode
#[inline]
fn insert_phase_two(&mut self,
key: HeaderName,
value: T,
hash: HashValue,
probe: usize,
danger: bool) -> usize
{
// Push the value and get the index
let index = self.entries.len();
self.insert_entry(hash, key, value);
let num_displaced = do_insert_phase_two(
&mut self.indices,
probe,
Pos::new(index, hash));
if danger || num_displaced >= DISPLACEMENT_THRESHOLD {
// Increase danger level
self.danger.to_yellow();
}
index
}
/// Removes a key from the map, returning the value associated with the key.
///
/// Returns `None` if the map does not contain the key. If there are
/// multiple values associated with the key, then the first one is returned.
/// See `remove_entry_mult` on `OccupiedEntry` for an API that yields all
/// values.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "hello.world".parse().unwrap());
///
/// let prev = map.remove(HOST).unwrap();
/// assert_eq!("hello.world", prev);
///
/// assert!(map.remove(HOST).is_none());
/// ```
pub fn remove<K>(&mut self, key: K) -> Option<T>
where K: AsHeaderName
{
match key.find(self) {
Some((probe, idx)) => {
if let Some(links) = self.entries[idx].links {
self.remove_all_extra_values(links.next);
}
let entry = self.remove_found(probe, idx);
Some(entry.value)
}
None => None,
}
}
/// Remove an entry from the map while in hashed mode
#[inline]
fn remove_found(&mut self, probe: usize, found: usize) -> Bucket<T> {
// index `probe` and entry `found` is to be removed
// use swap_remove, but then we need to update the index that points
// to the other entry that has to move
self.indices[probe] = Pos::none();
let entry = self.entries.swap_remove(found);
// correct index that points to the entry that had to swap places
if let Some(entry) = self.entries.get(found) {
// was not last element
// examine new element in `found` and find it in indices
let mut probe = desired_pos(self.mask, entry.hash);
probe_loop!(probe < self.indices.len(), {
if let Some((i, _)) = self.indices[probe].resolve() {
if i >= self.entries.len() {
// found it
self.indices[probe] = Pos::new(found, entry.hash);
break;
}
}
});
// Update links
if let Some(links) = entry.links {
self.extra_values[links.next].prev = Link::Entry(found);
self.extra_values[links.tail].next = Link::Entry(found);
}
}
// backward shift deletion in self.indices
// after probe, shift all non-ideally placed indices backward
if self.entries.len() > 0 {
let mut last_probe = probe;
let mut probe = probe + 1;
probe_loop!(probe < self.indices.len(), {
if let Some((_, entry_hash)) = self.indices[probe].resolve() {
if probe_distance(self.mask, entry_hash, probe) > 0 {
self.indices[last_probe] = self.indices[probe];
self.indices[probe] = Pos::none();
} else {
break;
}
} else {
break;
}
last_probe = probe;
});
}
entry
}
/// Removes the `ExtraValue` at the given index.
#[inline]
fn remove_extra_value(&mut self, idx: usize) -> ExtraValue<T> {
let prev;
let next;
{
debug_assert!(self.extra_values.len() > idx);
let extra = &self.extra_values[idx];
prev = extra.prev;
next = extra.next;
}
// First unlink the extra value
match (prev, next) {
(Link::Entry(prev), Link::Entry(next)) => {
debug_assert_eq!(prev, next);
debug_assert!(self.entries.len() > prev);
self.entries[prev].links = None;
}
(Link::Entry(prev), Link::Extra(next)) => {
debug_assert!(self.entries.len() > prev);
debug_assert!(self.entries[prev].links.is_some());
self.entries[prev].links.as_mut().unwrap()
.next = next;
debug_assert!(self.extra_values.len() > next);
self.extra_values[next].prev = Link::Entry(prev);
}
(Link::Extra(prev), Link::Entry(next)) => {
debug_assert!(self.entries.len() > next);
debug_assert!(self.entries[next].links.is_some());
self.entries[next].links.as_mut().unwrap()
.tail = prev;
debug_assert!(self.extra_values.len() > prev);
self.extra_values[prev].next = Link::Entry(next);
}
(Link::Extra(prev), Link::Extra(next)) => {
debug_assert!(self.extra_values.len() > next);
debug_assert!(self.extra_values.len() > prev);
self.extra_values[prev].next = Link::Extra(next);
self.extra_values[next].prev = Link::Extra(prev);
}
}
// Remove the extra value
let mut extra = self.extra_values.swap_remove(idx);
// This is the index of the value that was moved (possibly `extra`)
let old_idx = self.extra_values.len();
// Update the links
if extra.prev == Link::Extra(old_idx) {
extra.prev = Link::Extra(idx);
}
if extra.next == Link::Extra(old_idx) {
extra.next = Link::Extra(idx);
}
// Check if another entry was displaced. If it was, then the links
// need to be fixed.
if idx != old_idx {
let next;
let prev;
{
debug_assert!(self.extra_values.len() > idx);
let moved = &self.extra_values[idx];
next = moved.next;
prev = moved.prev;
}
// An entry was moved, we have to the links
match prev {
Link::Entry(entry_idx) => {
// It is critical that we do not attempt to read the
// header name or value as that memory may have been
// "released" already.
debug_assert!(self.entries.len() > entry_idx);
debug_assert!(self.entries[entry_idx].links.is_some());
let links = self.entries[entry_idx].links.as_mut().unwrap();
links.next = idx;
}
Link::Extra(extra_idx) => {
debug_assert!(self.extra_values.len() > extra_idx);
self.extra_values[extra_idx].next = Link::Extra(idx);
}
}
match next {
Link::Entry(entry_idx) => {
debug_assert!(self.entries.len() > entry_idx);
debug_assert!(self.entries[entry_idx].links.is_some());
let links = self.entries[entry_idx].links.as_mut().unwrap();
links.tail = idx;
}
Link::Extra(extra_idx) => {
debug_assert!(self.extra_values.len() > extra_idx);
self.extra_values[extra_idx].prev = Link::Extra(idx);
}
}
}
debug_assert!({
for v in &self.extra_values {
assert!(v.next != Link::Extra(old_idx));
assert!(v.prev != Link::Extra(old_idx));
}
true
});
extra
}
fn remove_all_extra_values(&mut self, mut head: usize) {
loop {
let extra = self.remove_extra_value(head);
if let Link::Extra(idx) = extra.next {
head = idx;
} else {
break;
}
}
}
#[inline]
fn insert_entry(&mut self, hash: HashValue, key: HeaderName, value: T) {
assert!(self.entries.len() < MAX_SIZE, "header map at capacity");
self.entries.push(Bucket {
hash: hash,
key: key,
value: value,
links: None,
});
}
fn rebuild(&mut self) {
// Loop over all entries and re-insert them into the map
'outer:
for (index, entry) in self.entries.iter_mut().enumerate() {
let hash = hash_elem_using(&self.danger, &entry.key);
let mut probe = desired_pos(self.mask, hash);
let mut dist = 0;
// Update the entry's hash code
entry.hash = hash;
probe_loop!(probe < self.indices.len(), {
if let Some((_, entry_hash)) = self.indices[probe].resolve() {
// if existing element probed less than us, swap
let their_dist = probe_distance(self.mask, entry_hash, probe);
if their_dist < dist {
// Robinhood
break;
}
} else {
// Vacant slot
self.indices[probe] = Pos::new(index, hash);
continue 'outer;
}
dist += 1;
});
do_insert_phase_two(
&mut self.indices,
probe,
Pos::new(index, hash));
}
}
fn reinsert_entry_in_order(&mut self, pos: Pos) {
if let Some((_, entry_hash)) = pos.resolve() {
// Find first empty bucket and insert there
let mut probe = desired_pos(self.mask, entry_hash);
probe_loop!(probe < self.indices.len(), {
if self.indices[probe].resolve().is_none() {
// empty bucket, insert here
self.indices[probe] = pos;
return;
}
});
}
}
fn reserve_one(&mut self) {
let len = self.entries.len();
if self.danger.is_yellow() {
let load_factor = self.entries.len() as f32 / self.indices.len() as f32;
if load_factor >= LOAD_FACTOR_THRESHOLD {
// Transition back to green danger level
self.danger.to_green();
// Double the capacity
let new_cap = self.indices.len() * 2;
// Grow the capacity
self.grow(new_cap);
} else {
self.danger.to_red();
// Rebuild hash table
for index in &mut self.indices {
*index = Pos::none();
}
self.rebuild();
}
} else if len == self.capacity() {
if len == 0 {
let new_raw_cap = 8;
self.mask = 8 - 1;
self.indices = vec![Pos::none(); new_raw_cap];
self.entries = Vec::with_capacity(usable_capacity(new_raw_cap));
} else {
let raw_cap = self.indices.len();
self.grow(raw_cap << 1);
}
}
}
#[inline]
fn grow(&mut self, new_raw_cap: usize) {
// This path can never be reached when handling the first allocation in
// the map.
// find first ideally placed element -- start of cluster
let mut first_ideal = 0;
for (i, pos) in self.indices.iter().enumerate() {
if let Some((_, entry_hash)) = pos.resolve() {
if 0 == probe_distance(self.mask, entry_hash, i) {
first_ideal = i;
break;
}
}
}
// visit the entries in an order where we can simply reinsert them
// into self.indices without any bucket stealing.
let old_indices = mem::replace(&mut self.indices, vec![Pos::none(); new_raw_cap]);
self.mask = new_raw_cap.wrapping_sub(1) as Size;
for &pos in &old_indices[first_ideal..] {
self.reinsert_entry_in_order(pos);
}
for &pos in &old_indices[..first_ideal] {
self.reinsert_entry_in_order(pos);
}
// Reserve additional entry slots
let more = self.capacity() - self.entries.len();
self.entries.reserve_exact(more);
}
}
impl<'a, T> IntoIterator for &'a HeaderMap<T> {
type Item = (&'a HeaderName, &'a T);
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<'a, T> IntoIterator for &'a mut HeaderMap<T> {
type Item = (&'a HeaderName, &'a mut T);
type IntoIter = IterMut<'a, T>;
fn into_iter(self) -> IterMut<'a, T> {
self.iter_mut()
}
}
impl<T> IntoIterator for HeaderMap<T> {
type Item = (Option<HeaderName>, T);
type IntoIter = IntoIter<T>;
/// Creates a consuming iterator, that is, one that moves keys and values
/// out of the map in arbitary order. The map cannot be used after calling
/// this.
///
/// For each yielded item that has `None` provided for the `HeaderName`,
/// then the associated header name is the same as that of the previously
/// yielded item. The first yielded item will have `HeaderName` set.
///
/// # Examples
///
/// Basic usage.
///
/// ```
/// # use http::header;
/// # use http::header::*;
/// let mut map = HeaderMap::new();
/// map.insert(header::CONTENT_LENGTH, "123".parse().unwrap());
/// map.insert(header::CONTENT_TYPE, "json".parse().unwrap());
///
/// let mut iter = map.into_iter();
/// assert_eq!(iter.next(), Some((Some(header::CONTENT_LENGTH), "123".parse().unwrap())));
/// assert_eq!(iter.next(), Some((Some(header::CONTENT_TYPE), "json".parse().unwrap())));
/// assert!(iter.next().is_none());
/// ```
///
/// Multiple values per key.
///
/// ```
/// # use http::header;
/// # use http::header::*;
/// let mut map = HeaderMap::new();
///
/// map.append(header::CONTENT_LENGTH, "123".parse().unwrap());
/// map.append(header::CONTENT_LENGTH, "456".parse().unwrap());
///
/// map.append(header::CONTENT_TYPE, "json".parse().unwrap());
/// map.append(header::CONTENT_TYPE, "html".parse().unwrap());
/// map.append(header::CONTENT_TYPE, "xml".parse().unwrap());
///
/// let mut iter = map.into_iter();
///
/// assert_eq!(iter.next(), Some((Some(header::CONTENT_LENGTH), "123".parse().unwrap())));
/// assert_eq!(iter.next(), Some((None, "456".parse().unwrap())));
///
/// assert_eq!(iter.next(), Some((Some(header::CONTENT_TYPE), "json".parse().unwrap())));
/// assert_eq!(iter.next(), Some((None, "html".parse().unwrap())));
/// assert_eq!(iter.next(), Some((None, "xml".parse().unwrap())));
/// assert!(iter.next().is_none());
/// ```
fn into_iter(self) -> IntoIter<T> {
IntoIter {
next: None,
entries: self.entries.into_iter(),
extra_values: self.extra_values,
}
}
}
impl<T> FromIterator<(HeaderName, T)> for HeaderMap<T>
{
fn from_iter<I>(iter: I) -> Self
where I: IntoIterator<Item = (HeaderName, T)>
{
let mut map = HeaderMap::default();
map.extend(iter);
map
}
}
impl<T> Extend<(Option<HeaderName>, T)> for HeaderMap<T> {
/// Extend a `HeaderMap` with the contents of another `HeaderMap`.
///
/// This function expects the yielded items to follow the same structure as
/// `IntoIter`.
///
/// # Panics
///
/// This panics if the first yielded item does not have a `HeaderName`.
///
/// # Examples
///
/// ```
/// # use http::header::*;
/// let mut map = HeaderMap::new();
///
/// map.insert(ACCEPT, "text/plain".parse().unwrap());
/// map.insert(HOST, "hello.world".parse().unwrap());
///
/// let mut extra = HeaderMap::new();
///
/// extra.insert(HOST, "foo.bar".parse().unwrap());
/// extra.insert(COOKIE, "hello".parse().unwrap());
/// extra.append(COOKIE, "world".parse().unwrap());
///
/// map.extend(extra);
///
/// assert_eq!(map["host"], "foo.bar");
/// assert_eq!(map["accept"], "text/plain");
/// assert_eq!(map["cookie"], "hello");
///
/// let v = map.get_all("host");
/// assert_eq!(1, v.iter().count());
///
/// let v = map.get_all("cookie");
/// assert_eq!(2, v.iter().count());
/// ```
fn extend<I: IntoIterator<Item = (Option<HeaderName>, T)>>(&mut self, iter: I) {
let mut iter = iter.into_iter();
// The structure of this is a bit weird, but it is mostly to make the
// borrow checker happy.
let (mut key, mut val) = match iter.next() {
Some((Some(key), val)) => (key, val),
Some((None, _)) => panic!("expected a header name, but got None"),
None => return,
};
'outer:
loop {
let mut entry = match self.entry(key).expect("HeaderName is always OK") {
Entry::Occupied(mut e) => {
// Replace all previous values while maintaining a handle to
// the entry.
e.insert(val);
e
}
Entry::Vacant(e) => {
e.insert_entry(val)
}
};
// As long as `HeaderName` is none, keep inserting the value into
// the current entry
'inner:
loop {
match iter.next() {
Some((Some(k), v)) => {
key = k;
val = v;
continue 'outer;
}
Some((None, v)) => {
entry.append(v);
}
None => {
return;
}
}
}
}
}
}
impl<T> Extend<(HeaderName, T)> for HeaderMap<T>
{
fn extend<I: IntoIterator<Item = (HeaderName, T)>>(&mut self, iter: I) {
// Keys may be already present or show multiple times in the iterator.
// Reserve the entire hint lower bound if the map is empty.
// Otherwise reserve half the hint (rounded up), so the map
// will only resize twice in the worst case.
let iter = iter.into_iter();
let reserve = if self.is_empty() {
iter.size_hint().0
} else {
(iter.size_hint().0 + 1) / 2
};
self.reserve(reserve);
for (k, v) in iter {
self.append(k, v);
}
}
}
impl<T: PartialEq> PartialEq for HeaderMap<T> {
fn eq(&self, other: &HeaderMap<T>) -> bool {
if self.len() != other.len() {
return false;
}
self.keys().all(|key| {
self.get_all(key) == other.get_all(key)
})
}
}
impl<T: Eq> Eq for HeaderMap<T> {}
impl<T: fmt::Debug> fmt::Debug for HeaderMap<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<T> Default for HeaderMap<T> {
fn default() -> Self {
HeaderMap::with_capacity(0)
}
}
impl<'a, K, T> ops::Index<K> for HeaderMap<T>
where K: AsHeaderName,
{
type Output = T;
#[inline]
fn index(&self, index: K) -> &T {
self.get(index).expect("no entry found for key")
}
}
/// phase 2 is post-insert where we forward-shift `Pos` in the indices.
///
/// returns the number of displaced elements
#[inline]
fn do_insert_phase_two(indices: &mut Vec<Pos>,
mut probe: usize,
mut old_pos: Pos)
-> usize
{
let mut num_displaced = 0;
probe_loop!(probe < indices.len(), {
let pos = &mut indices[probe];
if pos.is_none() {
*pos = old_pos;
break;
} else {
num_displaced += 1;
old_pos = mem::replace(pos, old_pos);
}
});
num_displaced
}
#[inline]
fn append_value<T>(entry_idx: usize,
entry: &mut Bucket<T>,
extra: &mut Vec<ExtraValue<T>>,
value: T)
{
match entry.links {
Some(links) => {
let idx = extra.len();
extra.push(ExtraValue {
value: value,
prev: Link::Extra(links.tail),
next: Link::Entry(entry_idx),
});
extra[links.tail].next = Link::Extra(idx);
entry.links = Some(Links {
tail: idx,
.. links
});
}
None => {
let idx = extra.len();
extra.push(ExtraValue {
value: value,
prev: Link::Entry(entry_idx),
next: Link::Entry(entry_idx),
});
entry.links = Some(Links {
next: idx,
tail: idx,
});
}
}
}
// ===== impl Iter =====
impl<'a, T> Iterator for Iter<'a, T> {
type Item = (&'a HeaderName, &'a T);
fn next(&mut self) -> Option<Self::Item> {
self.inner.next_unsafe().map(|(key, ptr)| {
(key, unsafe { &*ptr })
})
}
}
unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
unsafe impl<'a, T: Sync> Send for Iter<'a, T> {}
// ===== impl IterMut =====
impl<'a, T> IterMut<'a, T> {
fn next_unsafe(&mut self) -> Option<(&'a HeaderName, *mut T)> {
use self::Cursor::*;
if self.cursor.is_none() {
if (self.entry + 1) >= unsafe { &*self.map }.entries.len() {
return None;
}
self.entry += 1;
self.cursor = Some(Cursor::Head);
}
let entry = unsafe { &(*self.map).entries[self.entry] };
match self.cursor.unwrap() {
Head => {
self.cursor = entry.links.map(|l| Values(l.next));
Some((&entry.key, &entry.value as *const _ as *mut _))
}
Values(idx) => {
let extra = unsafe { &(*self.map).extra_values[idx] };
match extra.next {
Link::Entry(_) => self.cursor = None,
Link::Extra(i) => self.cursor = Some(Values(i)),
}
Some((&entry.key, &extra.value as *const _ as *mut _))
}
}
}
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = (&'a HeaderName, &'a mut T);
fn next(&mut self) -> Option<Self::Item> {
self.next_unsafe().map(|(key, ptr)| {
(key, unsafe { &mut *ptr })
})
}
}
unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
// ===== impl Keys =====
impl<'a, T> Iterator for Keys<'a, T> {
type Item = &'a HeaderName;
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|b| &b.key)
}
}
// ===== impl Values ====
impl<'a, T> Iterator for Values<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|(_, v)| v)
}
}
// ===== impl ValuesMut ====
impl<'a, T> Iterator for ValuesMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|(_, v)| v)
}
}
// ===== impl Drain =====
impl<'a, T> Iterator for Drain<'a, T> {
type Item = (HeaderName, ValueDrain<'a, T>);
fn next(&mut self) -> Option<Self::Item> {
let idx = self.idx;
if idx == unsafe { (*self.map).entries.len() } {
return None;
}
self.idx += 1;
let key;
let value;
let next;
unsafe {
let entry = &(*self.map).entries[idx];
// Read the header name
key = ptr::read(&entry.key as *const _);
value = ptr::read(&entry.value as *const _);
next = entry.links.map(|l| l.next);
};
let values = ValueDrain {
map: self.map,
first: Some(value),
next: next,
lt: PhantomData,
};
Some((key, values))
}
}
impl<'a, T> Drop for Drain<'a, T> {
fn drop(&mut self) {
unsafe {
let map = &mut *self.map;
debug_assert!(map.extra_values.is_empty());
map.entries.set_len(0);
}
}
}
unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
unsafe impl<'a, T: Send> Send for Drain<'a, T> {}
// ===== impl Entry =====
impl<'a, T> Entry<'a, T> {
/// Ensures a value is in the entry by inserting the default if empty.
///
/// Returns a mutable reference to the **first** value in the entry.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// let mut map: HeaderMap<u32> = HeaderMap::default();
///
/// let headers = &[
/// "content-length",
/// "x-hello",
/// "Content-Length",
/// "x-world",
/// ];
///
/// for &header in headers {
/// let counter = map.entry(header)
/// .expect("valid header names")
/// .or_insert(0);
/// *counter += 1;
/// }
///
/// assert_eq!(map["content-length"], 2);
/// assert_eq!(map["x-hello"], 1);
/// ```
pub fn or_insert(self, default: T) -> &'a mut T {
use self::Entry::*;
match self {
Occupied(e) => e.into_mut(),
Vacant(e) => e.insert(default),
}
}
/// Ensures a value is in the entry by inserting the result of the default
/// function if empty.
///
/// The default function is not called if the entry exists in the map.
/// Returns a mutable reference to the **first** value in the entry.
///
/// # Examples
///
/// Basic usage.
///
/// ```
/// # use http::HeaderMap;
/// let mut map = HeaderMap::new();
///
/// let res = map.entry("x-hello").unwrap()
/// .or_insert_with(|| "world".parse().unwrap());
///
/// assert_eq!(res, "world");
/// ```
///
/// The default function is not called if the entry exists in the map.
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "world".parse().unwrap());
///
/// let res = map.entry("host")
/// .expect("host is a valid string")
/// .or_insert_with(|| unreachable!());
///
///
/// assert_eq!(res, "world");
/// ```
pub fn or_insert_with<F: FnOnce() -> T>(self, default: F) -> &'a mut T {
use self::Entry::*;
match self {
Occupied(e) => e.into_mut(),
Vacant(e) => e.insert(default()),
}
}
/// Returns a reference to the entry's key
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// let mut map = HeaderMap::new();
///
/// assert_eq!(map.entry("x-hello").unwrap().key(), "x-hello");
/// ```
pub fn key(&self) -> &HeaderName {
use self::Entry::*;
match *self {
Vacant(ref e) => e.key(),
Occupied(ref e) => e.key(),
}
}
}
// ===== impl VacantEntry =====
impl<'a, T> VacantEntry<'a, T> {
/// Returns a reference to the entry's key
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// let mut map = HeaderMap::new();
///
/// assert_eq!(map.entry("x-hello").unwrap().key().as_str(), "x-hello");
/// ```
pub fn key(&self) -> &HeaderName {
&self.key
}
/// Take ownership of the key
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry};
/// let mut map = HeaderMap::new();
///
/// if let Entry::Vacant(v) = map.entry("x-hello").unwrap() {
/// assert_eq!(v.into_key().as_str(), "x-hello");
/// }
/// ```
pub fn into_key(self) -> HeaderName {
self.key
}
/// Insert the value into the entry.
///
/// The value will be associated with this entry's key. A mutable reference
/// to the inserted value will be returned.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry};
/// let mut map = HeaderMap::new();
///
/// if let Entry::Vacant(v) = map.entry("x-hello").unwrap() {
/// v.insert("world".parse().unwrap());
/// }
///
/// assert_eq!(map["x-hello"], "world");
/// ```
pub fn insert(self, value: T) -> &'a mut T {
// Ensure that there is space in the map
let index = self.map.insert_phase_two(
self.key,
value.into(),
self.hash,
self.probe,
self.danger);
&mut self.map.entries[index].value
}
/// Insert the value into the entry.
///
/// The value will be associated with this entry's key. The new
/// `OccupiedEntry` is returned, allowing for further manipulation.
///
/// # Examples
///
/// ```
/// # use http::header::*;
/// let mut map = HeaderMap::new();
///
/// if let Entry::Vacant(v) = map.entry("x-hello").unwrap() {
/// let mut e = v.insert_entry("world".parse().unwrap());
/// e.insert("world2".parse().unwrap());
/// }
///
/// assert_eq!(map["x-hello"], "world2");
/// ```
pub fn insert_entry(self, value: T) -> OccupiedEntry<'a, T> {
// Ensure that there is space in the map
let index = self.map.insert_phase_two(
self.key,
value.into(),
self.hash,
self.probe,
self.danger);
OccupiedEntry {
map: self.map,
index: index,
probe: self.probe,
}
}
}
// ===== impl GetAll =====
impl<'a, T: 'a> GetAll<'a, T> {
/// Returns an iterator visiting all values associated with the entry.
///
/// Values are iterated in insertion order.
///
/// # Examples
///
/// ```
/// # use http::HeaderMap;
/// # use http::header::HOST;
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "hello.world".parse().unwrap());
/// map.append(HOST, "hello.earth".parse().unwrap());
///
/// let values = map.get_all("host");
/// let mut iter = values.iter();
/// assert_eq!(&"hello.world", iter.next().unwrap());
/// assert_eq!(&"hello.earth", iter.next().unwrap());
/// assert!(iter.next().is_none());
/// ```
pub fn iter(&self) -> ValueIter<'a, T> {
// This creates a new GetAll struct so that the lifetime
// isn't bound to &self.
GetAll {
map: self.map,
index: self.index,
}.into_iter()
}
}
impl<'a, T: PartialEq> PartialEq for GetAll<'a, T> {
fn eq(&self, other: &Self) -> bool {
self.iter().eq(other.iter())
}
}
impl<'a, T> IntoIterator for GetAll<'a, T> {
type Item = &'a T;
type IntoIter = ValueIter<'a, T>;
fn into_iter(self) -> ValueIter<'a, T> {
self.map.value_iter(self.index)
}
}
impl<'a, 'b: 'a, T> IntoIterator for &'b GetAll<'a, T> {
type Item = &'a T;
type IntoIter = ValueIter<'a, T>;
fn into_iter(self) -> ValueIter<'a, T> {
self.map.value_iter(self.index)
}
}
// ===== impl ValueIter =====
impl<'a, T: 'a> Iterator for ValueIter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
use self::Cursor::*;
match self.front {
Some(Head) => {
let entry = &self.map.entries[self.index];
if self.back == Some(Head) {
self.front = None;
self.back = None;
} else {
// Update the iterator state
match entry.links {
Some(links) => {
self.front = Some(Values(links.next));
}
None => unreachable!(),
}
}
Some(&entry.value)
}
Some(Values(idx)) => {
let extra = &self.map.extra_values[idx];
if self.front == self.back {
self.front = None;
self.back = None;
} else {
match extra.next {
Link::Entry(_) => self.front = None,
Link::Extra(i) => self.front = Some(Values(i)),
}
}
Some(&extra.value)
}
None => None,
}
}
}
impl<'a, T: 'a> DoubleEndedIterator for ValueIter<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
use self::Cursor::*;
match self.back {
Some(Head) => {
self.front = None;
self.back = None;
Some(&self.map.entries[self.index].value)
}
Some(Values(idx)) => {
let extra = &self.map.extra_values[idx];
if self.front == self.back {
self.front = None;
self.back = None;
} else {
match extra.prev {
Link::Entry(_) => self.back = Some(Head),
Link::Extra(idx) => self.back = Some(Values(idx)),
}
}
Some(&extra.value)
}
None => None,
}
}
}
// ===== impl ValueIterMut =====
impl<'a, T: 'a> Iterator for ValueIterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
use self::Cursor::*;
let entry = unsafe { &mut (*self.map).entries[self.index] };
match self.front {
Some(Head) => {
if self.back == Some(Head) {
self.front = None;
self.back = None;
} else {
// Update the iterator state
match entry.links {
Some(links) => {
self.front = Some(Values(links.next));
}
None => unreachable!(),
}
}
Some(&mut entry.value)
}
Some(Values(idx)) => {
let extra = unsafe { &mut (*self.map).extra_values[idx] };
if self.front == self.back {
self.front = None;
self.back = None;
} else {
match extra.next {
Link::Entry(_) => self.front = None,
Link::Extra(i) => self.front = Some(Values(i)),
}
}
Some(&mut extra.value)
}
None => None,
}
}
}
impl<'a, T: 'a> DoubleEndedIterator for ValueIterMut<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
use self::Cursor::*;
let entry = unsafe { &mut (*self.map).entries[self.index] };
match self.back {
Some(Head) => {
self.front = None;
self.back = None;
Some(&mut entry.value)
}
Some(Values(idx)) => {
let extra = unsafe { &mut (*self.map).extra_values[idx] };
if self.front == self.back {
self.front = None;
self.back = None;
} else {
match extra.prev {
Link::Entry(_) => self.back = Some(Head),
Link::Extra(idx) => self.back = Some(Values(idx)),
}
}
Some(&mut extra.value)
}
None => None,
}
}
}
unsafe impl<'a, T: Sync> Sync for ValueIterMut<'a, T> {}
unsafe impl<'a, T: Send> Send for ValueIterMut<'a, T> {}
// ===== impl IntoIter =====
impl<T> Iterator for IntoIter<T> {
type Item = (Option<HeaderName>, T);
fn next(&mut self) -> Option<Self::Item> {
if let Some(next) = self.next {
self.next = match self.extra_values[next].next {
Link::Entry(_) => None,
Link::Extra(v) => Some(v),
};
let value = unsafe { ptr::read(&self.extra_values[next].value) };
return Some((None, value));
}
if let Some(bucket) = self.entries.next() {
self.next = bucket.links.map(|l| l.next);
let name = Some(bucket.key);
let value = bucket.value;
return Some((name, value));
}
None
}
}
impl<T> Drop for IntoIter<T> {
fn drop(&mut self) {
// Ensure the iterator is consumed
for _ in self.by_ref() { }
// All the values have already been yielded out.
unsafe { self.extra_values.set_len(0); }
}
}
// ===== impl OccupiedEntry =====
impl<'a, T> OccupiedEntry<'a, T> {
/// Returns a reference to the entry's key.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "world".parse().unwrap());
///
/// if let Entry::Occupied(e) = map.entry("host").unwrap() {
/// assert_eq!("host", e.key());
/// }
/// ```
pub fn key(&self) -> &HeaderName {
&self.map.entries[self.index].key
}
/// Get a reference to the first value in the entry.
///
/// Values are stored in insertion order.
///
/// # Panics
///
/// `get` panics if there are no values associated with the entry.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "hello.world".parse().unwrap());
///
/// if let Entry::Occupied(mut e) = map.entry("host").unwrap() {
/// assert_eq!(e.get(), &"hello.world");
///
/// e.append("hello.earth".parse().unwrap());
///
/// assert_eq!(e.get(), &"hello.world");
/// }
/// ```
pub fn get(&self) -> &T {
&self.map.entries[self.index].value
}
/// Get a mutable reference to the first value in the entry.
///
/// Values are stored in insertion order.
///
/// # Panics
///
/// `get_mut` panics if there are no values associated with the entry.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::default();
/// map.insert(HOST, "hello.world".to_string());
///
/// if let Entry::Occupied(mut e) = map.entry("host").unwrap() {
/// e.get_mut().push_str("-2");
/// assert_eq!(e.get(), &"hello.world-2");
/// }
/// ```
pub fn get_mut(&mut self) -> &mut T {
&mut self.map.entries[self.index].value
}
/// Converts the `OccupiedEntry` into a mutable reference to the **first**
/// value.
///
/// The lifetime of the returned reference is bound to the original map.
///
/// # Panics
///
/// `into_mut` panics if there are no values associated with the entry.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::default();
/// map.insert(HOST, "hello.world".to_string());
/// map.append(HOST, "hello.earth".to_string());
///
/// if let Entry::Occupied(e) = map.entry("host").unwrap() {
/// e.into_mut().push_str("-2");
/// }
///
/// assert_eq!("hello.world-2", map["host"]);
/// ```
pub fn into_mut(self) -> &'a mut T {
&mut self.map.entries[self.index].value
}
/// Sets the value of the entry.
///
/// All previous values associated with the entry are removed and the first
/// one is returned. See `insert_mult` for an API that returns all values.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "hello.world".parse().unwrap());
///
/// if let Entry::Occupied(mut e) = map.entry("host").unwrap() {
/// let mut prev = e.insert("earth".parse().unwrap());
/// assert_eq!("hello.world", prev);
/// }
///
/// assert_eq!("earth", map["host"]);
/// ```
pub fn insert(&mut self, value: T) -> T {
self.map.insert_occupied(self.index, value.into())
}
/// Sets the value of the entry.
///
/// This function does the same as `insert` except it returns an iterator
/// that yields all values previously associated with the key.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "world".parse().unwrap());
/// map.append(HOST, "world2".parse().unwrap());
///
/// if let Entry::Occupied(mut e) = map.entry("host").unwrap() {
/// let mut prev = e.insert_mult("earth".parse().unwrap());
/// assert_eq!("world", prev.next().unwrap());
/// assert_eq!("world2", prev.next().unwrap());
/// assert!(prev.next().is_none());
/// }
///
/// assert_eq!("earth", map["host"]);
/// ```
pub fn insert_mult(&mut self, value: T) -> ValueDrain<T> {
self.map.insert_occupied_mult(self.index, value.into())
}
/// Insert the value into the entry.
///
/// The new value is appended to the end of the entry's value list. All
/// previous values associated with the entry are retained.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "world".parse().unwrap());
///
/// if let Entry::Occupied(mut e) = map.entry("host").unwrap() {
/// e.append("earth".parse().unwrap());
/// }
///
/// let values = map.get_all("host");
/// let mut i = values.iter();
/// assert_eq!("world", *i.next().unwrap());
/// assert_eq!("earth", *i.next().unwrap());
/// ```
pub fn append(&mut self, value: T) {
let idx = self.index;
let entry = &mut self.map.entries[idx];
append_value(idx, entry, &mut self.map.extra_values, value.into());
}
/// Remove the entry from the map.
///
/// All values associated with the entry are removed and the first one is
/// returned. See `remove_entry_mult` for an API that returns all values.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "world".parse().unwrap());
///
/// if let Entry::Occupied(e) = map.entry("host").unwrap() {
/// let mut prev = e.remove();
/// assert_eq!("world", prev);
/// }
///
/// assert!(!map.contains_key("host"));
/// ```
pub fn remove(self) -> T {
self.remove_entry().1
}
/// Remove the entry from the map.
///
/// The key and all values associated with the entry are removed and the
/// first one is returned. See `remove_entry_mult` for an API that returns
/// all values.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "world".parse().unwrap());
///
/// if let Entry::Occupied(e) = map.entry("host").unwrap() {
/// let (key, mut prev) = e.remove_entry();
/// assert_eq!("host", key.as_str());
/// assert_eq!("world", prev);
/// }
///
/// assert!(!map.contains_key("host"));
/// ```
pub fn remove_entry(self) -> (HeaderName, T) {
let entry = self.map.remove_found(self.probe, self.index);
if let Some(links) = entry.links {
self.map.remove_all_extra_values(links.next);
}
(entry.key, entry.value)
}
/// Remove the entry from the map.
///
/// The key and all values associated with the entry are removed and
/// returned.
pub fn remove_entry_mult(self) -> (HeaderName, ValueDrain<'a, T>) {
let entry = self.map.remove_found(self.probe, self.index);
let drain = ValueDrain {
map: self.map as *mut _,
first: Some(entry.value),
next: entry.links.map(|l| l.next),
lt: PhantomData,
};
(entry.key, drain)
}
/// Returns an iterator visiting all values associated with the entry.
///
/// Values are iterated in insertion order.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::new();
/// map.insert(HOST, "world".parse().unwrap());
/// map.append(HOST, "earth".parse().unwrap());
///
/// if let Entry::Occupied(e) = map.entry("host").unwrap() {
/// let mut iter = e.iter();
/// assert_eq!(&"world", iter.next().unwrap());
/// assert_eq!(&"earth", iter.next().unwrap());
/// assert!(iter.next().is_none());
/// }
/// ```
pub fn iter(&self) -> ValueIter<T> {
self.map.value_iter(Some(self.index))
}
/// Returns an iterator mutably visiting all values associated with the
/// entry.
///
/// Values are iterated in insertion order.
///
/// # Examples
///
/// ```
/// # use http::header::{HeaderMap, Entry, HOST};
/// let mut map = HeaderMap::default();
/// map.insert(HOST, "world".to_string());
/// map.append(HOST, "earth".to_string());
///
/// if let Entry::Occupied(mut e) = map.entry("host").unwrap() {
/// for e in e.iter_mut() {
/// e.push_str("-boop");
/// }
/// }
///
/// let mut values = map.get_all("host");
/// let mut i = values.iter();
/// assert_eq!(&"world-boop", i.next().unwrap());
/// assert_eq!(&"earth-boop", i.next().unwrap());
/// ```
pub fn iter_mut(&mut self) -> ValueIterMut<T> {
self.map.value_iter_mut(self.index)
}
}
impl<'a, T> IntoIterator for OccupiedEntry<'a, T> {
type Item = &'a mut T;
type IntoIter = ValueIterMut<'a, T>;
fn into_iter(self) -> ValueIterMut<'a, T> {
self.map.value_iter_mut(self.index)
}
}
impl<'a, 'b: 'a, T> IntoIterator for &'b OccupiedEntry<'a, T> {
type Item = &'a T;
type IntoIter = ValueIter<'a, T>;
fn into_iter(self) -> ValueIter<'a, T> {
self.iter()
}
}
impl<'a, 'b: 'a, T> IntoIterator for &'b mut OccupiedEntry<'a, T> {
type Item = &'a mut T;
type IntoIter = ValueIterMut<'a, T>;
fn into_iter(self) -> ValueIterMut<'a, T> {
self.iter_mut()
}
}
// ===== impl ValueDrain =====
impl<'a, T> Iterator for ValueDrain<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.first.is_some() {
self.first.take()
} else if let Some(next) = self.next {
// Remove the extra value
let extra = unsafe { &mut (*self.map) }.remove_extra_value(next);
match extra.next {
Link::Extra(idx) => self.next = Some(idx),
Link::Entry(_) => self.next = None,
}
Some(extra.value)
} else {
None
}
}
}
impl<'a, T> Drop for ValueDrain<'a, T> {
fn drop(&mut self) {
while let Some(_) = self.next() {
}
}
}
unsafe impl<'a, T: Sync> Sync for ValueDrain<'a, T> {}
unsafe impl<'a, T: Send> Send for ValueDrain<'a, T> {}
// ===== impl Pos =====
impl Pos {
#[inline]
fn new(index: usize, hash: HashValue) -> Self {
Pos {
index: index as Size,
hash: hash,
}
}
#[inline]
fn none() -> Self {
Pos {
index: !0,
hash: HashValue(0),
}
}
#[inline]
fn is_some(&self) -> bool {
!self.is_none()
}
#[inline]
fn is_none(&self) -> bool {
self.index == !0
}
#[inline]
fn resolve(&self) -> Option<(usize, HashValue)> {
if self.is_some() {
Some((self.index, self.hash))
} else {
None
}
}
}
impl Danger {
fn is_red(&self) -> bool {
match *self {
Danger::Red(_) => true,
_ => false,
}
}
fn to_red(&mut self) {
debug_assert!(self.is_yellow());
*self = Danger::Red(RandomState::new());
}
fn is_yellow(&self) -> bool {
match *self {
Danger::Yellow => true,
_ => false,
}
}
fn to_yellow(&mut self) {
match *self {
Danger::Green => {
*self = Danger::Yellow;
}
_ => {}
}
}
fn to_green(&mut self) {
debug_assert!(self.is_yellow());
*self = Danger::Green;
}
}
// ===== impl Utils =====
#[inline]
fn usable_capacity(cap: usize) -> usize {
cap - cap / 4
}
#[inline]
fn to_raw_capacity(n: usize) -> usize {
n + n / 3
}
#[inline]
fn desired_pos(mask: Size, hash: HashValue) -> usize {
(hash.0 & mask)
}
/// The number of steps that `current` is forward of the desired position for hash
#[inline]
fn probe_distance(mask: Size, hash: HashValue, current: usize) -> usize {
current.wrapping_sub(desired_pos(mask, hash)) & mask
}
fn hash_elem_using<K: ?Sized>(danger: &Danger, k: &K) -> HashValue
where K: Hash
{
use fnv::FnvHasher;
const MASK: u64 = (MAX_SIZE as u64) - 1;
let hash = match *danger {
// Safe hash
Danger::Red(ref hasher) => {
let mut h = hasher.build_hasher();
k.hash(&mut h);
h.finish()
}
// Fast hash
_ => {
let mut h = FnvHasher::default();
k.hash(&mut h);
h.finish()
}
};
HashValue((hash & MASK) as usize)
}
/*
*
* ===== impl IntoHeaderName / AsHeaderName =====
*
*/
mod into_header_name {
use super::{HdrName, HeaderMap, HeaderName};
/// A marker trait used to identify values that can be used as insert keys
/// to a `HeaderMap`.
pub trait IntoHeaderName: Sealed {}
// All methods are on this pub(super) trait, instead of `IntoHeaderName`,
// so that they aren't publicly exposed to the world.
//
// Being on the `IntoHeaderName` trait would mean users could call
// `"host".insert(&mut map, "localhost")`.
//
// Ultimately, this allows us to adjust the signatures of these methods
// without breaking any external crate.
pub trait Sealed {
#[doc(hidden)]
fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T>;
#[doc(hidden)]
fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool;
}
// ==== impls ====
impl Sealed for HeaderName {
#[doc(hidden)]
#[inline]
fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T> {
map.insert2(self, val)
}
#[doc(hidden)]
#[inline]
fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool {
map.append2(self, val)
}
}
impl IntoHeaderName for HeaderName {}
impl<'a> Sealed for &'a HeaderName {
#[doc(hidden)]
#[inline]
fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T> {
map.insert2(self, val)
}
#[doc(hidden)]
#[inline]
fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool {
map.append2(self, val)
}
}
impl<'a> IntoHeaderName for &'a HeaderName {}
impl Sealed for &'static str {
#[doc(hidden)]
#[inline]
fn insert<T>(self, map: &mut HeaderMap<T>, val: T) -> Option<T> {
HdrName::from_static(self, move |hdr| map.insert2(hdr, val))
}
#[doc(hidden)]
#[inline]
fn append<T>(self, map: &mut HeaderMap<T>, val: T) -> bool {
HdrName::from_static(self, move |hdr| map.append2(hdr, val))
}
}
impl IntoHeaderName for &'static str {}
}
mod as_header_name {
use std::prelude::v1::*;
use super::{Entry, HdrName, HeaderMap, HeaderName, InvalidHeaderName};
/// A marker trait used to identify values that can be used as search keys
/// to a `HeaderMap`.
pub trait AsHeaderName: Sealed {}
// All methods are on this pub(super) trait, instead of `AsHeaderName`,
// so that they aren't publicly exposed to the world.
//
// Being on the `AsHeaderName` trait would mean users could call
// `"host".find(&map)`.
//
// Ultimately, this allows us to adjust the signatures of these methods
// without breaking any external crate.
pub trait Sealed {
#[doc(hidden)]
fn entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<T>, InvalidHeaderName>;
#[doc(hidden)]
fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)>;
}
// ==== impls ====
impl Sealed for HeaderName {
#[doc(hidden)]
#[inline]
fn entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<T>, InvalidHeaderName> {
Ok(map.entry2(self))
}
#[doc(hidden)]
#[inline]
fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
map.find(self)
}
}
impl AsHeaderName for HeaderName {}
impl<'a> Sealed for &'a HeaderName {
#[doc(hidden)]
#[inline]
fn entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<T>, InvalidHeaderName> {
Ok(map.entry2(self))
}
#[doc(hidden)]
#[inline]
fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
map.find(*self)
}
}
impl<'a> AsHeaderName for &'a HeaderName {}
impl<'a> Sealed for &'a str {
#[doc(hidden)]
#[inline]
fn entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<T>, InvalidHeaderName> {
HdrName::from_bytes(self.as_bytes(), move |hdr| map.entry2(hdr))
}
#[doc(hidden)]
#[inline]
fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
HdrName::from_bytes(self.as_bytes(), move |hdr| map.find(&hdr)).unwrap_or(None)
}
}
impl<'a> AsHeaderName for &'a str {}
impl Sealed for String {
#[doc(hidden)]
#[inline]
fn entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<T>, InvalidHeaderName> {
self.as_str().entry(map)
}
#[doc(hidden)]
#[inline]
fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
Sealed::find(&self.as_str(), map)
}
}
impl AsHeaderName for String {}
impl<'a> Sealed for &'a String {
#[doc(hidden)]
#[inline]
fn entry<T>(self, map: &mut HeaderMap<T>) -> Result<Entry<T>, InvalidHeaderName> {
self.as_str().entry(map)
}
#[doc(hidden)]
#[inline]
fn find<T>(&self, map: &HeaderMap<T>) -> Option<(usize, usize)> {
Sealed::find(*self, map)
}
}
impl<'a> AsHeaderName for &'a String {}
}
#[test]
fn test_bounds() {
fn check_bounds<T: Send + Send>() {}
check_bounds::<HeaderMap<()>>();
check_bounds::<Iter<'static, ()>>();
check_bounds::<IterMut<'static, ()>>();
check_bounds::<Keys<'static, ()>>();
check_bounds::<Values<'static, ()>>();
check_bounds::<ValuesMut<'static, ()>>();
check_bounds::<Drain<'static, ()>>();
check_bounds::<GetAll<'static, ()>>();
check_bounds::<Entry<'static, ()>>();
check_bounds::<VacantEntry<'static, ()>>();
check_bounds::<OccupiedEntry<'static, ()>>();
check_bounds::<ValueIter<'static, ()>>();
check_bounds::<ValueIterMut<'static, ()>>();
check_bounds::<ValueDrain<'static, ()>>();
}
#[test]
fn skip_duplicates_during_key_iteration() {
let mut map = HeaderMap::new();
map.append("a", HeaderValue::from_static("a"));
map.append("a", HeaderValue::from_static("b"));
assert_eq!(map.keys().count(), map.keys_len());
}