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