Joel Galenson | 2370d12 | 2020-10-12 16:02:26 -0700 | [diff] [blame] | 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 | //! |
David LeGare | 77e4bb9 | 2022-03-02 16:21:23 +0000 | [diff] [blame] | 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. |
Joel Galenson | 2370d12 | 2020-10-12 16:02:26 -0700 | [diff] [blame] | 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 | |
David LeGare | 77e4bb9 | 2022-03-02 16:21:23 +0000 | [diff] [blame] | 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::*; |
Joel Galenson | 2370d12 | 2020-10-12 16:02:26 -0700 | [diff] [blame] | 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 | |
David LeGare | 77e4bb9 | 2022-03-02 16:21:23 +0000 | [diff] [blame] | 159 | mod compat; |
Joel Galenson | 2370d12 | 2020-10-12 16:02:26 -0700 | [diff] [blame] | 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 | |