1 //! This library offers a variety of weak hash tables: 2 //! 3 //! - For a hash map where the keys are held by weak pointers and compared by key value, see 4 //! [`WeakKeyHashMap`](struct.WeakKeyHashMap.html). 5 //! 6 //! - For a hash map where the keys are held by weak pointers and compared by pointer, see 7 //! [`PtrWeakKeyHashMap`](struct.PtrWeakKeyHashMap.html). 8 //! 9 //! - For a hash map where the values are held by weak pointers, see 10 //! [`WeakValueHashMap`](struct.WeakValueHashMap.html). 11 //! 12 //! - For a hash map where the keys and values are both held by weak pointers and the keys are 13 //! compared by value, see 14 //! [`WeakWeakHashMap`](struct.WeakWeakHashMap.html). 15 //! 16 //! - For a hash map where the keys and values are both held by weak pointers and the keys are 17 //! compared by pointer, see 18 //! [`PtrWeakWeakHashMap`](struct.PtrWeakWeakHashMap.html). 19 //! 20 //! - For a hash set where the elements are held by weak pointers and compared by element value, see 21 //! [`WeakHashSet`](struct.WeakHashSet.html). 22 //! 23 //! - For a hash set where the elements are held by weak pointers and compared by pointer, see 24 //! [`PtrWeakHashSet`](struct.PtrWeakHashSet.html). 25 //! 26 //! To add support for your own weak pointers, see 27 //! [the traits `WeakElement` and `WeakKey`](traits/). 28 //! 29 //! ## Rust version support 30 //! 31 //! This crate supports Rust version 1.46 and later. 32 //! 33 //! ## Asymptotic complexity 34 //! 35 //! Most operations have documented asymptotic time complexities. When time complexities are 36 //! given in big-*O* notation, the following parameters are used consistently: 37 //! 38 //! - *n*: the *capacity* of the map or set being accessed or constructed 39 //! 40 //! - *m*: the *capacity* of a second map/set involved in a submap/subset operation 41 //! 42 //! - *p*: the length of the probe sequence for the key in question 43 //! 44 //! Note that *p* ∈ *O*(*n*), but we expect it to be *O*(1). 45 //! 46 //! # Crate features 47 //! 48 //! `weak-table` is built with the `std` feature, which enables 49 //! functionality dependent on the `std` library, enabled by default. 50 //! Optionally, the following dependency may be enabled: 51 //! 52 //! - `ahash`: use `ahash`’s hasher rather than the `std` hasher 53 //! 54 //! If the `std` feature is disabled (for no_std) then the `ahash` dependency **must** be enabled. 55 //! 56 //! # Examples 57 //! 58 //! Here we create a weak hash table mapping strings to integers. 59 //! Note that after dropping `one`, the key `"one"` is no longer present in the map. 60 //! This is because the map holds the strings as `std::sync::Weak<str>`s. 61 //! 62 //! ``` 63 //! use weak_table::WeakKeyHashMap; 64 //! use std::sync::{Arc, Weak}; 65 //! 66 //! let mut table = <WeakKeyHashMap<Weak<str>, u32>>::new(); 67 //! let one = Arc::<str>::from("one"); 68 //! let two = Arc::<str>::from("two"); 69 //! 70 //! table.insert(one.clone(), 1); 71 //! 72 //! assert_eq!( table.get("one"), Some(&1) ); 73 //! assert_eq!( table.get("two"), None ); 74 //! 75 //! table.insert(two.clone(), 2); 76 //! *table.get_mut(&one).unwrap() += 10; 77 //! 78 //! assert_eq!( table.get("one"), Some(&11) ); 79 //! assert_eq!( table.get("two"), Some(&2) ); 80 //! 81 //! drop(one); 82 //! 83 //! assert_eq!( table.get("one"), None ); 84 //! assert_eq!( table.get("two"), Some(&2) ); 85 //! ``` 86 //! 87 //! Here we use a weak hash set to implement a simple string interning facility: 88 //! 89 //! ``` 90 //! use weak_table::WeakHashSet; 91 //! use std::ops::Deref; 92 //! use std::rc::{Rc, Weak}; 93 //! 94 //! #[derive(Clone, Debug)] 95 //! pub struct Symbol(Rc<str>); 96 //! 97 //! impl PartialEq for Symbol { 98 //! fn eq(&self, other: &Symbol) -> bool { 99 //! Rc::ptr_eq(&self.0, &other.0) 100 //! } 101 //! } 102 //! 103 //! impl Eq for Symbol {} 104 //! 105 //! impl Deref for Symbol { 106 //! type Target = str; 107 //! fn deref(&self) -> &str { 108 //! &self.0 109 //! } 110 //! } 111 //! 112 //! #[derive(Debug, Default)] 113 //! pub struct SymbolTable(WeakHashSet<Weak<str>>); 114 //! 115 //! impl SymbolTable { 116 //! pub fn new() -> Self { 117 //! Self::default() 118 //! } 119 //! 120 //! pub fn intern(&mut self, name: &str) -> Symbol { 121 //! if let Some(rc) = self.0.get(name) { 122 //! Symbol(rc) 123 //! } else { 124 //! let rc = Rc::<str>::from(name); 125 //! self.0.insert(Rc::clone(&rc)); 126 //! Symbol(rc) 127 //! } 128 //! } 129 //! } 130 //! 131 //! #[test] 132 //! fn interning() { 133 //! let mut tab = SymbolTable::new(); 134 //! 135 //! let a0 = tab.intern("a"); 136 //! let a1 = tab.intern("a"); 137 //! let b = tab.intern("b"); 138 //! 139 //! assert_eq!(a0, a1); 140 //! assert_ne!(a0, b); 141 //! } 142 //! ``` 143 144 #![doc(html_root_url = "https://docs.rs/weak-table/0.3.2")] 145 146 #![cfg_attr(not(feature = "std"), no_std)] 147 148 use self::compat::*; 149 150 pub mod traits; 151 pub mod weak_key_hash_map; 152 pub mod ptr_weak_key_hash_map; 153 pub mod weak_value_hash_map; 154 pub mod weak_weak_hash_map; 155 pub mod ptr_weak_weak_hash_map; 156 pub mod weak_hash_set; 157 pub mod ptr_weak_hash_set; 158 159 mod compat; 160 mod util; 161 mod by_ptr; 162 mod size_policy; 163 164 #[derive(Copy, Clone, Debug, PartialEq, Eq)] 165 struct HashCode(u64); 166 167 type FullBucket<K, V> = (K, V, HashCode); 168 type Bucket<K, V> = Option<FullBucket<K, V>>; 169 type TablePtr<K, V> = Box<[Bucket<K, V>]>; 170 171 /// A hash map with weak keys, hashed on key value. 172 /// 173 /// When a weak pointer expires, its mapping is lazily removed. 174 #[derive(Clone)] 175 pub struct WeakKeyHashMap<K, V, S = RandomState> { 176 hash_builder: S, 177 inner: WeakKeyInnerMap<K, V>, 178 } 179 180 #[derive(Clone)] 181 struct WeakKeyInnerMap<K, V> { 182 buckets: TablePtr<K, V>, 183 len: usize, 184 } 185 186 /// A hash map with weak keys, hashed on key pointer. 187 /// 188 /// When a weak pointer expires, its mapping is lazily removed. 189 /// 190 /// # Examples 191 /// 192 /// ``` 193 /// use weak_table::PtrWeakKeyHashMap; 194 /// use std::rc::{Rc, Weak}; 195 /// 196 /// type Table = PtrWeakKeyHashMap<Weak<str>, usize>; 197 /// 198 /// let mut map = Table::new(); 199 /// let a = Rc::<str>::from("hello"); 200 /// let b = Rc::<str>::from("hello"); 201 /// 202 /// map.insert(a.clone(), 5); 203 /// 204 /// assert_eq!( map.get(&a), Some(&5) ); 205 /// assert_eq!( map.get(&b), None ); 206 /// 207 /// map.insert(b.clone(), 7); 208 /// 209 /// assert_eq!( map.get(&a), Some(&5) ); 210 /// assert_eq!( map.get(&b), Some(&7) ); 211 /// ``` 212 #[derive(Clone)] 213 pub struct PtrWeakKeyHashMap<K, V, S = RandomState>( 214 WeakKeyHashMap<by_ptr::ByPtr<K>, V, S> 215 ); 216 217 /// A hash map with weak values. 218 /// 219 /// When a weak pointer expires, its mapping is lazily removed. 220 #[derive(Clone)] 221 pub struct WeakValueHashMap<K, V, S = RandomState> { 222 hash_builder: S, 223 inner: WeakValueInnerMap<K, V>, 224 } 225 226 #[derive(Clone)] 227 struct WeakValueInnerMap<K, V> { 228 buckets: TablePtr<K, V>, 229 len: usize, 230 } 231 232 /// A hash map with weak keys and weak values, hashed on key value. 233 /// 234 /// When a weak pointer expires, its mapping is lazily removed. 235 #[derive(Clone)] 236 pub struct WeakWeakHashMap<K, V, S = RandomState> { 237 hash_builder: S, 238 inner: WeakWeakInnerMap<K, V>, 239 } 240 241 #[derive(Clone)] 242 struct WeakWeakInnerMap<K, V> { 243 buckets: TablePtr<K, V>, 244 len: usize, 245 } 246 247 /// A hash map with weak keys and weak values, hashed on key pointer. 248 /// 249 /// When a weak pointer expires, its mapping is lazily removed. 250 #[derive(Clone)] 251 pub struct PtrWeakWeakHashMap<K, V, S = RandomState>( 252 WeakWeakHashMap<by_ptr::ByPtr<K>, V, S> 253 ); 254 255 /// A hash set with weak elements, hashed on element value. 256 /// 257 /// When a weak pointer expires, its mapping is lazily removed. 258 #[derive(Clone)] 259 pub struct WeakHashSet<T, S = RandomState>(WeakKeyHashMap<T, (), S>); 260 261 /// A hash set with weak elements, hashed on element pointer. 262 /// 263 /// When a weak pointer expires, its mapping is lazily removed. 264 #[derive(Clone)] 265 pub struct PtrWeakHashSet<T, S = RandomState>(PtrWeakKeyHashMap<T, (), S>); 266 267