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