1use std::borrow::Borrow;
2use std::cell::{Cell, UnsafeCell};
3use std::collections::hash_map::RandomState;
4use std::collections::BTreeMap;
5use std::collections::HashMap;
6use std::hash::{BuildHasher, Hash};
7use std::iter::FromIterator;
8use std::ops::Index;
9
10use stable_deref_trait::StableDeref;
11
12/// Append-only version of `std::collections::HashMap` where
13/// insertion does not require mutable access
14pub 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
26impl<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
70impl<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
148impl<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
177impl<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
211impl<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
221impl<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
230impl<Q: ?Sized, K, V, S> Index<&Q> for FrozenMap<K, V, S>
231where
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
254impl<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
264impl<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
273impl<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
286impl<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
301pub 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
313impl<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
357impl<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
435impl<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
464impl<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
474impl<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
483impl<Q: ?Sized, K, V> Index<&Q> for FrozenBTreeMap<K, V>
484where
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
506impl<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
516impl<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
525impl<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
538impl<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