A better Rust ATProto crate
1use super::{
2 deques::Deques, AccessTime, CacheBuilder, Iter, KeyDate, KeyHashDate, ValueEntry, Weigher,
3};
4use crate::{
5 common::{
6 self,
7 deque::{DeqNode, Deque},
8 frequency_sketch::FrequencySketch,
9 time::{CheckedTimeOps, Clock, Instant},
10 CacheRegion,
11 },
12 Policy,
13};
14
15use smallvec::SmallVec;
16use std::{
17 borrow::Borrow,
18 collections::{hash_map::RandomState, HashMap},
19 fmt,
20 hash::{BuildHasher, Hash},
21 ptr::NonNull,
22 rc::Rc,
23 time::Duration,
24};
25
26const EVICTION_BATCH_SIZE: usize = 100;
27
28type CacheStore<K, V, S> = std::collections::HashMap<Rc<K>, ValueEntry<K, V>, S>;
29
30/// An in-memory cache that is _not_ thread-safe.
31///
32/// `Cache` utilizes a hash table [`std::collections::HashMap`][std-hashmap] from the
33/// standard library for the central key-value storage. `Cache` performs a
34/// best-effort bounding of the map using an entry replacement algorithm to determine
35/// which entries to evict when the capacity is exceeded.
36///
37/// [std-hashmap]: https://doc.rust-lang.org/std/collections/struct.HashMap.html
38///
39/// # Characteristic difference between `unsync` and `sync`/`future` caches
40///
41/// If you use a cache from a single thread application, `unsync::Cache` may
42/// outperform other caches for updates and retrievals because other caches have some
43/// overhead on syncing internal data structures between threads.
44///
45/// However, other caches may outperform `unsync::Cache` on the same operations when
46/// expiration polices are configured on a multi-core system. `unsync::Cache` evicts
47/// expired entries as a part of update and retrieval operations while others evict
48/// them using a dedicated background thread.
49///
50/// # Examples
51///
52/// Cache entries are manually added using the insert method, and are stored in the
53/// cache until either evicted or manually invalidated.
54///
55/// Here's an example of reading and updating a cache by using the main thread:
56///
57///```rust
58/// use mini_moka_wasm::unsync::Cache;
59///
60/// const NUM_KEYS: usize = 64;
61///
62/// fn value(n: usize) -> String {
63/// format!("value {}", n)
64/// }
65///
66/// // Create a cache that can store up to 10,000 entries.
67/// let mut cache = Cache::new(10_000);
68///
69/// // Insert 64 entries.
70/// for key in 0..NUM_KEYS {
71/// cache.insert(key, value(key));
72/// }
73///
74/// // Invalidate every 4 element of the inserted entries.
75/// for key in (0..NUM_KEYS).step_by(4) {
76/// cache.invalidate(&key);
77/// }
78///
79/// // Verify the result.
80/// for key in 0..NUM_KEYS {
81/// if key % 4 == 0 {
82/// assert_eq!(cache.get(&key), None);
83/// } else {
84/// assert_eq!(cache.get(&key), Some(&value(key)));
85/// }
86/// }
87/// ```
88///
89/// # Size-based Eviction
90///
91/// ```rust
92/// use std::convert::TryInto;
93/// use mini_moka_wasm::unsync::Cache;
94///
95/// // Evict based on the number of entries in the cache.
96/// let mut cache = Cache::builder()
97/// // Up to 10,000 entries.
98/// .max_capacity(10_000)
99/// // Create the cache.
100/// .build();
101/// cache.insert(1, "one".to_string());
102///
103/// // Evict based on the byte length of strings in the cache.
104/// let mut cache = Cache::builder()
105/// // A weigher closure takes &K and &V and returns a u32
106/// // representing the relative size of the entry.
107/// .weigher(|_key, value: &String| -> u32 {
108/// value.len().try_into().unwrap_or(u32::MAX)
109/// })
110/// // This cache will hold up to 32MiB of values.
111/// .max_capacity(32 * 1024 * 1024)
112/// .build();
113/// cache.insert(2, "two".to_string());
114/// ```
115///
116/// If your cache should not grow beyond a certain size, use the `max_capacity`
117/// method of the [`CacheBuilder`][builder-struct] to set the upper bound. The cache
118/// will try to evict entries that have not been used recently or very often.
119///
120/// At the cache creation time, a weigher closure can be set by the `weigher` method
121/// of the `CacheBuilder`. A weigher closure takes `&K` and `&V` as the arguments and
122/// returns a `u32` representing the relative size of the entry:
123///
124/// - If the `weigher` is _not_ set, the cache will treat each entry has the same
125/// size of `1`. This means the cache will be bounded by the number of entries.
126/// - If the `weigher` is set, the cache will call the weigher to calculate the
127/// weighted size (relative size) on an entry. This means the cache will be bounded
128/// by the total weighted size of entries.
129///
130/// Note that weighted sizes are not used when making eviction selections.
131///
132/// [builder-struct]: ./struct.CacheBuilder.html
133///
134/// # Time-based Expirations
135///
136/// `Cache` supports the following expiration policies:
137///
138/// - **Time to live**: A cached entry will be expired after the specified duration
139/// past from `insert`.
140/// - **Time to idle**: A cached entry will be expired after the specified duration
141/// past from `get` or `insert`.
142///
143/// See the [`CacheBuilder`][builder-struct]'s doc for how to configure a cache
144/// with them.
145///
146/// [builder-struct]: ./struct.CacheBuilder.html
147///
148/// # Hashing Algorithm
149///
150/// By default, `Cache` uses a hashing algorithm selected to provide resistance
151/// against HashDoS attacks. It will the same one used by
152/// `std::collections::HashMap`, which is currently SipHash 1-3.
153///
154/// While SipHash's performance is very competitive for medium sized keys, other
155/// hashing algorithms will outperform it for small keys such as integers as well as
156/// large keys such as long strings. However those algorithms will typically not
157/// protect against attacks such as HashDoS.
158///
159/// The hashing algorithm can be replaced on a per-`Cache` basis using the
160/// [`build_with_hasher`][build-with-hasher-method] method of the
161/// `CacheBuilder`. Many alternative algorithms are available on crates.io, such
162/// as the [aHash][ahash-crate] crate.
163///
164/// [build-with-hasher-method]: ./struct.CacheBuilder.html#method.build_with_hasher
165/// [ahash-crate]: https://crates.io/crates/ahash
166///
167pub struct Cache<K, V, S = RandomState> {
168 max_capacity: Option<u64>,
169 entry_count: u64,
170 weighted_size: u64,
171 cache: CacheStore<K, V, S>,
172 build_hasher: S,
173 weigher: Option<Weigher<K, V>>,
174 deques: Deques<K>,
175 frequency_sketch: FrequencySketch,
176 frequency_sketch_enabled: bool,
177 time_to_live: Option<Duration>,
178 time_to_idle: Option<Duration>,
179 expiration_clock: Option<Clock>,
180}
181
182impl<K, V, S> fmt::Debug for Cache<K, V, S>
183where
184 K: fmt::Debug + Eq + Hash,
185 V: fmt::Debug,
186 // TODO: Remove these bounds from S.
187 S: BuildHasher + Clone,
188{
189 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
190 let mut d_map = f.debug_map();
191
192 for (k, v) in self.iter() {
193 d_map.entry(&k, &v);
194 }
195
196 d_map.finish()
197 }
198}
199
200impl<K, V> Cache<K, V, RandomState>
201where
202 K: Hash + Eq,
203{
204 /// Constructs a new `Cache<K, V>` that will store up to the `max_capacity` entries.
205 ///
206 /// To adjust various configuration knobs such as `initial_capacity` or
207 /// `time_to_live`, use the [`CacheBuilder`][builder-struct].
208 ///
209 /// [builder-struct]: ./struct.CacheBuilder.html
210 pub fn new(max_capacity: u64) -> Self {
211 let build_hasher = RandomState::default();
212 Self::with_everything(Some(max_capacity), None, build_hasher, None, None, None)
213 }
214
215 /// Returns a [`CacheBuilder`][builder-struct], which can builds a `Cache` with
216 /// various configuration knobs.
217 ///
218 /// [builder-struct]: ./struct.CacheBuilder.html
219 pub fn builder() -> CacheBuilder<K, V, Cache<K, V, RandomState>> {
220 CacheBuilder::default()
221 }
222}
223
224//
225// public
226//
227impl<K, V, S> Cache<K, V, S> {
228 /// Returns a read-only cache policy of this cache.
229 ///
230 /// At this time, cache policy cannot be modified after cache creation.
231 /// A future version may support to modify it.
232 pub fn policy(&self) -> Policy {
233 Policy::new(self.max_capacity, self.time_to_live, self.time_to_idle)
234 }
235
236 /// Returns the number of entries in this cache.
237 ///
238 /// # Example
239 ///
240 /// ```rust
241 /// use mini_moka_wasm::unsync::Cache;
242 ///
243 /// let mut cache = Cache::new(10);
244 /// cache.insert('n', "Netherland Dwarf");
245 /// cache.insert('l', "Lop Eared");
246 /// cache.insert('d', "Dutch");
247 ///
248 /// // Ensure an entry exists.
249 /// assert!(cache.contains_key(&'n'));
250 ///
251 /// // Followings will print the actual numbers.
252 /// println!("{}", cache.entry_count()); // -> 3
253 /// println!("{}", cache.weighted_size()); // -> 3
254 /// ```
255 ///
256 pub fn entry_count(&self) -> u64 {
257 self.entry_count
258 }
259
260 /// Returns the total weighted size of entries in this cache.
261 ///
262 /// See [`entry_count`](#method.entry_count) for a sample code.
263 pub fn weighted_size(&self) -> u64 {
264 self.weighted_size
265 }
266}
267
268impl<K, V, S> Cache<K, V, S>
269where
270 K: Hash + Eq,
271 S: BuildHasher + Clone,
272{
273 pub(crate) fn with_everything(
274 max_capacity: Option<u64>,
275 initial_capacity: Option<usize>,
276 build_hasher: S,
277 weigher: Option<Weigher<K, V>>,
278 time_to_live: Option<Duration>,
279 time_to_idle: Option<Duration>,
280 ) -> Self {
281 let cache = HashMap::with_capacity_and_hasher(
282 initial_capacity.unwrap_or_default(),
283 build_hasher.clone(),
284 );
285
286 Self {
287 max_capacity,
288 entry_count: 0,
289 weighted_size: 0,
290 cache,
291 build_hasher,
292 weigher,
293 deques: Default::default(),
294 frequency_sketch: Default::default(),
295 frequency_sketch_enabled: false,
296 time_to_live,
297 time_to_idle,
298 expiration_clock: None,
299 }
300 }
301
302 /// Returns `true` if the cache contains a value for the key.
303 ///
304 /// Unlike the `get` method, this method is not considered a cache read operation,
305 /// so it does not update the historic popularity estimator or reset the idle
306 /// timer for the key.
307 ///
308 /// The key may be any borrowed form of the cache's key type, but `Hash` and `Eq`
309 /// on the borrowed form _must_ match those for the key type.
310 pub fn contains_key<Q>(&mut self, key: &Q) -> bool
311 where
312 Rc<K>: Borrow<Q>,
313 Q: Hash + Eq + ?Sized,
314 {
315 let timestamp = self.evict_expired_if_needed();
316 self.evict_lru_entries();
317
318 match (self.cache.get(key), timestamp) {
319 // Value not found.
320 (None, _) => false,
321 // Value found, no expiry.
322 (Some(_), None) => true,
323 // Value found, check if expired.
324 (Some(entry), Some(ts)) => {
325 !Self::is_expired_entry_wo(&self.time_to_live, entry, ts)
326 && !Self::is_expired_entry_ao(&self.time_to_idle, entry, ts)
327 }
328 }
329 }
330
331 /// Returns an immutable reference of the value corresponding to the key.
332 ///
333 /// The key may be any borrowed form of the cache's key type, but `Hash` and `Eq`
334 /// on the borrowed form _must_ match those for the key type.
335 pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
336 where
337 Rc<K>: Borrow<Q>,
338 Q: Hash + Eq + ?Sized,
339 {
340 let timestamp = self.evict_expired_if_needed();
341 self.evict_lru_entries();
342 self.frequency_sketch.increment(self.hash(key));
343
344 match (self.cache.get_mut(key), timestamp, &mut self.deques) {
345 // Value not found.
346 (None, _, _) => None,
347 // Value found, no expiry.
348 (Some(entry), None, deqs) => {
349 Self::record_hit(deqs, entry, None);
350 Some(&entry.value)
351 }
352 // Value found, check if expired.
353 (Some(entry), Some(ts), deqs) => {
354 if Self::is_expired_entry_wo(&self.time_to_live, entry, ts)
355 || Self::is_expired_entry_ao(&self.time_to_idle, entry, ts)
356 {
357 None
358 } else {
359 Self::record_hit(deqs, entry, timestamp);
360 Some(&entry.value)
361 }
362 }
363 }
364 }
365
366 pub(crate) fn is_expired_entry(&self, entry: &ValueEntry<K, V>) -> bool {
367 let now = self.current_time_from_expiration_clock();
368 Self::is_expired_entry_wo(&self.time_to_live, entry, now)
369 || Self::is_expired_entry_ao(&self.time_to_idle, entry, now)
370 }
371
372 /// Inserts a key-value pair into the cache.
373 ///
374 /// If the cache has this key present, the value is updated.
375 pub fn insert(&mut self, key: K, value: V) {
376 let timestamp = self.evict_expired_if_needed();
377 self.evict_lru_entries();
378 let policy_weight = weigh(&mut self.weigher, &key, &value);
379 let key = Rc::new(key);
380 let entry = ValueEntry::new(value, policy_weight);
381
382 if let Some(old_entry) = self.cache.insert(Rc::clone(&key), entry) {
383 self.handle_update(key, timestamp, policy_weight, old_entry);
384 } else {
385 let hash = self.hash(&key);
386 self.handle_insert(key, hash, policy_weight, timestamp);
387 }
388 }
389
390 /// Discards any cached value for the key.
391 ///
392 /// The key may be any borrowed form of the cache's key type, but `Hash` and `Eq`
393 /// on the borrowed form _must_ match those for the key type.
394 pub fn invalidate<Q>(&mut self, key: &Q)
395 where
396 Rc<K>: Borrow<Q>,
397 Q: Hash + Eq + ?Sized,
398 {
399 self.evict_expired_if_needed();
400 self.evict_lru_entries();
401
402 if let Some(mut entry) = self.cache.remove(key) {
403 let weight = entry.policy_weight();
404 self.deques.unlink_ao(&mut entry);
405 Deques::unlink_wo(&mut self.deques.write_order, &mut entry);
406 self.saturating_sub_from_total_weight(weight as u64);
407 }
408 }
409
410 /// Discards any cached value for the key, returning the cached value.
411 ///
412 /// The key may be any borrowed form of the cache's key type, but `Hash` and `Eq`
413 /// on the borrowed form _must_ match those for the key type.
414 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
415 where
416 Rc<K>: Borrow<Q>,
417 Q: Hash + Eq + ?Sized,
418 {
419 self.evict_expired_if_needed();
420 self.evict_lru_entries();
421
422 if let Some(mut entry) = self.cache.remove(key) {
423 let weight = entry.policy_weight();
424 self.deques.unlink_ao(&mut entry);
425 crate::unsync::deques::Deques::unlink_wo(&mut self.deques.write_order, &mut entry);
426 self.saturating_sub_from_total_weight(weight as u64);
427 Some(entry.value)
428 } else {
429 None
430 }
431 }
432
433 /// Discards all cached values.
434 ///
435 /// Like the `invalidate` method, this method does not clear the historic
436 /// popularity estimator of keys so that it retains the client activities of
437 /// trying to retrieve an item.
438 pub fn invalidate_all(&mut self) {
439 self.cache.clear();
440 self.deques.clear();
441 self.weighted_size = 0;
442 }
443
444 /// Discards cached values that satisfy a predicate.
445 ///
446 /// `invalidate_entries_if` takes a closure that returns `true` or `false`.
447 /// `invalidate_entries_if` will apply the closure to each cached value,
448 /// and if the closure returns `true`, the value will be invalidated.
449 ///
450 /// Like the `invalidate` method, this method does not clear the historic
451 /// popularity estimator of keys so that it retains the client activities of
452 /// trying to retrieve an item.
453 // -----------------------------------------------------------------------
454 // (The followings are not doc comments)
455 // We need this #[allow(...)] to avoid a false Clippy warning about needless
456 // collect to create keys_to_invalidate.
457 // clippy 0.1.52 (9a1dfd2dc5c 2021-04-30) in Rust 1.52.0-beta.7
458 #[allow(clippy::needless_collect)]
459 pub fn invalidate_entries_if(&mut self, mut predicate: impl FnMut(&K, &V) -> bool) {
460 let Self { cache, deques, .. } = self;
461
462 // Since we can't do cache.iter() and cache.remove() at the same time,
463 // invalidation needs to run in two steps:
464 // 1. Examine all entries in this cache and collect keys to invalidate.
465 // 2. Remove entries for the keys.
466
467 let keys_to_invalidate = cache
468 .iter()
469 .filter(|(key, entry)| (predicate)(key, &entry.value))
470 .map(|(key, _)| Rc::clone(key))
471 .collect::<Vec<_>>();
472
473 let mut invalidated = 0u64;
474
475 keys_to_invalidate.into_iter().for_each(|k| {
476 if let Some(mut entry) = cache.remove(&k) {
477 let weight = entry.policy_weight();
478 deques.unlink_ao(&mut entry);
479 Deques::unlink_wo(&mut deques.write_order, &mut entry);
480 invalidated = invalidated.saturating_sub(weight as u64);
481 }
482 });
483 self.saturating_sub_from_total_weight(invalidated);
484 }
485
486 /// Creates an iterator visiting all key-value pairs in arbitrary order. The
487 /// iterator element type is `(&K, &V)`.
488 ///
489 /// Unlike the `get` method, visiting entries via an iterator do not update the
490 /// historic popularity estimator or reset idle timers for keys.
491 ///
492 /// # Examples
493 ///
494 /// ```rust
495 /// use mini_moka_wasm::unsync::Cache;
496 ///
497 /// let mut cache = Cache::new(100);
498 /// cache.insert("Julia", 14);
499 ///
500 /// let mut iter = cache.iter();
501 /// let (k, v) = iter.next().unwrap(); // (&K, &V)
502 /// assert_eq!(k, &"Julia");
503 /// assert_eq!(v, &14);
504 ///
505 /// assert!(iter.next().is_none());
506 /// ```
507 ///
508 pub fn iter(&self) -> Iter<'_, K, V, S> {
509 Iter::new(self, self.cache.iter())
510 }
511}
512
513//
514// private
515//
516impl<K, V, S> Cache<K, V, S>
517where
518 K: Hash + Eq,
519 S: BuildHasher + Clone,
520{
521 #[inline]
522 fn hash<Q>(&self, key: &Q) -> u64
523 where
524 Rc<K>: Borrow<Q>,
525 Q: Hash + Eq + ?Sized,
526 {
527 self.build_hasher.hash_one(key)
528 }
529
530 #[inline]
531 fn has_expiry(&self) -> bool {
532 self.time_to_live.is_some() || self.time_to_idle.is_some()
533 }
534
535 #[inline]
536 fn evict_expired_if_needed(&mut self) -> Option<Instant> {
537 if self.has_expiry() {
538 let ts = self.current_time_from_expiration_clock();
539 self.evict_expired(ts);
540 Some(ts)
541 } else {
542 None
543 }
544 }
545
546 #[inline]
547 fn current_time_from_expiration_clock(&self) -> Instant {
548 if let Some(clock) = &self.expiration_clock {
549 Instant::new(clock.now())
550 } else {
551 Instant::now()
552 }
553 }
554
555 #[inline]
556 fn is_expired_entry_ao(
557 time_to_idle: &Option<Duration>,
558 entry: &impl AccessTime,
559 now: Instant,
560 ) -> bool {
561 if let (Some(ts), Some(tti)) = (entry.last_accessed(), time_to_idle) {
562 let checked_add = ts.checked_add(*tti);
563 if checked_add.is_none() {
564 panic!("ttl overflow")
565 }
566 return checked_add.unwrap() <= now;
567 }
568 false
569 }
570
571 #[inline]
572 fn is_expired_entry_wo(
573 time_to_live: &Option<Duration>,
574 entry: &impl AccessTime,
575 now: Instant,
576 ) -> bool {
577 if let (Some(ts), Some(ttl)) = (entry.last_modified(), time_to_live) {
578 let checked_add = ts.checked_add(*ttl);
579 if checked_add.is_none() {
580 panic!("ttl overflow")
581 }
582 return checked_add.unwrap() <= now;
583 }
584 false
585 }
586
587 fn record_hit(deques: &mut Deques<K>, entry: &mut ValueEntry<K, V>, ts: Option<Instant>) {
588 if let Some(ts) = ts {
589 entry.set_last_accessed(ts);
590 }
591 deques.move_to_back_ao(entry)
592 }
593
594 fn has_enough_capacity(&self, candidate_weight: u32, ws: u64) -> bool {
595 self.max_capacity
596 .map(|limit| ws + candidate_weight as u64 <= limit)
597 .unwrap_or(true)
598 }
599
600 fn weights_to_evict(&self) -> u64 {
601 self.max_capacity
602 .map(|limit| self.weighted_size.saturating_sub(limit))
603 .unwrap_or_default()
604 }
605
606 #[inline]
607 fn should_enable_frequency_sketch(&self) -> bool {
608 if self.frequency_sketch_enabled {
609 false
610 } else if let Some(max_cap) = self.max_capacity {
611 self.weighted_size >= max_cap / 2
612 } else {
613 false
614 }
615 }
616
617 #[inline]
618 fn enable_frequency_sketch(&mut self) {
619 if let Some(max_cap) = self.max_capacity {
620 let cap = if self.weigher.is_none() {
621 max_cap
622 } else {
623 (self.entry_count as f64 * (self.weighted_size as f64 / max_cap as f64)) as u64
624 };
625 self.do_enable_frequency_sketch(cap);
626 }
627 }
628
629 #[cfg(test)]
630 fn enable_frequency_sketch_for_testing(&mut self) {
631 if let Some(max_cap) = self.max_capacity {
632 self.do_enable_frequency_sketch(max_cap);
633 }
634 }
635
636 #[inline]
637 fn do_enable_frequency_sketch(&mut self, cache_capacity: u64) {
638 let skt_capacity = common::sketch_capacity(cache_capacity);
639 self.frequency_sketch.ensure_capacity(skt_capacity);
640 self.frequency_sketch_enabled = true;
641 }
642
643 fn saturating_add_to_total_weight(&mut self, weight: u64) {
644 let total = &mut self.weighted_size;
645 *total = total.saturating_add(weight);
646 }
647
648 fn saturating_sub_from_total_weight(&mut self, weight: u64) {
649 let total = &mut self.weighted_size;
650 *total = total.saturating_sub(weight);
651 }
652
653 #[inline]
654 fn handle_insert(
655 &mut self,
656 key: Rc<K>,
657 hash: u64,
658 policy_weight: u32,
659 timestamp: Option<Instant>,
660 ) {
661 let has_free_space = self.has_enough_capacity(policy_weight, self.weighted_size);
662 let (cache, deqs, freq) = (&mut self.cache, &mut self.deques, &self.frequency_sketch);
663
664 if has_free_space {
665 // Add the candidate to the deque.
666 let key = Rc::clone(&key);
667 let entry = cache.get_mut(&key).unwrap();
668 deqs.push_back_ao(
669 CacheRegion::MainProbation,
670 KeyHashDate::new(Rc::clone(&key), hash, timestamp),
671 entry,
672 );
673 if self.time_to_live.is_some() {
674 deqs.push_back_wo(KeyDate::new(key, timestamp), entry);
675 }
676 self.entry_count += 1;
677 self.saturating_add_to_total_weight(policy_weight as u64);
678
679 if self.should_enable_frequency_sketch() {
680 self.enable_frequency_sketch();
681 }
682
683 return;
684 }
685
686 if let Some(max) = self.max_capacity {
687 if policy_weight as u64 > max {
688 // The candidate is too big to fit in the cache. Reject it.
689 cache.remove(&Rc::clone(&key));
690 return;
691 }
692 }
693
694 let mut candidate = EntrySizeAndFrequency::new(policy_weight as u64);
695 candidate.add_frequency(freq, hash);
696
697 match Self::admit(&candidate, cache, deqs, freq, &mut self.weigher) {
698 AdmissionResult::Admitted {
699 victim_nodes,
700 victims_weight,
701 } => {
702 // Remove the victims from the cache (hash map) and deque.
703 for victim in victim_nodes {
704 // Remove the victim from the hash map.
705 let mut vic_entry = cache
706 .remove(unsafe { &victim.as_ref().element.key })
707 .expect("Cannot remove a victim from the hash map");
708 // And then remove the victim from the deques.
709 deqs.unlink_ao(&mut vic_entry);
710 Deques::unlink_wo(&mut deqs.write_order, &mut vic_entry);
711 self.entry_count -= 1;
712 }
713
714 // Add the candidate to the deque.
715 let entry = cache.get_mut(&key).unwrap();
716 let key = Rc::clone(&key);
717 deqs.push_back_ao(
718 CacheRegion::MainProbation,
719 KeyHashDate::new(Rc::clone(&key), hash, timestamp),
720 entry,
721 );
722 if self.time_to_live.is_some() {
723 deqs.push_back_wo(KeyDate::new(key, timestamp), entry);
724 }
725
726 self.entry_count += 1;
727 Self::saturating_sub_from_total_weight(self, victims_weight);
728 Self::saturating_add_to_total_weight(self, policy_weight as u64);
729
730 if self.should_enable_frequency_sketch() {
731 self.enable_frequency_sketch();
732 }
733 }
734 AdmissionResult::Rejected => {
735 // Remove the candidate from the cache.
736 cache.remove(&key);
737 }
738 }
739 }
740
741 /// Performs size-aware admission explained in the paper:
742 /// [Lightweight Robust Size Aware Cache Management][size-aware-cache-paper]
743 /// by Gil Einziger, Ohad Eytan, Roy Friedman, Ben Manes.
744 ///
745 /// [size-aware-cache-paper]: https://arxiv.org/abs/2105.08770
746 ///
747 /// There are some modifications in this implementation:
748 /// - To admit to the main space, candidate's frequency must be higher than
749 /// the aggregated frequencies of the potential victims. (In the paper,
750 /// `>=` operator is used rather than `>`) The `>` operator will do a better
751 /// job to prevent the main space from polluting.
752 /// - When a candidate is rejected, the potential victims will stay at the LRU
753 /// position of the probation access-order queue. (In the paper, they will be
754 /// promoted (to the MRU position?) to force the eviction policy to select a
755 /// different set of victims for the next candidate). We may implement the
756 /// paper's behavior later?
757 ///
758 #[inline]
759 fn admit(
760 candidate: &EntrySizeAndFrequency,
761 cache: &CacheStore<K, V, S>,
762 deqs: &Deques<K>,
763 freq: &FrequencySketch,
764 weigher: &mut Option<Weigher<K, V>>,
765 ) -> AdmissionResult<K> {
766 let mut victims = EntrySizeAndFrequency::default();
767 let mut victim_nodes = SmallVec::default();
768
769 // Get first potential victim at the LRU position.
770 let mut next_victim = deqs.probation.peek_front_ptr();
771
772 // Aggregate potential victims.
773 while victims.weight < candidate.weight {
774 if candidate.freq < victims.freq {
775 break;
776 }
777 if let Some(victim) = next_victim.take() {
778 next_victim = DeqNode::next_node_ptr(victim);
779 let vic_elem = &unsafe { victim.as_ref() }.element;
780
781 let vic_entry = cache
782 .get(&vic_elem.key)
783 .expect("Cannot get an victim entry");
784 victims.add_policy_weight(vic_elem.key.as_ref(), &vic_entry.value, weigher);
785 victims.add_frequency(freq, vic_elem.hash);
786 victim_nodes.push(victim);
787 } else {
788 // No more potential victims.
789 break;
790 }
791 }
792
793 // Admit or reject the candidate.
794
795 // TODO: Implement some randomness to mitigate hash DoS attack.
796 // See Caffeine's implementation.
797
798 if victims.weight >= candidate.weight && candidate.freq > victims.freq {
799 AdmissionResult::Admitted {
800 victim_nodes,
801 victims_weight: victims.weight,
802 }
803 } else {
804 AdmissionResult::Rejected
805 }
806 }
807
808 fn handle_update(
809 &mut self,
810 key: Rc<K>,
811 timestamp: Option<Instant>,
812 policy_weight: u32,
813 old_entry: ValueEntry<K, V>,
814 ) {
815 let old_policy_weight = old_entry.policy_weight();
816
817 let entry = self.cache.get_mut(&key).unwrap();
818 entry.replace_deq_nodes_with(old_entry);
819 if let Some(ts) = timestamp {
820 entry.set_last_accessed(ts);
821 entry.set_last_modified(ts);
822 }
823 entry.set_policy_weight(policy_weight);
824
825 let deqs = &mut self.deques;
826 deqs.move_to_back_ao(entry);
827 if self.time_to_live.is_some() {
828 deqs.move_to_back_wo(entry);
829 }
830
831 self.saturating_sub_from_total_weight(old_policy_weight as u64);
832 self.saturating_add_to_total_weight(policy_weight as u64);
833 }
834
835 fn evict_expired(&mut self, now: Instant) {
836 if self.time_to_live.is_some() {
837 let (count, weight) = self.remove_expired_wo(EVICTION_BATCH_SIZE, now);
838 self.entry_count -= count;
839 self.saturating_sub_from_total_weight(weight);
840 }
841
842 if self.time_to_idle.is_some() {
843 let deqs = &mut self.deques;
844 let (window, probation, protected, wo, cache, time_to_idle) = (
845 &mut deqs.window,
846 &mut deqs.probation,
847 &mut deqs.protected,
848 &mut deqs.write_order,
849 &mut self.cache,
850 &self.time_to_idle,
851 );
852
853 let mut rm_expired_ao = |name, deq| {
854 Self::remove_expired_ao(
855 name,
856 deq,
857 wo,
858 cache,
859 time_to_idle,
860 EVICTION_BATCH_SIZE,
861 now,
862 )
863 };
864
865 let (count1, weight1) = rm_expired_ao("window", window);
866 let (count2, weight2) = rm_expired_ao("probation", probation);
867 let (count3, weight3) = rm_expired_ao("protected", protected);
868
869 self.entry_count -= count1 + count2 + count3;
870 self.saturating_sub_from_total_weight(weight1);
871 self.saturating_sub_from_total_weight(weight2);
872 self.saturating_sub_from_total_weight(weight3);
873 }
874 }
875
876 // Returns (u64, u64) where (evicted_entry_count, evicted_policy_weight).
877 #[inline]
878 fn remove_expired_ao(
879 deq_name: &str,
880 deq: &mut Deque<KeyHashDate<K>>,
881 write_order_deq: &mut Deque<KeyDate<K>>,
882 cache: &mut CacheStore<K, V, S>,
883 time_to_idle: &Option<Duration>,
884 batch_size: usize,
885 now: Instant,
886 ) -> (u64, u64) {
887 let mut evicted_entry_count = 0u64;
888 let mut evicted_policy_weight = 0u64;
889
890 for _ in 0..batch_size {
891 let key = deq
892 .peek_front()
893 .and_then(|node| {
894 if Self::is_expired_entry_ao(time_to_idle, node, now) {
895 Some(Some(Rc::clone(&node.element.key)))
896 } else {
897 None
898 }
899 })
900 .unwrap_or_default();
901
902 if key.is_none() {
903 break;
904 }
905
906 let key = key.unwrap();
907
908 if let Some(mut entry) = cache.remove(&key) {
909 let weight = entry.policy_weight();
910 Deques::unlink_ao_from_deque(deq_name, deq, &mut entry);
911 Deques::unlink_wo(write_order_deq, &mut entry);
912 evicted_entry_count += 1;
913 evicted_policy_weight = evicted_policy_weight.saturating_add(weight as u64);
914 } else {
915 deq.pop_front();
916 }
917 }
918
919 (evicted_entry_count, evicted_policy_weight)
920 }
921
922 // Returns (u64, u64) where (evicted_entry_count, evicted_policy_weight).
923 #[inline]
924 fn remove_expired_wo(&mut self, batch_size: usize, now: Instant) -> (u64, u64) {
925 let mut evicted_entry_count = 0u64;
926 let mut evicted_policy_weight = 0u64;
927 let time_to_live = &self.time_to_live;
928
929 for _ in 0..batch_size {
930 let key = self
931 .deques
932 .write_order
933 .peek_front()
934 .and_then(|node| {
935 if Self::is_expired_entry_wo(time_to_live, node, now) {
936 Some(Some(Rc::clone(&node.element.key)))
937 } else {
938 None
939 }
940 })
941 .unwrap_or_default();
942
943 if key.is_none() {
944 break;
945 }
946
947 let key = key.unwrap();
948
949 if let Some(mut entry) = self.cache.remove(&key) {
950 let weight = entry.policy_weight();
951 self.deques.unlink_ao(&mut entry);
952 Deques::unlink_wo(&mut self.deques.write_order, &mut entry);
953 evicted_entry_count += 1;
954 evicted_policy_weight = evicted_policy_weight.saturating_sub(weight as u64);
955 } else {
956 self.deques.write_order.pop_front();
957 }
958 }
959
960 (evicted_entry_count, evicted_policy_weight)
961 }
962
963 #[inline]
964 fn evict_lru_entries(&mut self) {
965 const DEQ_NAME: &str = "probation";
966
967 let weights_to_evict = self.weights_to_evict();
968 let mut evicted_count = 0u64;
969 let mut evicted_policy_weight = 0u64;
970
971 {
972 let deqs = &mut self.deques;
973 let (probation, wo, cache) =
974 (&mut deqs.probation, &mut deqs.write_order, &mut self.cache);
975
976 for _ in 0..EVICTION_BATCH_SIZE {
977 if evicted_policy_weight >= weights_to_evict {
978 break;
979 }
980
981 // clippy::map_clone will give us a false positive warning here.
982 // Version: clippy 0.1.77 (f2048098a1c 2024-02-09) in Rust 1.77.0-beta.2
983 #[allow(clippy::map_clone)]
984 let key = probation
985 .peek_front()
986 .map(|node| Rc::clone(&node.element.key));
987
988 if key.is_none() {
989 break;
990 }
991 let key = key.unwrap();
992
993 if let Some(mut entry) = cache.remove(&key) {
994 let weight = entry.policy_weight();
995 Deques::unlink_ao_from_deque(DEQ_NAME, probation, &mut entry);
996 Deques::unlink_wo(wo, &mut entry);
997 evicted_count += 1;
998 evicted_policy_weight = evicted_policy_weight.saturating_add(weight as u64);
999 } else {
1000 probation.pop_front();
1001 }
1002 }
1003 }
1004
1005 self.entry_count -= evicted_count;
1006 self.saturating_sub_from_total_weight(evicted_policy_weight);
1007 }
1008}
1009
1010//
1011// for testing
1012//
1013#[cfg(test)]
1014impl<K, V, S> Cache<K, V, S>
1015where
1016 K: Hash + Eq,
1017 S: BuildHasher + Clone,
1018{
1019 fn set_expiration_clock(&mut self, clock: Option<crate::common::time::Clock>) {
1020 self.expiration_clock = clock;
1021 }
1022}
1023
1024#[derive(Default)]
1025struct EntrySizeAndFrequency {
1026 weight: u64,
1027 freq: u32,
1028}
1029
1030impl EntrySizeAndFrequency {
1031 fn new(policy_weight: u64) -> Self {
1032 Self {
1033 weight: policy_weight,
1034 ..Default::default()
1035 }
1036 }
1037
1038 fn add_policy_weight<K, V>(&mut self, key: &K, value: &V, weigher: &mut Option<Weigher<K, V>>) {
1039 self.weight += weigh(weigher, key, value) as u64;
1040 }
1041
1042 fn add_frequency(&mut self, freq: &FrequencySketch, hash: u64) {
1043 self.freq += freq.frequency(hash) as u32;
1044 }
1045}
1046
1047// Access-Order Queue Node
1048type AoqNode<K> = NonNull<DeqNode<KeyHashDate<K>>>;
1049
1050enum AdmissionResult<K> {
1051 Admitted {
1052 victim_nodes: SmallVec<[AoqNode<K>; 8]>,
1053 victims_weight: u64,
1054 },
1055 Rejected,
1056}
1057
1058//
1059// private free-standing functions
1060//
1061#[inline]
1062fn weigh<K, V>(weigher: &mut Option<Weigher<K, V>>, key: &K, value: &V) -> u32 {
1063 weigher.as_mut().map(|w| w(key, value)).unwrap_or(1)
1064}
1065
1066// To see the debug prints, run test as `cargo test -- --nocapture`
1067#[cfg(test)]
1068mod tests {
1069 use wasm_bindgen_test::wasm_bindgen_test;
1070
1071 use super::Cache;
1072 use crate::common::time::Clock;
1073
1074 use std::time::Duration;
1075
1076 #[test]
1077 #[wasm_bindgen_test]
1078 fn basic_single_thread() {
1079 let mut cache = Cache::new(3);
1080 cache.enable_frequency_sketch_for_testing();
1081
1082 cache.insert("a", "alice");
1083 cache.insert("b", "bob");
1084 assert_eq!(cache.get(&"a"), Some(&"alice"));
1085 assert!(cache.contains_key(&"a"));
1086 assert!(cache.contains_key(&"b"));
1087 assert_eq!(cache.get(&"b"), Some(&"bob"));
1088 // counts: a -> 1, b -> 1
1089
1090 cache.insert("c", "cindy");
1091 assert_eq!(cache.get(&"c"), Some(&"cindy"));
1092 assert!(cache.contains_key(&"c"));
1093 // counts: a -> 1, b -> 1, c -> 1
1094
1095 assert!(cache.contains_key(&"a"));
1096 assert_eq!(cache.get(&"a"), Some(&"alice"));
1097 assert_eq!(cache.get(&"b"), Some(&"bob"));
1098 assert!(cache.contains_key(&"b"));
1099 // counts: a -> 2, b -> 2, c -> 1
1100
1101 // "d" should not be admitted because its frequency is too low.
1102 cache.insert("d", "david"); // count: d -> 0
1103 assert_eq!(cache.get(&"d"), None); // d -> 1
1104 assert!(!cache.contains_key(&"d"));
1105
1106 cache.insert("d", "david");
1107 assert!(!cache.contains_key(&"d"));
1108 assert_eq!(cache.get(&"d"), None); // d -> 2
1109
1110 // "d" should be admitted and "c" should be evicted
1111 // because d's frequency is higher than c's.
1112 cache.insert("d", "dennis");
1113 assert_eq!(cache.get(&"a"), Some(&"alice"));
1114 assert_eq!(cache.get(&"b"), Some(&"bob"));
1115 assert_eq!(cache.get(&"c"), None);
1116 assert_eq!(cache.get(&"d"), Some(&"dennis"));
1117 assert!(cache.contains_key(&"a"));
1118 assert!(cache.contains_key(&"b"));
1119 assert!(!cache.contains_key(&"c"));
1120 assert!(cache.contains_key(&"d"));
1121
1122 cache.invalidate(&"b");
1123 assert_eq!(cache.get(&"b"), None);
1124 assert!(!cache.contains_key(&"b"));
1125 }
1126
1127 #[test]
1128 #[wasm_bindgen_test]
1129 fn size_aware_eviction() {
1130 let weigher = |_k: &&str, v: &(&str, u32)| v.1;
1131
1132 let alice = ("alice", 10);
1133 let bob = ("bob", 15);
1134 let bill = ("bill", 20);
1135 let cindy = ("cindy", 5);
1136 let david = ("david", 15);
1137 let dennis = ("dennis", 15);
1138
1139 let mut cache = Cache::builder().max_capacity(31).weigher(weigher).build();
1140 cache.enable_frequency_sketch_for_testing();
1141
1142 cache.insert("a", alice);
1143 cache.insert("b", bob);
1144 assert_eq!(cache.get(&"a"), Some(&alice));
1145 assert!(cache.contains_key(&"a"));
1146 assert!(cache.contains_key(&"b"));
1147 assert_eq!(cache.get(&"b"), Some(&bob));
1148 // order (LRU -> MRU) and counts: a -> 1, b -> 1
1149
1150 cache.insert("c", cindy);
1151 assert_eq!(cache.get(&"c"), Some(&cindy));
1152 assert!(cache.contains_key(&"c"));
1153 // order and counts: a -> 1, b -> 1, c -> 1
1154
1155 assert!(cache.contains_key(&"a"));
1156 assert_eq!(cache.get(&"a"), Some(&alice));
1157 assert_eq!(cache.get(&"b"), Some(&bob));
1158 assert!(cache.contains_key(&"b"));
1159 // order and counts: c -> 1, a -> 2, b -> 2
1160
1161 // To enter "d" (weight: 15), it needs to evict "c" (w: 5) and "a" (w: 10).
1162 // "d" must have higher count than 3, which is the aggregated count
1163 // of "a" and "c".
1164 cache.insert("d", david); // count: d -> 0
1165 assert_eq!(cache.get(&"d"), None); // d -> 1
1166 assert!(!cache.contains_key(&"d"));
1167
1168 cache.insert("d", david);
1169 assert!(!cache.contains_key(&"d"));
1170 assert_eq!(cache.get(&"d"), None); // d -> 2
1171
1172 cache.insert("d", david);
1173 assert_eq!(cache.get(&"d"), None); // d -> 3
1174 assert!(!cache.contains_key(&"d"));
1175
1176 cache.insert("d", david);
1177 assert!(!cache.contains_key(&"d"));
1178 assert_eq!(cache.get(&"d"), None); // d -> 4
1179
1180 // Finally "d" should be admitted by evicting "c" and "a".
1181 cache.insert("d", dennis);
1182 assert_eq!(cache.get(&"a"), None);
1183 assert_eq!(cache.get(&"b"), Some(&bob));
1184 assert_eq!(cache.get(&"c"), None);
1185 assert_eq!(cache.get(&"d"), Some(&dennis));
1186 assert!(!cache.contains_key(&"a"));
1187 assert!(cache.contains_key(&"b"));
1188 assert!(!cache.contains_key(&"c"));
1189 assert!(cache.contains_key(&"d"));
1190
1191 // Update "b" with "bill" (w: 15 -> 20). This should evict "d" (w: 15).
1192 cache.insert("b", bill);
1193 assert_eq!(cache.get(&"b"), Some(&bill));
1194 assert_eq!(cache.get(&"d"), None);
1195 assert!(cache.contains_key(&"b"));
1196 assert!(!cache.contains_key(&"d"));
1197
1198 // Re-add "a" (w: 10) and update "b" with "bob" (w: 20 -> 15).
1199 cache.insert("a", alice);
1200 cache.insert("b", bob);
1201 assert_eq!(cache.get(&"a"), Some(&alice));
1202 assert_eq!(cache.get(&"b"), Some(&bob));
1203 assert_eq!(cache.get(&"d"), None);
1204 assert!(cache.contains_key(&"a"));
1205 assert!(cache.contains_key(&"b"));
1206 assert!(!cache.contains_key(&"d"));
1207
1208 // Verify the sizes.
1209 assert_eq!(cache.entry_count(), 2);
1210 assert_eq!(cache.weighted_size(), 25);
1211 }
1212
1213 #[test]
1214 #[wasm_bindgen_test]
1215 fn invalidate_all() {
1216 let mut cache = Cache::new(100);
1217 cache.enable_frequency_sketch_for_testing();
1218
1219 cache.insert("a", "alice");
1220 cache.insert("b", "bob");
1221 cache.insert("c", "cindy");
1222 assert_eq!(cache.get(&"a"), Some(&"alice"));
1223 assert_eq!(cache.get(&"b"), Some(&"bob"));
1224 assert_eq!(cache.get(&"c"), Some(&"cindy"));
1225 assert!(cache.contains_key(&"a"));
1226 assert!(cache.contains_key(&"b"));
1227 assert!(cache.contains_key(&"c"));
1228
1229 cache.invalidate_all();
1230
1231 cache.insert("d", "david");
1232
1233 assert!(cache.get(&"a").is_none());
1234 assert!(cache.get(&"b").is_none());
1235 assert!(cache.get(&"c").is_none());
1236 assert_eq!(cache.get(&"d"), Some(&"david"));
1237 assert!(!cache.contains_key(&"a"));
1238 assert!(!cache.contains_key(&"b"));
1239 assert!(!cache.contains_key(&"c"));
1240 assert!(cache.contains_key(&"d"));
1241 }
1242
1243 #[test]
1244 #[wasm_bindgen_test]
1245 fn invalidate_entries_if() {
1246 use std::collections::HashSet;
1247
1248 let mut cache = Cache::new(100);
1249 cache.enable_frequency_sketch_for_testing();
1250
1251 let (clock, mock) = Clock::mock();
1252 cache.set_expiration_clock(Some(clock));
1253
1254 cache.insert(0, "alice");
1255 cache.insert(1, "bob");
1256 cache.insert(2, "alex");
1257
1258 mock.increment(Duration::from_secs(5)); // 5 secs from the start.
1259
1260 assert_eq!(cache.get(&0), Some(&"alice"));
1261 assert_eq!(cache.get(&1), Some(&"bob"));
1262 assert_eq!(cache.get(&2), Some(&"alex"));
1263 assert!(cache.contains_key(&0));
1264 assert!(cache.contains_key(&1));
1265 assert!(cache.contains_key(&2));
1266
1267 let names = ["alice", "alex"].iter().cloned().collect::<HashSet<_>>();
1268 cache.invalidate_entries_if(move |_k, &v| names.contains(v));
1269
1270 mock.increment(Duration::from_secs(5)); // 10 secs from the start.
1271
1272 cache.insert(3, "alice");
1273
1274 assert!(cache.get(&0).is_none());
1275 assert!(cache.get(&2).is_none());
1276 assert_eq!(cache.get(&1), Some(&"bob"));
1277 // This should survive as it was inserted after calling invalidate_entries_if.
1278 assert_eq!(cache.get(&3), Some(&"alice"));
1279
1280 assert!(!cache.contains_key(&0));
1281 assert!(cache.contains_key(&1));
1282 assert!(!cache.contains_key(&2));
1283 assert!(cache.contains_key(&3));
1284
1285 assert_eq!(cache.cache.len(), 2);
1286
1287 mock.increment(Duration::from_secs(5)); // 15 secs from the start.
1288
1289 cache.invalidate_entries_if(|_k, &v| v == "alice");
1290 cache.invalidate_entries_if(|_k, &v| v == "bob");
1291
1292 assert!(cache.get(&1).is_none());
1293 assert!(cache.get(&3).is_none());
1294
1295 assert!(!cache.contains_key(&1));
1296 assert!(!cache.contains_key(&3));
1297
1298 assert_eq!(cache.cache.len(), 0);
1299 }
1300
1301 #[test]
1302 #[wasm_bindgen_test]
1303 fn time_to_live() {
1304 let mut cache = Cache::builder()
1305 .max_capacity(100)
1306 .time_to_live(Duration::from_secs(10))
1307 .build();
1308 cache.enable_frequency_sketch_for_testing();
1309
1310 let (clock, mock) = Clock::mock();
1311 cache.set_expiration_clock(Some(clock));
1312
1313 cache.insert("a", "alice");
1314
1315 mock.increment(Duration::from_secs(5)); // 5 secs from the start.
1316
1317 assert_eq!(cache.get(&"a"), Some(&"alice"));
1318 assert!(cache.contains_key(&"a"));
1319
1320 mock.increment(Duration::from_secs(5)); // 10 secs.
1321
1322 assert_eq!(cache.get(&"a"), None);
1323 assert!(!cache.contains_key(&"a"));
1324 assert_eq!(cache.iter().count(), 0);
1325 assert!(cache.cache.is_empty());
1326
1327 cache.insert("b", "bob");
1328
1329 assert_eq!(cache.cache.len(), 1);
1330
1331 mock.increment(Duration::from_secs(5)); // 15 secs.
1332
1333 assert_eq!(cache.get(&"b"), Some(&"bob"));
1334 assert!(cache.contains_key(&"b"));
1335 assert_eq!(cache.cache.len(), 1);
1336
1337 cache.insert("b", "bill");
1338
1339 mock.increment(Duration::from_secs(5)); // 20 secs
1340
1341 assert_eq!(cache.get(&"b"), Some(&"bill"));
1342 assert!(cache.contains_key(&"b"));
1343 assert_eq!(cache.cache.len(), 1);
1344
1345 mock.increment(Duration::from_secs(5)); // 25 secs
1346
1347 assert_eq!(cache.get(&"a"), None);
1348 assert_eq!(cache.get(&"b"), None);
1349 assert!(!cache.contains_key(&"a"));
1350 assert!(!cache.contains_key(&"b"));
1351 assert_eq!(cache.iter().count(), 0);
1352 assert!(cache.cache.is_empty());
1353 }
1354
1355 #[test]
1356 #[wasm_bindgen_test]
1357 fn time_to_idle() {
1358 let mut cache = Cache::builder()
1359 .max_capacity(100)
1360 .time_to_idle(Duration::from_secs(10))
1361 .build();
1362 cache.enable_frequency_sketch_for_testing();
1363
1364 let (clock, mock) = Clock::mock();
1365 cache.set_expiration_clock(Some(clock));
1366
1367 cache.insert("a", "alice");
1368
1369 mock.increment(Duration::from_secs(5)); // 5 secs from the start.
1370
1371 assert_eq!(cache.get(&"a"), Some(&"alice"));
1372
1373 mock.increment(Duration::from_secs(5)); // 10 secs.
1374
1375 cache.insert("b", "bob");
1376
1377 assert_eq!(cache.cache.len(), 2);
1378
1379 mock.increment(Duration::from_secs(2)); // 12 secs.
1380
1381 // contains_key does not reset the idle timer for the key.
1382 assert!(cache.contains_key(&"a"));
1383 assert!(cache.contains_key(&"b"));
1384
1385 assert_eq!(cache.cache.len(), 2);
1386
1387 mock.increment(Duration::from_secs(3)); // 15 secs.
1388
1389 assert_eq!(cache.get(&"a"), None);
1390 assert_eq!(cache.get(&"b"), Some(&"bob"));
1391 assert!(!cache.contains_key(&"a"));
1392 assert!(cache.contains_key(&"b"));
1393 assert_eq!(cache.iter().count(), 1);
1394 assert_eq!(cache.cache.len(), 1);
1395
1396 mock.increment(Duration::from_secs(10)); // 25 secs
1397
1398 assert_eq!(cache.get(&"a"), None);
1399 assert_eq!(cache.get(&"b"), None);
1400 assert!(!cache.contains_key(&"a"));
1401 assert!(!cache.contains_key(&"b"));
1402 assert_eq!(cache.iter().count(), 0);
1403 assert!(cache.cache.is_empty());
1404 }
1405
1406 #[cfg_attr(target_pointer_width = "16", ignore)]
1407 #[test]
1408 #[wasm_bindgen_test]
1409 fn test_skt_capacity_will_not_overflow() {
1410 // power of two
1411 let pot = |exp| 2u64.pow(exp);
1412
1413 let ensure_sketch_len = |max_capacity, len, name| {
1414 let mut cache = Cache::<u8, u8>::new(max_capacity);
1415 cache.enable_frequency_sketch_for_testing();
1416 assert_eq!(cache.frequency_sketch.table_len(), len as usize, "{}", name);
1417 };
1418
1419 if cfg!(target_pointer_width = "32") {
1420 let pot24 = pot(24);
1421 let pot16 = pot(16);
1422 ensure_sketch_len(0, 128, "0");
1423 ensure_sketch_len(128, 128, "128");
1424 ensure_sketch_len(pot16, pot16, "pot16");
1425 // due to ceiling to next_power_of_two
1426 ensure_sketch_len(pot16 + 1, pot(17), "pot16 + 1");
1427 // due to ceiling to next_power_of_two
1428 ensure_sketch_len(pot24 - 1, pot24, "pot24 - 1");
1429 ensure_sketch_len(pot24, pot24, "pot24");
1430 ensure_sketch_len(pot(27), pot24, "pot(27)");
1431 ensure_sketch_len(u32::MAX as u64, pot24, "u32::MAX");
1432 } else {
1433 // target_pointer_width: 64 or larger.
1434 let pot30 = pot(30);
1435 let pot16 = pot(16);
1436 ensure_sketch_len(0, 128, "0");
1437 ensure_sketch_len(128, 128, "128");
1438 ensure_sketch_len(pot16, pot16, "pot16");
1439 // due to ceiling to next_power_of_two
1440 ensure_sketch_len(pot16 + 1, pot(17), "pot16 + 1");
1441
1442 // The following tests will allocate large memory (~8GiB).
1443 // Skip when running on Circle CI.
1444 if !cfg!(circleci) {
1445 // due to ceiling to next_power_of_two
1446 ensure_sketch_len(pot30 - 1, pot30, "pot30- 1");
1447 ensure_sketch_len(pot30, pot30, "pot30");
1448 ensure_sketch_len(u64::MAX, pot30, "u64::MAX");
1449 }
1450 };
1451 }
1452
1453 #[test]
1454 #[wasm_bindgen_test]
1455 fn test_debug_format() {
1456 let mut cache = Cache::new(10);
1457 cache.insert('a', "alice");
1458 cache.insert('b', "bob");
1459 cache.insert('c', "cindy");
1460
1461 let debug_str = format!("{:?}", cache);
1462 assert!(debug_str.starts_with('{'));
1463 assert!(debug_str.contains(r#"'a': "alice""#));
1464 assert!(debug_str.contains(r#"'b': "bob""#));
1465 assert!(debug_str.contains(r#"'c': "cindy""#));
1466 assert!(debug_str.ends_with('}'));
1467 }
1468}