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 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
//! An API for get-or-create operations on cache entries, similar to //! `std::collections::HashMap`'s entry API. use super::*; use std::fmt; /// A potentially-empty entry in a cache, used to perform get-or-create /// operations on the cache. /// /// Constructed via the `AssociativeCache::entry` method. pub struct Entry<'a, K, V, C, I, R> where C: Capacity, R: Replacement<V, C>, { pub(crate) cache: &'a mut AssociativeCache<K, V, C, I, R>, pub(crate) index: usize, pub(crate) kind: EntryKind, } impl<'a, K, V, C, I, R> fmt::Debug for Entry<'a, K, V, C, I, R> where C: Capacity, R: Replacement<V, C>, { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { let Entry { cache: _, ref index, ref kind, } = self; f.debug_struct("Entry") .field("index", index) .field("kind", kind) .finish() } } #[derive(Debug)] pub(crate) enum EntryKind { // The index is occupied with a cache entry for this key. Occupied, // The index is for a slot that has no entry in it. Vacant, // The index is for a slot that has a to-be-replaced entry for a // different key. Replace, } impl<'a, K, V, C, I, R> Entry<'a, K, V, C, I, R> where C: Capacity, I: Indices<K, C>, R: Replacement<V, C>, { /// Get the underlying cached data, creating and inserting it into the cache /// if it doesn't already exist. /// /// ## Differences from `std::collections::HashMap`'s `Entry` API /// /// `std::collections::HashMap`'s `Entry` API takes unconditional ownership /// of the query key, even in scenarios where there is already an entry with /// that key in the map. This means that if your keys are expensive to /// create (like `String` and its heap allocation) that you have to eagerly /// construct the key even if you don't end up needing it. /// /// In contrast, the `associative_cache::Entry` API allows you to get an /// `Entry` with just a borrow of a key, allowing you to delay the /// potentially-expensive key construction until we actually need /// it. However, this is not without drawbacks. Now the `or_insert_with` /// method needs a way to construct an owned key: the `make_key` parameter /// here. **`make_key` must return an owned key that is equivalent to the /// borrowed key that was used to get this `Entry`.** Failure to do this /// will result in an invalid cache (likely manifesting as wasted entries /// that take up space but can't ever be queried for). /// /// # Example /// /// ``` /// use associative_cache::*; /// /// let mut cache = AssociativeCache::< /// String, /// usize, /// Capacity4, /// HashTwoWay, /// RoundRobinReplacement, /// >::default(); /// /// // Get or create an entry for "hi", delaying the `&str` to `String` /// // allocation until if/when we actually insert into the cache. /// let val = cache.entry("hi").or_insert_with( /// || "hi".to_string(), /// || 42, /// ); /// /// // The cache was empty, so we inserted the default value of 42. /// assert_eq!(*val, 42); /// /// // We can modify the value. /// *val += 1; /// ``` #[inline] pub fn or_insert_with( self, make_key: impl FnOnce() -> K, make_val: impl FnOnce() -> V, ) -> &'a mut V { assert!(self.index < C::CAPACITY); match self.kind { EntryKind::Occupied => match &mut self.cache.entries[self.index] { Some((_, v)) => v, _ => unreachable!(), }, EntryKind::Vacant | EntryKind::Replace => { if let EntryKind::Vacant = self.kind { self.cache.len += 1; } self.cache.entries[self.index] = Some((make_key(), make_val())); match &mut self.cache.entries[self.index] { Some((_, v)) => { self.cache.replacement_policy.on_insert(v); v } _ => unreachable!(), } } } } /// If inserting into this `Entry` will replace another entry in the /// cache, remove that other entry from the cache and return it now. /// /// # Example /// /// ``` /// use associative_cache::*; /// /// let mut cache = AssociativeCache::< /// String, /// usize, /// Capacity256, /// HashTwoWay, /// RoundRobinReplacement, /// >::default(); /// /// cache.insert("hi".to_string(), 5); /// /// let mut entry = cache.entry("bye"); /// /// // Because this entry could replace the entry for "hi" depending on the hash /// // function in use, we have an opportunity to recover the /// // about-to-be-replaced entry here. /// if let Some((key, val)) = entry.take_entry_that_will_be_replaced() { /// assert_eq!(key, "hi"); /// assert_eq!(val, 5); /// } /// /// let val = entry.or_insert_with(|| "bye".into(), || 1337); /// assert_eq!(*val, 1337); /// ``` #[inline] pub fn take_entry_that_will_be_replaced(&mut self) -> Option<(K, V)> { assert!(self.index < C::CAPACITY); if let EntryKind::Replace = self.kind { self.cache.len -= 1; self.kind = EntryKind::Vacant; mem::replace(&mut self.cache.entries[self.index], None) } else { None } } }