associative_cache/lib.rs
1//! This crate provides a generic, fixed-size, N-way associative cache data
2//! structure that supports random and least recently used replacement (or your
3//! own custom algorithm).
4//!
5//! Dive into the documentation for [`AssociativeCache`] to begin.
6
7#![deny(missing_docs, missing_debug_implementations)]
8
9pub mod capacity;
10pub mod entry;
11pub mod indices;
12pub mod iter;
13pub mod replacement;
14
15pub use capacity::*;
16pub use entry::*;
17pub use indices::*;
18pub use iter::*;
19pub use replacement::*;
20
21use std::borrow::Borrow;
22use std::cmp::max;
23use std::marker::PhantomData;
24use std::mem;
25
26/// A constant cache capacity.
27///
28/// ## Provided `Capacity` Implementations
29///
30/// This crate defines all power-of-two capacities up to 8192 as
31/// `associative_cache::CapacityN`.
32///
33/// ```
34/// use associative_cache::Capacity256;
35/// ```
36///
37/// ## Defining Custom Cache Capacities
38///
39/// You may implement this trait yourself to define your own custom cache
40/// capacities:
41///
42/// ```
43/// use associative_cache::Capacity;
44///
45/// pub struct Capacity42;
46///
47/// impl Capacity for Capacity42 {
48/// const CAPACITY: usize = 42;
49/// }
50/// ```
51pub trait Capacity {
52 /// The constant capacity for a cache.
53 ///
54 /// Must be greater than zero.
55 const CAPACITY: usize;
56}
57
58/// Given a cache key, return all the slots within the cache where its entry
59/// might be.
60///
61/// ## Associativity
62///
63/// The associativity of a cache is how many slots in the cache a key might
64/// reside in. There are generally many more possible values than there is
65/// capacity in the cache. Allowing a entry to be in one of multiple slots
66/// within the cache raises the cache hit rate, but takes a little extra time
67/// when querying the cache because each of those multiple slots need to be
68/// considered.
69///
70/// * **Direct-mapped:** A cache key corresponds to only one possible slot in
71/// the cache.
72///
73/// * **Two-way:** A cache key corresponds to two possible slots in the cache.
74///
75/// * **Four-way:** A cache key corresponds to four possible slots in the cache.
76///
77/// * Etc...
78///
79/// [Wikipedia has more details on cache
80/// associativity.](https://en.wikipedia.org/wiki/CPU_cache#Associativity)
81///
82/// ## Provided Implementations
83///
84/// This crate provides two flavors of associativity out of the box:
85///
86/// 1. `Hash`-based implementations: `HashDirectMapped` and
87/// `Hash{Two,Four,Eight,Sixteen,ThirtyTwo}Way` provide various associativity
88/// levels based on the key's `Hash` implementation.
89///
90/// 2. Pointer-based implementations: `PointerDirectMapped` and
91/// `Pointer{Two,Four,Eight,Sixteen,ThirtyTwo}Way` provide various
92/// associativity levels based on the pointer value, taking advantage of its
93/// referenced type's alignment. This will generally provide faster lookups
94/// than hashing, but is less general.
95///
96/// ## Custom Implementation Requirements
97///
98/// Implementations must be deterministic.
99///
100/// All indices yielded must be within the capacity.
101///
102/// The iterator must always be non-empty.
103///
104/// For example, to implement a two-way cache, return an iterator of two
105/// indices.
106pub trait Indices<K, C>
107where
108 K: ?Sized,
109 C: Capacity,
110{
111 /// The iterator over indices within the range `0..C::CAPACITY` yielding the
112 /// slots in the cache where the key's entry might reside.
113 type Indices: ExactSizeIterator<Item = usize>;
114
115 /// Get the indices within the range `0..C::CAPACITY` representing slots in
116 /// the cache where the given key's entry might reside.
117 fn indices(key: &K) -> Self::Indices;
118}
119
120/// Given that we need to replace a cache entry when inserting a new one, consider
121/// each `(index, entry)` pair and return the index whose entry should be
122/// replaced.
123///
124/// The given iterator will always be non-empty, and its indices will always be
125/// within the capacity, assuming the `Indices` that this is paired with is
126/// conformant.
127pub trait Replacement<V, C: Capacity> {
128 /// Choose which of the given cache entries will be replaced.
129 fn choose_for_replacement<'a>(
130 &mut self,
131 candidates: impl ExactSizeIterator<Item = (usize, &'a V)>,
132 ) -> usize
133 where
134 V: 'a;
135
136 /// Called whenever an existing cache entry is hit.
137 fn on_hit(&self, value: &V) {
138 let _ = value;
139 }
140
141 /// Called whenever a new cache entry is inserted.
142 fn on_insert(&self, value: &V) {
143 let _ = value;
144 }
145}
146
147/// A fixed-size associative cache mapping `K` keys to `V` values.
148///
149/// ## Capacity
150///
151/// The cache has a constant, fixed-size capacity which is controlled by the `C`
152/// type parameter and the `Capacity` trait. The memory for the cache entries is
153/// eagerly allocated once and never resized.
154///
155/// ## Associativity
156///
157/// The cache can be configured as direct-mapped, two-way associative, four-way
158/// associative, etc... via the `I` type parameter and `Indices` trait.
159///
160/// ## Replacement Policy
161///
162/// Can be configured to replace the least-recently used entry, or a random
163/// entry via the `R` type parameter and the `Replacement` trait.
164///
165/// ## Examples
166///
167/// ```
168/// # #[cfg(feature = "rand")]
169/// # {
170/// use associative_cache::*;
171///
172/// // A two-way associative cache with random replacement mapping
173/// // `String`s to `usize`s.
174/// let cache = AssociativeCache::<
175/// String,
176/// usize,
177/// Capacity512,
178/// HashTwoWay,
179/// RandomReplacement
180/// >::default();
181///
182/// // A four-way associative cache with random replacement mapping
183/// // `*mut usize`s to `Vec<u8>`s.
184/// let cache = AssociativeCache::<
185/// *mut usize,
186/// Vec<u8>,
187/// Capacity32,
188/// PointerFourWay,
189/// RandomReplacement
190/// >::default();
191///
192/// // An eight-way associative, least recently used (LRU) cache mapping
193/// // `std::path::PathBuf`s to `std::fs::File`s.
194/// let cache = AssociativeCache::<
195/// std::path::PathBuf,
196/// WithLruTimestamp<std::fs::File>,
197/// Capacity128,
198/// HashEightWay,
199/// LruReplacement,
200/// >::default();
201/// # }
202/// ```
203#[derive(Debug)]
204pub struct AssociativeCache<K, V, C, I, R>
205where
206 C: Capacity,
207 R: Replacement<V, C>,
208{
209 entries: Vec<Option<(K, V)>>,
210 len: usize,
211 replacement_policy: R,
212 _capacity: PhantomData<C>,
213 _indices: PhantomData<I>,
214}
215
216impl<K, V, C, I, R> Default for AssociativeCache<K, V, C, I, R>
217where
218 C: Capacity,
219 R: Default + Replacement<V, C>,
220{
221 fn default() -> Self {
222 AssociativeCache::with_replacement_policy(R::default())
223 }
224}
225
226impl<K, V, C, I, R> AssociativeCache<K, V, C, I, R>
227where
228 C: Capacity,
229 R: Replacement<V, C>,
230{
231 /// Construct an `AssociativeCache` with the given replacement policy.
232 ///
233 /// ## Example
234 ///
235 /// ```
236 /// # #[cfg(feature = "rand")]
237 /// # {
238 /// use associative_cache::*;
239 /// use rand::{rngs::StdRng, SeedableRng};
240 /// use std::path::PathBuf;
241 /// use std::fs::File;
242 ///
243 /// // Note: `RandomReplacement` requires the "rand" feature to be enabled.
244 /// let policy = RandomReplacement::with_rng(StdRng::seed_from_u64(42));
245 ///
246 /// let cache = AssociativeCache::<
247 /// PathBuf,
248 /// File,
249 /// Capacity128,
250 /// HashEightWay,
251 /// _,
252 /// >::with_replacement_policy(policy);
253 /// # }
254 /// ```
255 pub fn with_replacement_policy(replacement_policy: R) -> Self {
256 assert!(C::CAPACITY > 0);
257 let mut entries = Vec::with_capacity(C::CAPACITY);
258 for _ in 0..C::CAPACITY {
259 entries.push(None);
260 }
261 AssociativeCache {
262 entries,
263 len: 0,
264 replacement_policy,
265 _capacity: PhantomData,
266 _indices: PhantomData,
267 }
268 }
269
270 /// Get a shared reference to this cache's replacement policy.
271 #[inline]
272 pub fn replacement_policy(&self) -> &R {
273 &self.replacement_policy
274 }
275
276 /// Get an exclusive reference to this cache's replacement policy.
277 #[inline]
278 pub fn replacement_policy_mut(&mut self) -> &mut R {
279 &mut self.replacement_policy
280 }
281
282 /// Get this cache's constant capacity, aka `C::CAPACITY`.
283 #[inline]
284 pub fn capacity(&self) -> usize {
285 assert_eq!(self.entries.len(), C::CAPACITY);
286 C::CAPACITY
287 }
288
289 /// Get the number of entries in this cache.
290 ///
291 /// This is always less than or equal to the capacity.
292 ///
293 /// ## Example
294 ///
295 /// ```
296 /// use associative_cache::*;
297 ///
298 /// let mut cache = AssociativeCache::<
299 /// String,
300 /// usize,
301 /// Capacity16,
302 /// HashDirectMapped,
303 /// RoundRobinReplacement,
304 /// >::default();
305 ///
306 /// // Initially, the cache is empty.
307 /// assert_eq!(cache.len(), 0);
308 ///
309 /// let old_entry = cache.insert("hi".to_string(), 2);
310 ///
311 /// // We know the cache was empty, so there can't be an old entry that was
312 /// // replaced.
313 /// assert!(old_entry.is_none());
314 ///
315 /// // And now the length is 1.
316 /// assert_eq!(cache.len(), 1);
317 ///
318 /// // Insert another entry. If this doesn't conflict with the existing
319 /// // entry, then we should have a length of 2. If it did conflict, and we
320 /// // replaced the old entry, then we should still have a length of 1.
321 /// if cache.insert("bye".to_string(), 3).is_none() {
322 /// assert_eq!(cache.len(), 2);
323 /// } else {
324 /// assert_eq!(cache.len(), 1);
325 /// }
326 /// ```
327 #[inline]
328 pub fn len(&self) -> usize {
329 debug_assert!(self.len <= self.capacity());
330 self.len
331 }
332
333 /// Return `true` if there are zero entries in the cache.
334 #[inline]
335 pub fn is_empty(&self) -> bool {
336 self.len == 0
337 }
338
339 /// Insert a new entry into the cache.
340 ///
341 /// If there is an old entry for this key, or if another entry ends up
342 /// getting replaced by this new one, return the old entry.
343 ///
344 /// ## Example
345 ///
346 /// ```
347 /// use associative_cache::*;
348 ///
349 /// let mut cache = AssociativeCache::<
350 /// String,
351 /// usize,
352 /// Capacity1,
353 /// HashDirectMapped,
354 /// RoundRobinReplacement,
355 /// >::default();
356 ///
357 /// // Insert an entry for "hi" into the cache.
358 /// let old_entry = cache.insert("hi".to_string(), 42);
359 ///
360 /// // The cache was empty, so no old entry.
361 /// assert!(old_entry.is_none());
362 ///
363 /// // Insert an entry for "bye" into the cache.
364 /// let old_entry = cache.insert("bye".to_string(), 1337);
365 ///
366 /// // Because the cache only has a capacity of one, we replaced "hi" when
367 /// // inserting "bye".
368 /// assert_eq!(old_entry, Some(("hi".to_string(), 42)));
369 /// ```
370 pub fn insert(&mut self, key: K, value: V) -> Option<(K, V)>
371 where
372 I: Indices<K, C>,
373 K: PartialEq,
374 {
375 let capacity = self.capacity();
376
377 #[derive(Ord, PartialOrd, Eq, PartialEq)]
378 enum InsertionCandidate {
379 New(usize),
380 Replace(usize),
381 }
382 assert!(None < Some(InsertionCandidate::New(0)));
383 assert!(InsertionCandidate::New(0) < InsertionCandidate::Replace(0));
384
385 // First see if we can insert the value to an existing entry for this
386 // key, or without replaceing any other entry.
387 let mut best = None;
388 for index in I::indices(&key) {
389 assert!(
390 index < capacity,
391 "`Indices::indices` must always yield indices within the capacity"
392 );
393 match self.entries[index] {
394 None => {
395 best = max(best, Some(InsertionCandidate::New(index)));
396 }
397 Some((ref k, _)) if *k == key => {
398 best = max(best, Some(InsertionCandidate::Replace(index)));
399 }
400 _ => continue,
401 }
402 }
403
404 match best {
405 None => {}
406 Some(InsertionCandidate::New(index)) => {
407 self.entries[index] = Some((key, value));
408 self.len += 1;
409 return None;
410 }
411 Some(InsertionCandidate::Replace(index)) => {
412 return mem::replace(&mut self.entries[index], Some((key, value)));
413 }
414 }
415
416 // Okay, we have to replace an entry. Let the `ReplacementPolicy` decide
417 // which one.
418 let AssociativeCache {
419 ref entries,
420 ref mut replacement_policy,
421 ..
422 } = self;
423 let candidates = I::indices(&key).map(|index| {
424 assert!(
425 index < capacity,
426 "`I::indices` must always yield indices within the capacity"
427 );
428 let value = &entries[index]
429 .as_ref()
430 // We know that all the indices we saw above are full, so the
431 // only way this `expect` would fail is if `Indices::indices` is
432 // non-deterministic.
433 .expect(
434 "`Indices::indices` must always yield the same indices for the same entries",
435 )
436 .1;
437 (index, value)
438 });
439 let index = replacement_policy.choose_for_replacement(candidates);
440 debug_assert!(
441 I::indices(&key).any(|i| i == index),
442 "`ReplacementPolicy::choose_for_replacement` must return a candidate index"
443 );
444 assert!(index < capacity);
445 assert!(self.entries[index].is_some());
446 mem::replace(&mut self.entries[index], Some((key, value)))
447 }
448
449 /// Get a shared reference to the value for a given key, if it exists in the
450 /// cache.
451 ///
452 /// ## Example
453 ///
454 /// ```
455 /// use associative_cache::*;
456 ///
457 /// let mut cache = AssociativeCache::<
458 /// String,
459 /// usize,
460 /// Capacity1,
461 /// HashDirectMapped,
462 /// RoundRobinReplacement,
463 /// >::default();
464 ///
465 /// // Returns `None` if there is no cache entry for the key.
466 /// assert!(cache.get("hi").is_none());
467 ///
468 /// cache.insert("hi".to_string(), 1234);
469 ///
470 /// // Otherwise, returns the value if there is an entry for the key.
471 /// assert_eq!(cache.get("hi"), Some(&1234));
472 /// ```
473 #[inline]
474 pub fn get<Q>(&self, key: &Q) -> Option<&V>
475 where
476 K: Borrow<Q>,
477 I: Indices<Q, C>,
478 Q: ?Sized + PartialEq,
479 {
480 assert_eq!(self.entries.len(), C::CAPACITY);
481
482 for index in I::indices(key) {
483 assert!(
484 index < self.entries.len(),
485 "`Indices::indices` must always yield indices within the capacity"
486 );
487 match &self.entries[index] {
488 Some((k, v)) if k.borrow() == key => {
489 self.replacement_policy.on_hit(v);
490 return Some(v);
491 }
492 _ => continue,
493 }
494 }
495
496 None
497 }
498
499 /// Get an exclusive reference to the value for a given key, if it exists in
500 /// the cache.
501 ///
502 /// ## Example
503 ///
504 /// ```
505 /// use associative_cache::*;
506 ///
507 /// let mut cache = AssociativeCache::<
508 /// String,
509 /// usize,
510 /// Capacity1,
511 /// HashDirectMapped,
512 /// RoundRobinReplacement,
513 /// >::default();
514 ///
515 /// // Returns `None` if there is no cache entry for the key.
516 /// assert!(cache.get_mut("hi").is_none());
517 ///
518 /// cache.insert("hi".to_string(), 1234);
519 ///
520 /// // Otherwise, returns the value if there is an entry for the key.
521 /// let val = cache.get_mut("hi").unwrap();
522 /// assert_eq!(*val, 1234);
523 ///
524 /// // And we can assign to the cache value.
525 /// *val = 5678;
526 /// ```
527 #[inline]
528 pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
529 where
530 K: Borrow<Q>,
531 I: Indices<Q, C>,
532 Q: ?Sized + PartialEq,
533 {
534 assert_eq!(self.entries.len(), C::CAPACITY);
535
536 for index in I::indices(key) {
537 assert!(
538 index < C::CAPACITY,
539 "`Indices::indices` must always yield indices within the capacity"
540 );
541 match &self.entries[index] {
542 Some((k, _)) if k.borrow() == key => {
543 let v = &mut self.entries[index].as_mut().unwrap().1;
544 self.replacement_policy.on_hit(v);
545 return Some(v);
546 }
547 _ => continue,
548 }
549 }
550
551 None
552 }
553
554 /// Remove an entry from the cache.
555 ///
556 /// If an entry for the key existed in the cache, it is removed and `Some`
557 /// is returned. Otherwise, `None` is returned.
558 ///
559 /// ## Example
560 ///
561 /// ```
562 /// use associative_cache::*;
563 ///
564 /// let mut cache = AssociativeCache::<
565 /// String,
566 /// usize,
567 /// Capacity1,
568 /// HashDirectMapped,
569 /// RoundRobinReplacement,
570 /// >::default();
571 ///
572 /// // Returns `None` if there is no cache entry for the key and therefore
573 /// // nothing was removed.
574 /// assert!(cache.remove("hi").is_none());
575 ///
576 /// cache.insert("hi".to_string(), 1234);
577 ///
578 /// // Otherwise, returns the value that was removed if there was an entry
579 /// // for the key.
580 /// assert_eq!(cache.remove("hi"), Some(1234));
581 /// ```
582 #[inline]
583 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
584 where
585 K: Borrow<Q>,
586 I: Indices<Q, C>,
587 Q: ?Sized + PartialEq,
588 {
589 assert_eq!(self.entries.len(), C::CAPACITY);
590
591 for index in I::indices(key) {
592 assert!(
593 index < self.entries.len(),
594 "`Indices::indices` must always yield indices within the capacity"
595 );
596 match &self.entries[index] {
597 Some((k, _)) if k.borrow() == key => {
598 self.len -= 1;
599 return self.entries[index].take().map(|(_, v)| v);
600 }
601 _ => continue,
602 }
603 }
604
605 None
606 }
607
608 /// Retain only the cache entries specified by the predicate.
609 ///
610 /// Calls `f` with each entry in the cache, and removes all entries where
611 /// `f` returned false.
612 ///
613 /// ## Example
614 ///
615 /// ```
616 /// use associative_cache::*;
617 ///
618 /// let mut cache = AssociativeCache::<
619 /// char,
620 /// usize,
621 /// Capacity8,
622 /// HashDirectMapped,
623 /// RoundRobinReplacement,
624 /// >::default();
625 ///
626 /// for (i, ch) in "I let my tape rock, 'til my tape popped".char_indices() {
627 /// cache.insert(ch, i);
628 /// }
629 ///
630 /// for (key, val) in cache.iter() {
631 /// println!("Last saw character '{}' at index {}", key, val);
632 /// }
633 /// ```
634 pub fn retain(&mut self, mut f: impl FnMut(&K, &mut V) -> bool) {
635 for e in &mut self.entries {
636 if let Some((k, v)) = e {
637 if !f(k, v) {
638 *e = None;
639 self.len -= 1;
640 }
641 }
642 }
643 }
644
645 /// Get the key's corresponding slot within the cache for in-place mutation
646 /// and performing get-or-create operations.
647 ///
648 /// ## Example
649 ///
650 /// ```
651 /// use associative_cache::*;
652 ///
653 /// let mut cache = AssociativeCache::<
654 /// String,
655 /// usize,
656 /// Capacity4,
657 /// HashTwoWay,
658 /// RoundRobinReplacement,
659 /// >::default();
660 ///
661 /// for word in "she sells sea shells down by the sea shore".split_whitespace() {
662 /// let count = cache.entry(word).or_insert_with(
663 /// || word.to_string(),
664 /// || 0,
665 /// );
666 /// *count += 1;
667 /// }
668 /// ```
669 #[inline]
670 pub fn entry<Q>(&mut self, key: &Q) -> Entry<'_, K, V, C, I, R>
671 where
672 K: Borrow<Q>,
673 I: Indices<Q, C>,
674 Q: ?Sized + PartialEq,
675 {
676 let capacity = self.capacity();
677
678 // First, see if we have an entry for this key, or if we have an empty
679 // slot where an entry could be placed without replaceing another entry.
680 let mut empty_index = None;
681 for index in I::indices(key) {
682 assert!(
683 index < capacity,
684 "`Indices::indices` must always yield indices within the capacity"
685 );
686 match &mut self.entries[index] {
687 None => {
688 empty_index = Some(index);
689 }
690 Some((k, v)) if (*k).borrow() == key => {
691 self.replacement_policy.on_hit(v);
692 return Entry {
693 cache: self,
694 kind: EntryKind::Occupied,
695 index,
696 };
697 }
698 _ => continue,
699 }
700 }
701 if let Some(index) = empty_index {
702 return Entry {
703 cache: self,
704 kind: EntryKind::Vacant,
705 index,
706 };
707 }
708
709 // Okay, we have to return an already-in-use entry, which will be
710 // replaced if the user inserts anything.
711 let AssociativeCache {
712 ref entries,
713 ref mut replacement_policy,
714 ..
715 } = self;
716 let candidates = I::indices(key).map(|index| {
717 assert!(
718 index < capacity,
719 "`I::indices` must always yield indices within the capacity"
720 );
721 let value = &entries[index]
722 .as_ref()
723 // We know that all the indices we saw above are full, so the
724 // only way this `expect` would fail is if `Indices::indices` is
725 // non-deterministic.
726 .expect(
727 "`Indices::indices` must always yield the same indices for the same entries",
728 )
729 .1;
730 (index, value)
731 });
732 let index = replacement_policy.choose_for_replacement(candidates);
733 Entry {
734 cache: self,
735 kind: EntryKind::Replace,
736 index,
737 }
738 }
739
740 /// Iterate over shared references to this cache's keys and values.
741 ///
742 /// ## Example
743 ///
744 /// ```
745 /// use associative_cache::*;
746 ///
747 /// let mut cache = AssociativeCache::<
748 /// String,
749 /// usize,
750 /// Capacity4,
751 /// HashTwoWay,
752 /// RoundRobinReplacement,
753 /// >::default();
754 ///
755 /// // First, insert some entries into the cache. Note that this is more
756 /// // entries than the cache has capacity for.
757 /// for s in vec!["red", "blue", "green", "pink", "purple", "orange"] {
758 /// cache.insert(s.to_string(), s.len());
759 /// }
760 ///
761 /// // Now iterate over the entries that are still in the cache:
762 /// for (k, v) in cache.iter() {
763 /// println!("{} -> {}", k, v);
764 /// }
765 /// ```
766 #[inline]
767 pub fn iter(&self) -> Iter<'_, K, V> {
768 <&Self as IntoIterator>::into_iter(self)
769 }
770
771 /// Iterate over shared references to this cache's keys and exclusive
772 /// references to its values.
773 ///
774 /// ## Example
775 ///
776 /// ```
777 /// use associative_cache::*;
778 ///
779 /// let mut cache = AssociativeCache::<
780 /// String,
781 /// usize,
782 /// Capacity4,
783 /// HashTwoWay,
784 /// RoundRobinReplacement,
785 /// >::default();
786 ///
787 /// // First, insert some entries into the cache. Note that this is more
788 /// // entries than the cache has capacity for.
789 /// for s in vec!["red", "blue", "green", "pink", "purple", "orange"] {
790 /// cache.insert(s.to_string(), s.len());
791 /// }
792 ///
793 /// // Now iterate over the entries that are still in the cache and mutate
794 /// // them:
795 /// for (k, v) in cache.iter_mut() {
796 /// println!("{} was {}...", k, v);
797 /// *v += 1;
798 /// println!("...but now it's {}!", v);
799 /// }
800 /// ```
801 #[inline]
802 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
803 <&mut Self as IntoIterator>::into_iter(self)
804 }
805
806 /// Consume this cache, and iterate over its keys and values.
807 ///
808 /// ## Example
809 ///
810 /// ```
811 /// use associative_cache::*;
812 ///
813 /// let mut cache = AssociativeCache::<
814 /// String,
815 /// usize,
816 /// Capacity4,
817 /// HashTwoWay,
818 /// RoundRobinReplacement,
819 /// >::default();
820 ///
821 /// // First, insert some entries into the cache. Note that this is more
822 /// // entries than the cache has capacity for.
823 /// for s in vec!["red", "blue", "green", "pink", "purple", "orange"] {
824 /// cache.insert(s.to_string(), s.len());
825 /// }
826 ///
827 /// // Not possible with `iter` or `iter_mut` without cloning.
828 /// let v: Vec<(String, usize)> = cache.into_iter().collect();
829 /// ```
830 #[inline]
831 #[allow(clippy::should_implement_trait)]
832 pub fn into_iter(self) -> IntoIter<K, V> {
833 <Self as IntoIterator>::into_iter(self)
834 }
835}
836
837#[cfg(test)]
838mod tests {
839 use super::*;
840
841 #[test]
842 fn replacement_policy() {
843 let mut policy = RoundRobinReplacement::default();
844 let mut cache = AssociativeCache::<usize, usize, Capacity4, HashDirectMapped,_>::with_replacement_policy(policy.clone());
845 assert_eq!(cache.replacement_policy(), &policy);
846 assert_eq!(cache.replacement_policy_mut(), &mut policy);
847 }
848
849 #[test]
850 fn capacity() {
851 let cache = AssociativeCache::<
852 usize,
853 usize,
854 Capacity2,
855 HashDirectMapped,
856 RoundRobinReplacement,
857 >::default();
858 assert_eq!(cache.capacity(), 2);
859
860 let cache = AssociativeCache::<
861 usize,
862 usize,
863 Capacity4,
864 HashDirectMapped,
865 RoundRobinReplacement,
866 >::default();
867 assert_eq!(cache.capacity(), 4);
868
869 let cache = AssociativeCache::<
870 usize,
871 usize,
872 Capacity8,
873 HashDirectMapped,
874 RoundRobinReplacement,
875 >::default();
876 assert_eq!(cache.capacity(), 8);
877 }
878
879 #[test]
880 fn len() {
881 let mut cache = AssociativeCache::<
882 usize,
883 usize,
884 Capacity512,
885 HashDirectMapped,
886 RoundRobinReplacement,
887 >::default();
888
889 assert_eq!(cache.insert(1, 2), None);
890 assert_eq!(cache.len(), 1);
891 assert_eq!(cache.insert(3, 4), None);
892 assert_eq!(cache.len(), 2);
893 assert_eq!(cache.insert(5, 6), None);
894 assert_eq!(cache.len(), 3);
895
896 cache.insert(1, 7).unwrap();
897 assert_eq!(cache.len(), 3);
898 cache.insert(3, 8).unwrap();
899 assert_eq!(cache.len(), 3);
900 cache.insert(5, 9).unwrap();
901 assert_eq!(cache.len(), 3);
902 }
903
904 #[test]
905 fn insert() {
906 let mut cache = AssociativeCache::<
907 *mut u8,
908 usize,
909 Capacity4,
910 PointerTwoWay,
911 RoundRobinReplacement,
912 >::default();
913
914 // Fill all the cache slots.
915 assert_eq!(cache.insert(0 as *mut u8, 0), None);
916 assert_eq!(cache.insert(1 as *mut u8, 1), None);
917 assert_eq!(cache.insert(2 as *mut u8, 2), None);
918 assert_eq!(cache.insert(3 as *mut u8, 3), None);
919
920 // Start replacing old entries with new insertions.
921 assert_eq!(cache.insert(4 as *mut u8, 4), Some((2 as *mut u8, 2)));
922 assert_eq!(cache.insert(6 as *mut u8, 6), Some((0 as *mut u8, 0)));
923 assert_eq!(cache.insert(5 as *mut u8, 5), Some((3 as *mut u8, 3)));
924 assert_eq!(cache.insert(7 as *mut u8, 7), Some((1 as *mut u8, 1)));
925 }
926
927 #[test]
928 fn get() {
929 let mut cache = AssociativeCache::<
930 *mut u8,
931 usize,
932 Capacity4,
933 PointerTwoWay,
934 RoundRobinReplacement,
935 >::default();
936
937 cache.insert(0 as *mut _, 0);
938 assert_eq!(cache.get(&(0 as *mut _)), Some(&0));
939 assert_eq!(cache.get(&(1 as *mut _)), None);
940
941 cache.insert(4 as *mut _, 4);
942 assert_eq!(cache.get(&(0 as *mut _)), Some(&0));
943 assert_eq!(cache.get(&(4 as *mut _)), Some(&4));
944 assert_eq!(cache.get(&(1 as *mut _)), None);
945
946 assert_eq!(cache.insert(8 as *mut _, 8), Some((4 as *mut _, 4)));
947 assert_eq!(cache.get(&(0 as *mut _)), Some(&0));
948 assert_eq!(cache.get(&(8 as *mut _)), Some(&8));
949 assert_eq!(cache.get(&(1 as *mut _)), None);
950 }
951
952 #[test]
953 fn get_mut() {
954 let mut cache = AssociativeCache::<
955 *mut u8,
956 usize,
957 Capacity4,
958 PointerTwoWay,
959 RoundRobinReplacement,
960 >::default();
961
962 cache.insert(0 as *mut _, 0);
963 assert_eq!(cache.get_mut(&(0 as *mut _)), Some(&mut 0));
964 assert_eq!(cache.get_mut(&(1 as *mut _)), None);
965
966 cache.insert(4 as *mut _, 4);
967 assert_eq!(cache.get_mut(&(0 as *mut _)), Some(&mut 0));
968 assert_eq!(cache.get_mut(&(4 as *mut _)), Some(&mut 4));
969 assert_eq!(cache.get_mut(&(1 as *mut _)), None);
970
971 assert_eq!(cache.insert(8 as *mut _, 8), Some((4 as *mut _, 4)));
972 assert_eq!(cache.get_mut(&(0 as *mut _)), Some(&mut 0));
973 assert_eq!(cache.get_mut(&(8 as *mut _)), Some(&mut 8));
974 assert_eq!(cache.get_mut(&(1 as *mut _)), None);
975 }
976
977 #[test]
978 fn remove() {
979 let mut cache = AssociativeCache::<
980 *mut u8,
981 usize,
982 Capacity4,
983 PointerTwoWay,
984 RoundRobinReplacement,
985 >::default();
986
987 cache.insert(0 as *mut _, 0);
988 cache.insert(4 as *mut _, 4);
989 assert_eq!(cache.len(), 2);
990
991 assert_eq!(cache.remove(&(4 as *mut _)), Some(4));
992 assert_eq!(cache.remove(&(4 as *mut _)), None);
993 assert_eq!(cache.remove(&(0 as *mut _)), Some(0));
994 assert_eq!(cache.remove(&(0 as *mut _)), None);
995 }
996
997 #[test]
998 fn retain() {
999 let mut cache = AssociativeCache::<
1000 *mut u8,
1001 usize,
1002 Capacity4,
1003 PointerTwoWay,
1004 RoundRobinReplacement,
1005 >::default();
1006
1007 cache.insert(0 as *mut _, 0);
1008 cache.insert(1 as *mut _, 1);
1009 cache.insert(2 as *mut _, 2);
1010 cache.insert(3 as *mut _, 3);
1011 assert_eq!(cache.len(), 4);
1012
1013 cache.retain(|_, v| *v % 2 == 0);
1014 assert_eq!(cache.len(), 2);
1015 assert_eq!(cache.get(&(0 as *mut _)), Some(&0));
1016 assert_eq!(cache.get(&(1 as *mut _)), None);
1017 assert_eq!(cache.get(&(2 as *mut _)), Some(&2));
1018 assert_eq!(cache.get(&(3 as *mut _)), None);
1019 }
1020
1021 #[test]
1022 fn entry() {
1023 let mut cache = AssociativeCache::<
1024 *mut u8,
1025 usize,
1026 Capacity1,
1027 PointerDirectMapped,
1028 RoundRobinReplacement,
1029 >::default();
1030
1031 // Vacant
1032 assert_eq!(
1033 cache
1034 .entry(&(0 as *mut _))
1035 .or_insert_with(|| 0 as *mut _, || 0),
1036 &mut 0
1037 );
1038 assert_eq!(cache.len(), 1);
1039
1040 // Occupied
1041 assert_eq!(
1042 cache
1043 .entry(&(0 as *mut _))
1044 .or_insert_with(|| unreachable!(), || unreachable!()),
1045 &mut 0
1046 );
1047 assert_eq!(cache.len(), 1);
1048
1049 // Replace
1050 let mut entry = cache.entry(&(1 as *mut _));
1051 assert_eq!(
1052 entry.take_entry_that_will_be_replaced(),
1053 Some((0 as *mut _, 0))
1054 );
1055 assert_eq!(entry.or_insert_with(|| 1 as *mut _, || 1), &mut 1);
1056 assert_eq!(cache.len(), 1);
1057 }
1058
1059 #[test]
1060 fn iter() {
1061 let mut cache = AssociativeCache::<
1062 *mut u8,
1063 usize,
1064 Capacity4,
1065 PointerDirectMapped,
1066 RoundRobinReplacement,
1067 >::default();
1068
1069 cache.insert(0 as *mut _, 0);
1070 cache.insert(1 as *mut _, 1);
1071 cache.insert(2 as *mut _, 2);
1072 cache.insert(3 as *mut _, 3);
1073 assert_eq!(cache.len(), 4);
1074
1075 let mut seen = vec![false; 4];
1076 for (&k, &v) in &cache {
1077 assert!(!seen[v]);
1078 seen[v] = true;
1079 assert_eq!(k as usize, v);
1080 }
1081 assert!(seen.iter().all(|&b| b));
1082 }
1083
1084 #[test]
1085 fn iter_mut() {
1086 let mut cache = AssociativeCache::<
1087 *mut u8,
1088 usize,
1089 Capacity4,
1090 PointerDirectMapped,
1091 RoundRobinReplacement,
1092 >::default();
1093
1094 cache.insert(0 as *mut _, 0);
1095 cache.insert(1 as *mut _, 1);
1096 cache.insert(2 as *mut _, 2);
1097 cache.insert(3 as *mut _, 3);
1098 assert_eq!(cache.len(), 4);
1099
1100 let mut seen = vec![false; 4];
1101 for (&k, v) in &mut cache {
1102 assert!(!seen[*v]);
1103 seen[*v] = true;
1104 assert_eq!(k as usize, *v);
1105 *v += 1;
1106 }
1107 assert!(seen.iter().all(|&b| b));
1108
1109 assert_eq!(cache.get(&(0 as *mut _)), Some(&1));
1110 assert_eq!(cache.get(&(1 as *mut _)), Some(&2));
1111 assert_eq!(cache.get(&(2 as *mut _)), Some(&3));
1112 assert_eq!(cache.get(&(3 as *mut _)), Some(&4));
1113 }
1114
1115 #[test]
1116 fn into_iter() {
1117 let mut cache = AssociativeCache::<
1118 *mut u8,
1119 usize,
1120 Capacity4,
1121 PointerDirectMapped,
1122 RoundRobinReplacement,
1123 >::default();
1124
1125 cache.insert(0 as *mut _, 0);
1126 cache.insert(1 as *mut _, 1);
1127 cache.insert(2 as *mut _, 2);
1128 cache.insert(3 as *mut _, 3);
1129 assert_eq!(cache.len(), 4);
1130
1131 let mut seen = vec![false; 4];
1132 for (k, v) in cache {
1133 assert!(!seen[v]);
1134 seen[v] = true;
1135 assert_eq!(k as usize, v);
1136 }
1137 assert!(seen.iter().all(|&b| b));
1138 }
1139}