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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

use std::collections::{BTreeMap, HashMap};
use std::hash::Hash;

/// The interface for the key-value map internal to a [`Prison`].
///
/// The Entry API is not supported, because it can't be used as is, anyway:
/// the reference passed as a key to `entry(K)` would be to something outside
/// the prison, which we absolutely don't want to store in the map. The Entry
/// API would have to be extended to allow changing the key before insertion.
///
/// [`Prison`]: struct.Prison.html
pub trait Map {
    type Key;
    type Value;

    /// Create an empty map.
    ///
    /// This is required for `Prison` to function properly.
    fn new() -> Self;

    /// Create an empty map with a capacity hint.
    ///
    /// Not all implementations may support this, making it equivalent to
    /// `Map::new`.
    fn with_capacity(usize) -> Self;

    /// Get the number of pairs in the map.
    fn len(&self) -> usize;

    /// Insert a key-value pair. If there was already an entry for the key,
    /// it gets replaced, and the previous returned.
    ///
    /// This is required for `Prison` to function properly.
    fn insert(&mut self, Self::Key, Self::Value) -> Option<Self::Value>;

    /// Get a value by its key.
    ///
    /// This is required for `Prison` to function properly.
    fn get(&self, Self::Key) -> Option<&Self::Value>;

    /// Remove a pair by its key.
    ///
    /// This is required for `Prison` to function properly.
    fn remove(&mut self, Self::Key) -> Option<Self::Value>;

    /// Reduce memory usage as much as possible.
    ///
    /// Not all implementations may support this, making it a no-op.
    fn shrink_to_fit(&mut self);
}

impl<K: Eq + Hash, V> Map for HashMap<K, V> {
    type Key = K;
    type Value = V;

    fn new() -> Self {
        HashMap::new()
    }

    fn with_capacity(capacity: usize) -> Self {
        HashMap::with_capacity(capacity)
    }

    fn len(&self) -> usize {
        self.len()
    }

    fn insert(&mut self, k: K, v: V) -> Option<V> {
        self.insert(k, v)
    }

    fn get(&self, k: K) -> Option<&V> {
        self.get(&k)
    }

    fn remove(&mut self, k: K) -> Option<V> {
        self.remove(&k)
    }

    fn shrink_to_fit(&mut self) {
        self.shrink_to_fit();
    }
}

impl<K: Eq + Ord, V> Map for BTreeMap<K, V> {
    type Key = K;
    type Value = V;

    fn new() -> Self {
        BTreeMap::new()
    }

    fn with_capacity(_: usize) -> Self {
        BTreeMap::new()
    }

    fn len(&self) -> usize {
        self.len()
    }

    fn insert(&mut self, k: K, v: V) -> Option<V> {
        self.insert(k, v)
    }

    fn get(&self, k: K) -> Option<&V> {
        self.get(&k)
    }

    fn remove(&mut self, k: K) -> Option<V> {
        self.remove(&k)
    }

    fn shrink_to_fit(&mut self) {}
}