xref: /aosp_15_r20/external/rust/android-crates-io/crates/weak-table/src/weak_key_hash_map.rs

//! A hash map where the keys are held by weak pointers and compared by key value.

use super::*;
use super::size_policy::*;
use super::traits::*;
use super::util::*;

pub use super::WeakKeyHashMap;

/// Represents an entry in the table which may be occupied or vacant.
pub enum Entry<'a, K: 'a + WeakKey, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>),
}

/// An occupied entry, which can be removed or viewed.
pub struct OccupiedEntry<'a, K: 'a + WeakKey, V: 'a>(InnerEntry<'a, K, V>);

/// A vacant entry, which can be inserted in or viewed.
pub struct VacantEntry<'a, K: 'a + WeakKey, V: 'a>(InnerEntry<'a, K, V>);

struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> {
    map:        &'a mut WeakKeyInnerMap<K, V>,
    pos:        usize,
    key:        K::Strong,
    hash_code:  HashCode,
}

/// An iterator over the keys and values of the weak hash map.
#[derive(Clone, Debug)]
pub struct Iter<'a, K: 'a, V: 'a> {
    base: slice::Iter<'a, Bucket<K, V>>,
    size: usize,
}

impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> {
    type Item = (K::Strong, &'a V);

    fn next(&mut self) -> Option<Self::Item> {
        for bucket in &mut self.base {
            if let Some((ref weak_ptr, ref value, _)) = *bucket {
                self.size -= 1;
                if let Some(strong_ptr) = weak_ptr.view() {
                    return Some((strong_ptr, value));
                }
            }
        }

        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.size))
    }
}

#[derive(Debug)]
/// An iterator over the keys and mutable values of the weak hash map.
pub struct IterMut<'a, K: 'a, V: 'a> {
    base: slice::IterMut<'a, Bucket<K, V>>,
    size: usize,
}

impl<'a, K: WeakElement, V> Iterator for IterMut<'a, K, V> {
    type Item = (K::Strong, &'a mut V);

    fn next(&mut self) -> Option<Self::Item> {
        for bucket in &mut self.base {
            if let Some((ref weak_ptr, ref mut value, _)) = *bucket {
                self.size -= 1;
                if let Some(strong_ptr) = weak_ptr.view() {
                    return Some((strong_ptr, value));
                }
            }
        }

        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.size))
    }
}

/// An iterator over the keys of the weak hash map.
#[derive(Clone, Debug)]
pub struct Keys<'a, K: 'a, V: 'a>(Iter<'a, K, V>);

impl<'a, K: WeakElement, V> Iterator for Keys<'a, K, V> {
    type Item = K::Strong;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(k, _)| k)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}

/// An iterator over the values of the weak hash map.
#[derive(Clone, Debug)]
pub struct Values<'a, K: 'a, V: 'a>(Iter<'a, K, V>);

impl<'a, K: WeakElement, V> Iterator for Values<'a, K, V> {
    type Item = &'a V;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(_, v)| v)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}

#[derive(Debug)]
/// An iterator over the mutable values of the weak hash map.
pub struct ValuesMut<'a, K: 'a, V: 'a>(IterMut<'a, K, V>);

impl<'a, K: WeakElement, V> Iterator for ValuesMut<'a, K, V> {
    type Item = &'a mut V;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(_, v)| v)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}

#[derive(Debug)]
/// An iterator that consumes the values of a weak hash map, leaving it empty.
pub struct Drain<'a, K: 'a, V: 'a> {
    base: slice::IterMut<'a, Bucket<K, V>>,
    size: usize,
}

impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> {
    type Item = (K::Strong, V);

    fn next(&mut self) -> Option<Self::Item> {
        for bucket in &mut self.base {
            if let Some((weak_ptr, value, _)) = bucket.take() {
                self.size -= 1;
                if let Some(strong_ptr) = weak_ptr.view() {
                    return Some((strong_ptr, value));
                }
            }
        }

        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.size))
    }
}

impl<'a, K, V> Drop for Drain<'a, K, V> {
    fn drop(&mut self) {
        for option in &mut self.base {
            *option = None;
        }
    }
}

/// An iterator that consumes the values of a weak hash map, leaving it empty.
pub struct IntoIter<K, V> {
    base: vec::IntoIter<Bucket<K, V>>,
    size: usize,
}

impl<K: WeakElement, V> Iterator for IntoIter<K, V> {
    type Item = (K::Strong, V);

    fn next(&mut self) -> Option<Self::Item> {
        for (weak_ptr, value, _) in (&mut self.base).flatten() {
            self.size -= 1;
            if let Some(strong_ptr) = weak_ptr.view() {
                return Some((strong_ptr, value));
            }
        }

        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.size))
    }
}

impl<K: WeakKey, V> WeakKeyHashMap<K, V, RandomState>
{
    /// Creates an empty `WeakKeyHashMap`.
    ///
    /// *O*(1) time
    pub fn new() -> Self {
        Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
    }

    /// Creates an empty `WeakKeyHashMap` with the given capacity.
    ///
    /// *O*(*n*) time
    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_capacity_and_hasher(capacity, Default::default())
    }
}

impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
{
    /// Creates an empty `WeakKeyHashMap` with the given capacity and hasher.
    ///
    /// *O*(*n*) time
    pub fn with_hasher(hash_builder: S) -> Self {
        Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder)
    }

    /// Creates an empty `WeakKeyHashMap` with the given capacity and hasher.
    ///
    /// *O*(*n*) time
    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
        WeakKeyHashMap {
            hash_builder,
            inner: WeakKeyInnerMap {
                buckets: new_boxed_option_slice(capacity),
                len: 0,
            }
        }
    }

    /// Returns a reference to the map's `BuildHasher`.
    ///
    /// *O*(1) time
    pub fn hasher(&self) -> &S {
        &self.hash_builder
    }

    /// Returns the number of elements the map can hold without reallocating.
    ///
    /// *O*(1) time
    pub fn capacity(&self) -> usize {
        self.inner.capacity()
    }

    /// This has some preconditions.
    fn resize(&mut self, capacity: usize) {
        let old_buckets = mem::replace(&mut self.inner.buckets,
                                       new_boxed_option_slice(capacity));

        let iter = IntoIter {
            base: old_buckets.into_vec().into_iter(),
            size: self.inner.len,
        };

        self.inner.len = 0;

        for (key, value) in iter {
            self.entry_no_grow(key).or_insert(value);
        }
    }

    /// Removes all mappings whose keys have expired.
    ///
    /// *O*(*n*) time
    pub fn remove_expired(&mut self) {
        self.retain(|_, _| true)
    }

    /// Reserves room for additional elements.
    ///
    /// *O*(*n*) time
    pub fn reserve(&mut self, additional_capacity: usize) {
        let new_capacity = additional_capacity + self.capacity();
        self.resize(new_capacity);
    }

    /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
    ///
    /// *O*(*n*) time
    pub fn shrink_to_fit(&mut self) {
        self.remove_expired();
        let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
        self.resize(new_capacity);
    }

    /// Returns an over-approximation of the number of elements.
    ///
    /// *O*(1) time
    pub fn len(&self) -> usize {
        self.inner.len
    }

    /// Is the map empty?
    ///
    /// Note that this may return false even if all keys in the map have
    /// expired, if they haven't been collected yet.
    ///
    /// *O*(1) time
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// The proportion of buckets that are used.
    ///
    /// This is an over-approximation because of expired keys.
    ///
    /// *O*(1) time
    pub fn load_factor(&self) -> f32 {
        (self.len() as f32 + 1.0) / self.capacity() as f32
    }

    fn maybe_adjust_size(&mut self) {
        if self.load_factor() > COLLECT_LOAD_FACTOR {
            self.remove_expired();

            let load_factor = self.load_factor();
            let capacity = self.capacity();
            if load_factor > GROW_LOAD_FACTOR {
                self.resize(max(1, capacity * 2));
            } else if load_factor < SHRINK_LOAD_FACTOR && capacity > DEFAULT_INITIAL_CAPACITY {
                self.resize(max(1, capacity / 2));
            }
        }
    }

    /// Gets the requested entry.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn entry(&mut self, key: K::Strong) -> Entry<K, V> {
        self.maybe_adjust_size();
        self.entry_no_grow(key)
    }

    fn entry_no_grow(&mut self, key: K::Strong) -> Entry<K, V> {
        let mut inner = {
            let hash_code = self.hash(&key, K::hash);
            InnerEntry {
                pos:        self.which_bucket(hash_code),
                map:        &mut self.inner,
                hash_code,
                key,
            }
        };

        for dist in 0 .. inner.capacity() {
            match inner.bucket_status() {
                BucketStatus::Unoccupied =>
                    return Entry::Vacant(VacantEntry(inner)),
                BucketStatus::MatchesKey =>
                    return Entry::Occupied(OccupiedEntry(inner)),
                BucketStatus::ProbeDistance(bucket_distance) => {
                    if bucket_distance < dist {
                        return Entry::Vacant(VacantEntry(inner))
                    } else {
                        inner.pos = inner.next_bucket(inner.pos);
                    }
                }
            }
        }

        panic!("WeakKeyHashTable::entry: out of space");
    }

    /// Removes all associations from the map.
    ///
    /// *O*(*n*) time
    pub fn clear(&mut self) {
        self.drain();
    }

    fn find_bucket<Q>(&self, key: &Q) -> Option<(usize, K::Strong, HashCode)>
        where Q: ?Sized + Hash + Eq,
              K::Key: Borrow<Q>
    {
        if self.capacity() == 0 { return None; }

        let hash_code = self.hash(key, Q::hash);
        let mut pos = self.which_bucket(hash_code);

        for dist in 0 .. self.capacity() {
            if let Some((ref weak_key, _, bucket_hash_code)) = self.inner.buckets[pos] {
                if bucket_hash_code == hash_code {
                    if let Some(bucket_key) = weak_key.view() {
                        if K::equals(&bucket_key, key) {
                            return Some((pos, bucket_key, bucket_hash_code));
                        }
                    }
                }

                let bucket_dist =
                    self.probe_distance(pos, self.which_bucket(bucket_hash_code));
                if bucket_dist < dist {
                    return None;
                }
            } else {
                return None;
            }

            pos = self.next_bucket(pos);
        }

        None
    }

    /// Returns a reference to the value corresponding to the key.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
        where Q: ?Sized + Hash + Eq,
              K::Key: Borrow<Q>
    {
        self.find_bucket(key).and_then(move |tup|
            self.inner.buckets[tup.0].as_ref().map(|bucket| &bucket.1))
    }

    /// Returns true if the map contains the specified key.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn contains_key<Q>(&self, key: &Q) -> bool
        where Q: ?Sized + Hash + Eq,
              K::Key: Borrow<Q>
    {
        self.find_bucket(key).is_some()
    }

    /// Returns a strong reference to the key, if found.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
        where Q: ?Sized + Hash + Eq,
              K::Key: Borrow<Q>
    {
        self.find_bucket(key).map(|tup| tup.1)
    }

    /// Returns a pair of a strong reference to the key, and a reference to the value, if present.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, &V)>
        where Q: ?Sized + Hash + Eq,
              K::Key: Borrow<Q>
    {
        self.find_bucket(key).and_then(move |tup|
            self.inner.buckets[tup.0].as_ref().map(|bucket| (tup.1, &bucket.1)))
    }

    /// Returns a mutable reference to the value corresponding to the key.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
        where Q: ?Sized + Hash + Eq,
              K::Key: Borrow<Q>
    {
        self.find_bucket(key).and_then(move |tup|
            self.inner.buckets[tup.0].as_mut().map(|bucket| &mut bucket.1))
    }

    /// Returns a pair of a strong reference to the key, and a mutable reference to the value,
    /// if present.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn get_both_mut<Q>(&mut self, key: &Q) -> Option<(K::Strong, &mut V)>
        where Q: ?Sized + Hash + Eq,
              K::Key: Borrow<Q>
    {
        self.find_bucket(key).and_then(move |tup|
            self.inner.buckets[tup.0].as_mut().map(|bucket| (tup.1, &mut bucket.1)))
    }

    /// Unconditionally inserts the value, returning the old value if already present.
    ///
    /// Unlike `std::collections::HashMap`, this replaced the key even if occupied.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> {
        match self.entry(key) {
            Entry::Occupied(mut occupied) => {
                Some(occupied.insert(value))
            },
            Entry::Vacant(vacant) => {
                vacant.insert(value);
                None
            }
        }
    }

    /// Removes the entry with the given key, if it exists, and returns the value.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
        where Q: ?Sized + Hash + Eq,
              K::Key: Borrow<Q>
    {
        self.find_bucket(key).map(|(pos, strong_key, hash_code)| {
            OccupiedEntry(InnerEntry {
                map:        &mut self.inner,
                pos,
                key:        strong_key,
                hash_code,
            }).remove()
        })
    }

    /// Removes all mappings not satisfying the given predicate.
    ///
    /// Also removes any expired mappings.
    ///
    /// *O*(*n*) time
    pub fn retain<F>(&mut self, mut f: F)
        where F: FnMut(K::Strong, &mut V) -> bool
    {
        for i in 0 .. self.capacity() {
            let remove = match self.inner.buckets[i] {
                None => false,
                Some(ref mut bucket) =>
                    match bucket.0.view() {
                        None => true,
                        Some(key) => !f(key, &mut bucket.1),
                    }
            };

            if remove {
                self.inner.remove_index(i);
            }
        }
    }

    /// Is this map a submap of the other under the given value comparison `cmp`?
    ///
    /// In particular, for every key `k` of `self`,
    ///
    ///  - `k` must also be a key of `other` and
    ///  - `cmp(self[k], other[k])` must hold.
    ///
    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
    /// `self.capacity()` and *q* is the length of the probe sequences
    /// in `other`)
    pub fn is_submap_with<F, S1, V1>(&self, other: &WeakKeyHashMap<K, V1, S1>,
                                     mut cmp: F) -> bool
        where F: FnMut(&V, &V1) -> bool,
              S1: BuildHasher
    {
        for (key, value1) in self {
            if let Some(value2) = K::with_key(&key, |k| other.get(k)) {
                if !cmp(value1, value2) {
                    return false;
                }
            } else {
                return false;
            }
        }

        true
    }

    /// Is `self` a submap of `other`?
    ///
    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
    /// `self.capacity()` and *q* is the length of the probe sequences
    /// in `other`)
    pub fn is_submap<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
        where V: PartialEq<V1>,
              S1: BuildHasher
    {
        self.is_submap_with(other, PartialEq::eq)
    }

    /// Are the keys of `self` a subset of the keys of `other`?
    ///
    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
    /// `self.capacity()` and *q* is the length of the probe sequences
    /// in `other`)
    pub fn domain_is_subset<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
        where S1: BuildHasher
    {
        self.is_submap_with(other, |_, _| true)
    }

    fn hash<Q, H>(&self, key: Q, hash: H) -> HashCode
        where H: FnOnce(Q, &mut S::Hasher)
    {
        let hasher = &mut self.hash_builder.build_hasher();
        hash(key, hasher);
        HashCode(hasher.finish())
    }
}

impl<K, V, V1, S, S1> PartialEq<WeakKeyHashMap<K, V1, S1>> for WeakKeyHashMap<K, V, S>
    where K: WeakKey,
          V: PartialEq<V1>,
          S: BuildHasher,
          S1: BuildHasher
{
    fn eq(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool {
        self.is_submap(other) && other.domain_is_subset(self)
    }
}

impl<K: WeakKey, V: Eq, S: BuildHasher> Eq for WeakKeyHashMap<K, V, S> { }

impl<K: WeakKey, V, S: BuildHasher + Default> Default for WeakKeyHashMap<K, V, S> {
    fn default() -> Self {
        WeakKeyHashMap::with_hasher(Default::default())
    }
}

impl<'a, K, V, S, Q> ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
    where K: WeakKey,
          K::Key: Borrow<Q>,
          S: BuildHasher,
          Q: ?Sized + Eq + Hash
{
    type Output = V;

    fn index(&self, index: &'a Q) -> &Self::Output {
        self.get(index).expect("Index::index: key not found")
    }
}

impl<'a, K, V, S, Q> ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
    where K: WeakKey,
          K::Key: Borrow<Q>,
          S: BuildHasher,
          Q: ?Sized + Eq + Hash
{
    fn index_mut(&mut self, index: &'a Q) -> &mut Self::Output {
        self.get_mut(index).expect("IndexMut::index_mut: key not found")
    }
}

impl<K, V, S> iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
    where K: WeakKey,
          S: BuildHasher + Default
{
    fn from_iter<T: IntoIterator<Item=(K::Strong, V)>>(iter: T) -> Self {
        let mut result = WeakKeyHashMap::with_hasher(Default::default());
        result.extend(iter);
        result
    }
}

impl<K, V, S> iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
    where K: WeakKey,
          S: BuildHasher
{
    fn extend<T: IntoIterator<Item=(K::Strong, V)>>(&mut self, iter: T) {
        for (key, value) in iter {
            self.insert(key, value);
        }
    }
}

impl<'a, K, V, S> iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S>
    where K: 'a + WeakKey,
          K::Strong: Clone,
          V: 'a + Clone,
          S: BuildHasher
{
    fn extend<T: IntoIterator<Item=(&'a K::Strong, &'a V)>>(&mut self, iter: T) {
        for (key, value) in iter {
            self.insert(key.clone(), value.clone());
        }
    }
}

enum BucketStatus {
    Unoccupied,
    MatchesKey,
    ProbeDistance(usize),
}

impl<'a, K: WeakKey, V> InnerEntry<'a, K, V> {
    // Gets the status of the current bucket.
    fn bucket_status(&self) -> BucketStatus {
        match &self.map.buckets[self.pos] {
            Some(bucket) => {
                if bucket.2 == self.hash_code {
                    if let Some(key) = bucket.0.view() {
                        if K::with_key(&self.key, |k| K::equals(&key, k)) {
                            return BucketStatus::MatchesKey;
                        }
                    }
                }

                let dist = self.probe_distance(self.pos,
                                               self.which_bucket(bucket.2));
                BucketStatus::ProbeDistance(dist)
            },
            None => BucketStatus::Unoccupied,
        }
    }
}

impl<'a, K: WeakKey, V> Entry<'a, K, V> {
    /// Ensures a value is in the entry by inserting a default value
    /// if empty, and returns a mutable reference to the value in the
    /// entry.
    ///
    /// *O*(1) time
    pub fn or_insert(self, default: V) -> &'a mut V {
        self.or_insert_with(|| default)
    }

    /// Ensures a value is in the entry by inserting the result of the
    /// default function if empty, and returns a mutable reference to
    /// the value in the entry.
    ///
    /// *O*(1) time
    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
        match self {
            Entry::Occupied(occupied) => occupied.into_mut(),
            Entry::Vacant(vacant) => vacant.insert(default()),
        }
    }

    /// Returns a reference to this entry's key.
    ///
    /// *O*(1) time
    pub fn key(&self) -> &K::Strong {
        match *self {
            Entry::Occupied(ref occupied) => occupied.key(),
            Entry::Vacant(ref vacant) => vacant.key(),
        }
    }
}

impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> {
    /// Gets a reference to the key held by the entry.
    ///
    /// *O*(1) time
    pub fn key(&self) -> &K::Strong {
        &self.0.key
    }

    /// Takes ownership of the key and value from the map.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn remove_entry(self) -> (K::Strong, V) {
        let (_, value, _) = self.0.map.buckets[self.0.pos].take().unwrap();
        self.0.map.remove_index(self.0.pos);
        (self.0.key, value)
    }

    /// Gets a reference to the value in the entry.
    ///
    /// *O*(1) time
    pub fn get(&self) -> &V {
        &self.0.map.buckets[self.0.pos].as_ref().unwrap().1
    }

    /// Gets a mutable reference to the value in the entry.
    ///
    /// *O*(1) time
    pub fn get_mut(&mut self) -> &mut V {
        &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
    }

    /// Turns the entry into a mutable reference to the value borrowed from the map.
    ///
    /// *O*(1) time
    pub fn into_mut(self) -> &'a mut V {
        &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
    }

    /// Replaces the value in the entry with the given value.
    ///
    /// *O*(1) time
    pub fn insert(&mut self, mut value: V) -> V {
        self.0.map.buckets[self.0.pos].as_mut().unwrap().0 = K::new(&self.0.key);
        mem::swap(self.get_mut(), &mut value);
        value
    }

    /// Removes the entry, returning the value.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn remove(self) -> V {
        self.remove_entry().1
    }
}

impl<'a, K: WeakKey, V> VacantEntry<'a, K, V> {
    /// Gets a reference to the key that would be used when inserting a
    /// value through the `VacantEntry`.
    ///
    /// *O*(1) time
    pub fn key(&self) -> &K::Strong {
        &self.0.key
    }

    /// Returns ownership of the key.
    ///
    /// *O*(1) time
    pub fn into_key(self) -> K::Strong {
        self.0.key
    }

    /// Inserts the key and value into the map and return a mutable
    /// reference to the value.
    ///
    /// expected *O*(1) time; worst-case *O*(*p*) time
    pub fn insert(self, value: V) -> &'a mut V {
        let old_bucket = mem::replace(
            &mut self.0.map.buckets[self.0.pos],
            Some((K::new(&self.0.key), value, self.0.hash_code)));

        if let Some(full_bucket) = old_bucket {
            let next_bucket = self.next_bucket(self.0.pos);
            self.0.map.steal(next_bucket, full_bucket);
        }

        self.0.map.len += 1;

        &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
    }
}

impl<K: WeakKey, V> WeakKeyInnerMap<K, V> {
    // Steals buckets starting at `pos`, replacing them with `bucket`.
    fn steal(&mut self, mut pos: usize, mut bucket: FullBucket<K, V>) {
        let mut my_dist = self.probe_distance(pos, self.which_bucket(bucket.2));

        while let Some(hash_code) = self.buckets[pos].as_ref().and_then(
            |bucket| if bucket.0.is_expired() {None} else {Some(bucket.2)}) {

            let victim_dist = self.probe_distance(pos, self.which_bucket(hash_code));

            if my_dist > victim_dist {
                mem::swap(self.buckets[pos].as_mut().unwrap(), &mut bucket);
                my_dist = victim_dist;
            }

            pos = self.next_bucket(pos);
            my_dist += 1;
        }

        self.buckets[pos] = Some(bucket);
    }

    /// Removes the element at `dst`, shifting if necessary to preserve invariants.
    fn remove_index(&mut self, mut dst: usize) {
        let mut src = self.next_bucket(dst);

        // We are going to remove the buckets in the range [dst, src)

        loop {
            let hash_code_option = self.buckets[src].as_ref().map(|tup| tup.2);

            if let Some(hash_code) = hash_code_option {
                let goal_pos = self.which_bucket(hash_code);
                let dist = self.probe_distance(src, goal_pos);
                if dist == 0 { break; }

                if !self.buckets[src].as_ref().unwrap().0.is_expired() {
                    if in_interval(dst, goal_pos, src) {
                        self.erase_range(dst, goal_pos);
                        self.buckets[goal_pos] = self.buckets[src].take();
                        dst = self.next_bucket(goal_pos);
                    } else {
                        self.buckets[dst] = self.buckets[src].take();
                        dst = self.next_bucket(dst);
                    }
                }
            } else {
                break;
            }

            src = self.next_bucket(src);
        }

        self.erase_range(dst, src);
    }

    /// Erases the (presumably expired, but not empty) elements in [start, limit).
    fn erase_range(&mut self, mut start: usize, limit: usize)
    {
        while start != limit {
            self.buckets[start] = None;
            self.len -= 1;
            start = self.next_bucket(start);
        }
    }
}

// Is value in [start, limit) modulo capacity?
fn in_interval(start: usize, value: usize, limit: usize) -> bool
{
    if start <= limit {
        start <= value && value < limit
    } else {
        start <= value || value < limit
    }
}

// Helper trait for computing with indices modulo capacity.
trait ModuloCapacity {
    fn capacity(&self) -> usize;

    fn probe_distance(&self, actual: usize, ideal: usize) -> usize {
        if actual >= ideal {
            actual - ideal
        } else {
            actual + self.capacity() - ideal
        }
    }

    fn next_bucket(&self, pos: usize) -> usize {
        assert_ne!( self.capacity(), 0 );
        (pos + 1) % self.capacity()
    }

    fn which_bucket(&self, hash_code: HashCode) -> usize {
        assert_ne!( self.capacity(), 0 );
        (hash_code.0 as usize) % self.capacity()
    }
}

impl<K, V> ModuloCapacity for WeakKeyInnerMap<K, V> {
    fn capacity(&self) -> usize {
        self.buckets.len()
    }
}

impl<K, V, S> ModuloCapacity for WeakKeyHashMap<K, V, S> {
    fn capacity(&self) -> usize {
        self.inner.capacity()
    }
}

impl<'a, K: WeakKey, V> ModuloCapacity for InnerEntry<'a, K, V> {
    fn capacity(&self) -> usize {
        self.map.capacity()
    }
}

impl<'a, K: WeakKey, V> ModuloCapacity for OccupiedEntry<'a, K, V> {
    fn capacity(&self) -> usize {
        self.0.capacity()
    }
}

impl<'a, K: WeakKey, V> ModuloCapacity for VacantEntry<'a, K, V> {
    fn capacity(&self) -> usize {
        self.0.capacity()
    }
}

impl<K, V> Debug for WeakKeyInnerMap<K, V>
    where K: WeakElement,
          K::Strong: Debug,
          V: Debug
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "{{ ")?;
        for (i, bucket) in self.buckets.iter().enumerate() {
            if let Some((ref k, ref v, _)) = *bucket {
                write!(f, "[{}] {:?} => {:?}, ", i, k.view(), *v)?;
            }
        }
        write!(f, "}}")
    }
}

impl<K: WeakElement, V: Debug, S> Debug for WeakKeyHashMap<K, V, S>
    where K::Strong: Debug
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        self.inner.fmt(f)
    }
}

impl<'a, K: WeakKey, V: Debug> Debug for Entry<'a, K, V>
    where K::Strong: Debug
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        match *self {
            Entry::Occupied(ref e)  => e.fmt(f),
            Entry::Vacant(ref e)    => e.fmt(f),
        }
    }
}

impl<'a, K: WeakKey, V: Debug> Debug for OccupiedEntry<'a, K, V>
    where K::Strong: Debug
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        self.0.fmt(f)
    }
}

impl<'a, K: WeakKey, V: Debug> Debug for VacantEntry<'a, K, V>
    where K::Strong: Debug
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        self.0.fmt(f)
    }
}

impl<'a, K: WeakKey, V: Debug> Debug for InnerEntry<'a, K, V>
    where K::Strong: Debug
{
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "InnerEntry {{ pos = {}, buckets = {:?} }}", self.pos, self.map)
    }
}

impl<K: WeakElement, V, S> IntoIterator for WeakKeyHashMap<K, V, S> {
    type Item = (K::Strong, V);
    type IntoIter = IntoIter<K, V>;

    /// Creates an owning iterator from `self`.
    ///
    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            size: self.inner.len,
            base: self.inner.buckets.into_vec().into_iter(),
        }
    }
}

impl<'a, K: WeakElement, V, S> IntoIterator for &'a WeakKeyHashMap<K, V, S> {
    type Item = (K::Strong, &'a V);
    type IntoIter = Iter<'a, K, V>;

    /// Creates a borrowing iterator from `self`.
    ///
    /// *O*(1) time
    fn into_iter(self) -> Self::IntoIter {
        Iter {
            base: self.inner.buckets.iter(),
            size: self.inner.len,
        }
    }
}

impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut WeakKeyHashMap<K, V, S> {
    type Item = (K::Strong, &'a mut V);
    type IntoIter = IterMut<'a, K, V>;

    /// Creates a borrowing iterator from `self`.
    ///
    /// *O*(1) time
    fn into_iter(self) -> Self::IntoIter {
        IterMut {
            base: self.inner.buckets.iter_mut(),
            size: self.inner.len,
        }
    }
}

impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> {
    /// Gets an iterator over the keys and values.
    ///
    /// *O*(1) time
    pub fn iter(&self) -> Iter<K, V> {
        self.into_iter()
    }

    /// Gets an iterator over the keys.
    ///
    /// *O*(1) time
    pub fn keys(&self) -> Keys<K, V> {
        Keys(self.iter())
    }

    /// Gets an iterator over the values.
    ///
    /// *O*(1) time
    pub fn values(&self) -> Values<K, V> {
        Values(self.iter())
    }

    /// Gets an iterator over the keys and mutable values.
    ///
    /// *O*(1) time
    pub fn iter_mut(&mut self) -> IterMut<K, V> {
        self.into_iter()
    }

    /// Gets an iterator over the mutable values.
    ///
    /// *O*(1) time
    pub fn values_mut(&mut self) -> ValuesMut<K, V> {
        ValuesMut(self.iter_mut())
    }

    /// Gets a draining iterator, which removes all the values but retains the storage.
    ///
    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
    pub fn drain(&mut self) -> Drain<K, V> {
        let old_len = self.inner.len;
        self.inner.len = 0;
        Drain {
            base: self.inner.buckets.iter_mut(),
            size: old_len,
        }
    }
}

#[cfg(test)]
mod test {
    use crate::compat::{
        eprintln,
        rc::{Rc, Weak},
        String,
        Vec,
    };
    use super::{Entry, WeakKeyHashMap};

    #[test]
    fn simple() {
        let mut map: WeakKeyHashMap<Weak<str>, usize> = WeakKeyHashMap::new();
        assert_eq!( map.len(), 0 );
        assert!( !map.contains_key("five") );

        let five: Rc<str> = Rc::from(String::from("five"));
        map.insert(five.clone(), 5);

        assert_eq!( map.len(), 1 );
        assert!( map.contains_key("five") );

        drop(five);

        assert_eq!( map.len(), 1 );
        assert!( !map.contains_key("five") );

        map.remove_expired();

        assert_eq!( map.len(), 0 );
        assert!( !map.contains_key("five") );
    }

    // From https://github.com/tov/weak-table-rs/issues/1#issuecomment-461858060
    #[test]
    fn insert_and_check() {
        let mut rcs: Vec<Rc<u32>> = Vec::new();

        for i in 0 .. 50 {
            rcs.push(Rc::new(i));
        }

        let mut weakmap: WeakKeyHashMap<Weak<u32>, f32> = WeakKeyHashMap::new();

        for key in rcs.iter().cloned() {
            let f = *key as f32 + 0.1;
            weakmap.insert(key, f);
        }

        let mut count = 0;

        for key in &rcs {
            assert_eq!(weakmap.get(key), Some(&(**key as f32 + 0.1)));

            match weakmap.entry(Rc::clone(key)) {
                Entry::Occupied(_) => count += 1,
                Entry::Vacant(_) => eprintln!("WeakKeyHashMap: missing: {}", *key),
            }
        }

        assert_eq!( count, rcs.len() );
    }
}