diff options
author | Joel Galenson <jgalenson@google.com> | 2020-10-13 15:50:29 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2020-10-13 15:50:29 +0000 |
commit | 27726a296acb1e4f7d38a4a939b03997a5f2ab32 (patch) | |
tree | 90cfb9e167dedd07055cec8c34b2f3995528c7d1 | |
parent | 3e2f28bf21e1d4d6c2c8e8dfcae2bed801271a47 (diff) | |
parent | a8c6c18ef6e266ca8ed4b92c84289f5d0b176704 (diff) | |
download | weak-table-27726a296acb1e4f7d38a4a939b03997a5f2ab32.tar.gz |
Import weak-table-0.3.0 am: 2370d12326 am: da90669abf am: d5068867a9 am: a8c6c18ef6
Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/weak-table/+/1457361
Change-Id: I9a0bf3d5b6af5a9f04f801760ebf0e7c975dc74f
-rw-r--r-- | .cargo_vcs_info.json | 5 | ||||
-rw-r--r-- | .gitignore | 10 | ||||
-rw-r--r-- | .travis.yml | 23 | ||||
-rw-r--r-- | CMakeLists.txt | 1 | ||||
-rw-r--r-- | Cargo.toml | 29 | ||||
-rw-r--r-- | Cargo.toml.orig | 17 | ||||
-rw-r--r-- | LICENSE | 21 | ||||
-rw-r--r-- | Makefile | 26 | ||||
-rw-r--r-- | README.md | 98 | ||||
-rw-r--r-- | release.toml | 3 | ||||
-rw-r--r-- | src/by_ptr.rs | 33 | ||||
-rw-r--r-- | src/lib.rs | 237 | ||||
-rw-r--r-- | src/ptr_weak_hash_set.rs | 257 | ||||
-rw-r--r-- | src/ptr_weak_key_hash_map.rs | 352 | ||||
-rw-r--r-- | src/ptr_weak_weak_hash_map.rs | 312 | ||||
-rw-r--r-- | src/size_policy.rs | 14 | ||||
-rw-r--r-- | src/traits.rs | 127 | ||||
-rw-r--r-- | src/util.rs | 7 | ||||
-rw-r--r-- | src/weak_hash_set.rs | 270 | ||||
-rw-r--r-- | src/weak_key_hash_map.rs | 1063 | ||||
-rw-r--r-- | src/weak_value_hash_map.rs | 886 | ||||
-rw-r--r-- | src/weak_weak_hash_map.rs | 902 | ||||
-rw-r--r-- | tests/symbols.rs | 54 | ||||
-rw-r--r-- | tests/weak_key_hash_map.rs | 163 |
24 files changed, 4910 insertions, 0 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json new file mode 100644 index 0000000..6f8967e --- /dev/null +++ b/.cargo_vcs_info.json @@ -0,0 +1,5 @@ +{ + "git": { + "sha1": "80489689035c908f1096c07a8a0c51250f3dc979" + } +} diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..9035e79 --- /dev/null +++ b/.gitignore @@ -0,0 +1,10 @@ +# Generated by Cargo +# will have compiled files and executables +/target/ + +# Remove Cargo.lock from gitignore if creating an executable, leave it for libraries +# More information here http://doc.crates.io/guide.html#cargotoml-vs-cargolock +Cargo.lock + +/.idea/ +/cmake-build-*/ diff --git a/.travis.yml b/.travis.yml new file mode 100644 index 0000000..563df5b --- /dev/null +++ b/.travis.yml @@ -0,0 +1,23 @@ +language: rust +rust: + - stable + - beta + - nightly +# Oldest supported version: + - 1.32.0 + +dist: trusty +sudo: false + +matrix: + allow_failures: + - rust: nightly + +notifications: + email: + on_success: never + +addons: + apt: + packages: + - texinfo diff --git a/CMakeLists.txt b/CMakeLists.txt new file mode 100644 index 0000000..68d8985 --- /dev/null +++ b/CMakeLists.txt @@ -0,0 +1 @@ +# This file is here to make CLion happy. diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..343cfab --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,29 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies +# +# If you believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) + +[package] +edition = "2018" +name = "weak-table" +version = "0.3.0" +authors = ["Jesse A. Tov <jesse.tov@gmail.com>"] +description = "Weak hash maps and sets" +readme = "README.md" +keywords = ["containers", "Rc", "Arc", "weak"] +license = "MIT" +repository = "https://github.com/tov/weak-table-rs" + +[dependencies] +[dev-dependencies.quickcheck] +version = "0.9" + +[dev-dependencies.rand] +version = "0.7.2" diff --git a/Cargo.toml.orig b/Cargo.toml.orig new file mode 100644 index 0000000..7cb87e3 --- /dev/null +++ b/Cargo.toml.orig @@ -0,0 +1,17 @@ +[package] +name = "weak-table" +version = "0.3.0" +authors = ["Jesse A. Tov <jesse.tov@gmail.com>"] +description = "Weak hash maps and sets" +repository = "https://github.com/tov/weak-table-rs" +readme = "README.md" +license = "MIT" +keywords = ["containers", "Rc", "Arc", "weak"] +edition = "2018" + +[dependencies] + +[dev-dependencies] +quickcheck = "0.9" +rand = "0.7.2" + @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2018 Jesse A. Tov + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..6720eab --- /dev/null +++ b/Makefile @@ -0,0 +1,26 @@ +default: build +hard: test + +CRATE = weak_table +REPO = weak-table-rs + +build: + clear + cargo build + make doc + +clippy: + rustup run nightly cargo build --features=clippy + +doc: + cargo doc + echo "<meta http-equiv='refresh' content='0;url=$(CRATE)/'>" > target/doc/index.html + +test: + clear + cargo test + +upload-doc: + make doc + ghp-import -n target/doc + git push -f https://github.com/tov/$(REPO).git gh-pages diff --git a/README.md b/README.md new file mode 100644 index 0000000..56fa462 --- /dev/null +++ b/README.md @@ -0,0 +1,98 @@ +# weak-table: weak hash maps and sets for Rust + +[![Build Status](https://travis-ci.org/tov/weak-table-rs.svg?branch=master)](https://travis-ci.org/tov/weak-table-rs) +[![Crates.io](https://img.shields.io/crates/v/weak-table.svg?maxAge=2592000)](https://crates.io/crates/weak-table) +[![License: MIT](https://img.shields.io/badge/license-MIT-blue.svg)](LICENSE-MIT) + +This crate defines several kinds of weak hash maps and sets. See +the [full API documentation](http://docs.rs/weak-table/) for details. + +This crate supports Rust version 1.32 and later. + +### Examples + +Here we create a weak hash map and demonstrate that it forgets mappings +whose keys expire: + +```rust +use weak_table::WeakKeyHashMap; +use std::sync::{Arc, Weak}; + +let mut table = <WeakKeyHashMap<Weak<str>, u32>>::new(); +let one = Arc::<str>::from("one"); +let two = Arc::<str>::from("two"); + +table.insert(one.clone(), 1); + +assert_eq!( table.get("one"), Some(&1) ); +assert_eq!( table.get("two"), None ); + +table.insert(two.clone(), 2); +*table.get_mut(&one).unwrap() += 10; + +assert_eq!( table.get("one"), Some(&11) ); +assert_eq!( table.get("two"), Some(&2) ); + +drop(one); + +assert_eq!( table.get("one"), None ); +assert_eq!( table.get("two"), Some(&2) ); +``` + +Here we use a weak hash set to implement a simple string interning facility: + +```rust +use weak_table::WeakHashSet; +use std::ops::Deref; +use std::rc::{Rc, Weak}; + +#[derive(Clone, Debug)] +pub struct Symbol(Rc<str>); + +impl PartialEq for Symbol { + fn eq(&self, other: &Symbol) -> bool { + Rc::ptr_eq(&self.0, &other.0) + } +} + +impl Eq for Symbol {} + +impl Deref for Symbol { + type Target = str; + fn deref(&self) -> &str { + &self.0 + } +} + +#[derive(Debug, Default)] +pub struct SymbolTable(WeakHashSet<Weak<str>>); + +impl SymbolTable { + pub fn new() -> Self { + Self::default() + } + + pub fn intern(&mut self, name: &str) -> Symbol { + if let Some(rc) = self.0.get(name) { + Symbol(rc) + } else { + let rc = Rc::<str>::from(name); + self.0.insert(Rc::clone(&rc)); + Symbol(rc) + } + } +} + +#[test] +fn interning() { + let mut tab = SymbolTable::new(); + + let a0 = tab.intern("a"); + let a1 = tab.intern("a"); + let b = tab.intern("b"); + + assert_eq!(a0, a1); + assert_ne!(a0, b); +} +``` + diff --git a/release.toml b/release.toml new file mode 100644 index 0000000..5d7a460 --- /dev/null +++ b/release.toml @@ -0,0 +1,3 @@ +pre-release-replacements = [ + { file="src/lib.rs", search="https://docs[.]rs/weak-table/[0-9.]*", replace="https://docs.rs/weak-table/{{version}}" } +] diff --git a/src/by_ptr.rs b/src/by_ptr.rs new file mode 100644 index 0000000..b541f9e --- /dev/null +++ b/src/by_ptr.rs @@ -0,0 +1,33 @@ +use std::ops::Deref; + +use super::traits::*; + +/// Wrapper struct for using pointer equality and hashes rather +/// than pointed-to value equality and hashes. +#[derive(Clone, Debug)] +pub struct ByPtr<K>(K); + +impl<K: WeakElement> WeakElement for ByPtr<K> { + type Strong = K::Strong; + + fn new(view: &Self::Strong) -> Self { + ByPtr(K::new(view)) + } + + fn view(&self) -> Option<Self::Strong> { + self.0.view() + } +} + +impl<K: WeakElement> WeakKey for ByPtr<K> + where K::Strong: Deref +{ + type Key = *const <K::Strong as Deref>::Target; + + fn with_key<F, R>(view: &Self::Strong, f: F) -> R + where F: FnOnce(&Self::Key) -> R + { + f(&(view.deref() as *const _)) + } +} + diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..ce5e596 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,237 @@ +#![doc(html_root_url = "https://docs.rs/weak-table/0.3.0")] +//! This library offers a variety of weak hash tables: +//! +//! - For a hash map where the keys are held by weak pointers and compared by key value, see +//! [`WeakKeyHashMap`](struct.WeakKeyHashMap.html). +//! +//! - For a hash map where the keys are held by weak pointers and compared by pointer, see +//! [`PtrWeakKeyHashMap`](struct.PtrWeakKeyHashMap.html). +//! +//! - For a hash map where the values are held by weak pointers, see +//! [`WeakValueHashMap`](struct.WeakValueHashMap.html). +//! +//! - For a hash map where the keys and values are both held by weak pointers and the keys are +//! compared by value, see +//! [`WeakWeakHashMap`](struct.WeakWeakHashMap.html). +//! +//! - For a hash map where the keys and values are both held by weak pointers and the keys are +//! compared by pointer, see +//! [`PtrWeakWeakHashMap`](struct.PtrWeakWeakHashMap.html). +//! +//! - For a hash set where the elements are held by weak pointers and compared by element value, see +//! [`WeakHashSet`](struct.WeakHashSet.html). +//! +//! - For a hash set where the elements are held by weak pointers and compared by pointer, see +//! [`PtrWeakHashSet`](struct.PtrWeakHashSet.html). +//! +//! To add support for your own weak pointers, see +//! [the traits `WeakElement` and `WeakKey`](traits/). +//! +//! This crate supports Rust version 1.32 and later. +//! +//! # Examples +//! +//! Here we create a weak hash table mapping strings to integers. +//! Note that after dropping `one`, the key `"one"` is no longer present in the map. +//! This is because the map holds the strings as `std::sync::Weak<str>`s. +//! +//! ``` +//! use weak_table::WeakKeyHashMap; +//! use std::sync::{Arc, Weak}; +//! +//! let mut table = <WeakKeyHashMap<Weak<str>, u32>>::new(); +//! let one = Arc::<str>::from("one"); +//! let two = Arc::<str>::from("two"); +//! +//! table.insert(one.clone(), 1); +//! +//! assert_eq!( table.get("one"), Some(&1) ); +//! assert_eq!( table.get("two"), None ); +//! +//! table.insert(two.clone(), 2); +//! *table.get_mut(&one).unwrap() += 10; +//! +//! assert_eq!( table.get("one"), Some(&11) ); +//! assert_eq!( table.get("two"), Some(&2) ); +//! +//! drop(one); +//! +//! assert_eq!( table.get("one"), None ); +//! assert_eq!( table.get("two"), Some(&2) ); +//! ``` +//! +//! Here we use a weak hash set to implement a simple string interning facility: +//! +//! ``` +//! use weak_table::WeakHashSet; +//! use std::ops::Deref; +//! use std::rc::{Rc, Weak}; +//! +//! #[derive(Clone, Debug)] +//! pub struct Symbol(Rc<str>); +//! +//! impl PartialEq for Symbol { +//! fn eq(&self, other: &Symbol) -> bool { +//! Rc::ptr_eq(&self.0, &other.0) +//! } +//! } +//! +//! impl Eq for Symbol {} +//! +//! impl Deref for Symbol { +//! type Target = str; +//! fn deref(&self) -> &str { +//! &self.0 +//! } +//! } +//! +//! #[derive(Debug, Default)] +//! pub struct SymbolTable(WeakHashSet<Weak<str>>); +//! +//! impl SymbolTable { +//! pub fn new() -> Self { +//! Self::default() +//! } +//! +//! pub fn intern(&mut self, name: &str) -> Symbol { +//! if let Some(rc) = self.0.get(name) { +//! Symbol(rc) +//! } else { +//! let rc = Rc::<str>::from(name); +//! self.0.insert(Rc::clone(&rc)); +//! Symbol(rc) +//! } +//! } +//! } +//! +//! #[test] +//! fn interning() { +//! let mut tab = SymbolTable::new(); +//! +//! let a0 = tab.intern("a"); +//! let a1 = tab.intern("a"); +//! let b = tab.intern("b"); +//! +//! assert_eq!(a0, a1); +//! assert_ne!(a0, b); +//! } +//! ``` + +use std::collections::hash_map::RandomState; + +pub mod traits; +pub mod weak_key_hash_map; +pub mod ptr_weak_key_hash_map; +pub mod weak_value_hash_map; +pub mod weak_weak_hash_map; +pub mod ptr_weak_weak_hash_map; +pub mod weak_hash_set; +pub mod ptr_weak_hash_set; + +mod util; +mod by_ptr; +mod size_policy; + +#[derive(Copy, Clone, Debug, PartialEq, Eq)] +struct HashCode(u64); + +type FullBucket<K, V> = (K, V, HashCode); +type Bucket<K, V> = Option<FullBucket<K, V>>; +type TablePtr<K, V> = Box<[Bucket<K, V>]>; + +/// A hash map with weak keys, hashed on key value. +/// +/// When a weak pointer expires, its mapping is lazily removed. +#[derive(Clone)] +pub struct WeakKeyHashMap<K, V, S = RandomState> { + hash_builder: S, + inner: WeakKeyInnerMap<K, V>, +} + +#[derive(Clone)] +struct WeakKeyInnerMap<K, V> { + buckets: TablePtr<K, V>, + len: usize, +} + +/// A hash map with weak keys, hashed on key pointer. +/// +/// When a weak pointer expires, its mapping is lazily removed. +/// +/// # Examples +/// +/// ``` +/// use weak_table::PtrWeakKeyHashMap; +/// use std::rc::{Rc, Weak}; +/// +/// type Table = PtrWeakKeyHashMap<Weak<str>, usize>; +/// +/// let mut map = Table::new(); +/// let a = Rc::<str>::from("hello"); +/// let b = Rc::<str>::from("hello"); +/// +/// map.insert(a.clone(), 5); +/// +/// assert_eq!( map.get(&a), Some(&5) ); +/// assert_eq!( map.get(&b), None ); +/// +/// map.insert(b.clone(), 7); +/// +/// assert_eq!( map.get(&a), Some(&5) ); +/// assert_eq!( map.get(&b), Some(&7) ); +/// ``` +#[derive(Clone)] +pub struct PtrWeakKeyHashMap<K, V, S = RandomState>( + WeakKeyHashMap<by_ptr::ByPtr<K>, V, S> +); + +/// A hash map with weak values. +/// +/// When a weak pointer expires, its mapping is lazily removed. +#[derive(Clone)] +pub struct WeakValueHashMap<K, V, S = RandomState> { + hash_builder: S, + inner: WeakValueInnerMap<K, V>, +} + +#[derive(Clone)] +struct WeakValueInnerMap<K, V> { + buckets: TablePtr<K, V>, + len: usize, +} + +/// A hash map with weak keys and weak values, hashed on key value. +/// +/// When a weak pointer expires, its mapping is lazily removed. +#[derive(Clone)] +pub struct WeakWeakHashMap<K, V, S = RandomState> { + hash_builder: S, + inner: WeakWeakInnerMap<K, V>, +} + +#[derive(Clone)] +struct WeakWeakInnerMap<K, V> { + buckets: TablePtr<K, V>, + len: usize, +} + +/// A hash map with weak keys and weak values, hashed on key pointer. +/// +/// When a weak pointer expires, its mapping is lazily removed. +#[derive(Clone)] +pub struct PtrWeakWeakHashMap<K, V, S = RandomState>( + WeakWeakHashMap<by_ptr::ByPtr<K>, V, S> +); + +/// A hash set with weak elements, hashed on element value. +/// +/// When a weak pointer expires, its mapping is lazily removed. +#[derive(Clone)] +pub struct WeakHashSet<T, S = RandomState>(WeakKeyHashMap<T, (), S>); + +/// A hash set with weak elements, hashed on element pointer. +/// +/// When a weak pointer expires, its mapping is lazily removed. +#[derive(Clone)] +pub struct PtrWeakHashSet<T, S = RandomState>(PtrWeakKeyHashMap<T, (), S>); + diff --git a/src/ptr_weak_hash_set.rs b/src/ptr_weak_hash_set.rs new file mode 100644 index 0000000..9a38b4e --- /dev/null +++ b/src/ptr_weak_hash_set.rs @@ -0,0 +1,257 @@ +//! A hash set where the elements are held by weak pointers and compared by pointer. + +use std::collections::hash_map::RandomState; +use std::fmt::{self, Debug}; +use std::hash::BuildHasher; +use std::iter::FromIterator; +use std::ops::Deref; + +use super::traits::*; +use super::ptr_weak_key_hash_map as base; +use super::by_ptr::ByPtr; + +pub use super::PtrWeakHashSet; + +impl <T: WeakElement> PtrWeakHashSet<T, RandomState> + where T::Strong: Deref +{ + /// Creates an empty `PtrWeakHashSet`. + pub fn new() -> Self { + PtrWeakHashSet(base::PtrWeakKeyHashMap::new()) + } + + /// Creates an empty `PtrWeakHashSet` with the given capacity. + pub fn with_capacity(capacity: usize) -> Self { + PtrWeakHashSet(base::PtrWeakKeyHashMap::with_capacity(capacity)) + } +} + +impl <T: WeakElement, S: BuildHasher> PtrWeakHashSet<T, S> + where T::Strong: Deref +{ + /// Creates an empty `PtrWeakHashSet` with the given capacity and hasher. + pub fn with_hasher(hash_builder: S) -> Self { + PtrWeakHashSet(base::PtrWeakKeyHashMap::with_hasher(hash_builder)) + } + + /// Creates an empty `PtrWeakHashSet` with the given capacity and hasher. + pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { + PtrWeakHashSet(base::PtrWeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder)) + } + + /// Returns a reference to the map's `BuildHasher`. + pub fn hasher(&self) -> &S { + self.0.hasher() + } + + /// Returns the number of elements the map can hold without reallocating. + pub fn capacity(&self) -> usize { + self.0.capacity() + } + + /// Removes all mappings whose keys have expired. + pub fn remove_expired(&mut self) { + self.0.remove_expired() + } + + /// Reserves room for additional elements. + pub fn reserve(&mut self, additional_capacity: usize) { + self.0.reserve(additional_capacity) + } + + /// Shrinks the capacity to the minimum allowed to hold the current number of elements. + pub fn shrink_to_fit(&mut self) { + self.0.shrink_to_fit() + } + + /// Returns an over-approximation of the number of elements. + pub fn len(&self) -> usize { + self.0.len() + } + + /// Is the set known to be empty? + /// + /// This could answer `false` for an empty set whose elements have + /// expired but have yet to be collected. + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + + /// The proportion of buckets that are used. + /// + /// This is an over-approximation because of expired elements. + pub fn load_factor(&self) -> f32 { + self.0.load_factor() + } + + /// Removes all associations from the map. + pub fn clear(&mut self) { + self.0.clear() + } + + /// Returns true if the map contains the specified key. + pub fn contains(&self, key: &T::Strong) -> bool { + self.0.contains_key(key) + } + + /// Unconditionally inserts the value, returning the old value if already present. Does not + /// replace the key. + pub fn insert(&mut self, key: T::Strong) -> bool { + self.0.insert(key, ()).is_some() + } + + /// Removes the entry with the given key, if it exists, and returns the value. + pub fn remove(&mut self, key: &T::Strong) -> bool { + self.0.remove(key).is_some() + } + + /// Removes all mappings not satisfying the given predicate. + /// + /// Also removes any expired mappings. + pub fn retain<F>(&mut self, mut f: F) + where F: FnMut(T::Strong) -> bool + { + self.0.retain(|k, _| f(k)) + } + + /// Is self a subset of other? + pub fn is_subset<S1>(&self, other: &PtrWeakHashSet<T, S1>) -> bool + where S1: BuildHasher + { + self.0.domain_is_subset(&other.0) + } +} + +/// An iterator over the elements of a set. +pub struct Iter<'a, T: 'a>(base::Keys<'a, ByPtr<T>, ()>); + +impl<'a, T: WeakElement> Iterator for Iter<'a, T> { + type Item = T::Strong; + + fn next(&mut self) -> Option<Self::Item> { + self.0.next() + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +/// An iterator over the elements of a set. +pub struct IntoIter<T>(base::IntoIter<ByPtr<T>, ()>); + +impl<T: WeakElement> Iterator for IntoIter<T> { + type Item = T::Strong; + + fn next(&mut self) -> Option<Self::Item> { + self.0.next().map(|pair| pair.0) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +/// A draining iterator over the elements of a set. +pub struct Drain<'a, T: 'a>(base::Drain<'a, ByPtr<T>, ()>); + +impl<'a, T: WeakElement> Iterator for Drain<'a, T> { + type Item = T::Strong; + + fn next(&mut self) -> Option<Self::Item> { + self.0.next().map(|pair| pair.0) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +impl<T: WeakElement, S> PtrWeakHashSet<T, S> + where T::Strong: Deref +{ + /// Gets an iterator over the keys and values. + pub fn iter(&self) -> Iter<T> { + Iter(self.0.keys()) + } + + /// Gets a draining iterator, which removes all the values but retains the storage. + pub fn drain(&mut self) -> Drain<T> { + Drain(self.0.drain()) + } +} + +impl<T, S, S1> PartialEq<PtrWeakHashSet<T, S1>> for PtrWeakHashSet<T, S> + where T: WeakElement, + T::Strong: Deref, + S: BuildHasher, + S1: BuildHasher +{ + fn eq(&self, other: &PtrWeakHashSet<T, S1>) -> bool { + self.0 == other.0 + } +} + +impl<T: WeakElement, S: BuildHasher> Eq for PtrWeakHashSet<T, S> + where T::Strong: Deref +{ } + +impl<T: WeakElement, S: BuildHasher + Default> Default for PtrWeakHashSet<T, S> + where T::Strong: Deref +{ + fn default() -> Self { + PtrWeakHashSet(base::PtrWeakKeyHashMap::<T, (), S>::default()) + } +} + +impl<T, S> FromIterator<T::Strong> for PtrWeakHashSet<T, S> + where T: WeakElement, + T::Strong: Deref, + S: BuildHasher + Default +{ + fn from_iter<I: IntoIterator<Item=T::Strong>>(iter: I) -> Self { + PtrWeakHashSet(base::PtrWeakKeyHashMap::<T, (), S>::from_iter( + iter.into_iter().map(|k| (k, ())))) + } +} + +impl<T, S> Extend<T::Strong> for PtrWeakHashSet<T, S> + where T: WeakElement, + T::Strong: Deref, + S: BuildHasher +{ + fn extend<I: IntoIterator<Item=T::Strong>>(&mut self, iter: I) { + self.0.extend(iter.into_iter().map(|k| (k, ()))) + } +} + +impl<T, S> Debug for PtrWeakHashSet<T, S> + where T: WeakElement, + T::Strong: Debug +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.0.fmt(f) + } +} + +impl<T: WeakElement, S> IntoIterator for PtrWeakHashSet<T, S> { + type Item = T::Strong; + type IntoIter = IntoIter<T>; + + fn into_iter(self) -> Self::IntoIter { + IntoIter(self.0.into_iter()) + } +} + +impl<'a, T: WeakElement, S> IntoIterator for &'a PtrWeakHashSet<T, S> + where T::Strong: Deref +{ + type Item = T::Strong; + type IntoIter = Iter<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + Iter(self.0.keys()) + } +} + diff --git a/src/ptr_weak_key_hash_map.rs b/src/ptr_weak_key_hash_map.rs new file mode 100644 index 0000000..cd48809 --- /dev/null +++ b/src/ptr_weak_key_hash_map.rs @@ -0,0 +1,352 @@ +//! A hash map where the keys are held by weak pointers and compared by pointer. + +use std::collections::hash_map::RandomState; +use std::fmt::{self, Debug}; +use std::hash::BuildHasher; +use std::iter::FromIterator; +use std::ops::{Deref, Index, IndexMut}; + +use super::by_ptr::*; +use super::traits::*; +use super::weak_key_hash_map as base; + +pub use super::PtrWeakKeyHashMap; +pub use super::weak_key_hash_map::{Entry, Iter, IterMut, Keys, Values, ValuesMut, Drain, IntoIter}; + +impl <K: WeakElement, V> PtrWeakKeyHashMap<K, V, RandomState> + where K::Strong: Deref +{ + /// Creates an empty `PtrWeakKeyHashMap`. + pub fn new() -> Self { + PtrWeakKeyHashMap(base::WeakKeyHashMap::new()) + } + + /// Creates an empty `PtrWeakKeyHashMap` with the given capacity. + pub fn with_capacity(capacity: usize) -> Self { + PtrWeakKeyHashMap(base::WeakKeyHashMap::with_capacity(capacity)) + } +} + +impl <K: WeakElement, V, S: BuildHasher> PtrWeakKeyHashMap<K, V, S> + where K::Strong: Deref +{ + /// Creates an empty `PtrWeakKeyHashMap` with the given capacity and hasher. + pub fn with_hasher(hash_builder: S) -> Self { + PtrWeakKeyHashMap(base::WeakKeyHashMap::with_hasher(hash_builder)) + } + + /// Creates an empty `PtrWeakKeyHashMap` with the given capacity and hasher. + pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { + PtrWeakKeyHashMap(base::WeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder)) + } + + /// Returns a reference to the map's `BuildHasher`. + pub fn hasher(&self) -> &S { + self.0.hasher() + } + + /// Returns the number of elements the map can hold without reallocating. + pub fn capacity(&self) -> usize { + self.0.capacity() + } + + /// Removes all mappings whose keys have expired. + pub fn remove_expired(&mut self) { + self.0.remove_expired() + } + + /// Reserves room for additional elements. + pub fn reserve(&mut self, additional_capacity: usize) { + self.0.reserve(additional_capacity) + } + + /// Shrinks the capacity to the minimum allowed to hold the current number of elements. + pub fn shrink_to_fit(&mut self) { + self.0.shrink_to_fit() + } + + /// Returns an over-approximation of the number of elements. + pub fn len(&self) -> usize { + self.0.len() + } + + /// Is the map known to be empty? + /// + /// This could answer `false` for an empty map whose keys have + /// expired but have yet to be collected. + 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. + pub fn load_factor(&self) -> f32 { + self.0.load_factor() + } + + /// Gets the requested entry. + pub fn entry(&mut self, key: K::Strong) -> Entry<ByPtr<K>, V> { + self.0.entry(key) + } + + /// Removes all associations from the map. + pub fn clear(&mut self) { + self.0.clear() + } + + /// Returns a reference to the value corresponding to the key. + pub fn get(&self, key: &K::Strong) -> Option<&V> { + self.0.get(&(key.deref() as *const _)) + } + + /// Returns true if the map contains the specified key. + pub fn contains_key(&self, key:&K::Strong) -> bool { + self.0.contains_key(&(key.deref() as *const _)) + } + + /// Returns a mutable reference to the value corresponding to the key. + pub fn get_mut(&mut self, key: &K::Strong) -> Option<&mut V> { + self.0.get_mut(&(key.deref() as *const _)) + } + + /// Unconditionally inserts the value, returning the old value if already present. Does not + /// replace the key. + pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> { + self.0.insert(key, value) + } + + /// Removes the entry with the given key, if it exists, and returns the value. + pub fn remove(&mut self, key: &K::Strong) -> Option<V> { + self.0.remove(&(key.deref() as *const _)) + } + + /// Removes all mappings not satisfying the given predicate. + /// + /// Also removes any expired mappings. + pub fn retain<F>(&mut self, f: F) + where F: FnMut(K::Strong, &mut V) -> bool + { + self.0.retain(f) + } + + /// Is this map a submap of the other, using the given value comparison. + /// + /// In particular, all the keys of self must be in other and the values must compare true with + /// value_equal. + pub fn submap_with<F, S1, V1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>, value_equal: F) -> bool + where F: FnMut(&V, &V1) -> bool, + S1: BuildHasher + { + self.0.is_submap_with(&other.0, value_equal) + } + + /// Is self a submap of other? + pub fn is_submap<V1, S1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool + where V: PartialEq<V1>, + S1: BuildHasher + { + self.0.is_submap(&other.0) + } + + /// Are the keys of self a subset of the keys of other? + pub fn domain_is_subset<V1, S1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool + where S1: BuildHasher + { + self.0.domain_is_subset(&other.0) + } +} + +impl<K: WeakElement, V, S> PtrWeakKeyHashMap<K, V, S> + where K::Strong: Deref +{ + /// Gets an iterator over the keys and values. + pub fn iter(&self) -> Iter<ByPtr<K>, V> { + self.0.iter() + } + + /// Gets an iterator over the keys. + pub fn keys(&self) -> Keys<ByPtr<K>, V> { + self.0.keys() + } + + /// Gets an iterator over the values. + pub fn values(&self) -> Values<ByPtr<K>, V> { + self.0.values() + } + + /// Gets an iterator over the keys and mutable values. + pub fn iter_mut(&mut self) -> IterMut<ByPtr<K>, V> { + self.0.iter_mut() + } + + /// Gets an iterator over the mutable values. + pub fn values_mut(&mut self) -> ValuesMut<ByPtr<K>, V> { + self.0.values_mut() + } + + /// Gets a draining iterator, which removes all the values but retains the storage. + pub fn drain(&mut self) -> Drain<ByPtr<K>, V> { + self.0.drain() + } +} + +impl<K, V, V1, S, S1> PartialEq<PtrWeakKeyHashMap<K, V1, S1>> + for PtrWeakKeyHashMap<K, V, S> + where K: WeakElement, + K::Strong: Deref, + V: PartialEq<V1>, + S: BuildHasher, + S1: BuildHasher +{ + fn eq(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool { + self.0 == other.0 + } +} + +impl<K: WeakElement, V: Eq, S: BuildHasher> Eq for PtrWeakKeyHashMap<K, V, S> + where K::Strong: Deref +{ } + +impl<K: WeakElement, V, S: BuildHasher + Default> Default for PtrWeakKeyHashMap<K, V, S> + where K::Strong: Deref +{ + fn default() -> Self { + PtrWeakKeyHashMap(base::WeakKeyHashMap::<ByPtr<K>, V, S>::default()) + } +} + +impl<'a, K, V, S> Index<&'a K::Strong> for PtrWeakKeyHashMap<K, V, S> + where K: WeakElement, + K::Strong: Deref, + S: BuildHasher +{ + type Output = V; + + fn index(&self, index: &'a K::Strong) -> &Self::Output { + self.0.index(&(index.deref() as *const _)) + } +} + +impl<'a, K, V, S> IndexMut<&'a K::Strong> for PtrWeakKeyHashMap<K, V, S> + where + K: WeakElement, + K::Strong: Deref, + S: BuildHasher +{ + fn index_mut(&mut self, index: &'a K::Strong) -> &mut Self::Output { + self.0.index_mut(&(index.deref() as *const _)) + } +} + +impl<K, V, S> FromIterator<(K::Strong, V)> for PtrWeakKeyHashMap<K, V, S> + where K: WeakElement, + K::Strong: Deref, + S: BuildHasher + Default +{ + fn from_iter<T: IntoIterator<Item=(K::Strong, V)>>(iter: T) -> Self { + PtrWeakKeyHashMap(base::WeakKeyHashMap::<ByPtr<K>, V, S>::from_iter(iter)) + } +} + +impl<K, V, S> Extend<(K::Strong, V)> for PtrWeakKeyHashMap<K, V, S> + where K: WeakElement, + K::Strong: Deref, + S: BuildHasher +{ + fn extend<T: IntoIterator<Item=(K::Strong, V)>>(&mut self, iter: T) { + self.0.extend(iter) + } +} + +impl<'a, K, V, S> Extend<(&'a K::Strong, &'a V)> for PtrWeakKeyHashMap<K, V, S> + where K: 'a + WeakElement, + K::Strong: Clone + Deref, + V: 'a + Clone, + S: BuildHasher +{ + fn extend<T: IntoIterator<Item=(&'a K::Strong, &'a V)>>(&mut self, iter: T) { + self.0.extend(iter) + } +} + +impl<K, V: Debug, S> Debug for PtrWeakKeyHashMap<K, V, S> + where K: WeakElement, + K::Strong: Debug +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.0.fmt(f) + } +} + +impl<K: WeakElement, V, S> IntoIterator for PtrWeakKeyHashMap<K, V, S> { + type Item = (K::Strong, V); + type IntoIter = IntoIter<ByPtr<K>, V>; + + fn into_iter(self) -> Self::IntoIter { + self.0.into_iter() + } +} + +impl<'a, K: WeakElement, V, S> IntoIterator for &'a PtrWeakKeyHashMap<K, V, S> { + type Item = (K::Strong, &'a V); + type IntoIter = Iter<'a, ByPtr<K>, V>; + + fn into_iter(self) -> Self::IntoIter { + (&self.0).into_iter() + } +} + +impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut PtrWeakKeyHashMap<K, V, S> { + type Item = (K::Strong, &'a mut V); + type IntoIter = IterMut<'a, ByPtr<K>, V>; + + fn into_iter(self) -> Self::IntoIter { + (&mut self.0).into_iter() + } +} + +#[cfg(test)] +mod test +{ + use crate::PtrWeakKeyHashMap; + use crate::weak_key_hash_map::Entry; + use std::rc::{Rc, Weak}; + +// fn show_me(weakmap: &PtrWeakKeyHashMap<Weak<u32>, f32>) { +// for (key, _) in weakmap { +// eprint!(" {:2}", *key); +// } +// eprintln!(); +// } + + // 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 .. 200 { + rcs.push(Rc::new(i)); + } + + let mut weakmap: PtrWeakKeyHashMap<Weak<u32>, f32> = PtrWeakKeyHashMap::new(); + + for item in rcs.iter().cloned() { + let f = *item as f32 + 0.1; + weakmap.insert(item, f); + } + + let mut count = 0; + + for item in &rcs { + assert!(weakmap.contains_key(item)); + + match weakmap.entry(Rc::clone(item)) { + Entry::Occupied(_) => count += 1, + Entry::Vacant(_) => eprintln!("PointerWeakKeyHashMap: missing: {}", *item), + } + } + + assert_eq!( count, rcs.len() ); + } +} diff --git a/src/ptr_weak_weak_hash_map.rs b/src/ptr_weak_weak_hash_map.rs new file mode 100644 index 0000000..e842cd2 --- /dev/null +++ b/src/ptr_weak_weak_hash_map.rs @@ -0,0 +1,312 @@ +//! A hash map where the keys and values are both held by weak pointers, and keys are compared by +//! pointer. + +use std::collections::hash_map::RandomState; +use std::fmt::{self, Debug}; +use std::hash::BuildHasher; +use std::iter::FromIterator; +use std::ops::Deref; + +use super::by_ptr::*; +use super::traits::*; +use super::weak_weak_hash_map as base; + +pub use super::PtrWeakWeakHashMap; +pub use super::weak_weak_hash_map::{Entry, Iter, Keys, Values, Drain, IntoIter}; + +impl <K: WeakElement, V: WeakElement> PtrWeakWeakHashMap<K, V, RandomState> + where K::Strong: Deref +{ + /// Creates an empty `PtrWeakWeakHashMap`. + pub fn new() -> Self { + PtrWeakWeakHashMap(base::WeakWeakHashMap::new()) + } + + /// Creates an empty `PtrWeakWeakHashMap` with the given capacity. + pub fn with_capacity(capacity: usize) -> Self { + PtrWeakWeakHashMap(base::WeakWeakHashMap::with_capacity(capacity)) + } +} + +impl <K: WeakElement, V: WeakElement, S: BuildHasher> PtrWeakWeakHashMap<K, V, S> + where K::Strong: Deref +{ + /// Creates an empty `PtrWeakWeakHashMap` with the given capacity and hasher. + pub fn with_hasher(hash_builder: S) -> Self { + PtrWeakWeakHashMap(base::WeakWeakHashMap::with_hasher(hash_builder)) + } + + /// Creates an empty `PtrWeakWeakHashMap` with the given capacity and hasher. + pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { + PtrWeakWeakHashMap(base::WeakWeakHashMap::with_capacity_and_hasher(capacity, hash_builder)) + } + + /// Returns a reference to the map's `BuildHasher`. + pub fn hasher(&self) -> &S { + self.0.hasher() + } + + /// Returns the number of elements the map can hold without reallocating. + pub fn capacity(&self) -> usize { + self.0.capacity() + } + + /// Removes all mappings whose keys have expired. + pub fn remove_expired(&mut self) { + self.0.remove_expired() + } + + /// Reserves room for additional elements. + pub fn reserve(&mut self, additional_capacity: usize) { + self.0.reserve(additional_capacity) + } + + /// Shrinks the capacity to the minimum allowed to hold the current number of elements. + pub fn shrink_to_fit(&mut self) { + self.0.shrink_to_fit() + } + + /// Returns an over-approximation of the number of elements. + pub fn len(&self) -> usize { + self.0.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. + pub fn is_empty(&self) -> bool { + self.0.is_empty() + } + + /// The proportion of buckets that are used. + /// + /// This is an over-approximation because of expired keys. + pub fn load_factor(&self) -> f32 { + self.0.load_factor() + } + + /// Gets the requested entry. + pub fn entry(&mut self, key: K::Strong) -> Entry<ByPtr<K>, V> { + self.0.entry(key) + } + + /// Removes all associations from the map. + pub fn clear(&mut self) { + self.0.clear() + } + + /// Returns a reference to the value corresponding to the key. + pub fn get(&self, key: &K::Strong) -> Option<V::Strong> { + self.0.get(&(key.deref() as *const _)) + } + + /// Returns true if the map contains the specified key. + pub fn contains_key(&self, key: &K::Strong) -> bool { + self.0.contains_key(&(key.deref() as *const _)) + } + + /// Unconditionally inserts the value, returning the old value if already present. Does not + /// replace the key. + pub fn insert(&mut self, key: K::Strong, value: V::Strong) -> Option<V::Strong> { + self.0.insert(key, value) + } + + /// Removes the entry with the given key, if it exists, and returns the value. + pub fn remove(&mut self, key: &K::Strong) -> Option<V::Strong> { + self.0.remove(&(key.deref() as *const _)) + } + + /// Removes all mappings not satisfying the given predicate. + /// + /// Also removes any expired mappings. + pub fn retain<F>(&mut self, f: F) + where F: FnMut(K::Strong, V::Strong) -> bool + { + self.0.retain(f) + } + + /// Is this map a submap of the other, using the given value comparison. + /// + /// In particular, all the keys of self must be in other and the values must compare true with + /// value_equal. + pub fn submap_with<F, S1, V1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>, value_equal: F) -> bool + where F: FnMut(V::Strong, V1::Strong) -> bool, + V1: WeakElement, + S1: BuildHasher + { + self.0.is_submap_with(&other.0, value_equal) + } + + /// Is self a submap of other? + pub fn is_submap<V1, S1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool + where V1: WeakElement, + V::Strong: PartialEq<V1::Strong>, + S1: BuildHasher + { + self.0.is_submap(&other.0) + } + + /// Are the keys of self a subset of the keys of other? + pub fn domain_is_subset<V1, S1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool + where V1: WeakElement, + S1: BuildHasher + { + self.0.domain_is_subset(&other.0) + } +} + +impl<K: WeakElement, V: WeakElement, S> PtrWeakWeakHashMap<K, V, S> + where K::Strong: Deref +{ + /// Gets an iterator over the keys and values. + pub fn iter(&self) -> Iter<ByPtr<K>, V> { + self.0.iter() + } + + /// Gets an iterator over the keys. + pub fn keys(&self) -> Keys<ByPtr<K>, V> { + self.0.keys() + } + + /// Gets an iterator over the values. + pub fn values(&self) -> Values<ByPtr<K>, V> { + self.0.values() + } + + /// Gets a draining iterator, which removes all the values but retains the storage. + pub fn drain(&mut self) -> Drain<ByPtr<K>, V> { + self.0.drain() + } +} + +impl<K, V, V1, S, S1> PartialEq<PtrWeakWeakHashMap<K, V1, S1>> + for PtrWeakWeakHashMap<K, V, S> + where K: WeakElement, + K::Strong: Deref, + V: WeakElement, + V1: WeakElement, + V::Strong: PartialEq<V1::Strong>, + S: BuildHasher, + S1: BuildHasher +{ + fn eq(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool { + self.0 == other.0 + } +} + +impl<K: WeakElement, V: WeakElement, S: BuildHasher> Eq for PtrWeakWeakHashMap<K, V, S> + where K::Strong: Deref, + V::Strong: Eq +{ } + +impl<K: WeakElement, V: WeakElement, S: BuildHasher + Default> Default for PtrWeakWeakHashMap<K, V, S> + where K::Strong: Deref +{ + fn default() -> Self { + PtrWeakWeakHashMap(base::WeakWeakHashMap::<ByPtr<K>, V, S>::default()) + } +} + +impl<K, V, S> FromIterator<(K::Strong, V::Strong)> for PtrWeakWeakHashMap<K, V, S> + where K: WeakElement, + K::Strong: Deref, + V: WeakElement, + S: BuildHasher + Default +{ + fn from_iter<T: IntoIterator<Item=(K::Strong, V::Strong)>>(iter: T) -> Self { + PtrWeakWeakHashMap(base::WeakWeakHashMap::<ByPtr<K>, V, S>::from_iter(iter)) + } +} + +impl<K, V, S> Extend<(K::Strong, V::Strong)> for PtrWeakWeakHashMap<K, V, S> + where K: WeakElement, + K::Strong: Deref, + V: WeakElement, + S: BuildHasher +{ + fn extend<T: IntoIterator<Item=(K::Strong, V::Strong)>>(&mut self, iter: T) { + self.0.extend(iter) + } +} + +impl<K, V, S> Debug for PtrWeakWeakHashMap<K, V, S> + where K: WeakElement, + K::Strong: Debug, + V: WeakElement, + V::Strong: Debug +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.0.fmt(f) + } +} + +impl<K: WeakElement, V: WeakElement, S> IntoIterator for PtrWeakWeakHashMap<K, V, S> { + type Item = (K::Strong, V::Strong); + type IntoIter = IntoIter<ByPtr<K>, V>; + + fn into_iter(self) -> Self::IntoIter { + self.0.into_iter() + } +} + +impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a PtrWeakWeakHashMap<K, V, S> { + type Item = (K::Strong, V::Strong); + type IntoIter = Iter<'a, ByPtr<K>, V>; + + fn into_iter(self) -> Self::IntoIter { + (&self.0).into_iter() + } +} + +#[cfg(test)] +mod test +{ + use crate::PtrWeakWeakHashMap; + use crate::weak_weak_hash_map::Entry; + use std::rc::{Rc, Weak}; + +// fn show_me(weakmap: &PtrWeakWeakHashMap<Weak<u32>, Weak<f32>>) { +// for (key, _) in weakmap { +// eprint!(" {:2}", *key); +// } +// eprintln!(); +// } + + // From https://github.com/tov/weak-table-rs/issues/1#issuecomment-461858060 + #[test] + fn insert_and_check() { + let mut rcs: Vec<(Rc<u32>, Rc<f32>)> = Vec::new(); + + for i in 0 .. 200 { + rcs.push((Rc::new(i), Rc::new(i as f32 + 0.1))); + } + + let mut weakmap: PtrWeakWeakHashMap<Weak<u32>, Weak<f32>> = PtrWeakWeakHashMap::new(); + + for (key, value) in rcs.iter().cloned() { + weakmap.insert(key, value); +// show_me(&weakmap); + } + + let mut count = 0; + + for (key, value) in &rcs { + assert!(weakmap.contains_key(key)); + + match weakmap.entry(Rc::clone(key)) { + Entry::Occupied(occ) => { + assert_eq!( occ.get(), value ); + count += 1; + } + Entry::Vacant(_) => { + eprintln!("PointerWeakWeakHashMap: missing: {}", *key); + } + } + } + + assert_eq!( count, rcs.len() ); + } +} + + diff --git a/src/size_policy.rs b/src/size_policy.rs new file mode 100644 index 0000000..7eb5c6a --- /dev/null +++ b/src/size_policy.rs @@ -0,0 +1,14 @@ +/// No reason for this number as of now. +pub const DEFAULT_INITIAL_CAPACITY: usize = 8; + +/// When the approximate load factor reaches `COLLECT_LOAD_FACTOR`, we remove +/// all the expired pointers and then consider resizing. +pub const COLLECT_LOAD_FACTOR: f32 = 0.9; + +/// If, after collection, the load factor is above `GROW_LOAD_FACTOR`, we grow. +pub const GROW_LOAD_FACTOR: f32 = 0.75; + +/// If, after collection, the load factor is below `SHRINK_LOAD_FACTOR`, we shrink. +pub const SHRINK_LOAD_FACTOR: f32 = 0.25; + + diff --git a/src/traits.rs b/src/traits.rs new file mode 100644 index 0000000..440a6c9 --- /dev/null +++ b/src/traits.rs @@ -0,0 +1,127 @@ +//! Traits for describing strong and weak pointers and their use as elements and keys. +//! +//! These traits provide mechanisms for converting between weak and strong pointers +//! ([`WeakElement`](trait.WeakElement.html)) and for dereferencing strong pointers +//! ([`WeakKey`](trait.WeakKey.html)). Implementations of these traits are provided for +//! `std::rc::Weak` and `std::sync::Weak`. If you would like to use your own pointer type +//! as a weak element, you need to implement `WeakElement` for your weak pointer type; to use it +//! as a weak key, implement `WeakKey` as well. + +use std::hash::Hash; +use std::{rc, sync}; + +/// Interface for elements that can be stored in weak hash tables. +/// +/// This trait applies to the weak version of a reference-counted pointer; it can be used to +/// convert a weak pointer into a strong pointer and back. For example, the impl for +/// `std::rc::Weak<T>` defines the `Strong` associated type as `std::rc::Rc<T>`. Then method +/// `new` can be used to downgrade an `Rc<T>` to a `Weak<T>`, and method `view` can be used to +/// upgrade a `Weak<T>` into an `Rc<T>`, if it's still alive. If we think of the weak pointer as +/// what is stored, then the strong pointer is a temporary view of it. +pub trait WeakElement { + /// The type at which a weak element can be viewed. + /// + /// For example, for `std::rc::Weak<T>`, this will be `std::rc::Rc<T>`. + type Strong; + + /// Constructs a weak pointer from a strong pointer. + /// + /// This is usually implemented by a `downgrade` method. + fn new(view: &Self::Strong) -> Self; + + /// Acquires a strong pointer from a weak pointer. + /// + /// This is usually implemented by an `upgrade` method. + fn view(&self) -> Option<Self::Strong>; + + /// Is the given weak element expired? + /// + /// The default implemention checks whether a strong pointer can be obtained via `view`. + fn is_expired(&self) -> bool { + self.view().is_none() + } + + /// Clones a strong pointer. + /// + /// The default implementation uses `new` and `view`; you should override it. + fn clone(view: &Self::Strong) -> Self::Strong + where Self: Sized + { + Self::new(view).view().expect("WeakElement::clone") + } +} + +/// Interface for elements that can act as keys in weak hash tables. +/// +/// To use an element as a weak hash map key or weak hash set element), the hash table +/// needs to be able to view the actual key values to hash and compare them. This trait +/// provides the necessary mechanism. +pub trait WeakKey : WeakElement { + /// The underlying key type. + /// + /// For example, for `std::rc::Weak<T>`, this will be `T`. + type Key: ?Sized + Eq + Hash; + + /// Allows borrowing a view of the key, via a callback. + /// + /// Rather than returning a borrowed reference to the actual key, this method passes a + /// reference to the key to a callback with an implicit higher-order lifetime bound. This is + /// necessary to get the lifetimes right in cases where the key is not actually store in the + /// strong pointer. + fn with_key<F, R>(view: &Self::Strong, f: F) -> R + where F: FnOnce(&Self::Key) -> R; +} + +impl<T: ?Sized> WeakElement for rc::Weak<T> { + type Strong = rc::Rc<T>; + + fn new(view: &Self::Strong) -> Self { + rc::Rc::<T>::downgrade(view) + } + + fn view(&self) -> Option<Self::Strong> { + self.upgrade() + } + + fn clone(view: &Self::Strong) -> Self::Strong { + view.clone() + } +} + +impl<T: ?Sized + Eq + Hash> WeakKey for rc::Weak<T> { + type Key = T; + + fn with_key<F, R>(view: &Self::Strong, f: F) -> R + where F: FnOnce(&Self::Key) -> R + { + f(&view) + } +} + +impl<T: ?Sized> WeakElement for sync::Weak<T> { + type Strong = sync::Arc<T>; + + fn new(view: &Self::Strong) -> Self { + sync::Arc::<T>::downgrade(view) + } + + fn view(&self) -> Option<Self::Strong> { + self.upgrade() + } + + fn clone(view: &Self::Strong) -> Self::Strong { + view.clone() + } +} + +impl<T: ?Sized + Eq + Hash> WeakKey for sync::Weak<T> +{ + type Key = T; + + fn with_key<F, R>(view: &Self::Strong, f: F) -> R + where F: FnOnce(&Self::Key) -> R + { + f(&view) + } +} + diff --git a/src/util.rs b/src/util.rs new file mode 100644 index 0000000..3792ec7 --- /dev/null +++ b/src/util.rs @@ -0,0 +1,7 @@ +pub fn new_boxed_option_slice<T>(size: usize) -> Box<[Option<T>]> { + let mut vector = Vec::with_capacity(size); + for _ in 0 .. size { + vector.push(None) + } + vector.into_boxed_slice() +} diff --git a/src/weak_hash_set.rs b/src/weak_hash_set.rs new file mode 100644 index 0000000..a3bc151 --- /dev/null +++ b/src/weak_hash_set.rs @@ -0,0 +1,270 @@ +//! A hash set where the elements are held by weak pointers and compared by value. + +use std::borrow::Borrow; +use std::collections::hash_map::RandomState; +use std::fmt::{self, Debug}; +use std::hash::{BuildHasher, Hash}; +use std::iter::FromIterator; + +use super::traits::*; +use super::weak_key_hash_map as base; + +pub use super::WeakHashSet; + +impl <T: WeakKey> WeakHashSet<T, RandomState> { + /// Creates an empty `WeakHashSet`. + pub fn new() -> Self { + WeakHashSet(base::WeakKeyHashMap::new()) + } + + /// Creates an empty `WeakHashSet` with the given capacity. + pub fn with_capacity(capacity: usize) -> Self { + WeakHashSet(base::WeakKeyHashMap::with_capacity(capacity)) + } +} + +impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> { + /// Creates an empty `WeakHashSet` with the given capacity and hasher. + pub fn with_hasher(hash_builder: S) -> Self { + WeakHashSet(base::WeakKeyHashMap::with_hasher(hash_builder)) + } + + /// Creates an empty `WeakHashSet` with the given capacity and hasher. + pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { + WeakHashSet(base::WeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder)) + } + + /// Returns a reference to the map's `BuildHasher`. + pub fn hasher(&self) -> &S { + self.0.hasher() + } + + /// Returns the number of elements the map can hold without reallocating. + pub fn capacity(&self) -> usize { + self.0.capacity() + } + + /// Removes all mappings whose keys have expired. + pub fn remove_expired(&mut self) { + self.0.remove_expired() + } + + /// Reserves room for additional elements. + pub fn reserve(&mut self, additional_capacity: usize) { + self.0.reserve(additional_capacity) + } + + /// Shrinks the capacity to the minimum allowed to hold the current number of elements. + pub fn shrink_to_fit(&mut self) { + self.0.shrink_to_fit() + } + + /// Returns an over-approximation of the number of elements. + pub fn len(&self) -> usize { + self.0.len() + } + + /// Is the set empty? + /// + /// Note that this may return false even if all keys in the set have + /// expired, if they haven't been collected yet. + pub fn is_empty(&self) -> bool { + self.0.is_empty() + } + + /// The proportion of buckets that are used. + /// + /// This is an over-approximation because of expired elements. + pub fn load_factor(&self) -> f32 { + self.0.load_factor() + } + + /// Removes all associations from the map. + pub fn clear(&mut self) { + self.0.clear() + } + + // Non-ptr WeakHashSet should probably have `get` method. + + /// Returns true if the map contains the specified key. + pub fn contains<Q>(&self, key: &Q) -> bool + where Q: ?Sized + Eq + Hash, + T::Key: Borrow<Q> + { + self.0.contains_key(key) + } + + /// Gets a strong reference to the given key, if found. + /// + /// # Examples + /// + /// ``` + /// use weak_table::WeakHashSet; + /// use std::rc::{Rc, Weak}; + /// use std::ops::Deref; + /// + /// let mut set: WeakHashSet<Weak<String>> = WeakHashSet::new(); + /// + /// let a = Rc::new("a".to_owned()); + /// set.insert(a.clone()); + /// + /// let also_a = set.get("a").unwrap(); + /// + /// assert!(Rc::ptr_eq( &a, &also_a )); + /// ``` + pub fn get<Q>(&self, key: &Q) -> Option<T::Strong> + where Q: ?Sized + Eq + Hash, + T::Key: Borrow<Q> + { + self.0.get_key(key) + } + + /// Unconditionally inserts the value, returning the old value if already present. Does not + /// replace the key. + pub fn insert(&mut self, key: T::Strong) -> bool { + self.0.insert(key, ()).is_some() + } + + /// Removes the entry with the given key, if it exists, and returns the value. + pub fn remove<Q>(&mut self, key: &Q) -> bool + where Q: ?Sized + Eq + Hash, + T::Key: Borrow<Q> + { + self.0.remove(key).is_some() + } + + /// Removes all mappings not satisfying the given predicate. + /// + /// Also removes any expired mappings. + pub fn retain<F>(&mut self, mut f: F) + where F: FnMut(T::Strong) -> bool + { + self.0.retain(|k, _| f(k)) + } + + /// Is self a subset of other? + pub fn is_subset<S1>(&self, other: &WeakHashSet<T, S1>) -> bool + where S1: BuildHasher + { + self.0.domain_is_subset(&other.0) + } +} + +/// An iterator over the elements of a set. +pub struct Iter<'a, T: 'a>(base::Keys<'a, T, ()>); + +impl<'a, T: WeakElement> Iterator for Iter<'a, T> { + type Item = T::Strong; + + fn next(&mut self) -> Option<Self::Item> { + self.0.next() + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +/// An iterator over the elements of a set. +pub struct IntoIter<T>(base::IntoIter<T, ()>); + +impl<T: WeakElement> Iterator for IntoIter<T> { + type Item = T::Strong; + + fn next(&mut self) -> Option<Self::Item> { + self.0.next().map(|pair| pair.0) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +/// A draining iterator over the elements of a set. +pub struct Drain<'a, T: 'a>(base::Drain<'a, T, ()>); + +impl<'a, T: WeakElement> Iterator for Drain<'a, T> { + type Item = T::Strong; + + fn next(&mut self) -> Option<Self::Item> { + self.0.next().map(|pair| pair.0) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +impl<T: WeakKey, S> WeakHashSet<T, S> { + /// Gets an iterator over the keys and values. + pub fn iter(&self) -> Iter<T> { + Iter(self.0.keys()) + } + + /// Gets a draining iterator, which removes all the values but retains the storage. + pub fn drain(&mut self) -> Drain<T> { + Drain(self.0.drain()) + } +} + +impl<T, S, S1> PartialEq<WeakHashSet<T, S1>> for WeakHashSet<T, S> + where T: WeakKey, + S: BuildHasher, + S1: BuildHasher +{ + fn eq(&self, other: &WeakHashSet<T, S1>) -> bool { + self.0 == other.0 + } +} + +impl<T: WeakKey, S: BuildHasher> Eq for WeakHashSet<T, S> + where T::Key: Eq +{ } + +impl<T: WeakKey, S: BuildHasher + Default> Default for WeakHashSet<T, S> { + fn default() -> Self { + WeakHashSet(base::WeakKeyHashMap::<T, (), S>::default()) + } +} + +impl<T, S> FromIterator<T::Strong> for WeakHashSet<T, S> + where T: WeakKey, + S: BuildHasher + Default +{ + fn from_iter<I: IntoIterator<Item=T::Strong>>(iter: I) -> Self { + WeakHashSet(base::WeakKeyHashMap::<T, (), S>::from_iter( + iter.into_iter().map(|k| (k, ())))) + } +} + +impl<T: WeakKey, S: BuildHasher> Extend<T::Strong> for WeakHashSet<T, S> { + fn extend<I: IntoIterator<Item=T::Strong>>(&mut self, iter: I) { + self.0.extend(iter.into_iter().map(|k| (k, ()))) + } +} + +impl<T: WeakKey, S> Debug for WeakHashSet<T, S> + where T::Strong: Debug +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.0.fmt(f) + } +} + +impl<T: WeakKey, S> IntoIterator for WeakHashSet<T, S> { + type Item = T::Strong; + type IntoIter = IntoIter<T>; + + fn into_iter(self) -> Self::IntoIter { + IntoIter(self.0.into_iter()) + } +} + +impl<'a, T: WeakKey, S> IntoIterator for &'a WeakHashSet<T, S> { + type Item = T::Strong; + type IntoIter = Iter<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + Iter(self.0.keys()) + } +} diff --git a/src/weak_key_hash_map.rs b/src/weak_key_hash_map.rs new file mode 100644 index 0000000..91bee2a --- /dev/null +++ b/src/weak_key_hash_map.rs @@ -0,0 +1,1063 @@ +//! A hash map where the keys are held by weak pointers and compared by key value. + +use std::borrow::Borrow; +use std::cmp::max; +use std::collections::hash_map::RandomState; +use std::hash::{BuildHasher, Hash, Hasher}; +use std::fmt::{self, Debug, Formatter}; +use std::mem; + +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: ::std::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> { + while let Some(bucket) = self.base.next() { + 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: ::std::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> { + while let Some(bucket) = self.base.next() { + 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: ::std::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> { + while let Some(bucket) = self.base.next() { + 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) { + while let Some(option) = self.base.next() { + *option = None; + } + } +} + +/// An iterator that consumes the values of a weak hash map, leaving it empty. +pub struct IntoIter<K, V> { + base: ::std::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> { + while let Some(bucket) = self.base.next() { + if let Some((weak_ptr, 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)) + } +} + +impl<K: WeakKey, V> WeakKeyHashMap<K, V, RandomState> +{ + /// Creates an empty `WeakKeyHashMap`. + pub fn new() -> Self { + Self::with_capacity(DEFAULT_INITIAL_CAPACITY) + } + + /// Creates an empty `WeakKeyHashMap` with the given capacity. + 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. + 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. + 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`. + pub fn hasher(&self) -> &S { + &self.hash_builder + } + + /// Returns the number of elements the map can hold without reallocating. + 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. + pub fn remove_expired(&mut self) { + self.retain(|_, _| true) + } + + /// Reserves room for additional elements. + 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. + 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. + 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. + 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. + 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. + 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 = K::with_key(&key, |k| self.hash(k)); + 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. + 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); + 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::with_key(&bucket_key, |k| k.borrow() == 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. + 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. + 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. + 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. + 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. + 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. + 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. + 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. + 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. + 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, using the given value comparison. + /// + /// In particular, all the keys of `self` must be in `other` and the values must compare + /// `true` with `value_equal`. + pub fn is_submap_with<F, S1, V1>(&self, other: &WeakKeyHashMap<K, V1, S1>, + mut value_equal: 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 !value_equal(value1, value2) { + return false; + } + } else { + return false; + } + } + + true + } + + /// Is `self` a submap of `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`? + 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>(&self, key: &Q) -> HashCode + where Q: ?Sized + Hash, + K::Key: Borrow<Q> + { + let mut hasher = self.hash_builder.build_hasher(); + key.hash(&mut 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> ::std::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> ::std::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> ::std::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> ::std::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> ::std::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, |k1| K::with_key(&key, |k2| k1 == k2)) { + 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. + 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. + 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. + 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. + pub fn key(&self) -> &K::Strong { + &self.0.key + } + + /// Takes ownership of the key and value from the map. + 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. + 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. + 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. + 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. + 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. + 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`. + pub fn key(&self) -> &K::Strong { + &self.0.key + } + + /// Returns ownership of the key. + 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. + 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>; + + 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>; + + 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>; + + 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. + pub fn iter(&self) -> Iter<K, V> { + self.into_iter() + } + + /// Gets an iterator over the keys. + pub fn keys(&self) -> Keys<K, V> { + Keys(self.iter()) + } + + /// Gets an iterator over the values. + pub fn values(&self) -> Values<K, V> { + Values(self.iter()) + } + + /// Gets an iterator over the keys and mutable values. + pub fn iter_mut(&mut self) -> IterMut<K, V> { + self.into_iter() + } + + /// Gets an iterator over the mutable values. + 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. + 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 tests { + use std::rc::{Rc, Weak}; + 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("five".to_string()); + 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() ); + } +} diff --git a/src/weak_value_hash_map.rs b/src/weak_value_hash_map.rs new file mode 100644 index 0000000..8b60a17 --- /dev/null +++ b/src/weak_value_hash_map.rs @@ -0,0 +1,886 @@ +//! A hash map where the values are held by weak pointers. + +use std::borrow::Borrow; +use std::cmp::max; +use std::collections::hash_map::RandomState; +use std::hash::{BuildHasher, Hash, Hasher}; +use std::fmt::{self, Debug, Formatter}; +use std::mem; + +use super::*; +use super::size_policy::*; +use super::traits::*; +use super::util::*; + +pub use super::WeakValueHashMap; + +/// Represents an entry in the table which may be occupied or vacant. +pub enum Entry<'a, K: 'a, V: 'a + WeakElement> { + 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, V: 'a + WeakElement> { + inner: InnerEntry<'a, K, V>, + value: V::Strong, +} + +/// A vacant entry, which can be inserted in or viewed. +pub struct VacantEntry<'a, K: 'a, V: 'a + WeakElement> { + inner: InnerEntry<'a, K, V>, +} + +struct InnerEntry<'a, K: 'a, V: 'a + WeakElement> { + map: &'a mut WeakValueInnerMap<K, V>, + pos: usize, + key: K, + 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: ::std::slice::Iter<'a, Bucket<K, V>>, + size: usize, +} + +impl<'a, K, V: WeakElement> Iterator for Iter<'a, K, V> { + type Item = (&'a K, V::Strong); + + fn next(&mut self) -> Option<Self::Item> { + while let Some(bucket) = self.base.next() { + if let Some((ref key, ref weak_value, _)) = *bucket { + self.size -= 1; + if let Some(value) = weak_value.view() { + return Some((key, 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, V: WeakElement> Iterator for Keys<'a, K, V> { + type Item = &'a K; + + 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, V: WeakElement> Iterator for Values<'a, K, V> { + type Item = V::Strong; + + 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: ::std::slice::IterMut<'a, Bucket<K, V>>, + size: usize, +} + +impl<'a, K, V: WeakElement> Iterator for Drain<'a, K, V> { + type Item = (K, V::Strong); + + fn next(&mut self) -> Option<Self::Item> { + while let Some(bucket) = self.base.next() { + if let Some((key, weak_value, _)) = bucket.take() { + self.size -= 1; + if let Some(value) = weak_value.view() { + return Some((key, 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) { + while let Some(option) = self.base.next() { + *option = None; + } + } +} + +/// An iterator that consumes the values of a weak hash map, leaving it empty. +pub struct IntoIter<K, V> { + base: ::std::vec::IntoIter<Bucket<K, V>>, + size: usize, +} + +impl<K, V: WeakElement> Iterator for IntoIter<K, V> { + type Item = (K, V::Strong); + + fn next(&mut self) -> Option<Self::Item> { + while let Some(bucket) = self.base.next() { + if let Some((key, weak_value, _)) = bucket { + self.size -= 1; + if let Some(value) = weak_value.view() { + return Some((key, value)); + } + } + } + + None + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (0, Some(self.size)) + } +} + +impl<K: Eq + Hash, V: WeakElement> WeakValueHashMap<K, V, RandomState> +{ + /// Creates an empty `WeakValueHashMap`. + pub fn new() -> Self { + Self::with_capacity(DEFAULT_INITIAL_CAPACITY) + } + + /// Creates an empty `WeakValueHashMap` with the given capacity. + pub fn with_capacity(capacity: usize) -> Self { + Self::with_capacity_and_hasher(capacity, Default::default()) + } +} + +impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S> +{ + /// Creates an empty `WeakValueHashMap` with the given capacity and hasher. + pub fn with_hasher(hash_builder: S) -> Self { + Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder) + } + + /// Creates an empty `WeakValueHashMap` with the given capacity and hasher. + pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { + WeakValueHashMap { + hash_builder, + inner: WeakValueInnerMap { + buckets: new_boxed_option_slice(capacity), + len: 0, + } + } + } + + /// Returns a reference to the map's `BuildHasher`. + pub fn hasher(&self) -> &S { + &self.hash_builder + } + + /// Returns the number of elements the map can hold without reallocating. + 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. + pub fn remove_expired(&mut self) { + self.retain(|_, _| true) + } + + /// Reserves room for additional elements. + 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. + 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. + 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. + 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. + 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. + pub fn entry(&mut self, key: K) -> Entry<K, V> { + self.maybe_adjust_size(); + self.entry_no_grow(key) + } + + fn entry_no_grow(&mut self, key: K) -> Entry<K, V> { + let mut inner = { + let hash_code = self.hash(&key); + 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(value) => { + return Entry::Occupied(OccupiedEntry {inner, value}) + } + BucketStatus::ProbeDistance(bucket_distance) => { + if bucket_distance < dist { + return Entry::Vacant(VacantEntry {inner}) + } else { + inner.pos = inner.next_bucket(inner.pos); + } + } + } + } + + panic!("WeakValueHashTable::entry: out of space"); + } + + /// Removes all associations from the map. + pub fn clear(&mut self) { + self.drain(); + } + + fn find_bucket<Q>(&self, key: &Q) -> Option<(usize, V::Strong)> + where Q: ?Sized + Hash + Eq, + K: Borrow<Q> + { + if self.capacity() == 0 { return None; } + + let hash_code = self.hash(key); + let mut pos = self.which_bucket(hash_code); + + for dist in 0 .. self.capacity() { + if let Some((ref bucket_key, ref weak_value, bucket_hash_code)) = self.inner.buckets[pos] { + if bucket_hash_code == hash_code { + if let Some(value) = weak_value.view() { + if bucket_key.borrow() == key { + return Some((pos, value)); + } + } + } + + let bucket_dist = + self.probe_distance(pos, self.which_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. + pub fn get<Q>(&self, key: &Q) -> Option<V::Strong> + where Q: ?Sized + Hash + Eq, + K: Borrow<Q> + { + self.find_bucket(key).map(|tup| tup.1) + } + + /// Returns true if the map contains the specified key. + pub fn contains_key<Q>(&self, key: &Q) -> bool + where Q: ?Sized + Hash + Eq, + K: Borrow<Q> + { + self.find_bucket(key).is_some() + } + + /// Unconditionally inserts the value, returning the old value if already present. + /// + /// Like `std::collections::HashMap`, this does not replace the key if occupied. + pub fn insert(&mut self, key: K, value: V::Strong) -> Option<V::Strong> { + 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. + pub fn remove<Q>(&mut self, key: &Q) -> Option<V::Strong> + where Q: ?Sized + Hash + Eq, + K: Borrow<Q> + { + if let Some((pos, value)) = self.find_bucket(key) { + self.inner.remove_index(pos); + Some(value) + } else { + None + } + } + + /// Removes all mappings not satisfying the given predicate. + /// + /// Also removes any expired mappings. + pub fn retain<F>(&mut self, mut f: F) + where F: FnMut(&K, V::Strong) -> bool + { + for i in 0 .. self.capacity() { + let remove = match self.inner.buckets[i] { + None => false, + Some(ref mut bucket) => + match bucket.1.view() { + None => true, + Some(value) => !f(&bucket.0, value), + } + }; + + if remove { + self.inner.remove_index(i); + } + } + } + + /// Is this map a submap of the other, using the given value comparison. + /// + /// In particular, all the keys of `self` must be in `other` and the values must compare + /// `true` with `value_equal`. + pub fn is_submap_with<F, S1, V1>(&self, other: &WeakValueHashMap<K, V1, S1>, + mut value_equal: F) -> bool + where V1: WeakElement, + F: FnMut(V::Strong, V1::Strong) -> bool, + S1: BuildHasher + { + for (key, value1) in self { + if let Some(value2) = other.get(key) { + if !value_equal(value1, value2) { + return false; + } + } else { + return false; + } + } + + true + } + + /// Is `self` a submap of `other`? + pub fn is_submap<V1, S1>(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool + where V1: WeakElement, + V::Strong: PartialEq<V1::Strong>, + S1: BuildHasher + { + self.is_submap_with(other, |v, v1| v == v1) + } + + /// Are the keys of `self` a subset of the keys of `other`? + pub fn domain_is_subset<V1, S1>(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool + where V1: WeakElement, + S1: BuildHasher + { + self.is_submap_with(other, |_, _| true) + } + + fn hash<Q>(&self, key: &Q) -> HashCode + where Q: ?Sized + Hash, + K: Borrow<Q> + { + let mut hasher = self.hash_builder.build_hasher(); + key.hash(&mut hasher); + HashCode(hasher.finish()) + } +} + +impl<K, V, V1, S, S1> PartialEq<WeakValueHashMap<K, V1, S1>> for WeakValueHashMap<K, V, S> + where K: Eq + Hash, + V: WeakElement, + V1: WeakElement, + V::Strong: PartialEq<V1::Strong>, + S: BuildHasher, + S1: BuildHasher +{ + fn eq(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool { + self.is_submap(other) && other.domain_is_subset(self) + } +} + +impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> Eq for WeakValueHashMap<K, V, S> + where V::Strong: Eq +{ } + +impl<K: Eq + Hash, V: WeakElement, S: BuildHasher + Default> Default for WeakValueHashMap<K, V, S> { + fn default() -> Self { + WeakValueHashMap::with_hasher(Default::default()) + } +} + +impl<K, V, S> ::std::iter::FromIterator<(K, V::Strong)> for WeakValueHashMap<K, V, S> + where K: Eq + Hash, + V: WeakElement, + S: BuildHasher + Default +{ + fn from_iter<T: IntoIterator<Item=(K, V::Strong)>>(iter: T) -> Self { + let mut result = WeakValueHashMap::with_hasher(Default::default()); + result.extend(iter); + result + } +} + +impl<K, V, S> Extend<(K, V::Strong)> for WeakValueHashMap<K, V, S> + where K: Eq + Hash, + V: WeakElement, + S: BuildHasher +{ + fn extend<T: IntoIterator<Item=(K, V::Strong)>>(&mut self, iter: T) { + for (key, value) in iter { + self.insert(key, value); + } + } +} + +impl<'a, K, V, S> Extend<(&'a K, &'a V::Strong)> for WeakValueHashMap<K, V, S> + where K: 'a + Eq + Hash + Clone, + V: 'a + WeakElement, + V::Strong: Clone, + S: BuildHasher +{ + fn extend<T: IntoIterator<Item=(&'a K, &'a V::Strong)>>(&mut self, iter: T) { + for (key, value) in iter { + self.insert(key.clone(), value.clone()); + } + } +} + +enum BucketStatus<V: WeakElement> { + Unoccupied, + MatchesKey(V::Strong), + ProbeDistance(usize), +} + +impl<'a, K: Eq + Hash, V: WeakElement> InnerEntry<'a, K, V> { + // Gets the status of the current bucket. + fn bucket_status(&self) -> BucketStatus<V> { + match &self.map.buckets[self.pos] { + Some(bucket) => { + if bucket.2 == self.hash_code { + if let Some(value) = bucket.1.view() { + if self.key == bucket.0 { + return BucketStatus::MatchesKey(value); + } + } + } + + let dist = self.probe_distance(self.pos, + self.which_bucket(bucket.2)); + BucketStatus::ProbeDistance(dist) + }, + None => BucketStatus::Unoccupied, + } + } +} + +impl<'a, K, V: WeakElement> Entry<'a, K, V> { + /// Ensures a value is in the entry by inserting a default value + /// if empty. + pub fn or_insert(self, default: V::Strong) -> V::Strong { + self.or_insert_with(|| default) + } + + /// Ensures a value is in the entry by inserting the result of the + /// default function if empty. + pub fn or_insert_with<F: FnOnce() -> V::Strong>(self, default: F) -> V::Strong { + match self { + Entry::Occupied(occupied) => occupied.get_strong(), + Entry::Vacant(vacant) => vacant.insert(default()), + } + } + + /// Returns a reference to this entry's key. + pub fn key(&self) -> &K { + match *self { + Entry::Occupied(ref occupied) => occupied.key(), + Entry::Vacant(ref vacant) => vacant.key(), + } + } +} + +impl<'a, K, V: WeakElement> OccupiedEntry<'a, K, V> { + /// Gets a reference to the key held by the entry. + pub fn key(&self) -> &K { + &self.inner.key + } + + /// Takes ownership of the key and value from the map. + pub fn remove_entry(self) -> (K, V::Strong) { + let (key, w_value, _) = self.inner.map.buckets[self.inner.pos].take().unwrap(); + let value = w_value.view().unwrap(); + self.inner.map.remove_index(self.inner.pos); + (key, value) + } + + /// Gets a reference to the value in the entry. + pub fn get(&self) -> &V::Strong { + &self.value + } + + /// Gets a copy of the strong value reference stored in the entry. + pub fn get_strong(&self) -> V::Strong { + V::clone(&self.value) + } + + /// Replaces the value in the entry with the given value, returning the old value. + pub fn insert(&mut self, value: V::Strong) -> V::Strong { + self.inner.map.buckets[self.inner.pos].as_mut().unwrap().1 = V::new(&value); + mem::replace(&mut self.value, value) + } + + /// Removes the entry, returning the value. + pub fn remove(self) -> V::Strong { + self.remove_entry().1 + } +} + +impl<'a, K, V: WeakElement> VacantEntry<'a, K, V> { + /// Gets a reference to the key that would be used when inserting a + /// value through the `VacantEntry`. + pub fn key(&self) -> &K { + &self.inner.key + } + + /// Returns ownership of the key. + pub fn into_key(self) -> K { + self.inner.key + } + + /// Inserts the value into the map, returning the same value. + pub fn insert(self, value: V::Strong) -> V::Strong { + let InnerEntry { map, key, hash_code, pos } = self.inner; + + let old_bucket = mem::replace( + &mut map.buckets[pos], + Some((key, V::new(&value), hash_code))); + + if let Some(full_bucket) = old_bucket { + let next_bucket = map.next_bucket(pos); + map.steal(next_bucket, full_bucket); + } + + map.len += 1; + + value + } +} + +impl<K, V: WeakElement> WeakValueInnerMap<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.1.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().1.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 WeakValueInnerMap<K, V> { + fn capacity(&self) -> usize { + self.buckets.len() + } +} + +impl<K, V, S> ModuloCapacity for WeakValueHashMap<K, V, S> { + fn capacity(&self) -> usize { + self.inner.capacity() + } +} + +impl<'a, K, V: WeakElement> ModuloCapacity for InnerEntry<'a, K, V> { + fn capacity(&self) -> usize { + self.map.capacity() + } +} + +impl<'a, K, V: WeakElement> ModuloCapacity for OccupiedEntry<'a, K, V> { + fn capacity(&self) -> usize { + self.inner.capacity() + } +} + +impl<'a, K, V: WeakElement> ModuloCapacity for VacantEntry<'a, K, V> { + fn capacity(&self) -> usize { + self.inner.capacity() + } +} + +impl<K, V> Debug for WeakValueInnerMap<K, V> + where K: Debug, + V: WeakElement, + V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + write!(f, "{{ ")?; + for (i, bucket) in self.buckets.iter().enumerate() { + if let Some((k, v, _)) = bucket { + write!(f, "[{}] {:?} => {:?}, ", i, *k, v.view())?; + } + } + write!(f, "}}") + } +} + +impl<K: Debug, V: WeakElement, S> Debug for WeakValueHashMap<K, V, S> + where V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.inner.fmt(f) + } +} + +impl<'a, K: Debug, V: WeakElement> Debug for Entry<'a, K, V> + where V::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: Debug, V: WeakElement> Debug for OccupiedEntry<'a, K, V> + where V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.inner.fmt(f) + } +} + +impl<'a, K: Debug, V: WeakElement> Debug for VacantEntry<'a, K, V> + where V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.inner.fmt(f) + } +} + +impl<'a, K: Debug, V: WeakElement> Debug for InnerEntry<'a, K, V> + where V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + write!(f, "InnerEntry {{ pos = {}, buckets = {:?} }}", self.pos, self.map) + } +} + +impl<K, V: WeakElement, S> IntoIterator for WeakValueHashMap<K, V, S> { + type Item = (K, V::Strong); + type IntoIter = IntoIter<K, V>; + + fn into_iter(self) -> Self::IntoIter { + IntoIter { + size: self.inner.len, + base: self.inner.buckets.into_vec().into_iter(), + } + } +} + +impl<'a, K, V: WeakElement, S> IntoIterator for &'a WeakValueHashMap<K, V, S> { + type Item = (&'a K, V::Strong); + type IntoIter = Iter<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + Iter { + base: self.inner.buckets.iter(), + size: self.inner.len, + } + } +} + +impl<K, V: WeakElement, S> WeakValueHashMap<K, V, S> { + /// Gets an iterator over the keys and values. + pub fn iter(&self) -> Iter<K, V> { + self.into_iter() + } + + /// Gets an iterator over the keys. + pub fn keys(&self) -> Keys<K, V> { + Keys(self.iter()) + } + + /// Gets an iterator over the values. + pub fn values(&self) -> Values<K, V> { + Values(self.iter()) + } + + /// Gets a draining iterator, which removes all the values but retains the storage. + 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, + } + } +} + + diff --git a/src/weak_weak_hash_map.rs b/src/weak_weak_hash_map.rs new file mode 100644 index 0000000..0ed89f6 --- /dev/null +++ b/src/weak_weak_hash_map.rs @@ -0,0 +1,902 @@ +//! A hash map where the keys and values are both held by weak pointers, and keys are compared by +//! value. + +use std::borrow::Borrow; +use std::cmp::max; +use std::collections::hash_map::RandomState; +use std::hash::{BuildHasher, Hash, Hasher}; +use std::fmt::{self, Debug, Formatter}; +use std::mem; + +use super::*; +use super::size_policy::*; +use super::traits::*; +use super::util::*; + +pub use super::WeakWeakHashMap; + +/// Represents an entry in the table which may be occupied or vacant. +pub enum Entry<'a, K: 'a + WeakKey, V: 'a + WeakElement> { + 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 + WeakElement> { + inner: InnerEntry<'a, K, V>, + value: V::Strong, +} + +/// A vacant entry, which can be inserted in or viewed. +pub struct VacantEntry<'a, K: 'a + WeakKey, V: 'a + WeakElement> { + inner: InnerEntry<'a, K, V>, +} + +struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> { + map: &'a mut WeakWeakInnerMap<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: ::std::slice::Iter<'a, Bucket<K, V>>, + size: usize, +} + +impl<'a, K: WeakElement, V: WeakElement> Iterator for Iter<'a, K, V> { + type Item = (K::Strong, V::Strong); + + fn next(&mut self) -> Option<Self::Item> { + while let Some(bucket) = self.base.next() { + if let Some((ref weak_key, ref weak_value, _)) = *bucket { + self.size -= 1; + if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) { + return Some((key, 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: WeakElement> 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: WeakElement> Iterator for Values<'a, K, V> { + type Item = V::Strong; + + 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: ::std::slice::IterMut<'a, Bucket<K, V>>, + size: usize, +} + +impl<'a, K: WeakElement, V: WeakElement> Iterator for Drain<'a, K, V> { + type Item = (K::Strong, V::Strong); + + fn next(&mut self) -> Option<Self::Item> { + while let Some(bucket) = self.base.next() { + if let Some((weak_key, weak_value, _)) = bucket.take() { + self.size -= 1; + if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) { + return Some((key, 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) { + while let Some(option) = self.base.next() { + *option = None; + } + } +} + +/// An iterator that consumes the values of a weak hash map, leaving it empty. +pub struct IntoIter<K, V> { + base: ::std::vec::IntoIter<Bucket<K, V>>, + size: usize, +} + +impl<K: WeakElement, V: WeakElement> Iterator for IntoIter<K, V> { + type Item = (K::Strong, V::Strong); + + fn next(&mut self) -> Option<Self::Item> { + while let Some(bucket) = self.base.next() { + if let Some((weak_key, weak_value, _)) = bucket { + self.size -= 1; + if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) { + return Some((key, value)); + } + } + } + + None + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (0, Some(self.size)) + } +} + +impl<K: WeakKey, V: WeakElement> WeakWeakHashMap<K, V, RandomState> +{ + /// Creates an empty `WeakWeakHashMap`. + pub fn new() -> Self { + Self::with_capacity(DEFAULT_INITIAL_CAPACITY) + } + + /// Creates an empty `WeakWeakHashMap` with the given capacity. + pub fn with_capacity(capacity: usize) -> Self { + Self::with_capacity_and_hasher(capacity, Default::default()) + } +} + +impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> { + /// Creates an empty `WeakWeakHashMap` with the given capacity and hasher. + pub fn with_hasher(hash_builder: S) -> Self { + Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder) + } + + /// Creates an empty `WeakWeakHashMap` with the given capacity and hasher. + pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { + WeakWeakHashMap { + hash_builder, + inner: WeakWeakInnerMap { + buckets: new_boxed_option_slice(capacity), + len: 0, + } + } + } + + /// Returns a reference to the map's `BuildHasher`. + pub fn hasher(&self) -> &S { + &self.hash_builder + } + + /// Returns the number of elements the map can hold without reallocating. + 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. + pub fn remove_expired(&mut self) { + self.retain(|_, _| true) + } + + /// Reserves room for additional elements. + 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. + 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. + 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. + 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. + 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. + 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 = K::with_key(&key, |k| self.hash(k)); + 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(value) => + return Entry::Occupied(OccupiedEntry {value, 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. + pub fn clear(&mut self) { + self.drain(); + } + + fn find_bucket<Q>(&self, key: &Q) -> Option<(usize, K::Strong, V::Strong)> + where Q: ?Sized + Hash + Eq, + K::Key: Borrow<Q> + { + if self.capacity() == 0 { return None; } + + let hash_code = self.hash(key); + let mut pos = self.which_bucket(hash_code); + + for dist in 0 .. self.capacity() { + if let Some((ref w_key, ref w_value, b_hash_code)) = self.inner.buckets[pos] { + if b_hash_code == hash_code { + if let (Some(b_key), Some(b_value)) = (w_key.view(), w_value.view()) { + if K::with_key(&b_key, |k| k.borrow() == key) { + return Some((pos, b_key, b_value)); + } + } + } + + let bucket_dist = + self.probe_distance(pos, self.which_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. + pub fn get<Q>(&self, key: &Q) -> Option<V::Strong> + where Q: ?Sized + Hash + Eq, + K::Key: Borrow<Q> + { + self.find_bucket(key).map(|tup| tup.2) + } + + /// Returns the strong reference to the key, if present. + 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 strong references to both the key and the value, if present. + pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, V::Strong)> + where Q: ?Sized + Hash + Eq, + K::Key: Borrow<Q> + { + self.find_bucket(key).map(|tup| (tup.1, tup.2)) + } + + /// Returns true if the map contains the specified key. + pub fn contains_key<Q>(&self, key: &Q) -> bool + where Q: ?Sized + Hash + Eq, + K::Key: Borrow<Q> + { + self.find_bucket(key).is_some() + } + + /// Unconditionally inserts the value, returning the old value if already present. + /// + /// Unlike `std::collections::HashMap`, this replaces the key even if occupied. + pub fn insert(&mut self, key: K::Strong, value: V::Strong) -> Option<V::Strong> { + 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. + pub fn remove<Q>(&mut self, key: &Q) -> Option<V::Strong> + where Q: ?Sized + Hash + Eq, + K::Key: Borrow<Q> + { + if let Some((pos, _, value)) = self.find_bucket(key) { + self.inner.remove_index(pos); + Some(value) + } else { + None + } + } + + /// Removes all mappings not satisfying the given predicate. + /// + /// Also removes any expired mappings. + pub fn retain<F>(&mut self, mut f: F) + where F: FnMut(K::Strong, V::Strong) -> bool + { + for i in 0 .. self.capacity() { + let remove = match self.inner.buckets[i] { + None => false, + Some(ref bucket) => + match (bucket.0.view(), bucket.1.view()) { + (Some(key), Some(value)) => !f(key, value), + _ => true, + } + }; + + if remove { + self.inner.remove_index(i); + } + } + } + + /// Is this map a submap of the other, using the given value comparison. + /// + /// In particular, all the keys of `self` must be in `other` and the values must compare + /// `true` with `value_equal`. + pub fn is_submap_with<F, S1, V1>(&self, other: &WeakWeakHashMap<K, V1, S1>, + mut value_equal: F) -> bool + where V1: WeakElement, + F: FnMut(V::Strong, V1::Strong) -> bool, + S1: BuildHasher + { + for (key, value1) in self { + if let Some(value2) = K::with_key(&key, |k| other.get(k)) { + if !value_equal(value1, value2) { + return false; + } + } else { + return false; + } + } + + true + } + + /// Is `self` a submap of `other`? + pub fn is_submap<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool + where V1: WeakElement, + V::Strong: PartialEq<V1::Strong>, + S1: BuildHasher + { + self.is_submap_with(other, |v, v1| v == v1) + } + + /// Are the keys of `self` a subset of the keys of `other`? + pub fn domain_is_subset<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool + where V1: WeakElement, + S1: BuildHasher + { + self.is_submap_with(other, |_, _| true) + } + + fn hash<Q>(&self, key: &Q) -> HashCode + where Q: ?Sized + Hash, + K::Key: Borrow<Q> + { + let mut hasher = self.hash_builder.build_hasher(); + key.hash(&mut hasher); + HashCode(hasher.finish()) + } +} + +impl<K, V, V1, S, S1> PartialEq<WeakWeakHashMap<K, V1, S1>> for WeakWeakHashMap<K, V, S> + where K: WeakKey, + V: WeakElement, + V1: WeakElement, + V::Strong: PartialEq<V1::Strong>, + S: BuildHasher, + S1: BuildHasher +{ + fn eq(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool { + self.is_submap(other) && other.domain_is_subset(self) + } +} + +impl<K: WeakKey, V: WeakElement, S: BuildHasher> Eq for WeakWeakHashMap<K, V, S> + where V::Strong: Eq +{ } + +impl<K: WeakKey, V: WeakElement, S: BuildHasher + Default> Default for WeakWeakHashMap<K, V, S> { + fn default() -> Self { + WeakWeakHashMap::with_hasher(Default::default()) + } +} + +impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S> + where K: WeakKey, + V: WeakElement, + S: BuildHasher + Default +{ + fn from_iter<T: IntoIterator<Item=(K::Strong, V::Strong)>>(iter: T) -> Self { + let mut result = WeakWeakHashMap::with_hasher(Default::default()); + result.extend(iter); + result + } +} + +impl<K, V, S> Extend<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S> + where K: WeakKey, + V: WeakElement, + S: BuildHasher +{ + fn extend<T: IntoIterator<Item=(K::Strong, V::Strong)>>(&mut self, iter: T) { + for (key, value) in iter { + self.insert(key, value); + } + } +} + +enum BucketStatus<V: WeakElement> { + Unoccupied, + MatchesKey(V::Strong), + ProbeDistance(usize), +} + +impl<'a, K: WeakKey, V: WeakElement> InnerEntry<'a, K, V> { + // Gets the status of the current bucket. + fn bucket_status(&self) -> BucketStatus<V> { + match &self.map.buckets[self.pos] { + Some(bucket) => { + if bucket.2 == self.hash_code { + if let (Some(key), Some(value)) = (bucket.0.view(), bucket.1.view()) { + if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) { + return BucketStatus::MatchesKey(value); + } + } + } + + let dist = self.probe_distance(self.pos, + self.which_bucket(bucket.2)); + BucketStatus::ProbeDistance(dist) + }, + None => BucketStatus::Unoccupied, + } + } +} + +impl<'a, K: WeakKey, V: WeakElement> 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. + pub fn or_insert(self, default: V::Strong) -> V::Strong { + 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. + pub fn or_insert_with<F: FnOnce() -> V::Strong>(self, default: F) -> V::Strong { + match self { + Entry::Occupied(occupied) => occupied.get_strong(), + Entry::Vacant(vacant) => vacant.insert(default()), + } + } + + /// Returns a reference to this entry's key. + 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: WeakElement> OccupiedEntry<'a, K, V> { + /// Gets a reference to the key held by the entry. + pub fn key(&self) -> &K::Strong { + &self.inner.key + } + + /// Takes ownership of the key and value from the map. + pub fn remove_entry(self) -> (K::Strong, V::Strong) { + let (_, w_value, _) = self.inner.map.buckets[self.inner.pos].take().unwrap(); + let value = w_value.view().unwrap(); + self.inner.map.remove_index(self.inner.pos); + (self.inner.key, value) + } + + /// Gets a reference to the value in the entry. + pub fn get(&self) -> &V::Strong { + &self.value + } + + /// Gets a clone of the reference to the value in the entry. + pub fn get_strong(&self) -> V::Strong { + V::clone(&self.value) + } + + /// Replaces the value in the entry with the given value. + pub fn insert(&mut self, value: V::Strong) -> V::Strong { + self.inner.map.buckets[self.inner.pos].as_mut().unwrap().1 = V::new(&value); + mem::replace(&mut self.value, value) + } + + /// Removes the entry, returning the value. + pub fn remove(self) -> V::Strong { + self.remove_entry().1 + } +} + +impl<'a, K: WeakKey, V: WeakElement> VacantEntry<'a, K, V> { + /// Gets a reference to the key that would be used when inserting a + /// value through the `VacantEntry`. + pub fn key(&self) -> &K::Strong { + &self.inner.key + } + + /// Returns ownership of the key. + pub fn into_key(self) -> K::Strong { + self.inner.key + } + + /// Inserts the key and value into the map, returning the same value. + pub fn insert(self, value: V::Strong) -> V::Strong { + let old_bucket = mem::replace( + &mut self.inner.map.buckets[self.inner.pos], + Some((K::new(&self.inner.key), V::new(&value), self.inner.hash_code))); + + if let Some(full_bucket) = old_bucket { + let next_bucket = self.next_bucket(self.inner.pos); + self.inner.map.steal(next_bucket, full_bucket); + } + + self.inner.map.len += 1; + + value + } +} + +impl<K: WeakKey, V: WeakElement> WeakWeakInnerMap<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() || bucket.1.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; } + + let expired = { + let bucket = self.buckets[src].as_ref().unwrap(); + bucket.0.is_expired() || bucket.1.is_expired() + }; + + if !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 WeakWeakInnerMap<K, V> { + fn capacity(&self) -> usize { + self.buckets.len() + } +} + +impl<K, V, S> ModuloCapacity for WeakWeakHashMap<K, V, S> { + fn capacity(&self) -> usize { + self.inner.capacity() + } +} + +impl<'a, K: WeakKey, V: WeakElement> ModuloCapacity for InnerEntry<'a, K, V> { + fn capacity(&self) -> usize { + self.map.capacity() + } +} + +impl<'a, K: WeakKey, V: WeakElement> ModuloCapacity for OccupiedEntry<'a, K, V> { + fn capacity(&self) -> usize { + self.inner.capacity() + } +} + +impl<'a, K: WeakKey, V: WeakElement> ModuloCapacity for VacantEntry<'a, K, V> { + fn capacity(&self) -> usize { + self.inner.capacity() + } +} + +impl<K, V> Debug for WeakWeakInnerMap<K, V> + where K: WeakElement, + K::Strong: Debug, + V: WeakElement, + V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + write!(f, "{{ ")?; + for (i, bucket) in self.buckets.iter().enumerate() { + if let Some((k, v, _)) = bucket { + write!(f, "[{}] {:?} => {:?}, ", i, k.view(), v.view())?; + } + } + write!(f, "}}") + } +} + +impl<K: WeakElement, V: WeakElement, S> Debug for WeakWeakHashMap<K, V, S> + where K::Strong: Debug, + V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.inner.fmt(f) + } +} + +impl<'a, K: WeakKey, V: WeakElement> Debug for Entry<'a, K, V> + where K::Strong: Debug, + V::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: WeakElement> Debug for OccupiedEntry<'a, K, V> + where K::Strong: Debug, + V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.inner.fmt(f) + } +} + +impl<'a, K: WeakKey, V: WeakElement> Debug for VacantEntry<'a, K, V> + where K::Strong: Debug, + V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + self.inner.fmt(f) + } +} + +impl<'a, K: WeakKey, V: WeakElement> Debug for InnerEntry<'a, K, V> + where K::Strong: Debug, + V::Strong: Debug +{ + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + write!(f, "InnerEntry {{ pos = {}, buckets = {:?} }}", self.pos, self.map) + } +} + +impl<K: WeakElement, V: WeakElement, S> IntoIterator for WeakWeakHashMap<K, V, S> { + type Item = (K::Strong, V::Strong); + type IntoIter = IntoIter<K, V>; + + fn into_iter(self) -> Self::IntoIter { + IntoIter { + size: self.inner.len, + base: self.inner.buckets.into_vec().into_iter(), + } + } +} + +impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a WeakWeakHashMap<K, V, S> { + type Item = (K::Strong, V::Strong); + type IntoIter = Iter<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + Iter { + base: self.inner.buckets.iter(), + size: self.inner.len, + } + } +} + +impl<K: WeakElement, V: WeakElement, S> WeakWeakHashMap<K, V, S> { + /// Gets an iterator over the keys and values. + pub fn iter(&self) -> Iter<K, V> { + self.into_iter() + } + + /// Gets an iterator over the keys. + pub fn keys(&self) -> Keys<K, V> { + Keys(self.iter()) + } + + /// Gets an iterator over the values. + pub fn values(&self) -> Values<K, V> { + Values(self.iter()) + } + + /// Gets a draining iterator, which removes all the values but retains the storage. + 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, + } + } +} + diff --git a/tests/symbols.rs b/tests/symbols.rs new file mode 100644 index 0000000..4f01b0d --- /dev/null +++ b/tests/symbols.rs @@ -0,0 +1,54 @@ +extern crate weak_table; + +use weak_table::WeakHashSet; +use std::ops::Deref; +use std::rc::{Rc, Weak}; + +#[derive(Clone, Debug)] +pub struct Symbol(Rc<str>); + +impl PartialEq for Symbol { + fn eq(&self, other: &Symbol) -> bool { + Rc::ptr_eq(&self.0, &other.0) + } +} + +impl Eq for Symbol {} + +impl Deref for Symbol { + type Target = str; + fn deref(&self) -> &str { + &self.0 + } +} + +#[derive(Debug, Default)] +pub struct SymbolTable(WeakHashSet<Weak<str>>); + +impl SymbolTable { + pub fn new() -> Self { + Self::default() + } + + pub fn intern(&mut self, name: &str) -> Symbol { + if let Some(rc) = self.0.get(name) { + Symbol(rc) + } else { + let rc = Rc::<str>::from(name); + self.0.insert(Rc::clone(&rc)); + Symbol(rc) + } + } +} + +#[test] +fn interning() { + let mut tab = SymbolTable::new(); + + let a0 = tab.intern("a"); + let a1 = tab.intern("a"); + let b = tab.intern("b"); + + assert_eq!(a0, a1); + assert_ne!(a0, b); +} diff --git a/tests/weak_key_hash_map.rs b/tests/weak_key_hash_map.rs new file mode 100644 index 0000000..fe18890 --- /dev/null +++ b/tests/weak_key_hash_map.rs @@ -0,0 +1,163 @@ +use std::collections::HashMap; +use std::fmt::Debug; +use std::hash::Hash; +use std::rc::{Rc, Weak}; + +use rand::Rng; +use quickcheck::{Arbitrary, Gen, quickcheck}; + +use weak_table::WeakKeyHashMap; + +use self::Cmd::*; + +fn test_script<K, V>(script: &Script<K, V>) -> bool + where K: Clone + Debug + Eq + Hash, + V: Clone + Debug + Eq +{ + let mut tester = Tester::with_capacity(4); + tester.execute_script(script); + tester.check() +} + +quickcheck! { + fn prop_u8_u8(script: Script<u8, u8>) -> bool { + test_script(&script) + } + + fn prop_string_usize(script: Script<String, usize>) -> bool { + test_script(&script) + } +} + +#[derive(Clone, Debug)] +pub enum Cmd<K, V> +{ + Insert(K, V), + Reinsert(usize, V), + RemoveInserted(usize), + RemoveOther(K), + ForgetInserted(usize), +} + +#[derive(Clone, Debug)] +pub struct Script<K, V>(Vec<Cmd<K, V>>); + +#[derive(Clone, Debug)] +pub struct Tester<K: Hash + Eq, V> { + weak: WeakKeyHashMap<Weak<K>, V>, + strong: HashMap<Rc<K>, V>, + log: Vec<K>, +} + +impl<K, V> Tester<K, V> + where K: Hash + Eq + Clone + Debug, + V: Eq + Clone + Debug +{ + pub fn new() -> Self { + Tester::with_capacity(8) + } + + pub fn with_capacity(capacity: usize) -> Self { + Tester { + weak: WeakKeyHashMap::with_capacity(capacity), + strong: HashMap::new(), + log: Vec::new(), + } + } + + pub fn check(&self) -> bool { + let copy = self.weak.iter().map(|(k, v)| (k, v.clone())).collect(); + if self.strong == copy { +// eprintln!("Tester::check: succeeded: {:?}", self.weak); + true + } else { + eprintln!("Tester::check: failed: {:?} ≠ {:?}", self.strong, copy); + false + } + } + + pub fn execute_script(&mut self, script: &Script<K, V>) { +// eprintln!("\n*** Starting script ***"); + for cmd in &script.0 { + self.execute_command(cmd); + } + } + + pub fn execute_command(&mut self, cmd: &Cmd<K, V>) { +// eprintln!("Executing command: {:?}", cmd); + match *cmd { + Insert(ref k, ref v) => self.insert(k, v, true), + Reinsert(index, ref v) => self.reinsert(index, v), + RemoveInserted(index) => self.remove_inserted(index), + RemoveOther(ref k) => self.remove_other(k), + ForgetInserted(index) => self.forget_inserted(index), + } +// eprintln!("Table state: {:?}", self.weak); + } + + pub fn insert(&mut self, key: &K, value: &V, log: bool) { + let key_ptr = Rc::new(key.clone()); + self.weak.insert(key_ptr.clone(), value.clone()); + self.strong.remove(key); + self.strong.insert(key_ptr, value.clone()); + if log { self.log.push(key.clone()); } + } + + pub fn reinsert(&mut self, index: usize, value: &V) { + if let Some(key) = self.nth_key_mod_len(index) { + self.insert(&key, value, false); + } + } + + pub fn remove_inserted(&mut self, index: usize) { + if let Some(key) = self.nth_key_mod_len(index) { + self.strong.remove(&key); + self.weak.remove(&key); + } + } + + pub fn remove_other(&mut self, key: &K) { + self.strong.remove(key); + self.weak.remove(key); + } + + pub fn forget_inserted(&mut self, index: usize) { + if let Some(key) = self.nth_key_mod_len(index) { + self.strong.remove(&key); + } + } + + fn nth_key_mod_len(&self, n: usize) -> Option<K> + { + if self.log.is_empty() { + None + } else { + Some(self.log[n % self.log.len()].clone()) + } + } +} + +impl<K: Arbitrary, V: Arbitrary> Arbitrary for Cmd<K, V> { + fn arbitrary<G: Gen>(g: &mut G) -> Self { + let choice = g.gen_range(0, 100); + + match choice { + 00..=39 => Insert(K::arbitrary(g), V::arbitrary(g)), + 40..=49 => Reinsert(usize::arbitrary(g), V::arbitrary(g)), + 50..=69 => RemoveInserted(usize::arbitrary(g)), + 70..=79 => RemoveOther(K::arbitrary(g)), + 80..=99 => ForgetInserted(usize::arbitrary(g)), + _ => unreachable!(), + } + } +} + +impl<K: Arbitrary, V: Arbitrary> Arbitrary for Script<K, V> { + fn arbitrary<G: Gen>(g: &mut G) -> Self { + Script(Vec::<Cmd<K, V>>::arbitrary(g)) + } + + fn shrink(&self) -> Box<dyn Iterator<Item=Self>> { + Box::new(self.0.shrink().map(|v| Script(v))) + } +} |