1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#![deny(missing_docs)]
//! append-only
//!
//! append-only contains versions of data structures that ... only allow appends.
//! Data structures where values cannot be modified once added, combined with
//! Boxing, allow immutable references to one key's value to be handed out while
//! preserving the ability to append other key/value pairs to the structure.

use std::borrow::Borrow;
use std::collections::{hash_map, HashMap};
use std::hash::Hash;
use std::mem;
use std::ops::Deref;
use std::sync::Mutex;

/// The sync module contains append-only data structures that can be used from
/// multiple threads.
pub mod sync {
    use super::*;

    /// Like `std::collections::HashMap`, but append-only.
    #[derive(Debug)]
    pub struct AppendOnlyHashMap<K, V>(Mutex<HashMap<K, Box<V>>>);

    impl<K, V> AppendOnlyHashMap<K, V> {
        /// Creates an empty `AppendOnlyHashMap`.
        pub fn new() -> Self {
            AppendOnlyHashMap(Mutex::new(HashMap::new()))
        }

        /// Creates an empty `AppendOnlyHashMap` with the specified capacity.
        pub fn with_capacity(capacity: usize) -> Self {
            AppendOnlyHashMap(Mutex::new(HashMap::with_capacity(capacity)))
        }
    }

    impl<K, V> AppendOnlyHashMap<K, V>
    where
        K: Eq + Hash,
    {
        /// Returns a reference to the value corresponding to the key.
        pub fn get<'map, Q: ?Sized>(&'map self, key: &Q) -> Option<&'map V>
        where
            Q: Borrow<K>
        {
            let locked = self.0.lock().unwrap();
            let value_ptr = locked.get(key.borrow())?.deref() as *const V;
            mem::drop(locked);
            // Safe because this value can never be removed or mutated as long
            // as this map survives.
            Some(unsafe {
                &*value_ptr
            })
        }

        /// Returns a reference to the value corresponding to the key, invoking
        /// the provided callback if it is not already present.
        pub fn get_or_insert_with<'map, F>(&'map self, key: K, f: F) -> &'map V
        where
            F: FnOnce(&K) -> V
        {
            self.get_or_insert_with_fallible::<(), _>(key, |k| Ok(f(k))).unwrap()
        }

        /// Returns a reference to the value corresponding to the key, invoking
        /// the provided callback if it is not already present.
        pub fn get_or_insert_with_fallible<'map, E, F>(&'map self, key: K, f: F) -> Result<&'map V, E>
        where
            F: FnOnce(&K) -> Result<V, E>
        {
            let mut locked = self.0.lock().unwrap();
            let value_ptr = match locked.entry(key) {
                hash_map::Entry::Occupied(o) => o.get().deref() as *const V,
                hash_map::Entry::Vacant(v) => {
                    let value = Box::new(f(v.key())?);
                    (*v.insert(value)).deref() as *const V
                }
            };
            mem::drop(locked);
            // Safe because this value can never be removed or mutated as long
            // as this map survives.
            Ok(unsafe {
                &*value_ptr
            })
        }
    }
}