| //! 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/). |
| //! |
| //! ## Rust version support |
| //! |
| //! This crate supports Rust version 1.46 and later. |
| //! |
| //! ## Asymptotic complexity |
| //! |
| //! Most operations have documented asymptotic time complexities. When time complexities are |
| //! given in big-*O* notation, the following parameters are used consistently: |
| //! |
| //! - *n*: the *capacity* of the map or set being accessed or constructed |
| //! |
| //! - *m*: the *capacity* of a second map/set involved in a submap/subset operation |
| //! |
| //! - *p*: the length of the probe sequence for the key in question |
| //! |
| //! Note that *p* ∈ *O*(*n*), but we expect it to be *O*(1). |
| //! |
| //! # Crate features |
| //! |
| //! `weak-table` is built with the `std` feature, which enables |
| //! functionality dependent on the `std` library, enabled by default. |
| //! Optionally, the following dependency may be enabled: |
| //! |
| //! - `ahash`: use `ahash`’s hasher rather than the `std` hasher |
| //! |
| //! If the `std` feature is disabled (for no_std) then the `ahash` dependency **must** be enabled. |
| //! |
| //! # 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); |
| //! } |
| //! ``` |
| |
| #![doc(html_root_url = "https://docs.rs/weak-table/0.3.2")] |
| |
| #![cfg_attr(not(feature = "std"), no_std)] |
| |
| use self::compat::*; |
| |
| 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 compat; |
| 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>); |
| |