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: ?Sized>(&self, k: &Q) -> Option<&V::Target>
101 where
102 K: Borrow<Q>,
103 Q: Hash + Eq,
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: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T>
132 where
133 K: Borrow<Q>,
134 Q: Hash + Eq,
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 pub fn into_map(self) -> HashMap<K, V, S> {
148 self.map.into_inner()
149 }
150
151 // TODO add more
152}
153
154impl<K: Eq + Hash + StableDeref, V: StableDeref, S: BuildHasher> FrozenMap<K, V, S> {
155 /// Returns a reference to the key and value matching a borrowed
156 /// key.
157 ///
158 /// The key argument may be any borrowed form of the map's key type,
159 /// but [`Hash`] and [`Eq`] on the borrowed form *must* match those
160 /// for the key type.
161 ///
162 /// # Examples
163 ///
164 /// ```
165 /// use elsa::FrozenMap;
166 ///
167 /// let map = FrozenMap::new();
168 /// map.insert(Box::new("1"), Box::new("a"));
169 /// assert_eq!(map.get_key_value(&"1"), Some((&"1", &"a")));
170 /// assert_eq!(map.get_key_value(&"2"), None);
171 /// ```
172 pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K::Target, &V::Target)>
173 where
174 K: Borrow<Q>,
175 Q: Hash + Eq,
176 {
177 assert!(!self.in_use.get());
178 self.in_use.set(true);
179 let ret = unsafe {
180 let map = self.map.get();
181 (*map).get_key_value(k).map(|(k, v)| (&**k, &**v))
182 };
183 self.in_use.set(false);
184 ret
185 }
186}
187
188impl<K, V, S> std::convert::AsMut<HashMap<K, V, S>> for FrozenMap<K, V, S> {
189 /// Get mutable access to the underlying [`HashMap`].
190 ///
191 /// This is safe, as it requires a `&mut self`, ensuring nothing is using
192 /// the 'frozen' contents.
193 fn as_mut(&mut self) -> &mut HashMap<K, V, S> {
194 unsafe { &mut *self.map.get() }
195 }
196}
197
198impl<K, V, S> From<HashMap<K, V, S>> for FrozenMap<K, V, S> {
199 fn from(map: HashMap<K, V, S>) -> Self {
200 Self {
201 map: UnsafeCell::new(map),
202 in_use: Cell::new(false),
203 }
204 }
205}
206
207impl<Q: ?Sized, K, V, S> Index<&Q> for FrozenMap<K, V, S>
208where
209 Q: Eq + Hash,
210 K: Eq + Hash + Borrow<Q>,
211 V: StableDeref,
212 S: BuildHasher,
213{
214 type Output = V::Target;
215
216 /// # Examples
217 ///
218 /// ```
219 /// use elsa::FrozenMap;
220 ///
221 /// let map = FrozenMap::new();
222 /// map.insert(1, Box::new("a"));
223 /// assert_eq!(map[&1], "a");
224 /// ```
225 fn index(&self, idx: &Q) -> &V::Target {
226 self.get(idx)
227 .expect(msg:"attempted to index FrozenMap with unknown key")
228 }
229}
230
231impl<K: Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> for FrozenMap<K, V, S> {
232 fn from_iter<T>(iter: T) -> Self
233 where
234 T: IntoIterator<Item = (K, V)>,
235 {
236 let map: HashMap<_, _, _> = iter.into_iter().collect();
237 map.into()
238 }
239}
240
241impl<K: Eq + Hash, V, S: Default> Default for FrozenMap<K, V, S> {
242 fn default() -> Self {
243 Self {
244 map: UnsafeCell::new(Default::default()),
245 in_use: Cell::new(false),
246 }
247 }
248}
249
250/// Append-only version of `std::collections::BTreeMap` where
251/// insertion does not require mutable access
252pub struct FrozenBTreeMap<K, V> {
253 map: UnsafeCell<BTreeMap<K, V>>,
254 /// Eq/Hash implementations can have side-effects, and using Rc it is possible
255 /// for FrozenBTreeMap::insert to be called on a key that itself contains the same
256 /// `FrozenBTreeMap`, whose `eq` implementation also calls FrozenBTreeMap::insert
257 ///
258 /// We use this `in_use` flag to guard against any reentrancy.
259 in_use: Cell<bool>,
260}
261
262// safety: UnsafeCell implies !Sync
263
264impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> {
265 pub fn new() -> Self {
266 Self {
267 map: UnsafeCell::new(Default::default()),
268 in_use: Cell::new(false),
269 }
270 }
271
272 /// # Examples
273 ///
274 /// ```
275 /// use elsa::FrozenBTreeMap;
276 ///
277 /// let map = FrozenBTreeMap::new();
278 /// assert_eq!(map.len(), 0);
279 /// map.insert(1, Box::new("a"));
280 /// assert_eq!(map.len(), 1);
281 /// ```
282 pub fn len(&self) -> usize {
283 assert!(!self.in_use.get());
284 self.in_use.set(true);
285 let len = unsafe {
286 let map = self.map.get();
287 (*map).len()
288 };
289 self.in_use.set(false);
290 len
291 }
292
293 /// # Examples
294 ///
295 /// ```
296 /// use elsa::FrozenBTreeMap;
297 ///
298 /// let map = FrozenBTreeMap::new();
299 /// assert_eq!(map.is_empty(), true);
300 /// map.insert(1, Box::new("a"));
301 /// assert_eq!(map.is_empty(), false);
302 /// ```
303 pub fn is_empty(&self) -> bool {
304 self.len() == 0
305 }
306}
307
308impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> {
309 // these should never return &K or &V
310 // these should never delete any entries
311 pub fn insert(&self, k: K, v: V) -> &V::Target {
312 assert!(!self.in_use.get());
313 self.in_use.set(true);
314 let ret = unsafe {
315 let map = self.map.get();
316 &*(*map).entry(k).or_insert(v)
317 };
318 self.in_use.set(false);
319 ret
320 }
321
322 /// Returns a reference to the value corresponding to the key.
323 ///
324 /// The key may be any borrowed form of the map's key type, but
325 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
326 /// the key type.
327 ///
328 /// # Examples
329 ///
330 /// ```
331 /// use elsa::FrozenBTreeMap;
332 ///
333 /// let map = FrozenBTreeMap::new();
334 /// map.insert(1, Box::new("a"));
335 /// assert_eq!(map.get(&1), Some(&"a"));
336 /// assert_eq!(map.get(&2), None);
337 /// ```
338 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target>
339 where
340 K: Borrow<Q>,
341 Q: Ord,
342 {
343 assert!(!self.in_use.get());
344 self.in_use.set(true);
345 let ret = unsafe {
346 let map = self.map.get();
347 (*map).get(k).map(|x| &**x)
348 };
349 self.in_use.set(false);
350 ret
351 }
352
353 /// Applies a function to the owner of the value corresponding to the key (if any).
354 ///
355 /// The key may be any borrowed form of the map's key type, but
356 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
357 /// the key type.
358 ///
359 /// # Examples
360 ///
361 /// ```
362 /// use elsa::FrozenBTreeMap;
363 ///
364 /// let map = FrozenBTreeMap::new();
365 /// map.insert(1, Box::new("a"));
366 /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a")));
367 /// assert_eq!(map.map_get(&2, Clone::clone), None);
368 /// ```
369 pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T>
370 where
371 K: Borrow<Q>,
372 Q: Ord,
373 F: FnOnce(&V) -> T,
374 {
375 assert!(!self.in_use.get());
376 self.in_use.set(true);
377 let ret = unsafe {
378 let map = self.map.get();
379 (*map).get(k).map(f)
380 };
381 self.in_use.set(false);
382 ret
383 }
384
385 pub fn into_map(self) -> BTreeMap<K, V> {
386 self.map.into_inner()
387 }
388
389 // TODO add more
390}
391
392impl<K, V> std::convert::AsMut<BTreeMap<K, V>> for FrozenBTreeMap<K, V> {
393 /// Get mutable access to the underlying [`HashMap`].
394 ///
395 /// This is safe, as it requires a `&mut self`, ensuring nothing is using
396 /// the 'frozen' contents.
397 fn as_mut(&mut self) -> &mut BTreeMap<K, V> {
398 unsafe { &mut *self.map.get() }
399 }
400}
401
402impl<K: Clone + Ord, V: StableDeref> From<BTreeMap<K, V>> for FrozenBTreeMap<K, V> {
403 fn from(map: BTreeMap<K, V>) -> Self {
404 Self {
405 map: UnsafeCell::new(map),
406 in_use: Cell::new(false),
407 }
408 }
409}
410
411impl<Q: ?Sized, K, V> Index<&Q> for FrozenBTreeMap<K, V>
412where
413 Q: Ord,
414 K: Clone + Ord + Borrow<Q>,
415 V: StableDeref,
416{
417 type Output = V::Target;
418
419 /// # Examples
420 ///
421 /// ```
422 /// use elsa::FrozenBTreeMap;
423 ///
424 /// let map = FrozenBTreeMap::new();
425 /// map.insert(1, Box::new("a"));
426 /// assert_eq!(map[&1], "a");
427 /// ```
428 fn index(&self, idx: &Q) -> &V::Target {
429 self.get(idx)
430 .expect(msg:"attempted to index FrozenBTreeMap with unknown key")
431 }
432}
433
434impl<K: Clone + Ord, V: StableDeref> FromIterator<(K, V)> for FrozenBTreeMap<K, V> {
435 fn from_iter<T>(iter: T) -> Self
436 where
437 T: IntoIterator<Item = (K, V)>,
438 {
439 let map: BTreeMap<_, _> = iter.into_iter().collect();
440 map.into()
441 }
442}
443
444impl<K: Clone + Ord, V: StableDeref> Default for FrozenBTreeMap<K, V> {
445 fn default() -> Self {
446 Self {
447 map: UnsafeCell::new(Default::default()),
448 in_use: Cell::new(false),
449 }
450 }
451}
452