cache_2q/lib.rs
1//! A 2Q cache
2//!
3//! This cache based on the paper entitled
4//! **[2Q: A Low Overhead High-Performance Buffer Management Replacement Algorithm](http://www.vldb.org/conf/1994/P439.PDF)**.
5#![deny(
6 missing_docs,
7 missing_debug_implementations,
8 missing_copy_implementations,
9 trivial_casts,
10 trivial_numeric_casts,
11 unsafe_code,
12 unstable_features,
13 unused_import_braces,
14 unused_qualifications,
15 clippy::all
16)]
17#![warn(clippy::pedantic)]
18
19use std::borrow::Borrow;
20use std::fmt;
21use std::hash::{BuildHasher, Hash};
22use std::iter;
23
24use linked_hash_map::LinkedHashMap;
25use std::collections::hash_map::RandomState;
26
27/// A 2Q Cache which maps keys to values
28///
29/// 2Q is an enhancement over an LRU cache by tracking both recent and frequently accessed entries
30/// separately. This avoids the cache being trashed by a scan of many new items: Only the recent
31/// list will be trashed.
32///
33/// The cache is split into 3 sections, recent entries, frequent entries, and ghost entries.
34///
35/// * recent contains the most recently added entries.
36/// * frequent is an LRU cache which contains entries which are frequently accessed
37/// * ghost contains the keys which have been recently evicted from the recent cache.
38///
39/// New entries in the cache are initially placed in recent.
40/// After recent fills up, the oldest entry from recent will be removed, and its key is placed in
41/// ghost. When an entry is requested and not found, but its key is found in the ghost list,
42/// an entry is pushed to the front of frequent.
43///
44/// # Examples
45///
46/// ```
47/// use cache_2q::Cache;
48///
49/// // type inference lets us omit an explicit type signature (which
50/// // would be `Cache<&str, &str>` in this example).
51/// let mut book_reviews = Cache::new(1024);
52///
53/// // review some books.
54/// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
55/// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
56/// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
57/// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
58///
59/// // check for a specific one.
60/// if !book_reviews.contains_key("Les Misérables") {
61/// println!("We've got {} reviews, but Les Misérables ain't one.",
62/// book_reviews.len());
63/// }
64///
65/// // oops, this review has a lot of spelling mistakes, let's delete it.
66/// book_reviews.remove("The Adventures of Sherlock Holmes");
67///
68/// // look up the values associated with some keys.
69/// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
70/// for book in &to_find {
71/// match book_reviews.get(book) {
72/// Some(review) => println!("{}: {}", book, review),
73/// None => println!("{} is unreviewed.", book)
74/// }
75/// }
76///
77/// // iterate over everything.
78/// for (book, review) in &book_reviews {
79/// println!("{}: \"{}\"", book, review);
80/// }
81/// ```
82///
83/// Cache also implements an Entry API, which allows for more complex methods of getting,
84/// setting, updating and removing keys and their values:
85///
86/// ```
87/// use cache_2q::Cache;
88///
89/// // type inference lets us omit an explicit type signature (which
90/// // would be `Cache<&str, u8>` in this example).
91/// let mut player_stats = Cache::new(32);
92///
93/// fn random_stat_buff() -> u8 {
94/// // could actually return some random value here - let's just return
95/// // some fixed value for now
96/// 42
97/// }
98///
99/// // insert a key only if it doesn't already exist
100/// player_stats.entry("health").or_insert(100);
101///
102/// // insert a key using a function that provides a new value only if it
103/// // doesn't already exist
104/// player_stats.entry("defence").or_insert_with(random_stat_buff);
105///
106/// // update a key, guarding against the key possibly not being set
107/// let stat = player_stats.entry("attack").or_insert(100);
108/// *stat += random_stat_buff();
109/// ```
110#[derive(Clone, PartialEq, Eq)]
111pub struct Cache<K: Eq + Hash, V, S: BuildHasher = RandomState> {
112 recent: LinkedHashMap<K, V, S>,
113 frequent: LinkedHashMap<K, V, S>,
114 ghost: LinkedHashMap<K, (), S>,
115 size: usize,
116 ghost_size: usize,
117}
118
119impl<K: Eq + Hash, V> Cache<K, V, RandomState> {
120 /// Creates an empty cache, with the specified size
121 ///
122 /// The returned cache will have enough room for `size` recent entries,
123 /// and `size` frequent entries. In addition, up to `size * 4` keys will be kept
124 /// as remembered items
125 ///
126 /// # Examples
127 ///
128 /// ```
129 /// use cache_2q::Cache;
130 ///
131 /// let mut cache: Cache<u64, Vec<u8>> = Cache::new(8);
132 /// cache.insert(1, vec![1,2,3,4]);
133 /// assert_eq!(*cache.get(&1).unwrap(), &[1,2,3,4]);
134 /// ```
135 ///
136 /// # Panics
137 /// panics if `size` is zero. A zero-sized cache isn't very useful, and breaks some apis
138 /// (like [VacantEntry::insert], which returns a reference to the newly inserted item)
139 ///
140 /// [VacantEntry::insert]: struct.VacantEntry.html#method.insert
141 pub fn new(size: usize) -> Self {
142 Self::with_hasher(size, RandomState::new())
143 }
144}
145
146impl<K: Eq + Hash, V, S: BuildHasher + Clone> Cache<K, V, S> {
147 /// Creates an empty `Cache` with the specified capacity, using `hash_builder` to hash the keys
148 ///
149 /// The returned cache will have enough room for `size` recent entries,
150 /// and `size` frequent entries. In addition, up to `size * 4` keys will be kept
151 /// as remembered items
152 ///
153 /// # Examples
154 ///
155 /// ```
156 /// use cache_2q::Cache;
157 /// use std::collections::hash_map::DefaultHasher;
158 /// use std::hash::BuildHasherDefault;
159 ///
160 /// let mut cache: Cache<u64, Vec<u8>, BuildHasherDefault<DefaultHasher>> = Cache::with_hasher(16, BuildHasherDefault::default());
161 /// cache.insert(1, vec![1,2,3,4]);
162 /// assert_eq!(*cache.get(&1).unwrap(), &[1,2,3,4]);
163 /// ```
164 ///
165 /// # Panics
166 /// panics if `size` is zero. A zero-sized cache isn't very useful, and breaks some apis
167 /// (like [VacantEntry::insert], which returns a reference to the newly inserted item)
168 ///
169 /// [VacantEntry::insert]: struct.VacantEntry.html#method.insert
170 pub fn with_hasher(size: usize, hash_builder: S) -> Self {
171 assert!(size > 0);
172 let ghost_size = size * 4;
173 Self {
174 recent: LinkedHashMap::with_capacity_and_hasher(size, hash_builder.clone()),
175 frequent: LinkedHashMap::with_capacity_and_hasher(size, hash_builder.clone()),
176 ghost: LinkedHashMap::with_capacity_and_hasher(ghost_size, hash_builder),
177 size,
178 ghost_size,
179 }
180 }
181}
182
183impl<K: Eq + Hash, V, S: BuildHasher> Cache<K, V, S> {
184 /// Returns true if the cache contains a value for the specified key.
185 ///
186 /// The key may be any borrowed form of the cache's key type, but
187 /// Eq on the borrowed form must match those for the key type.
188 ///
189 /// # Examples
190 ///
191 /// ```
192 /// use cache_2q::Cache;
193 ///
194 /// let mut cache = Cache::new(8);
195 /// cache.insert(1, "a");
196 /// assert_eq!(cache.contains_key(&1), true);
197 /// assert_eq!(cache.contains_key(&2), false);
198 /// ```
199 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
200 where
201 K: Borrow<Q>,
202 Q: Eq + Hash,
203 {
204 self.recent.contains_key(key) || self.frequent.contains_key(key)
205 }
206
207 /// Returns a reference to the value corresponding to the key.
208 ///
209 /// The key may be any borrowed form of the cache's key type, but Eq on the borrowed form
210 /// must match those for the key type.
211 ///
212 /// Unlike [get()], the the cache will not be updated to reflect a new access of `key`.
213 /// Because the cache is not updated, `peek()` can operate without mutable access to the cache
214 ///
215 /// # Examples
216 ///
217 /// ```
218 /// use cache_2q::Cache;
219 ///
220 /// let mut cache = Cache::new(32);
221 /// cache.insert(1, "a");
222 /// let cache = cache;
223 /// // peek doesn't require mutable access to the cache
224 /// assert_eq!(cache.peek(&1), Some(&"a"));
225 /// assert_eq!(cache.peek(&2), None);
226 /// ```
227 ///
228 /// [get()]: struct.Cache.html#method.get
229 pub fn peek<Q: ?Sized>(&self, key: &Q) -> Option<&V>
230 where
231 K: Borrow<Q>,
232 Q: Eq + Hash,
233 {
234 self.recent.get(key).or_else(|| self.frequent.get(key))
235 }
236
237 /// Returns a mutable reference to the value corresponding to the key.
238 ///
239 /// The key may be any borrowed form of the cache's key type, but
240 /// Eq on the borrowed form *must* match those for
241 /// the key type.
242 ///
243 /// # Examples
244 ///
245 /// ```
246 /// use cache_2q::Cache;
247 ///
248 /// let mut cache = Cache::new(8);
249 /// cache.insert(1, "a");
250 /// if let Some(x) = cache.get(&1) {
251 /// *x = "b";
252 /// }
253 /// assert_eq!(cache.get(&1), Some(&mut "b"));
254 /// ```
255 pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
256 where
257 K: Borrow<Q>,
258 Q: Eq + Hash,
259 {
260 if let Some(value) = self.recent.get_refresh(key) {
261 return Some(value);
262 }
263 self.frequent.get_refresh(key)
264 }
265
266 /// Inserts a key-value pair into the cache.
267 ///
268 /// If the cache did not have this key present, None is returned.
269 ///
270 /// If the cache did have this key present, the value is updated, and the old
271 /// value is returned.
272 ///
273 /// # Examples
274 ///
275 /// ```
276 /// use cache_2q::Cache;
277 ///
278 /// let mut cache = Cache::new(8);
279 /// assert_eq!(cache.insert(37, "a"), None);
280 /// assert_eq!(cache.is_empty(), false);
281 ///
282 /// cache.insert(37, "b");
283 /// assert_eq!(cache.insert(37, "c"), Some("b"));
284 /// assert_eq!(*cache.get(&37).unwrap(), "c");
285 /// ```
286 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
287 match self.entry(key) {
288 Entry::Occupied(mut entry) => Some(entry.insert(value)),
289 Entry::Vacant(entry) => {
290 entry.insert(value);
291 None
292 }
293 }
294 }
295
296 /// Gets the given key's corresponding entry in the cache for in-place manipulation.
297 /// The LRU portion of the cache is not updated
298 ///
299 /// # Examples
300 ///
301 /// ```
302 /// use cache_2q::Cache;
303 ///
304 /// let mut stringified = Cache::new(8);
305 ///
306 /// for &i in &[1, 2, 5, 1, 2, 8, 1, 2, 102, 25, 1092, 1, 2, 82, 10, 1095] {
307 /// let string = stringified.peek_entry(i).or_insert_with(|| i.to_string());
308 /// assert_eq!(string, &i.to_string());
309 /// }
310 /// ```
311 pub fn peek_entry(&mut self, key: K) -> Entry<K, V, S> {
312 if self.recent.contains_key(&key) {
313 return Entry::Occupied(OccupiedEntry::new(OccupiedKind::Recent, key, &mut self.recent));
314 }
315 if self.frequent.contains_key(&key) {
316 return Entry::Occupied(OccupiedEntry::new(OccupiedKind::Frequent, key, &mut self.frequent));
317 }
318 if self.ghost.contains_key(&key) {
319 return Entry::Vacant(VacantEntry {
320 cache: self,
321 kind: VacantKind::Ghost,
322 key,
323 });
324 }
325
326 Entry::Vacant(VacantEntry {
327 cache: self,
328 kind: VacantKind::Unknown,
329 key,
330 })
331 }
332
333 /// Gets the given key's corresponding entry in the cache for in-place manipulation.
334 ///
335 /// # Examples
336 ///
337 /// ```
338 /// use cache_2q::Cache;
339 ///
340 /// let mut stringified = Cache::new(8);
341 ///
342 /// for &i in &[1, 2, 5, 1, 2, 8, 1, 2, 102, 25, 1092, 1, 2, 82, 10, 1095] {
343 /// let string = stringified.entry(i).or_insert_with(|| i.to_string());
344 /// assert_eq!(string, &i.to_string());
345 /// }
346 /// ```
347 pub fn entry(&mut self, key: K) -> Entry<K, V, S> {
348 if self.recent.get_refresh(&key).is_some() {
349 return Entry::Occupied(OccupiedEntry::new(OccupiedKind::Recent, key, &mut self.recent));
350 }
351 if self.frequent.get_refresh(&key).is_some() {
352 return Entry::Occupied(OccupiedEntry::new(OccupiedKind::Frequent, key, &mut self.frequent));
353 }
354 if self.ghost.contains_key(&key) {
355 return Entry::Vacant(VacantEntry {
356 cache: self,
357 kind: VacantKind::Ghost,
358 key,
359 });
360 }
361
362 Entry::Vacant(VacantEntry {
363 cache: self,
364 kind: VacantKind::Unknown,
365 key,
366 })
367 }
368
369 /// Returns the number of entries currently in the cache.
370 ///
371 /// # Examples
372 ///
373 /// ```
374 /// use cache_2q::Cache;
375 ///
376 /// let mut a = Cache::new(8);
377 /// assert_eq!(a.len(), 0);
378 /// a.insert(1, "a");
379 /// assert_eq!(a.len(), 1);
380 /// ```
381 pub fn len(&self) -> usize {
382 self.recent.len() + self.frequent.len()
383 }
384
385 /// Returns true if the cache contains no elements.
386 ///
387 /// # Examples
388 ///
389 /// ```
390 /// use cache_2q::Cache;
391 ///
392 /// let mut a = Cache::new(8);
393 /// assert!(a.is_empty());
394 /// a.insert(1, "a");
395 /// assert!(!a.is_empty());
396 /// ```
397 pub fn is_empty(&self) -> bool {
398 self.recent.is_empty() && self.frequent.is_empty()
399 }
400
401 /// Removes a key from the cache, returning the value associated with the key if the key
402 /// was previously in the cache.
403 ///
404 /// The key may be any borrowed form of the cache's key type, but
405 /// Eq on the borrowed form *must* match those for
406 /// the key type.
407 ///
408 /// # Examples
409 ///
410 /// ```
411 /// use cache_2q::Cache;
412 ///
413 /// let mut cache = Cache::new(8);
414 /// cache.insert(1, "a");
415 /// assert_eq!(cache.remove(&1), Some("a"));
416 /// assert_eq!(cache.remove(&1), None);
417 /// ```
418 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
419 where
420 K: Borrow<Q>,
421 Q: Eq + Hash,
422 {
423 self.recent
424 .remove(key)
425 .or_else(|| self.frequent.remove(key))
426 }
427
428 /// Clears the cache, removing all key-value pairs. Keeps the allocated memory for reuse.
429 ///
430 /// # Examples
431 ///
432 /// ```
433 /// use cache_2q::Cache;
434 ///
435 /// let mut a = Cache::new(32);
436 /// a.insert(1, "a");
437 /// a.clear();
438 /// assert!(a.is_empty());
439 /// ```
440 pub fn clear(&mut self) {
441 self.recent.clear();
442 self.ghost.clear();
443 self.frequent.clear();
444 }
445
446 /// An iterator visiting all key-value pairs in arbitrary order.
447 /// The iterator element type is `(&'a K, &'a V)`.
448 ///
449 /// # Examples
450 ///
451 /// ```
452 /// use cache_2q::Cache;
453 ///
454 /// let mut cache = Cache::new(8);
455 /// cache.insert("a", 1);
456 /// cache.insert("b", 2);
457 /// cache.insert("c", 3);
458 ///
459 /// for (key, val) in cache.iter() {
460 /// println!("key: {} val: {}", key, val);
461 /// }
462 /// ```
463 pub fn iter(&self) -> Iter<K, V> {
464 Iter {
465 inner: self.recent.iter().chain(self.frequent.iter()),
466 }
467 }
468}
469
470impl<'a, K: 'a + Eq + Hash, V: 'a> IntoIterator for &'a Cache<K, V> {
471 type Item = (&'a K, &'a V);
472 type IntoIter = Iter<'a, K, V>;
473 fn into_iter(self) -> Iter<'a, K, V> {
474 self.iter()
475 }
476}
477
478impl<K: Eq + Hash + fmt::Debug, V: fmt::Debug, S: BuildHasher> fmt::Debug for Cache<K, V, S> {
479 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
480 f.debug_map().entries(self.iter()).finish()
481 }
482}
483
484/// A view into a single entry in a cache, which may either be vacant or occupied.
485///
486/// This enum is constructed from the entry method on Cache.
487pub enum Entry<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher = RandomState> {
488 /// An occupied entry
489 Occupied(OccupiedEntry<'a, K, V, S>),
490 /// An vacant entry
491 Vacant(VacantEntry<'a, K, V, S>),
492}
493
494impl<'a, K: 'a + fmt::Debug + Eq + Hash, V: 'a + fmt::Debug, S: 'a + BuildHasher> fmt::Debug
495 for Entry<'a, K, V, S>
496{
497 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
498 match *self {
499 Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
500 Entry::Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
501 }
502 }
503}
504
505impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher> Entry<'a, K, V, S> {
506 /// Returns a reference to this entry's key.
507 ///
508 /// # Examples
509 ///
510 /// ```
511 /// use cache_2q::Cache;
512 ///
513 /// let mut cache: Cache<&str, u32> = Cache::new(8);
514 /// assert_eq!(cache.entry("poneyland").key(), &"poneyland");
515 /// ```
516 pub fn key(&self) -> &K {
517 match *self {
518 Entry::Occupied(ref entry) => entry.key(),
519 Entry::Vacant(ref entry) => entry.key(),
520 }
521 }
522
523 /// Ensures a value is in the entry by inserting the default if empty, and returns a mutable
524 /// reference to the value in the entry.
525 ///
526 /// # Examples
527 /// ```
528 /// use cache_2q::Cache;
529 ///
530 /// let mut cache = Cache::new(8);
531 /// {
532 /// let value = cache.entry(0xFF00).or_insert(0);
533 /// assert_eq!(*value, 0);
534 /// }
535 ///
536 /// *cache.entry(0xFF00).or_insert(100) += 1;
537 /// assert_eq!(*cache.get(&0xFF00).unwrap(), 1);
538 /// ```
539 pub fn or_insert(self, default: V) -> &'a mut V {
540 match self {
541 Entry::Occupied(entry) => entry.into_mut(),
542 Entry::Vacant(entry) => entry.insert(default),
543 }
544 }
545
546 /// Ensures a value is in the entry by inserting the result of the default function if empty,
547 /// and returns a mutable reference to the value in the entry.
548 ///
549 /// # Examples
550 ///
551 /// ```
552 /// use cache_2q::Cache;
553 ///
554 /// let mut cache: Cache<&'static str, String> = Cache::new(8);
555 /// cache.entry("key").or_insert_with(|| "value".to_string());
556 ///
557 /// assert_eq!(cache.get(&"key").unwrap(), &"value".to_string());
558 /// ```
559 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
560 match self {
561 Entry::Occupied(entry) => entry.into_mut(),
562 Entry::Vacant(entry) => entry.insert(default()),
563 }
564 }
565
566 /// Provides in-place mutable access to an occupied entry before any
567 /// potential inserts into the map.
568 ///
569 /// # Examples
570 /// ```
571 /// use cache_2q::Cache;
572 ///
573 /// let mut cache = Cache::new(1);
574 /// cache.entry("poneyland")
575 /// .and_modify(|e| { *e += 1 })
576 /// .or_insert(42);
577 /// assert_eq!(*cache.get("poneyland").unwrap(), 42);
578 ///
579 /// cache.entry("poneyland")
580 /// .and_modify(|e| { *e += 1 })
581 /// .or_insert(42);
582 /// assert_eq!(*cache.get("poneyland").unwrap(), 43);
583 /// ```
584 pub fn and_modify<F>(self, f: F) -> Self
585 where
586 F: FnOnce(&mut V),
587 {
588 match self {
589 Entry::Occupied(mut entry) => {
590 f(entry.get_mut());
591 Entry::Occupied(entry)
592 },
593 Entry::Vacant(entry) => Entry::Vacant(entry)
594 }
595 }
596}
597
598impl<'a, K: 'a + Eq + Hash, V: 'a + Default, S: 'a + BuildHasher> Entry<'a, K, V, S> {
599 /// Ensures a value is in the entry by inserting the default value if empty, and returns a
600 /// mutable reference to the value in the entry.
601 ///
602 /// # Examples
603 /// ```
604 /// use cache_2q::Cache;
605 ///
606 /// let mut cache = Cache::new(1);
607 /// assert_eq!(*cache.entry(1).or_default(), 0u8);
608 /// assert_eq!(cache.get(&1), Some(&mut 0))
609 /// ```
610 pub fn or_default(self) -> &'a mut V {
611 match self {
612 Entry::Occupied(entry) => entry.into_mut(),
613 Entry::Vacant(entry) => entry.insert(V::default()),
614 }
615 }
616}
617
618/// A view into an occupied entry in a [`Cache`].
619/// It is part of the [`Entry`] enum.
620///
621/// [`Cache`]: struct.Cache.html
622/// [`Entry`]: enum.Entry.html
623pub struct OccupiedEntry<'a, K: 'a + Eq + Hash, V: 'a, S: 'a = RandomState> {
624 kind: OccupiedKind,
625 entry: linked_hash_map::OccupiedEntry<'a, K, V, S>,
626}
627
628impl<'a, K: 'a + fmt::Debug + Eq + Hash, V: 'a + fmt::Debug, S: 'a + BuildHasher> fmt::Debug
629 for OccupiedEntry<'a, K, V, S>
630{
631 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
632 f.debug_struct("OccupiedEntry")
633 .field("key", self.key())
634 .field("value", self.get())
635 .field(
636 "kind",
637 &if self.kind == OccupiedKind::Frequent {
638 "frequent"
639 } else {
640 "recent"
641 },
642 )
643 .finish()
644 }
645}
646
647impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher> OccupiedEntry<'a, K, V, S> {
648 fn new(kind: OccupiedKind, key: K, map: &'a mut LinkedHashMap<K, V, S>) -> Self {
649 let entry = match map.entry(key) {
650 linked_hash_map::Entry::Occupied(entry) => entry,
651 linked_hash_map::Entry::Vacant(_) => panic!("Expected entry for key"),
652 };
653 Self {
654 kind,
655 entry,
656 }
657 }
658 /// Gets a reference to the key in the entry.
659 ///
660 /// # Examples
661 ///
662 /// ```
663 /// use cache_2q::{Cache, Entry};
664 ///
665 /// let mut cache: Cache<&str, u32> = Cache::new(8);
666 /// cache.entry("poneyland").or_insert(12);
667 /// match cache.entry("poneyland") {
668 /// Entry::Vacant(_) => {
669 /// panic!("Should be occupied");
670 /// },
671 /// Entry::Occupied(occupied) => {
672 /// assert_eq!(occupied.key(), &"poneyland");
673 /// },
674 /// }
675 /// ```
676 pub fn key(&self) -> &K {
677 self.entry.key()
678 }
679
680 /// Gets a reference to the value in the entry.
681 ///
682 /// # Examples
683 ///
684 /// ```
685 /// use cache_2q::{Cache, Entry};
686 ///
687 /// let mut cache: Cache<&str, u32> = Cache::new(8);
688 /// cache.entry("poneyland").or_insert(12);
689 ///
690 /// if let Entry::Occupied(o) = cache.entry("poneyland") {
691 /// assert_eq!(o.get(), &12);
692 /// } else {
693 /// panic!("Entry should be occupied");
694 /// }
695 /// ```
696 pub fn get(&self) -> &V {
697 self.entry.get()
698 }
699
700 /// Gets a mutable reference to the value in the entry.
701 ///
702 /// # Examples
703 ///
704 /// ```
705 /// use cache_2q::{Cache, Entry};
706 ///
707 /// let mut cache: Cache<&str, u32> = Cache::new(8);
708 /// cache.entry("poneyland").or_insert(12);
709 ///
710 /// assert_eq!(*cache.get("poneyland").unwrap(), 12);
711 /// if let Entry::Occupied(mut o) = cache.entry("poneyland") {
712 /// *o.get_mut() += 10;
713 /// } else {
714 /// panic!("Entry should be occupied");
715 /// }
716 ///
717 /// assert_eq!(*cache.get("poneyland").unwrap(), 22);
718 /// ```
719 pub fn get_mut(&mut self) -> &mut V {
720 self.entry.get_mut()
721 }
722
723 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
724 /// with a lifetime bound to the cache itself.
725 ///
726 /// # Examples
727 ///
728 /// ```
729 /// use cache_2q::{Cache, Entry};
730 ///
731 /// let mut cache: Cache<&str, u32> = Cache::new(8);
732 /// cache.entry("poneyland").or_insert(12);
733 ///
734 /// assert_eq!(*cache.get("poneyland").unwrap(), 12);
735 /// if let Entry::Occupied(o) = cache.entry("poneyland") {
736 /// *o.into_mut() += 10;
737 /// } else {
738 /// panic!("Entry should be occupied");
739 /// }
740 ///
741 /// assert_eq!(*cache.get("poneyland").unwrap(), 22);
742 /// ```
743 pub fn into_mut(self) -> &'a mut V {
744 self.entry.into_mut()
745 }
746
747 /// Sets the value of the entry, and returns the entry's old value.
748 ///
749 /// # Examples
750 ///
751 /// ```
752 /// use cache_2q::{Cache, Entry};
753 ///
754 /// let mut cache: Cache<&str, u32> = Cache::new(8);
755 /// cache.entry("poneyland").or_insert(12);
756 ///
757 /// if let Entry::Occupied(mut o) = cache.entry("poneyland") {
758 /// assert_eq!(o.insert(15), 12);
759 /// } else {
760 /// panic!("Entry should be occupied");
761 /// }
762 ///
763 /// assert_eq!(*cache.get("poneyland").unwrap(), 15);
764 /// ```
765 pub fn insert(&mut self, value: V) -> V {
766 self.entry.insert(value)
767 }
768
769 /// Takes the value out of the entry, and returns it.
770 ///
771 /// # Examples
772 ///
773 /// ```
774 /// use cache_2q::{Cache, Entry};
775 ///
776 /// let mut cache: Cache<&str, u32> = Cache::new(8);
777 /// cache.entry("poneyland").or_insert(12);
778 ///
779 /// if let Entry::Occupied(o) = cache.entry("poneyland") {
780 /// assert_eq!(o.remove(), 12);
781 /// } else {
782 /// panic!("Entry should be occupied");
783 /// }
784 ///
785 /// assert_eq!(cache.contains_key("poneyland"), false);
786 /// ```
787 pub fn remove(self) -> V {
788 self.entry.remove()
789 }
790}
791
792/// A view into a vacant entry in a [`Cache`].
793/// It is part of the [`Entry`] enum.
794///
795/// [`Cache`]: struct.Cache.html
796/// [`Entry`]: enum.Entry.html
797pub struct VacantEntry<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher = RandomState> {
798 cache: &'a mut Cache<K, V, S>,
799 kind: VacantKind,
800 key: K,
801}
802
803impl<'a, K: 'a + fmt::Debug + Eq + Hash, V: 'a + fmt::Debug, S: 'a + BuildHasher> fmt::Debug
804 for VacantEntry<'a, K, V, S>
805{
806 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
807 f.debug_struct("VacantEntry")
808 .field("key", self.key())
809 .field("remembered", &(self.kind == VacantKind::Ghost))
810 .finish()
811 }
812}
813
814impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher> VacantEntry<'a, K, V, S> {
815 /// Gets a reference to the key that would be used when inserting a value
816 /// through the `VacantEntry`.
817 ///
818 /// # Examples
819 ///
820 /// ```
821 /// use cache_2q::{Cache, Entry};
822 ///
823 /// let mut cache: Cache<&str, u32> = Cache::new(8);
824 ///
825 /// if let Entry::Vacant(v) = cache.entry("poneyland") {
826 /// assert_eq!(v.key(), &"poneyland");
827 /// } else {
828 /// panic!("Entry should be vacant");
829 /// }
830 /// ```
831 pub fn key(&self) -> &K {
832 &self.key
833 }
834
835 /// Take ownership of the key.
836 ///
837 /// # Examples
838 ///
839 /// ```
840 /// use cache_2q::{Cache, Entry};
841 ///
842 /// let mut cache: Cache<String, u32> = Cache::new(8);
843 ///
844 /// if let Entry::Vacant(v) = cache.entry("poneyland".into()) {
845 /// assert_eq!(v.into_key(), "poneyland".to_string());
846 /// } else {
847 /// panic!("Entry should be vacant");
848 /// }
849 /// ```
850 pub fn into_key(self) -> K {
851 self.key
852 }
853
854 /// If this vacant entry is remembered
855 ///
856 /// Keys are remembered after they are evicted from the cache. If this entry is remembered,
857 /// if inserted, it will be insert to a `frequent` list, instead of the usual `recent` list
858 ///
859 /// # Examples
860 ///
861 /// ```
862 /// use cache_2q::{Cache, Entry};
863 ///
864 /// let mut cache: Cache<&str, u32> = Cache::new(1);
865 ///
866 /// if let Entry::Vacant(v) = cache.entry("poneyland") {
867 /// assert!(!v.is_remembered());
868 /// } else {
869 /// panic!("Entry should be vacant");
870 /// }
871 ///
872 /// cache.insert("poneyland", 0);
873 /// cache.insert("other", 1); // Force poneyland out of the cache
874 /// if let Entry::Vacant(v) = cache.entry("poneyland") {
875 /// assert!(v.is_remembered());
876 /// v.insert(0);
877 /// } else {
878 /// panic!("Entry should be vacant");
879 /// }
880 /// ```
881 pub fn is_remembered(&self) -> bool {
882 self.kind == VacantKind::Ghost
883 }
884}
885
886impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher> VacantEntry<'a, K, V, S> {
887 /// Sets the value of the entry with the VacantEntry's key,
888 /// and returns a mutable reference to it.
889 ///
890 /// # Examples
891 ///
892 /// ```
893 /// use cache_2q::{Cache, Entry};
894 ///
895 /// let mut cache: Cache<&str, u32> = Cache::new(8);
896 ///
897 /// if let Entry::Vacant(o) = cache.entry("poneyland") {
898 /// o.insert(37);
899 /// } else {
900 /// panic!("Entry should be vacant");
901 /// }
902 /// assert_eq!(*cache.get("poneyland").unwrap(), 37);
903 /// ```
904 pub fn insert(self, value: V) -> &'a mut V {
905 let VacantEntry { cache, key, kind } = self;
906 match kind {
907 VacantKind::Ghost => {
908 cache.ghost.remove(&key).expect("No ghost with key");
909 if cache.frequent.len() + 1 > cache.size {
910 cache.frequent.pop_front();
911 }
912 cache.frequent.entry(key).or_insert(value)
913 }
914 VacantKind::Unknown => {
915 if cache.recent.len() + 1 > cache.size {
916 let (old_key, _) = cache.recent.pop_front().unwrap();
917 if cache.ghost.len() + 1 > cache.ghost_size {
918 cache.ghost.pop_back();
919 }
920 cache.ghost.insert(old_key, ());
921 }
922 cache.recent.entry(key).or_insert(value)
923 }
924 }
925 }
926}
927type InnerIter<'a, K, V> =
928 iter::Chain<linked_hash_map::Iter<'a, K, V>, linked_hash_map::Iter<'a, K, V>>;
929
930/// An iterator over the entries of a [`Cache`].
931///
932/// This `struct` is created by the [`iter`] method on [`Cache`]. See its
933/// documentation for more.
934///
935/// [`iter`]: struct.Cache.html#method.iter
936/// [`Cache`]: struct.Cache.html
937pub struct Iter<'a, K: 'a, V: 'a> {
938 inner: InnerIter<'a, K, V>,
939}
940
941impl<'a, K: 'a, V: 'a> Clone for Iter<'a, K, V> {
942 fn clone(&self) -> Self {
943 Iter {
944 inner: self.inner.clone(),
945 }
946 }
947}
948
949impl<'a, K: 'a + fmt::Debug, V: 'a + fmt::Debug> fmt::Debug for Iter<'a, K, V> {
950 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
951 f.debug_list().entries(self.clone()).finish()
952 }
953}
954
955impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
956 type Item = (&'a K, &'a V);
957
958 fn next(&mut self) -> Option<Self::Item> {
959 self.inner.next()
960 }
961
962 fn size_hint(&self) -> (usize, Option<usize>) {
963 self.inner.size_hint()
964 }
965
966 fn count(self) -> usize {
967 self.inner.count()
968 }
969
970 fn last(self) -> Option<Self::Item> {
971 self.inner.last()
972 }
973
974 fn nth(&mut self, n: usize) -> Option<Self::Item> {
975 self.inner.nth(n)
976 }
977
978 fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
979 where
980 P: FnMut(&Self::Item) -> bool,
981 {
982 self.inner.find(predicate)
983 }
984}
985
986#[derive(Debug, Copy, Clone, PartialEq, Eq)]
987enum VacantKind {
988 Ghost,
989 Unknown,
990}
991
992#[derive(Debug, Copy, Clone, PartialEq, Eq)]
993enum OccupiedKind {
994 Recent,
995 Frequent,
996}
997
998#[cfg(test)]
999mod tests {
1000 use super::Cache;
1001
1002 #[test]
1003 fn expected_sizes() {
1004 let cache: Cache<u8, u8> = Cache::new(16);
1005 assert_eq!(cache.size, 16);
1006 assert_eq!(cache.ghost_size, 16 * 4);
1007 }
1008
1009 #[test]
1010 fn cache_zero_sized_entries() {
1011 let mut cache = Cache::new(8);
1012 for _ in 0..1024 {
1013 cache.entry(()).or_insert_with(|| ());
1014 }
1015 }
1016
1017 #[test]
1018 fn get_borrowed() {
1019 let mut cache = Cache::new(8);
1020 cache.entry("hi".to_string()).or_insert(0);
1021 cache.entry("there".to_string()).or_insert(0);
1022 assert_eq!(*cache.get("hi").unwrap(), 0);
1023 }
1024
1025 #[test]
1026 #[should_panic]
1027 fn empty_cache() {
1028 Cache::<(), ()>::new(0);
1029 }
1030
1031 #[test]
1032 fn size_1_cache() {
1033 let mut cache = Cache::new(1);
1034 cache.insert(100, "value");
1035 assert_eq!(cache.get(&100), Some(&mut "value"));
1036 cache.insert(200, "other");
1037 assert_eq!(cache.get(&200), Some(&mut "other"));
1038 assert_eq!(cache.get(&100), None);
1039 assert!(cache.ghost.contains_key(&100));
1040 cache.insert(10, "value");
1041 assert_eq!(cache.get(&10), Some(&mut "value"));
1042 assert!(cache.ghost.contains_key(&100));
1043 assert!(cache.ghost.contains_key(&200));
1044 cache.insert(20, "other");
1045 assert_eq!(cache.get(&20), Some(&mut "other"));
1046 assert_eq!(cache.get(&10), None);
1047 assert_eq!(cache.get(&100), None);
1048 }
1049
1050 #[test]
1051 fn frequents() {
1052 let mut cache = Cache::new(2);
1053 cache.insert(100, "100");
1054 cache.insert(200, "200");
1055 assert_eq!(
1056 cache.recent.iter().collect::<Vec<_>>(),
1057 vec![(&100, &"100"), (&200, &"200")]
1058 );
1059 cache.insert(300, "300");
1060 assert_eq!(
1061 cache.recent.iter().collect::<Vec<_>>(),
1062 vec![(&200, &"200"), (&300, &"300")]
1063 );
1064 assert_eq!(cache.ghost.iter().collect::<Vec<_>>(), vec![(&100, &())]);
1065 cache.insert(400, "400");
1066 assert_eq!(
1067 cache.recent.iter().collect::<Vec<_>>(),
1068 vec![(&300, &"300"), (&400, &"400")]
1069 );
1070 assert_eq!(
1071 cache.ghost.iter().collect::<Vec<_>>(),
1072 vec![(&100, &()), (&200, &())]
1073 );
1074 cache.insert(100, "100");
1075 assert_eq!(
1076 cache.recent.iter().collect::<Vec<_>>(),
1077 vec![(&300, &"300"), (&400, &"400")]
1078 );
1079 assert_eq!(cache.ghost.iter().collect::<Vec<_>>(), vec![(&200, &())]);
1080 assert_eq!(
1081 cache.frequent.iter().collect::<Vec<_>>(),
1082 vec![(&100, &"100")]
1083 );
1084
1085 for x in 500..600 {
1086 cache.insert(x, "junk");
1087 }
1088 assert_eq!(cache.get(&100), Some(&mut "100"));
1089 }
1090}