1 | use std::borrow::Borrow; |
2 | use std::cell::{Cell, UnsafeCell}; |
3 | use std::collections::hash_map::RandomState; |
4 | use std::collections::BTreeMap; |
5 | use std::collections::HashMap; |
6 | use std::hash::{BuildHasher, Hash}; |
7 | use std::iter::FromIterator; |
8 | use std::ops::Index; |
9 | |
10 | use stable_deref_trait::StableDeref; |
11 | |
12 | /// Append-only version of `std::collections::HashMap` where |
13 | /// insertion does not require mutable access |
14 | pub struct FrozenMap<K, V, S = RandomState> { |
15 | map: UnsafeCell<HashMap<K, V, S>>, |
16 | /// Eq/Hash implementations can have side-effects, and using Rc it is possible |
17 | /// for FrozenMap::insert to be called on a key that itself contains the same |
18 | /// `FrozenMap`, whose `eq` implementation also calls FrozenMap::insert |
19 | /// |
20 | /// We use this `in_use` flag to guard against any reentrancy. |
21 | in_use: Cell<bool>, |
22 | } |
23 | |
24 | // safety: UnsafeCell implies !Sync |
25 | |
26 | impl<K: Eq + Hash, V> FrozenMap<K, V> { |
27 | pub fn new() -> Self { |
28 | Self { |
29 | map: UnsafeCell::new(Default::default()), |
30 | in_use: Cell::new(false), |
31 | } |
32 | } |
33 | |
34 | /// # Examples |
35 | /// |
36 | /// ``` |
37 | /// use elsa::FrozenMap; |
38 | /// |
39 | /// let map = FrozenMap::new(); |
40 | /// assert_eq!(map.len(), 0); |
41 | /// map.insert(1, Box::new("a" )); |
42 | /// assert_eq!(map.len(), 1); |
43 | /// ``` |
44 | pub fn len(&self) -> usize { |
45 | assert!(!self.in_use.get()); |
46 | self.in_use.set(true); |
47 | let len = unsafe { |
48 | let map = self.map.get(); |
49 | (*map).len() |
50 | }; |
51 | self.in_use.set(false); |
52 | len |
53 | } |
54 | |
55 | /// # Examples |
56 | /// |
57 | /// ``` |
58 | /// use elsa::FrozenMap; |
59 | /// |
60 | /// let map = FrozenMap::new(); |
61 | /// assert_eq!(map.is_empty(), true); |
62 | /// map.insert(1, Box::new("a" )); |
63 | /// assert_eq!(map.is_empty(), false); |
64 | /// ``` |
65 | pub fn is_empty(&self) -> bool { |
66 | self.len() == 0 |
67 | } |
68 | } |
69 | |
70 | impl<K: Eq + Hash, V: StableDeref, S: BuildHasher> FrozenMap<K, V, S> { |
71 | // these should never return &K or &V |
72 | // these should never delete any entries |
73 | pub fn insert(&self, k: K, v: V) -> &V::Target { |
74 | assert!(!self.in_use.get()); |
75 | self.in_use.set(true); |
76 | let ret = unsafe { |
77 | let map = self.map.get(); |
78 | &*(*map).entry(k).or_insert(v) |
79 | }; |
80 | self.in_use.set(false); |
81 | ret |
82 | } |
83 | |
84 | /// Returns a reference to the value corresponding to the key. |
85 | /// |
86 | /// The key may be any borrowed form of the map's key type, but |
87 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for |
88 | /// the key type. |
89 | /// |
90 | /// # Examples |
91 | /// |
92 | /// ``` |
93 | /// use elsa::FrozenMap; |
94 | /// |
95 | /// let map = FrozenMap::new(); |
96 | /// map.insert(1, Box::new("a" )); |
97 | /// assert_eq!(map.get(&1), Some(&"a" )); |
98 | /// assert_eq!(map.get(&2), None); |
99 | /// ``` |
100 | pub fn get<Q>(&self, k: &Q) -> Option<&V::Target> |
101 | where |
102 | K: Borrow<Q>, |
103 | Q: Hash + Eq + ?Sized, |
104 | { |
105 | assert!(!self.in_use.get()); |
106 | self.in_use.set(true); |
107 | let ret = unsafe { |
108 | let map = self.map.get(); |
109 | (*map).get(k).map(|x| &**x) |
110 | }; |
111 | self.in_use.set(false); |
112 | ret |
113 | } |
114 | |
115 | /// Applies a function to the owner of the value corresponding to the key (if any). |
116 | /// |
117 | /// The key may be any borrowed form of the map's key type, but |
118 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for |
119 | /// the key type. |
120 | /// |
121 | /// # Examples |
122 | /// |
123 | /// ``` |
124 | /// use elsa::FrozenMap; |
125 | /// |
126 | /// let map = FrozenMap::new(); |
127 | /// map.insert(1, Box::new("a" )); |
128 | /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a" ))); |
129 | /// assert_eq!(map.map_get(&2, Clone::clone), None); |
130 | /// ``` |
131 | pub fn map_get<Q, T, F>(&self, k: &Q, f: F) -> Option<T> |
132 | where |
133 | K: Borrow<Q>, |
134 | Q: Hash + Eq + ?Sized, |
135 | F: FnOnce(&V) -> T, |
136 | { |
137 | assert!(!self.in_use.get()); |
138 | self.in_use.set(true); |
139 | let ret = unsafe { |
140 | let map = self.map.get(); |
141 | (*map).get(k).map(f) |
142 | }; |
143 | self.in_use.set(false); |
144 | ret |
145 | } |
146 | } |
147 | |
148 | impl<K, V, S> FrozenMap<K, V, S> { |
149 | /// Collects the contents of this map into a vector of tuples. |
150 | /// |
151 | /// The order of the entries is as if iterating a [`HashMap`] (stochastic). |
152 | /// |
153 | /// # Examples |
154 | /// |
155 | /// ``` |
156 | /// use elsa::FrozenMap; |
157 | /// |
158 | /// let map = FrozenMap::new(); |
159 | /// map.insert(1, Box::new("a" )); |
160 | /// map.insert(2, Box::new("b" )); |
161 | /// let mut tuple_vec = map.into_tuple_vec(); |
162 | /// tuple_vec.sort(); |
163 | /// |
164 | /// assert_eq!(tuple_vec, vec![(1, Box::new("a" )), (2, Box::new("b" ))]); |
165 | /// ``` |
166 | pub fn into_tuple_vec(self) -> Vec<(K, V)> { |
167 | self.map.into_inner().into_iter().collect::<Vec<_>>() |
168 | } |
169 | |
170 | pub fn into_map(self) -> HashMap<K, V, S> { |
171 | self.map.into_inner() |
172 | } |
173 | |
174 | // TODO add more |
175 | } |
176 | |
177 | impl<K: Eq + Hash + StableDeref, V: StableDeref, S: BuildHasher> FrozenMap<K, V, S> { |
178 | /// Returns a reference to the key and value matching a borrowed |
179 | /// key. |
180 | /// |
181 | /// The key argument may be any borrowed form of the map's key type, |
182 | /// but [`Hash`] and [`Eq`] on the borrowed form *must* match those |
183 | /// for the key type. |
184 | /// |
185 | /// # Examples |
186 | /// |
187 | /// ``` |
188 | /// use elsa::FrozenMap; |
189 | /// |
190 | /// let map = FrozenMap::new(); |
191 | /// map.insert(Box::new("1" ), Box::new("a" )); |
192 | /// assert_eq!(map.get_key_value(&"1" ), Some((&"1" , &"a" ))); |
193 | /// assert_eq!(map.get_key_value(&"2" ), None); |
194 | /// ``` |
195 | pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K::Target, &V::Target)> |
196 | where |
197 | K: Borrow<Q>, |
198 | Q: Hash + Eq + ?Sized, |
199 | { |
200 | assert!(!self.in_use.get()); |
201 | self.in_use.set(true); |
202 | let ret = unsafe { |
203 | let map = self.map.get(); |
204 | (*map).get_key_value(k).map(|(k, v)| (&**k, &**v)) |
205 | }; |
206 | self.in_use.set(false); |
207 | ret |
208 | } |
209 | } |
210 | |
211 | impl<K, V, S> std::convert::AsMut<HashMap<K, V, S>> for FrozenMap<K, V, S> { |
212 | /// Get mutable access to the underlying [`HashMap`]. |
213 | /// |
214 | /// This is safe, as it requires a `&mut self`, ensuring nothing is using |
215 | /// the 'frozen' contents. |
216 | fn as_mut(&mut self) -> &mut HashMap<K, V, S> { |
217 | unsafe { &mut *self.map.get() } |
218 | } |
219 | } |
220 | |
221 | impl<K, V, S> From<HashMap<K, V, S>> for FrozenMap<K, V, S> { |
222 | fn from(map: HashMap<K, V, S>) -> Self { |
223 | Self { |
224 | map: UnsafeCell::new(map), |
225 | in_use: Cell::new(false), |
226 | } |
227 | } |
228 | } |
229 | |
230 | impl<Q: ?Sized, K, V, S> Index<&Q> for FrozenMap<K, V, S> |
231 | where |
232 | Q: Eq + Hash, |
233 | K: Eq + Hash + Borrow<Q>, |
234 | V: StableDeref, |
235 | S: BuildHasher, |
236 | { |
237 | type Output = V::Target; |
238 | |
239 | /// # Examples |
240 | /// |
241 | /// ``` |
242 | /// use elsa::FrozenMap; |
243 | /// |
244 | /// let map = FrozenMap::new(); |
245 | /// map.insert(1, Box::new("a" )); |
246 | /// assert_eq!(map[&1], "a" ); |
247 | /// ``` |
248 | fn index(&self, idx: &Q) -> &V::Target { |
249 | self.get(idx) |
250 | .expect(msg:"attempted to index FrozenMap with unknown key" ) |
251 | } |
252 | } |
253 | |
254 | impl<K: Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> for FrozenMap<K, V, S> { |
255 | fn from_iter<T>(iter: T) -> Self |
256 | where |
257 | T: IntoIterator<Item = (K, V)>, |
258 | { |
259 | let map: HashMap<_, _, _> = iter.into_iter().collect(); |
260 | map.into() |
261 | } |
262 | } |
263 | |
264 | impl<K: Eq + Hash, V, S: Default> Default for FrozenMap<K, V, S> { |
265 | fn default() -> Self { |
266 | Self { |
267 | map: UnsafeCell::new(Default::default()), |
268 | in_use: Cell::new(false), |
269 | } |
270 | } |
271 | } |
272 | |
273 | impl<K: Clone, V: Clone, S: Clone> Clone for FrozenMap<K, V, S> { |
274 | fn clone(&self) -> Self { |
275 | assert!(!self.in_use.get()); |
276 | self.in_use.set(val:true); |
277 | let self_clone: FrozenMap = Self { |
278 | map: unsafe { self.map.get().as_ref().unwrap() }.clone().into(), |
279 | in_use: Cell::from(false), |
280 | }; |
281 | self.in_use.set(val:false); |
282 | self_clone |
283 | } |
284 | } |
285 | |
286 | impl<K: Eq + Hash, V: PartialEq + StableDeref> PartialEq for FrozenMap<K, V> { |
287 | fn eq(&self, other: &Self) -> bool { |
288 | assert!(!self.in_use.get()); |
289 | assert!(!other.in_use.get()); |
290 | self.in_use.set(val:true); |
291 | other.in_use.set(val:true); |
292 | let ret: bool = unsafe { self.map.get().as_ref() == other.map.get().as_ref() }; |
293 | self.in_use.set(val:false); |
294 | other.in_use.set(val:false); |
295 | ret |
296 | } |
297 | } |
298 | |
299 | /// Append-only version of `std::collections::BTreeMap` where |
300 | /// insertion does not require mutable access |
301 | pub struct FrozenBTreeMap<K, V> { |
302 | map: UnsafeCell<BTreeMap<K, V>>, |
303 | /// Eq/Hash implementations can have side-effects, and using Rc it is possible |
304 | /// for FrozenBTreeMap::insert to be called on a key that itself contains the same |
305 | /// `FrozenBTreeMap`, whose `eq` implementation also calls FrozenBTreeMap::insert |
306 | /// |
307 | /// We use this `in_use` flag to guard against any reentrancy. |
308 | in_use: Cell<bool>, |
309 | } |
310 | |
311 | // safety: UnsafeCell implies !Sync |
312 | |
313 | impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> { |
314 | pub const fn new() -> Self { |
315 | Self { |
316 | map: UnsafeCell::new(BTreeMap::new()), |
317 | in_use: Cell::new(false), |
318 | } |
319 | } |
320 | |
321 | /// # Examples |
322 | /// |
323 | /// ``` |
324 | /// use elsa::FrozenBTreeMap; |
325 | /// |
326 | /// let map = FrozenBTreeMap::new(); |
327 | /// assert_eq!(map.len(), 0); |
328 | /// map.insert(1, Box::new("a" )); |
329 | /// assert_eq!(map.len(), 1); |
330 | /// ``` |
331 | pub fn len(&self) -> usize { |
332 | assert!(!self.in_use.get()); |
333 | self.in_use.set(true); |
334 | let len = unsafe { |
335 | let map = self.map.get(); |
336 | (*map).len() |
337 | }; |
338 | self.in_use.set(false); |
339 | len |
340 | } |
341 | |
342 | /// # Examples |
343 | /// |
344 | /// ``` |
345 | /// use elsa::FrozenBTreeMap; |
346 | /// |
347 | /// let map = FrozenBTreeMap::new(); |
348 | /// assert_eq!(map.is_empty(), true); |
349 | /// map.insert(1, Box::new("a" )); |
350 | /// assert_eq!(map.is_empty(), false); |
351 | /// ``` |
352 | pub fn is_empty(&self) -> bool { |
353 | self.len() == 0 |
354 | } |
355 | } |
356 | |
357 | impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> { |
358 | // these should never return &K or &V |
359 | // these should never delete any entries |
360 | pub fn insert(&self, k: K, v: V) -> &V::Target { |
361 | assert!(!self.in_use.get()); |
362 | self.in_use.set(true); |
363 | let ret = unsafe { |
364 | let map = self.map.get(); |
365 | &*(*map).entry(k).or_insert(v) |
366 | }; |
367 | self.in_use.set(false); |
368 | ret |
369 | } |
370 | |
371 | /// Returns a reference to the value corresponding to the key. |
372 | /// |
373 | /// The key may be any borrowed form of the map's key type, but |
374 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for |
375 | /// the key type. |
376 | /// |
377 | /// # Examples |
378 | /// |
379 | /// ``` |
380 | /// use elsa::FrozenBTreeMap; |
381 | /// |
382 | /// let map = FrozenBTreeMap::new(); |
383 | /// map.insert(1, Box::new("a" )); |
384 | /// assert_eq!(map.get(&1), Some(&"a" )); |
385 | /// assert_eq!(map.get(&2), None); |
386 | /// ``` |
387 | pub fn get<Q>(&self, k: &Q) -> Option<&V::Target> |
388 | where |
389 | K: Borrow<Q>, |
390 | Q: Ord + ?Sized, |
391 | { |
392 | assert!(!self.in_use.get()); |
393 | self.in_use.set(true); |
394 | let ret = unsafe { |
395 | let map = self.map.get(); |
396 | (*map).get(k).map(|x| &**x) |
397 | }; |
398 | self.in_use.set(false); |
399 | ret |
400 | } |
401 | |
402 | /// Applies a function to the owner of the value corresponding to the key (if any). |
403 | /// |
404 | /// The key may be any borrowed form of the map's key type, but |
405 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for |
406 | /// the key type. |
407 | /// |
408 | /// # Examples |
409 | /// |
410 | /// ``` |
411 | /// use elsa::FrozenBTreeMap; |
412 | /// |
413 | /// let map = FrozenBTreeMap::new(); |
414 | /// map.insert(1, Box::new("a" )); |
415 | /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a" ))); |
416 | /// assert_eq!(map.map_get(&2, Clone::clone), None); |
417 | /// ``` |
418 | pub fn map_get<Q, T, F>(&self, k: &Q, f: F) -> Option<T> |
419 | where |
420 | K: Borrow<Q>, |
421 | Q: Ord + ?Sized, |
422 | F: FnOnce(&V) -> T, |
423 | { |
424 | assert!(!self.in_use.get()); |
425 | self.in_use.set(true); |
426 | let ret = unsafe { |
427 | let map = self.map.get(); |
428 | (*map).get(k).map(f) |
429 | }; |
430 | self.in_use.set(false); |
431 | ret |
432 | } |
433 | } |
434 | |
435 | impl<K, V> FrozenBTreeMap<K, V> { |
436 | /// Collects the contents of this map into a vector of tuples. |
437 | /// |
438 | /// The order of the entries is as if iterating a [`BTreeMap`] (ordered by key). |
439 | /// |
440 | /// # Examples |
441 | /// |
442 | /// ``` |
443 | /// use elsa::FrozenBTreeMap; |
444 | /// |
445 | /// let map = FrozenBTreeMap::new(); |
446 | /// map.insert(1, Box::new("a" )); |
447 | /// map.insert(2, Box::new("b" )); |
448 | /// let mut tuple_vec = map.into_tuple_vec(); |
449 | /// tuple_vec.sort(); |
450 | /// |
451 | /// assert_eq!(tuple_vec, vec![(1, Box::new("a" )), (2, Box::new("b" ))]); |
452 | /// ``` |
453 | pub fn into_tuple_vec(self) -> Vec<(K, V)> { |
454 | self.map.into_inner().into_iter().collect::<Vec<_>>() |
455 | } |
456 | |
457 | pub fn into_map(self) -> BTreeMap<K, V> { |
458 | self.map.into_inner() |
459 | } |
460 | |
461 | // TODO add more |
462 | } |
463 | |
464 | impl<K, V> std::convert::AsMut<BTreeMap<K, V>> for FrozenBTreeMap<K, V> { |
465 | /// Get mutable access to the underlying [`HashMap`]. |
466 | /// |
467 | /// This is safe, as it requires a `&mut self`, ensuring nothing is using |
468 | /// the 'frozen' contents. |
469 | fn as_mut(&mut self) -> &mut BTreeMap<K, V> { |
470 | unsafe { &mut *self.map.get() } |
471 | } |
472 | } |
473 | |
474 | impl<K: Clone + Ord, V: StableDeref> From<BTreeMap<K, V>> for FrozenBTreeMap<K, V> { |
475 | fn from(map: BTreeMap<K, V>) -> Self { |
476 | Self { |
477 | map: UnsafeCell::new(map), |
478 | in_use: Cell::new(false), |
479 | } |
480 | } |
481 | } |
482 | |
483 | impl<Q: ?Sized, K, V> Index<&Q> for FrozenBTreeMap<K, V> |
484 | where |
485 | Q: Ord, |
486 | K: Clone + Ord + Borrow<Q>, |
487 | V: StableDeref, |
488 | { |
489 | type Output = V::Target; |
490 | |
491 | /// # Examples |
492 | /// |
493 | /// ``` |
494 | /// use elsa::FrozenBTreeMap; |
495 | /// |
496 | /// let map = FrozenBTreeMap::new(); |
497 | /// map.insert(1, Box::new("a" )); |
498 | /// assert_eq!(map[&1], "a" ); |
499 | /// ``` |
500 | fn index(&self, idx: &Q) -> &V::Target { |
501 | self.get(idx) |
502 | .expect(msg:"attempted to index FrozenBTreeMap with unknown key" ) |
503 | } |
504 | } |
505 | |
506 | impl<K: Clone + Ord, V: StableDeref> FromIterator<(K, V)> for FrozenBTreeMap<K, V> { |
507 | fn from_iter<T>(iter: T) -> Self |
508 | where |
509 | T: IntoIterator<Item = (K, V)>, |
510 | { |
511 | let map: BTreeMap<_, _> = iter.into_iter().collect(); |
512 | map.into() |
513 | } |
514 | } |
515 | |
516 | impl<K: Clone + Ord, V: StableDeref> Default for FrozenBTreeMap<K, V> { |
517 | fn default() -> Self { |
518 | Self { |
519 | map: UnsafeCell::new(Default::default()), |
520 | in_use: Cell::new(false), |
521 | } |
522 | } |
523 | } |
524 | |
525 | impl<K: Clone, V: Clone> Clone for FrozenBTreeMap<K, V> { |
526 | fn clone(&self) -> Self { |
527 | assert!(!self.in_use.get()); |
528 | self.in_use.set(val:true); |
529 | let self_clone: FrozenBTreeMap = Self { |
530 | map: unsafe { self.map.get().as_ref().unwrap() }.clone().into(), |
531 | in_use: Cell::from(false), |
532 | }; |
533 | self.in_use.set(val:false); |
534 | self_clone |
535 | } |
536 | } |
537 | |
538 | impl<K: Eq + Hash, V: PartialEq + StableDeref> PartialEq for FrozenBTreeMap<K, V> { |
539 | fn eq(&self, other: &Self) -> bool { |
540 | assert!(!self.in_use.get()); |
541 | assert!(!other.in_use.get()); |
542 | self.in_use.set(val:true); |
543 | other.in_use.set(val:true); |
544 | let ret: bool = unsafe { self.map.get().as_ref() == other.map.get().as_ref() }; |
545 | self.in_use.set(val:false); |
546 | other.in_use.set(val:false); |
547 | ret |
548 | } |
549 | } |
550 | |