once_map/
unsync.rs

1use crate::{map, map::HashMap, Equivalent, InfallibleResult, ToOwnedEquivalent};
2use core::{
3    cell::RefCell,
4    fmt,
5    hash::{BuildHasher, Hash},
6};
7#[cfg(feature = "serde")]
8use serde_core as serde;
9use stable_deref_trait::StableDeref;
10
11unsafe fn extend_lifetime<'a, T: StableDeref>(ptr: &T) -> &'a T::Target {
12    &*(&**ptr as *const T::Target)
13}
14
15pub struct OnceMap<K, V, S = crate::RandomState> {
16    map: RefCell<HashMap<K, V>>,
17    hash_builder: S,
18}
19
20impl<K, V> OnceMap<K, V> {
21    /// Creates an empty `OnceMap`.
22    pub fn new() -> Self {
23        Self::with_hasher(crate::RandomState::new())
24    }
25}
26
27impl<K, V, S> OnceMap<K, V, S> {
28    /// Creates an empty `OnceMap` which will use the given hash builder to hash keys.
29    pub const fn with_hasher(hash_builder: S) -> Self {
30        let map = RefCell::new(HashMap::new());
31        Self { map, hash_builder }
32    }
33
34    pub fn len(&self) -> usize {
35        self.map.borrow().len()
36    }
37
38    pub fn is_empty(&self) -> bool {
39        self.map.borrow().is_empty()
40    }
41
42    /// Returns a reference to the map's [`BuildHasher`].
43    pub fn hasher(&self) -> &S {
44        &self.hash_builder
45    }
46
47    /// Locks the whole map for reading.
48    ///
49    /// This enables more methods, such as iterating on the maps, but will cause
50    /// a panic if trying to insert values in the map while the view is live.
51    pub fn read_only_view(&self) -> ReadOnlyView<'_, K, V, S> {
52        ReadOnlyView::new(self)
53    }
54
55    /// Removes all key-value pairs from the map, but keeps the allocated memory.
56    pub fn clear(&mut self) {
57        self.map.get_mut().clear();
58    }
59
60    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
61        self.map.get_mut().values_mut()
62    }
63
64    pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
65        self.map.get_mut().iter_mut()
66    }
67
68    #[allow(clippy::should_implement_trait)]
69    pub fn into_iter(self) -> impl Iterator<Item = (K, V)> {
70        self.map.into_inner().into_iter()
71    }
72}
73
74#[cfg(feature = "rayon")]
75#[cfg_attr(docsrs, doc(cfg(feature = "rayon")))]
76impl<K, V, S> OnceMap<K, V, S>
77where
78    K: Send,
79    V: Send,
80{
81    pub fn into_par_iter(self) -> impl rayon::iter::ParallelIterator<Item = (K, V)> {
82        self.map.into_inner().into_par_iter()
83    }
84}
85
86impl<K, V, S> OnceMap<K, V, S>
87where
88    K: Eq + Hash,
89    S: BuildHasher,
90{
91    fn hash_one<Q>(&self, key: &Q) -> u64
92    where
93        Q: Hash + Equivalent<K> + ?Sized,
94    {
95        crate::hash_one(&self.hash_builder, key)
96    }
97
98    /// Returns `true` if the map contains a value for the specified key.
99    pub fn contains_key<Q>(&self, key: &Q) -> bool
100    where
101        Q: Hash + Equivalent<K> + ?Sized,
102    {
103        let hash = self.hash_one(key);
104        self.map.borrow().contains_key(hash, key)
105    }
106
107    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
108    where
109        Q: Hash + Equivalent<K> + ?Sized,
110    {
111        let hash = self.hash_one(key);
112        self.map.get_mut().remove(hash, key)
113    }
114
115    pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
116    where
117        Q: Hash + Equivalent<K> + ?Sized,
118    {
119        let hash = self.hash_one(key);
120        self.map.get_mut().remove_entry(hash, key)
121    }
122}
123
124impl<K, V, S> OnceMap<K, V, S>
125where
126    K: Eq + Hash,
127    S: BuildHasher,
128    V: StableDeref,
129{
130    /// Returns a reference to the value corresponding to the key.
131    pub fn get<Q>(&self, key: &Q) -> Option<&V::Target>
132    where
133        Q: Hash + Equivalent<K> + ?Sized,
134    {
135        self.map_get(key, |_, v| unsafe { extend_lifetime(v) })
136    }
137
138    /// Returns a reference to the value corresponding to the key or insert one
139    /// with the given closure.
140    pub fn insert(&self, key: K, make_val: impl FnOnce(&K) -> V) -> &V::Target {
141        self.map_insert(key, make_val, |_, v| unsafe { extend_lifetime(v) })
142    }
143
144    /// Same as `insert` but the closure is allowed to fail.
145    ///
146    /// If the closure is called and an error is returned, no value is stored in
147    /// the map.
148    pub fn try_insert<E>(
149        &self,
150        key: K,
151        make_val: impl FnOnce(&K) -> Result<V, E>,
152    ) -> Result<&V::Target, E> {
153        self.map_try_insert(key, make_val, |_, v| unsafe { extend_lifetime(v) })
154    }
155}
156
157impl<K, V, S> OnceMap<K, V, S>
158where
159    K: Eq + Hash,
160    S: BuildHasher,
161    V: Clone,
162{
163    pub fn get_cloned<Q>(&self, key: &Q) -> Option<V>
164    where
165        Q: Hash + Equivalent<K> + ?Sized,
166    {
167        self.map_get(key, |_, v| v.clone())
168    }
169
170    pub fn insert_cloned(&self, key: K, make_val: impl FnOnce(&K) -> V) -> V {
171        self.map_insert(key, make_val, |_, v| v.clone())
172    }
173
174    pub fn try_insert_cloned<E>(
175        &self,
176        key: K,
177        make_val: impl FnOnce(&K) -> Result<V, E>,
178    ) -> Result<V, E> {
179        self.map_try_insert(key, make_val, |_, v| v.clone())
180    }
181}
182
183impl<K, V, S> OnceMap<K, V, S>
184where
185    K: Eq + Hash,
186    S: BuildHasher,
187{
188    pub fn map_get<Q, T>(&self, key: &Q, with_result: impl FnOnce(&K, &V) -> T) -> Option<T>
189    where
190        Q: Hash + Equivalent<K> + ?Sized,
191    {
192        let map = self.map.borrow();
193        let hash = self.hash_one(key);
194        let (key, value) = map.get_key_value(hash, key)?;
195        Some(with_result(key, value))
196    }
197
198    pub fn map_insert<T>(
199        &self,
200        key: K,
201        make_val: impl FnOnce(&K) -> V,
202        with_result: impl FnOnce(&K, &V) -> T,
203    ) -> T {
204        self.map_try_insert(key, |k| Ok(make_val(k)), with_result)
205            .unwrap_infallible()
206    }
207
208    pub fn map_insert_ref<Q, T>(
209        &self,
210        key: &Q,
211        make_key: impl FnOnce(&Q) -> K,
212        make_val: impl FnOnce(&K) -> V,
213        with_result: impl FnOnce(&K, &V) -> T,
214    ) -> T
215    where
216        Q: Hash + Equivalent<K> + ?Sized,
217    {
218        self.map_try_insert_ref(key, make_key, |k| Ok(make_val(k)), with_result)
219            .unwrap_infallible()
220    }
221
222    pub fn map_try_insert<T, E>(
223        &self,
224        key: K,
225        make_val: impl FnOnce(&K) -> Result<V, E>,
226        with_result: impl FnOnce(&K, &V) -> T,
227    ) -> Result<T, E> {
228        self.get_or_try_insert(
229            key,
230            with_result,
231            |with_result, k| {
232                let v = make_val(k)?;
233                let ret = with_result(k, &v);
234                Ok((v, ret))
235            },
236            |with_result, k, v| with_result(k, v),
237        )
238    }
239
240    pub fn map_try_insert_ref<Q, T, E>(
241        &self,
242        key: &Q,
243        make_key: impl FnOnce(&Q) -> K,
244        make_val: impl FnOnce(&K) -> Result<V, E>,
245        with_result: impl FnOnce(&K, &V) -> T,
246    ) -> Result<T, E>
247    where
248        Q: Hash + Equivalent<K> + ?Sized,
249    {
250        self.get_or_try_insert_ref(
251            key,
252            with_result,
253            make_key,
254            |with_result, k| {
255                let v = make_val(k)?;
256                let ret = with_result(k, &v);
257                Ok((v, ret))
258            },
259            |with_result, k, v| with_result(k, v),
260        )
261    }
262
263    pub fn get_or_try_insert<T, U, E>(
264        &self,
265        key: K,
266        data: T,
267        on_vacant: impl FnOnce(T, &K) -> Result<(V, U), E>,
268        on_occupied: impl FnOnce(T, &K, &V) -> U,
269    ) -> Result<U, E> {
270        let map = self.map.borrow();
271        let hash = self.hash_one(&key);
272
273        if let Some((key, value)) = map.get_key_value(hash, &key) {
274            return Ok(on_occupied(data, key, value));
275        }
276        drop(map);
277
278        // We must not borrow `self.map` here
279        let (value, ret) = on_vacant(data, &key)?;
280
281        self.raw_insert(hash, key, value);
282        Ok(ret)
283    }
284
285    pub fn get_or_try_insert_ref<Q, T, U, E>(
286        &self,
287        key: &Q,
288        data: T,
289        make_key: impl FnOnce(&Q) -> K,
290        on_vacant: impl FnOnce(T, &K) -> Result<(V, U), E>,
291        on_occupied: impl FnOnce(T, &K, &V) -> U,
292    ) -> Result<U, E>
293    where
294        Q: Hash + Equivalent<K> + ?Sized,
295    {
296        let map = self.map.borrow();
297        let hash = self.hash_one(key);
298
299        if let Some((key, value)) = map.get_key_value(hash, key) {
300            return Ok(on_occupied(data, key, value));
301        }
302        drop(map);
303
304        // We must not borrow `self.map` here
305        let owned_key = make_key(key);
306        debug_assert!(key.equivalent(&owned_key));
307        let (value, ret) = on_vacant(data, &owned_key)?;
308
309        self.raw_insert(hash, owned_key, value);
310        Ok(ret)
311    }
312
313    fn raw_insert(&self, hash: u64, key: K, value: V) {
314        let mut map = self.map.borrow_mut();
315        match map.entry(hash, &key, &self.hash_builder) {
316            map::Entry::Vacant(entry) => {
317                entry.insert(key, value);
318            }
319            map::Entry::Occupied(_) => panic!("re-entrant init"),
320        }
321    }
322}
323
324impl<K, V, S: Default> Default for OnceMap<K, V, S> {
325    fn default() -> Self {
326        Self::with_hasher(S::default())
327    }
328}
329
330impl<K, V, S> Extend<(K, V)> for OnceMap<K, V, S>
331where
332    K: Eq + Hash,
333    S: BuildHasher,
334{
335    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
336        iter.into_iter()
337            .for_each(|(k, v)| self.map_insert(k, |_| v, |_, _| ()))
338    }
339}
340
341impl<K, V, S> Extend<(K, V)> for &'_ OnceMap<K, V, S>
342where
343    K: Eq + Hash,
344    S: BuildHasher,
345{
346    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
347        iter.into_iter()
348            .for_each(|(k, v)| self.map_insert(k, |_| v, |_, _| ()))
349    }
350}
351
352impl<K, V, S> FromIterator<(K, V)> for OnceMap<K, V, S>
353where
354    K: Eq + Hash,
355    S: BuildHasher + Default,
356{
357    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
358        let mut map = OnceMap::default();
359        map.extend(iter);
360        map
361    }
362}
363
364impl<K, V, S, const N: usize> From<[(K, V); N]> for OnceMap<K, V, S>
365where
366    K: Eq + Hash,
367    S: BuildHasher + Default,
368{
369    fn from(array: [(K, V); N]) -> Self {
370        Self::from_iter(array)
371    }
372}
373
374#[cfg(feature = "serde")]
375#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
376impl<K, V, S> serde::Serialize for OnceMap<K, V, S>
377where
378    K: serde::Serialize,
379    V: serde::Serialize,
380{
381    fn serialize<Ser>(&self, serializer: Ser) -> Result<Ser::Ok, Ser::Error>
382    where
383        Ser: serde::Serializer,
384    {
385        serializer.collect_map(self.read_only_view().iter())
386    }
387}
388
389#[cfg(feature = "serde")]
390#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
391impl<'de, K, V, S> serde::Deserialize<'de> for OnceMap<K, V, S>
392where
393    K: Eq + Hash + serde::Deserialize<'de>,
394    V: serde::Deserialize<'de>,
395    S: BuildHasher + Default,
396{
397    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
398    where
399        D: serde::Deserializer<'de>,
400    {
401        struct OnceMapVisitor<K, V, S>(OnceMap<K, V, S>);
402
403        impl<'de, K, V, S> serde::de::Visitor<'de> for OnceMapVisitor<K, V, S>
404        where
405            K: Eq + Hash + serde::Deserialize<'de>,
406            V: serde::Deserialize<'de>,
407            S: BuildHasher,
408        {
409            type Value = OnceMap<K, V, S>;
410
411            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
412                formatter.write_str("a map")
413            }
414
415            fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
416            where
417                A: serde::de::MapAccess<'de>,
418            {
419                while let Some((key, value)) = map.next_entry()? {
420                    self.0.map_insert(key, |_| value, |_, _| ())
421                }
422
423                Ok(self.0)
424            }
425        }
426
427        deserializer.deserialize_map(OnceMapVisitor(OnceMap::default()))
428    }
429}
430
431impl<K, V, S> fmt::Debug for OnceMap<K, V, S>
432where
433    K: fmt::Debug,
434    V: fmt::Debug,
435{
436    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
437        self.map.borrow().fmt(f)
438    }
439}
440
441pub struct ReadOnlyView<'a, K, V, S = crate::RandomState> {
442    map: core::cell::Ref<'a, HashMap<K, V>>,
443    hash_builder: &'a S,
444}
445
446impl<'a, K, V, S> ReadOnlyView<'a, K, V, S> {
447    fn new(map: &'a OnceMap<K, V, S>) -> Self {
448        Self {
449            map: map.map.borrow(),
450            hash_builder: &map.hash_builder,
451        }
452    }
453
454    pub fn len(&self) -> usize {
455        self.map.len()
456    }
457
458    pub fn is_empty(&self) -> bool {
459        self.map.is_empty()
460    }
461
462    pub fn hasher(&self) -> &S {
463        self.hash_builder
464    }
465
466    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
467        self.map.iter()
468    }
469
470    pub fn keys(&self) -> impl Iterator<Item = &K> {
471        self.map.keys()
472    }
473
474    pub fn values(&self) -> impl Iterator<Item = &V> {
475        self.map.values()
476    }
477}
478
479impl<K, V, S> ReadOnlyView<'_, K, V, S>
480where
481    K: Eq + Hash,
482    S: BuildHasher,
483{
484    fn hash_one<Q>(&self, key: &Q) -> u64
485    where
486        Q: Hash + Equivalent<K> + ?Sized,
487    {
488        crate::hash_one(self.hash_builder, key)
489    }
490
491    pub fn get<Q>(&self, key: &Q) -> Option<&V>
492    where
493        Q: Hash + Equivalent<K> + ?Sized,
494    {
495        let hash = self.hash_one(key);
496        self.map.get(hash, key)
497    }
498
499    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
500    where
501        Q: Hash + Equivalent<K> + ?Sized,
502    {
503        let hash = self.hash_one(key);
504        self.map.get_key_value(hash, key)
505    }
506
507    pub fn contains_key<Q>(&self, key: &Q) -> bool
508    where
509        Q: Hash + Equivalent<K> + ?Sized,
510    {
511        let hash = self.hash_one(key);
512        self.map.contains_key(hash, key)
513    }
514}
515
516#[cfg(feature = "rayon")]
517#[cfg_attr(docsrs, doc(cfg(feature = "rayon")))]
518impl<K, V, S> ReadOnlyView<'_, K, V, S>
519where
520    K: Sync,
521    V: Sync,
522{
523    pub fn par_iter(&self) -> impl rayon::iter::ParallelIterator<Item = (&K, &V)> {
524        self.map.par_iter()
525    }
526
527    pub fn par_keys(&self) -> impl rayon::iter::ParallelIterator<Item = &K> {
528        self.map.par_keys()
529    }
530
531    pub fn par_values(&self) -> impl rayon::iter::ParallelIterator<Item = &V> {
532        self.map.par_values()
533    }
534}
535
536#[cfg(feature = "serde")]
537#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
538impl<K, V, S> serde::Serialize for ReadOnlyView<'_, K, V, S>
539where
540    K: serde::Serialize,
541    V: serde::Serialize,
542{
543    fn serialize<Ser>(&self, serializer: Ser) -> Result<Ser::Ok, Ser::Error>
544    where
545        Ser: serde::Serializer,
546    {
547        serializer.collect_map(self.iter())
548    }
549}
550
551impl<K, V, S> fmt::Debug for ReadOnlyView<'_, K, V, S>
552where
553    K: fmt::Debug,
554    V: fmt::Debug,
555{
556    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
557        f.debug_struct("ReadOnlyView")
558            .field("map", &self.map)
559            .finish()
560    }
561}
562
563/// A map where values are automatically filled at access.
564///
565/// This type has less overhead than [`crate::sync::LazyMap`] but it cannot be
566/// shared across threads.
567///
568/// ```
569/// let map = once_map::unsync::LazyMap::new(|x: &i32| x.to_string());
570///
571/// assert_eq!(&map[&3], "3");
572/// assert_eq!(map.get(&-67), "-67");
573/// ```
574pub struct LazyMap<K, V, S = crate::RandomState, F = fn(&K) -> V> {
575    map: OnceMap<K, V, S>,
576    init: F,
577}
578
579impl<K, V, F> LazyMap<K, V, crate::RandomState, F> {
580    pub fn new(f: F) -> Self {
581        Self::with_hasher(crate::RandomState::new(), f)
582    }
583}
584
585impl<K, V, S, F> LazyMap<K, V, S, F> {
586    pub const fn with_hasher(hash_builder: S, f: F) -> Self {
587        Self {
588            map: OnceMap::with_hasher(hash_builder),
589            init: f,
590        }
591    }
592
593    /// Removes all entries from the map.
594    pub fn clear(&mut self) {
595        self.map.clear();
596    }
597}
598
599impl<K, V, S, F> LazyMap<K, V, S, F>
600where
601    K: Eq + Hash,
602    S: BuildHasher,
603    F: Fn(&K) -> V,
604    V: StableDeref,
605{
606    pub fn get<Q>(&self, key: &Q) -> &V::Target
607    where
608        Q: Hash + ToOwnedEquivalent<K> + ?Sized,
609    {
610        self.map_get(key, |_, v| unsafe { extend_lifetime(v) })
611    }
612}
613
614impl<K, V, S, F> LazyMap<K, V, S, F>
615where
616    K: Eq + Hash,
617    S: BuildHasher,
618    F: Fn(&K) -> V,
619    V: Clone,
620{
621    pub fn get_cloned<Q>(&self, key: &Q) -> V
622    where
623        Q: Hash + ToOwnedEquivalent<K> + ?Sized,
624    {
625        self.map_get(key, |_, v| v.clone())
626    }
627}
628
629impl<K, V, S, F> LazyMap<K, V, S, F>
630where
631    K: Eq + Hash,
632    S: BuildHasher,
633    F: Fn(&K) -> V,
634{
635    pub fn map_get<Q, T>(&self, key: &Q, with_result: impl FnOnce(&K, &V) -> T) -> T
636    where
637        Q: Hash + ToOwnedEquivalent<K> + ?Sized,
638    {
639        self.map
640            .map_insert_ref(key, Q::to_owned_equivalent, &self.init, with_result)
641    }
642}
643
644impl<K, V, S, F> LazyMap<K, V, S, F>
645where
646    K: Eq + Hash,
647    S: BuildHasher,
648{
649    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
650    where
651        Q: Hash + Equivalent<K> + ?Sized,
652    {
653        self.map.remove(key)
654    }
655}
656
657/// Creates a `LazyMap` that fills all values with `V::default()`.
658impl<K, V: Default, S: Default> Default for LazyMap<K, V, S> {
659    fn default() -> Self {
660        Self::with_hasher(S::default(), |_| V::default())
661    }
662}
663
664impl<K, V, S, F, Q> core::ops::Index<&Q> for LazyMap<K, V, S, F>
665where
666    K: Eq + Hash,
667    S: BuildHasher,
668    F: Fn(&K) -> V,
669    V: StableDeref,
670    Q: Hash + ToOwnedEquivalent<K> + ?Sized,
671{
672    type Output = V::Target;
673
674    fn index(&self, key: &Q) -> &V::Target {
675        self.get(key)
676    }
677}
678
679impl<K, V, S> fmt::Debug for LazyMap<K, V, S>
680where
681    K: fmt::Debug,
682    V: fmt::Debug,
683{
684    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
685        f.debug_struct("LazyMap")
686            .field("values", &self.map)
687            .finish_non_exhaustive()
688    }
689}
once_map/unsync.rs

once_map/
unsync.rs
