algorithm/cache/
arc.rs

1// Copyright 2022 - 2024 Wenmeng See the COPYRIGHT
2// file at the top-level directory of this distribution.
3//
4// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5// http://www.apache.org/licenses/LICENSE-2.0>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8//
9// Author: tickbh
10// -----
11// Created Date: 2024/05/24 03:04:11
12
13use std::{
14    borrow::Borrow,
15    fmt::{self, Debug},
16    hash::{BuildHasher, Hash},
17    ops::{Index, IndexMut},
18};
19
20use crate::DefaultHasher;
21use crate::{LfuCache, LruCache};
22
23use super::{lfu, lru};
24
25#[cfg(feature = "ttl")]
26use crate::get_milltimestamp;
27#[cfg(feature = "ttl")]
28const DEFAULT_CHECK_STEP: u64 = 120;
29
30/// ARC(Adaptive Replacement Cache): 自适应缓存替换算法,它结合了LRU与LFU,来获得可用缓存的最佳使用。
31/// 设置容量之后将最大保持该容量大小的数据
32/// 后进的数据将会淘汰最久没有被访问的数据
33///
34/// # Examples
35///
36/// ```
37/// use algorithm::ArcCache;
38/// fn main() {
39///     let mut arc = ArcCache::new(3);
40///     arc.insert("now", "ok");
41///     arc.insert("hello", "algorithm");
42///     arc.insert("this", "arc");
43///     arc.insert("auth", "tickbh");
44///     assert!(arc.len() == 4);
45///     assert_eq!(arc.get("hello"), Some(&"algorithm"));
46///     assert_eq!(arc.get("this"), Some(&"arc"));
47///     assert_eq!(arc.get("now"), Some(&"ok"));
48///
49/// }
50/// ```
51pub struct ArcCache<K, V, S> {
52    main_lru: LruCache<K, V, S>,
53    ghost_lru: LruCache<K, V, S>,
54
55    main_lfu: LfuCache<K, V, S>,
56    ghost_lfu: LruCache<K, V, S>,
57
58    cap: usize,
59    /// 下一次检查的时间点，如果大于该时间点则全部检查是否过期
60    #[cfg(feature = "ttl")]
61    check_next: u64,
62    /// 每次大检查点的时间间隔，如果不想启用该特性，可以将该值设成u64::MAX
63    #[cfg(feature = "ttl")]
64    check_step: u64,
65    /// 所有节点中是否存在带ttl的结点，如果均为普通的元素，则过期的将不进行检查
66    #[cfg(feature = "ttl")]
67    has_ttl: bool,
68}
69
70impl<K: Hash + Eq, V> Default for ArcCache<K, V, DefaultHasher> {
71    fn default() -> Self {
72        ArcCache::new(100)
73    }
74}
75
76impl<K: Hash + Eq, V> ArcCache<K, V, DefaultHasher> {
77    /// 因为存在四个数组, 所以实际的容量为这个的4倍
78    pub fn new(cap: usize) -> Self {
79        ArcCache::with_hasher(cap, DefaultHasher::default())
80    }
81}
82
83impl<K, V, S: Clone> ArcCache<K, V, S> {
84    /// 提供hash函数
85    pub fn with_hasher(cap: usize, hash_builder: S) -> ArcCache<K, V, S> {
86        let cap = cap.max(1);
87        Self {
88            main_lru: LruCache::with_hasher(cap, hash_builder.clone()),
89            ghost_lru: LruCache::with_hasher(cap, hash_builder.clone()),
90
91            main_lfu: LfuCache::with_hasher(cap, hash_builder.clone()),
92            ghost_lfu: LruCache::with_hasher(cap, hash_builder),
93
94            cap,
95            #[cfg(feature = "ttl")]
96            check_step: DEFAULT_CHECK_STEP,
97            #[cfg(feature = "ttl")]
98            check_next: get_milltimestamp() + DEFAULT_CHECK_STEP * 1000,
99            #[cfg(feature = "ttl")]
100            has_ttl: false,
101        }
102    }
103}
104
105impl<K, V, S> ArcCache<K, V, S> {
106    /// 获取当前检查lru的间隔
107    #[cfg(feature = "ttl")]
108    pub fn get_check_step(&self) -> u64 {
109        self.check_step
110    }
111
112    /// 设置当前检查lru的间隔
113    /// 单位为秒，意思就是每隔多少秒会清理一次数据
114    /// 如果数据太大的话遍历一次可能会比较久的时长
115    /// 一次清理时间复杂度O(n)
116    /// 仅仅在插入时触发检查，获取时仅检查当前元素
117    #[cfg(feature = "ttl")]
118    pub fn set_check_step(&mut self, check_step: u64) {
119        self.check_step = check_step;
120        self.check_next = get_milltimestamp() + self.check_step * 1000;
121        self.main_lru.set_check_step(check_step);
122        self.main_lfu.set_check_step(check_step);
123    }
124
125    /// 获取当前容量
126    pub fn capacity(&self) -> usize {
127        self.cap
128    }
129
130    /// 清理当前数据
131    /// # Examples
132    ///
133    /// ```
134    /// use algorithm::ArcCache;
135    /// fn main() {
136    ///     let mut arc = ArcCache::new(3);
137    ///     arc.insert("now", "ok");
138    ///     arc.insert("hello", "algorithm");
139    ///     arc.insert("this", "arc");
140    ///     assert!(arc.len() == 3);
141    ///     arc.clear();
142    ///     assert!(arc.len() == 0);
143    /// }
144    /// ```
145    pub fn clear(&mut self) {
146        self.main_lru.clear();
147        self.ghost_lru.clear();
148
149        self.main_lfu.clear();
150        self.ghost_lfu.clear();
151    }
152
153    /// 获取当前长度
154    pub fn len(&self) -> usize {
155        self.main_lru.len() + self.main_lfu.len() + self.ghost_lfu.len() + self.ghost_lru.len()
156    }
157
158    pub fn is_empty(&self) -> bool {
159        self.len() == 0
160    }
161
162    /// 扩展当前容量
163    pub fn reserve(&mut self, additional: usize) -> &mut Self {
164        self.cap += additional;
165        self.main_lfu.reserve(additional);
166        self.main_lru.reserve(additional);
167        self.ghost_lfu.reserve(additional);
168        self.ghost_lru.reserve(additional);
169        self
170    }
171
172    /// 遍历当前的所有值
173    ///
174    /// ```
175    /// use algorithm::ArcCache;
176    /// fn main() {
177    ///     let mut arc = ArcCache::new(3);
178    ///     arc.insert("hello", "algorithm");
179    ///     arc.insert("this", "arc");
180    ///     for (k, v) in arc.iter() {
181    ///         assert!(k == &"hello" || k == &"this");
182    ///         assert!(v == &"algorithm" || v == &"arc");
183    ///     }
184    ///     assert!(arc.len() == 2);
185    /// }
186    /// ```
187    pub fn iter(&self) -> Iter<'_, K, V, S> {
188        Iter {
189            lru_iter: self.main_lru.iter(),
190            lfu_iter: self.main_lfu.iter(),
191        }
192    }
193
194    /// 遍历当前的所有值, 可变
195    ///
196    /// ```
197    /// use algorithm::ArcCache;
198    /// fn main() {
199    ///     let mut arc = ArcCache::new(3);
200    ///     arc.insert("hello", "algorithm".to_string());
201    ///     arc.insert("this", "arc".to_string());
202    ///     for (k, v) in arc.iter_mut() {
203    ///         v.push_str(" ok");
204    ///     }
205    ///     assert!(arc.len() == 2);
206    ///     assert!(arc.get(&"this") == Some(&"arc ok".to_string()));
207    /// assert!(arc.get(&"hello") == Some(&"algorithm ok".to_string()));
208    /// }
209    /// ```
210    pub fn iter_mut(&mut self) -> IterMut<'_, K, V, S> {
211        IterMut {
212            lru_iter: self.main_lru.iter_mut(),
213            lfu_iter: self.main_lfu.iter_mut(),
214        }
215    }
216
217    /// 遍历当前的key值
218    ///
219    /// ```
220    /// use algorithm::ArcCache;
221    /// fn main() {
222    ///     let mut arc = ArcCache::new(3);
223    ///     arc.insert("hello", "algorithm");
224    ///     arc.insert("this", "arc");
225    ///     let mut keys = arc.keys();
226    ///     assert!(keys.next()==Some(&"this"));
227    ///     assert!(keys.next()==Some(&"hello"));
228    ///     assert!(keys.next() == None);
229    /// }
230    /// ```
231    pub fn keys(&self) -> Keys<'_, K, V, S> {
232        Keys { iter: self.iter() }
233    }
234
235    /// 遍历当前的valus值
236    ///
237    /// ```
238    /// use algorithm::ArcCache;
239    /// fn main() {
240    ///     let vec = vec![(1, 1), (2, 2), (3, 3)];
241    ///     let mut map: ArcCache<_, _, _> = vec.into_iter().collect();
242    ///     for value in map.values_mut() {
243    ///     *value = (*value) * 2
244    ///     }
245    ///     let values: Vec<_> = map.values().cloned().collect();
246    ///     assert_eq!(values.len(), 3);
247    ///     assert!(values.contains(&2));
248    ///     assert!(values.contains(&4));
249    ///     assert!(values.contains(&6));
250    /// }
251    /// ```
252    pub fn values(&self) -> Values<'_, K, V, S> {
253        Values { iter: self.iter() }
254    }
255
256    /// 遍历当前的valus值
257    ///
258    /// ```
259    /// use algorithm::ArcCache;
260    /// fn main() {
261    ///     let mut arc = ArcCache::new(3);
262    ///     arc.insert("hello", "algorithm".to_string());
263    ///     arc.insert("this", "arc".to_string());
264    ///     {
265    ///         let mut values = arc.values_mut();
266    ///         values.next().unwrap().push_str(" ok");
267    ///         values.next().unwrap().push_str(" ok");
268    ///         assert!(values.next() == None);
269    ///     }
270    ///     assert_eq!(arc.get(&"this"), Some(&"arc ok".to_string()))
271    /// }
272    /// ```
273    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V, S> {
274        ValuesMut {
275            iter: self.iter_mut(),
276        }
277    }
278
279    pub fn hasher(&self) -> &S {
280        self.main_lru.hasher()
281    }
282}
283
284impl<K: Hash + Eq, V, S: BuildHasher> ArcCache<K, V, S> {
285    /// 弹出栈顶上的数据, 最常使用的数据
286    ///
287    /// ```
288    /// use algorithm::ArcCache;
289    /// fn main() {
290    ///     let mut arc = ArcCache::new(3);
291    ///     arc.insert("hello", "algorithm");
292    ///     arc.insert("this", "arc");
293    ///     assert!(arc.pop_usual()==Some(("this", "arc")));
294    ///     assert!(arc.len() == 1);
295    /// }
296    /// ```
297    pub fn pop_usual(&mut self) -> Option<(K, V)> {
298        if self.main_lru.len() != 0 {
299            return self.main_lru.pop_usual();
300        }
301        self.main_lfu.pop_usual()
302    }
303
304    /// 弹出栈尾上的数据, 最久未使用的数据
305    ///
306    /// ```
307    /// use algorithm::ArcCache;
308    /// fn main() {
309    ///     let mut arc = ArcCache::new(3);
310    ///     arc.insert("hello", "algorithm");
311    ///     arc.insert("this", "arc");
312    ///     assert!(arc.pop_unusual()==Some(("hello", "algorithm")));
313    ///     assert!(arc.len() == 1);
314    /// }
315    /// ```
316    pub fn pop_unusual(&mut self) -> Option<(K, V)> {
317        if self.main_lru.len() != 0 {
318            return self.main_lru.pop_unusual();
319        }
320        self.main_lfu.pop_unusual()
321    }
322
323    /// 取出栈顶上的数据, 最近使用的数据
324    ///
325    /// ```
326    /// use algorithm::ArcCache;
327    /// fn main() {
328    ///     let mut arc = ArcCache::new(3);
329    ///     arc.insert("hello", "algorithm");
330    ///     arc.insert("this", "arc");
331    ///     assert!(arc.peek_usual()==Some((&"this", &"arc")));
332    ///     assert!(arc.len() == 2);
333    /// }
334    /// ```
335    pub fn peek_usual(&mut self) -> Option<(&K, &V)> {
336        if self.main_lru.len() != 0 {
337            return self.main_lru.peek_usual();
338        }
339        self.main_lfu.peek_usual()
340    }
341
342    /// 取出栈尾上的数据, 最久未使用的数据
343    ///
344    /// ```
345    /// use algorithm::ArcCache;
346    /// fn main() {
347    ///     let mut arc = ArcCache::new(3);
348    ///     arc.insert("hello", "algorithm");
349    ///     arc.insert("this", "arc");
350    ///     assert!(arc.peek_last()==Some((&"hello", &"algorithm")));
351    ///     assert!(arc.len() == 2);
352    /// }
353    /// ```
354    pub fn peek_last(&mut self) -> Option<(&K, &V)> {
355        if self.main_lru.len() != 0 {
356            return self.main_lru.peek_unusual();
357        }
358        self.main_lfu.peek_unusual()
359    }
360
361    pub fn contains_key<Q>(&mut self, k: &Q) -> bool
362    where
363        K: Borrow<Q>,
364        Q: Hash + Eq + ?Sized,
365    {
366        self.main_lru.contains_key(k) || self.main_lfu.contains_key(k)
367    }
368
369    /// 获取key值相对应的value值, 根据hash判定
370    ///
371    /// ```
372    /// use algorithm::ArcCache;
373    /// fn main() {
374    ///     let mut arc = ArcCache::new(3);
375    ///     arc.insert("hello", "algorithm");
376    ///     arc.insert("this", "arc");
377    ///     assert!(arc.raw_get(&"this") == Some(&"arc"));
378    /// }
379    /// ```
380    pub fn raw_get<Q>(&self, k: &Q) -> Option<&V>
381    where
382        K: Borrow<Q>,
383        Q: Hash + Eq + ?Sized,
384    {
385        if let Some(v) = self.main_lru.raw_get(k) {
386            return Some(v);
387        }
388        self.main_lfu.raw_get(k)
389    }
390
391    /// 获取key值相对应的value值, 根据hash判定
392    ///
393    /// ```
394    /// use algorithm::ArcCache;
395    /// fn main() {
396    ///     let mut arc = ArcCache::new(3);
397    ///     arc.insert("hello", "algorithm");
398    ///     arc.insert("this", "arc");
399    ///     assert!(arc.get(&"this") == Some(&"arc"));
400    /// }
401    /// ```
402    pub fn get<Q>(&mut self, k: &Q) -> Option<&V>
403    where
404        K: Borrow<Q>,
405        Q: Hash + Eq + ?Sized,
406    {
407        self.get_key_value(k).map(|(_, v)| v)
408    }
409
410    /// 获取key值相对应的key和value值, 根据hash判定
411    ///
412    /// ```
413    /// use algorithm::ArcCache;
414    /// fn main() {
415    ///     let mut arc = ArcCache::new(3);
416    ///     arc.insert("hello", "algorithm");
417    ///     arc.insert("this", "arc");
418    ///     assert!(arc.get_key_value(&"this") == Some((&"this", &"arc")));
419    /// }
420    /// ```
421    pub fn get_key_value<Q>(&mut self, k: &Q) -> Option<(&K, &V)>
422    where
423        K: Borrow<Q>,
424        Q: Hash + Eq + ?Sized,
425    {
426        self.get_mut_key_value(k).map(|(k, v)| (k, &*v))
427    }
428
429    /// 获取key值相对应的value值, 根据hash判定, 可编辑被改变
430    ///
431    /// ```
432    /// use algorithm::ArcCache;
433    /// fn main() {
434    ///     let mut arc = ArcCache::new(3);
435    ///     arc.insert("hello", "algorithm".to_string());
436    ///     arc.insert("this", "arc".to_string());
437    ///     arc.get_mut(&"this").unwrap().insert_str(3, " good");
438    ///     assert!(arc.get_key_value(&"this") == Some((&"this", &"arc good".to_string())));
439    /// }
440    /// ```
441    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
442    where
443        K: Borrow<Q>,
444        Q: Hash + Eq + ?Sized,
445    {
446        self.get_mut_key_value(k).map(|(_, v)| v)
447    }
448
449    #[cfg(feature = "ttl")]
450    pub fn get_mut_key_value<Q>(&mut self, k: &Q) -> Option<(&K, &mut V)>
451    where
452        K: Borrow<Q>,
453        Q: Hash + Eq + ?Sized,
454    {
455        // {
456        //     if let Some(v) = self.main_lfu.get_mut_key_value(k) {
457        //         return Some(v)
458        //     }
459        // }
460        if let Some((key, val, ttl)) = self.main_lru.remove_with_ttl(k) {
461            self.main_lfu.insert_with_ttl(key, val, ttl);
462            return self.main_lfu.get_mut_key_value(k);
463        }
464
465        if let Some((key, val, ttl)) = self.ghost_lfu.remove_with_ttl(k) {
466            self.main_lfu.full_increase();
467            self.main_lru.full_decrease();
468            self.main_lfu.insert_with_ttl(key, val, ttl);
469            return self.main_lfu.get_mut_key_value(k);
470        }
471
472        if let Some((key, val, ttl)) = self.ghost_lru.remove_with_ttl(k) {
473            self.main_lru.full_increase();
474            self.main_lfu.full_decrease();
475            self.main_lru.insert_with_ttl(key, val, ttl);
476            return self.main_lru.get_mut_key_value(k);
477        }
478        self.main_lfu.get_mut_key_value(k)
479    }
480
481    #[cfg(not(feature = "ttl"))]
482    pub fn get_mut_key_value<Q>(&mut self, k: &Q) -> Option<(&K, &mut V)>
483    where
484        K: Borrow<Q>,
485        Q: Hash + Eq + ?Sized,
486    {
487        // {
488        //     if let Some(v) = self.main_lfu.get_mut_key_value(k) {
489        //         return Some(v)
490        //     }
491        // }
492        if let Some((key, val)) = self.main_lru.remove(k) {
493            self.main_lfu.insert(key, val);
494            return self.main_lfu.get_mut_key_value(k);
495        }
496
497        if let Some((key, val)) = self.ghost_lfu.remove(k) {
498            self.main_lfu.full_increase();
499            self.main_lru.full_decrease();
500            self.main_lfu.insert(key, val);
501            return self.main_lfu.get_mut_key_value(k);
502        }
503
504        if let Some((key, val)) = self.ghost_lru.remove(k) {
505            self.main_lru.full_increase();
506            self.main_lfu.full_decrease();
507            self.main_lru.insert(key, val);
508            return self.main_lru.get_mut_key_value(k);
509        }
510        self.main_lfu.get_mut_key_value(k)
511    }
512
513    /// 插入值, 如果值重复将返回原来的数据
514    ///
515    /// ```
516    /// use algorithm::ArcCache;
517    /// fn main() {
518    ///     let mut arc = ArcCache::new(3);
519    ///     arc.insert("hello", "algorithm");
520    ///     arc.insert("this", "arc");
521    ///     assert!(arc.insert("this", "arc good") == Some(&"arc"));
522    /// }
523    /// ```
524    #[inline(always)]
525    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
526        self.capture_insert(k, v).map(|(_, v, _)| v)
527    }
528
529    /// 插入带有生存时间的元素
530    /// 每次获取像redis一样，并不会更新生存时间
531    /// 如果需要更新则需要手动的进行重新设置
532    #[cfg(feature = "ttl")]
533    #[inline(always)]
534    pub fn insert_with_ttl(&mut self, k: K, v: V, ttl: u64) -> Option<V> {
535        self.capture_insert_with_ttl(k, v, ttl).map(|(_, v, _)| v)
536    }
537
538    #[inline(always)]
539    pub fn capture_insert(&mut self, k: K, v: V) -> Option<(K, V, bool)> {
540        self._capture_insert_with_ttl(k, v, u64::MAX)
541    }
542
543    #[cfg(feature = "ttl")]
544    #[inline(always)]
545    pub fn capture_insert_with_ttl(&mut self, k: K, v: V, ttl: u64) -> Option<(K, V, bool)> {
546        if ttl == 0 {
547            return None;
548        };
549        self.has_ttl = true;
550        self._capture_insert_with_ttl(k, v, ttl)
551    }
552
553    #[cfg(feature = "ttl")]
554    #[allow(unused_variables)]
555    fn _capture_insert_with_ttl(&mut self, k: K, v: V, ttl: u64) -> Option<(K, V, bool)> {
556        if let Some((key, val, same)) = self.main_lru.capture_insert_with_ttl(k, v, ttl) {
557            if same {
558                Some((key, val, true))
559            } else {
560                self.ghost_lru.capture_insert_with_ttl(key, val, ttl)
561            }
562        } else {
563            None
564        }
565    }
566
567    #[cfg(not(feature = "ttl"))]
568    #[allow(unused_variables)]
569    fn _capture_insert_with_ttl(&mut self, k: K, v: V, ttl: u64) -> Option<(K, V, bool)> {
570        if let Some((key, val, same)) = self.main_lru.capture_insert(k, v) {
571            if same {
572                Some((key, val, true))
573            } else {
574                self.ghost_lru.capture_insert(key, val)
575            }
576        } else {
577            None
578        }
579    }
580
581    pub fn get_or_insert<F>(&mut self, k: K, f: F) -> &V
582    where
583        F: FnOnce() -> V,
584    {
585        &*self.get_or_insert_mut(k, f)
586    }
587
588    pub fn get_or_insert_mut<F>(&mut self, k: K, f: F) -> &mut V
589    where
590        F: FnOnce() -> V,
591    {
592        if let Some((key, val)) = self.main_lru.remove(&k) {
593            self.main_lfu.insert(key, val);
594            return self.main_lfu.get_mut_key_value(&k).map(|(_, v)| v).unwrap();
595        }
596
597        if let Some((key, val)) = self.ghost_lfu.remove(&k) {
598            self.main_lfu.full_increase();
599            self.main_lru.full_decrease();
600            self.main_lfu.insert(key, val);
601            return self.main_lfu.get_mut_key_value(&k).map(|(_, v)| v).unwrap();
602        }
603
604        if let Some((key, val)) = self.ghost_lru.remove(&k) {
605            self.main_lru.full_increase();
606            self.main_lfu.full_decrease();
607            self.main_lru.insert(key, val);
608            return self.main_lru.get_mut_key_value(&k).map(|(_, v)| v).unwrap();
609        }
610
611        if self.main_lfu.contains_key(&k) {
612            return self.main_lfu.get_mut_key_value(&k).map(|(_, v)| v).unwrap();
613        }
614
615        if self.main_lru.is_full() {
616            let (pk, pv) = self.main_lru.pop_unusual().unwrap();
617            self.ghost_lru.insert(pk, pv);
618        }
619        self.get_or_insert_mut(k, f)
620    }
621
622    #[cfg(feature = "ttl")]
623    pub fn clear_expire(&mut self) {
624        if !self.has_ttl {
625            return;
626        }
627        let now = get_milltimestamp();
628        if now < self.check_next {
629            return;
630        }
631        self.check_next = now + self.check_step;
632        self.main_lfu.clear_expire();
633        self.main_lru.clear_expire();
634    }
635
636    #[cfg(feature = "ttl")]
637    #[inline(always)]
638    pub fn del_ttl<Q>(&mut self, k: &Q)
639    where
640        K: Borrow<Q>,
641        Q: Hash + Eq + ?Sized,
642    {
643        self.set_ttl(k, u64::MAX);
644    }
645
646    #[cfg(feature = "ttl")]
647    pub fn set_ttl<Q>(&mut self, k: &Q, expire: u64) -> bool
648    where
649        K: Borrow<Q>,
650        Q: Hash + Eq + ?Sized,
651    {
652        if self.main_lru.set_ttl(k, expire) {
653            return true;
654        }
655        self.main_lfu.set_ttl(k, expire)
656    }
657
658    #[cfg(feature = "ttl")]
659    pub fn get_ttl<Q>(&mut self, k: &Q) -> Option<u64>
660    where
661        K: Borrow<Q>,
662        Q: Hash + Eq + ?Sized,
663    {
664        if let Some(v) = self.main_lfu.get_ttl(k) {
665            return Some(v);
666        }
667        self.main_lru.get_ttl(k)
668    }
669
670    /// 移除元素
671    ///
672    /// ```
673    /// use algorithm::ArcCache;
674    /// fn main() {
675    ///     let mut arc = ArcCache::new(3);
676    ///     arc.insert("hello", "algorithm");
677    ///     arc.insert("this", "arc");
678    ///     assert!(arc.remove("this") == Some(("this", "arc")));
679    ///     assert!(arc.len() == 1);
680    /// }
681    /// ```
682    pub fn remove<Q>(&mut self, k: &Q) -> Option<(K, V)>
683    where
684        K: Borrow<Q>,
685        Q: Hash + Eq + ?Sized,
686    {
687        if let Some(v) = self.main_lru.remove(k) {
688            return Some(v);
689        }
690        if let Some(v) = self.main_lfu.remove(k) {
691            return Some(v);
692        }
693        None
694    }
695
696    /// 根据保留当前的元素, 返回false则表示抛弃元素
697    ///
698    /// ```
699    /// use algorithm::ArcCache;
700    /// fn main() {
701    ///     let mut arc = ArcCache::new(3);
702    ///     arc.insert("hello", "algorithm");
703    ///     arc.insert("this", "arc");
704    ///     arc.insert("year", "2024");
705    ///     arc.retain(|_, v| *v == "2024" || *v == "arc");
706    ///     assert!(arc.len() == 2);
707    ///     assert!(arc.get("this") == Some(&"arc"));
708    /// }
709    /// ```
710    pub fn retain<F>(&mut self, mut f: F)
711    where
712        F: FnMut(&K, &mut V) -> bool,
713    {
714        self.main_lru.retain(|k, v| f(k, v));
715        self.main_lfu.retain(|k, v| f(k, v));
716    }
717}
718
719impl<K: Hash + Eq, V: Default, S: BuildHasher> ArcCache<K, V, S> {
720    pub fn get_or_insert_default(&mut self, k: K) -> &V {
721        &*self.get_or_insert_mut(k, || V::default())
722    }
723
724    pub fn get_or_insert_default_mut(&mut self, k: K) -> &mut V {
725        self.get_or_insert_mut(k, || V::default())
726    }
727}
728
729impl<K: Clone + Hash + Eq, V: Clone, S: Clone + BuildHasher> Clone for ArcCache<K, V, S> {
730    fn clone(&self) -> Self {
731        ArcCache {
732            main_lfu: self.main_lfu.clone(),
733            main_lru: self.main_lru.clone(),
734            ghost_lru: self.ghost_lru.clone(),
735            ghost_lfu: self.ghost_lfu.clone(),
736            cap: self.cap,
737            #[cfg(feature = "ttl")]
738            check_next: self.check_next,
739            #[cfg(feature = "ttl")]
740            check_step: self.check_step,
741            #[cfg(feature = "ttl")]
742            has_ttl: self.has_ttl,
743        }
744    }
745}
746
747impl<K, V, S> Drop for ArcCache<K, V, S> {
748    fn drop(&mut self) {
749        self.clear();
750    }
751}
752
753/// Convert ArcCache to iter, move out the tree.
754pub struct IntoIter<K: Hash + Eq, V, S: BuildHasher> {
755    base: ArcCache<K, V, S>,
756}
757
758// Drop all owned pointers if the collection is dropped
759impl<K: Hash + Eq, V, S: BuildHasher> Drop for IntoIter<K, V, S> {
760    #[inline]
761    fn drop(&mut self) {
762        for (_, _) in self {}
763    }
764}
765
766impl<K: Hash + Eq, V, S: BuildHasher> Iterator for IntoIter<K, V, S> {
767    type Item = (K, V);
768
769    fn next(&mut self) -> Option<(K, V)> {
770        self.base.pop_usual()
771    }
772
773    fn size_hint(&self) -> (usize, Option<usize>) {
774        (self.base.len(), Some(self.base.len()))
775    }
776}
777
778impl<K: Hash + Eq, V, S: BuildHasher> IntoIterator for ArcCache<K, V, S> {
779    type Item = (K, V);
780    type IntoIter = IntoIter<K, V, S>;
781
782    #[inline]
783    fn into_iter(self) -> IntoIter<K, V, S> {
784        IntoIter { base: self }
785    }
786}
787
788pub struct Iter<'a, K: 'a, V: 'a, S> {
789    lru_iter: lru::Iter<'a, K, V>,
790    lfu_iter: lfu::Iter<'a, K, V, S>,
791}
792
793impl<'a, K: Hash + Eq, V, S: BuildHasher> Iterator for Iter<'a, K, V, S> {
794    type Item = (&'a K, &'a V);
795
796    fn next(&mut self) -> Option<Self::Item> {
797        if let Some(v) = self.lru_iter.next() {
798            return Some(v);
799        }
800        self.lfu_iter.next()
801    }
802
803    fn size_hint(&self) -> (usize, Option<usize>) {
804        (
805            self.lru_iter.size_hint().0 + self.lfu_iter.size_hint().0,
806            None,
807        )
808    }
809}
810
811impl<'a, K: Hash + Eq, V, S: BuildHasher> DoubleEndedIterator for Iter<'a, K, V, S> {
812    fn next_back(&mut self) -> Option<Self::Item> {
813        if let Some(v) = self.lru_iter.next_back() {
814            return Some(v);
815        }
816        self.lfu_iter.next_back()
817    }
818}
819
820impl<K: Hash + Eq, V, S: BuildHasher> DoubleEndedIterator for IntoIter<K, V, S> {
821    #[inline]
822    fn next_back(&mut self) -> Option<(K, V)> {
823        self.base.pop_unusual()
824    }
825}
826
827pub struct IterMut<'a, K: 'a, V: 'a, S> {
828    lru_iter: lru::IterMut<'a, K, V>,
829    lfu_iter: lfu::IterMut<'a, K, V, S>,
830}
831
832impl<'a, K: Hash + Eq, V, S: BuildHasher> Iterator for IterMut<'a, K, V, S> {
833    type Item = (&'a K, &'a mut V);
834
835    fn next(&mut self) -> Option<Self::Item> {
836        if let Some(v) = self.lru_iter.next() {
837            return Some(v);
838        }
839        self.lfu_iter.next()
840    }
841
842    fn size_hint(&self) -> (usize, Option<usize>) {
843        (
844            self.lru_iter.size_hint().0 + self.lfu_iter.size_hint().0,
845            None,
846        )
847    }
848}
849
850impl<'a, K: Hash + Eq, V, S: BuildHasher> DoubleEndedIterator for IterMut<'a, K, V, S> {
851    fn next_back(&mut self) -> Option<Self::Item> {
852        if let Some(v) = self.lru_iter.next_back() {
853            return Some(v);
854        }
855        self.lfu_iter.next_back()
856    }
857}
858
859pub struct Keys<'a, K, V, S> {
860    iter: Iter<'a, K, V, S>,
861}
862
863impl<'a, K: Hash + Eq, V, S: BuildHasher> Iterator for Keys<'a, K, V, S> {
864    type Item = &'a K;
865
866    fn next(&mut self) -> Option<Self::Item> {
867        self.iter.next().map(|(k, _)| k)
868    }
869
870    fn size_hint(&self) -> (usize, Option<usize>) {
871        self.iter.size_hint()
872    }
873}
874
875pub struct Values<'a, K, V, S> {
876    iter: Iter<'a, K, V, S>,
877}
878
879impl<'a, K: Hash + Eq, V, S: BuildHasher> Iterator for Values<'a, K, V, S> {
880    type Item = &'a V;
881
882    fn next(&mut self) -> Option<Self::Item> {
883        self.iter.next().map(|(_, v)| v)
884    }
885
886    fn size_hint(&self) -> (usize, Option<usize>) {
887        self.iter.size_hint()
888    }
889}
890
891pub struct ValuesMut<'a, K, V, S> {
892    iter: IterMut<'a, K, V, S>,
893}
894
895impl<'a, K: Hash + Eq, V, S: BuildHasher> Iterator for ValuesMut<'a, K, V, S> {
896    type Item = &'a mut V;
897
898    fn next(&mut self) -> Option<Self::Item> {
899        self.iter.next().map(|(_, v)| v)
900    }
901
902    fn size_hint(&self) -> (usize, Option<usize>) {
903        self.iter.size_hint()
904    }
905}
906
907impl<K: Hash + Eq, V> FromIterator<(K, V)> for ArcCache<K, V, DefaultHasher> {
908    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> ArcCache<K, V, DefaultHasher> {
909        let mut arc = ArcCache::new(2);
910        arc.extend(iter);
911        arc
912    }
913}
914
915impl<K: Hash + Eq, V> Extend<(K, V)> for ArcCache<K, V, DefaultHasher> {
916    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
917        let iter = iter.into_iter();
918        for (k, v) in iter {
919            self.reserve(1);
920            self.insert(k, v);
921        }
922    }
923}
924
925impl<K, V, S> PartialEq for ArcCache<K, V, S>
926where
927    K: Eq + Hash,
928    V: PartialEq,
929    S: BuildHasher,
930{
931    fn eq(&self, other: &ArcCache<K, V, S>) -> bool {
932        if self.len() != other.len() {
933            return false;
934        }
935
936        self.iter()
937            .all(|(key, value)| other.raw_get(key).map_or(false, |v| *value == *v))
938    }
939}
940
941impl<K, V, S> Eq for ArcCache<K, V, S>
942where
943    K: Eq + Hash,
944    V: PartialEq,
945    S: BuildHasher,
946{
947}
948
949impl<K, V, S> Debug for ArcCache<K, V, S>
950where
951    K: Eq + Hash + Debug,
952    V: Debug,
953    S: BuildHasher,
954{
955    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
956        f.debug_map().entries(self.iter()).finish()
957    }
958}
959
960impl<'a, K, V, S> Index<&'a K> for ArcCache<K, V, S>
961where
962    K: Hash + Eq,
963    S: BuildHasher,
964{
965    type Output = V;
966
967    #[inline]
968    fn index(&self, index: &K) -> &V {
969        self.raw_get(index).expect("no entry found for key")
970    }
971}
972
973impl<'a, K, V, S> IndexMut<&'a K> for ArcCache<K, V, S>
974where
975    K: Hash + Eq,
976    S: BuildHasher,
977{
978    #[inline]
979    fn index_mut(&mut self, index: &K) -> &mut V {
980        self.get_mut(index).expect("no entry found for key")
981    }
982}
983
984unsafe impl<K: Send, V: Send, S: Send> Send for ArcCache<K, V, S> {}
985unsafe impl<K: Sync, V: Sync, S: Sync> Sync for ArcCache<K, V, S> {}
986
987#[cfg(test)]
988mod tests {
989    use super::ArcCache;
990    use crate::DefaultHasher;
991
992    #[test]
993    fn test_insert() {
994        let mut m = ArcCache::new(2);
995        assert_eq!(m.len(), 0);
996        m.insert(1, 2);
997        assert_eq!(m.len(), 1);
998        m.insert(2, 4);
999        assert_eq!(m.len(), 2);
1000        m.insert(3, 6);
1001        assert_eq!(m.len(), 3);
1002        assert_eq!(*m.get(&1).unwrap(), 2);
1003        assert_eq!(m.len(), 3);
1004        assert_eq!(*m.get(&2).unwrap(), 4);
1005        assert_eq!(*m.get(&3).unwrap(), 6);
1006        assert_eq!(m.len(), 3);
1007        m.insert(4, 8);
1008        m.insert(5, 10);
1009        assert_eq!(m.len(), 5);
1010        m.insert(6, 12);
1011        assert_eq!(m.len(), 6);
1012        assert_eq!(*m.get(&6).unwrap(), 12);
1013        assert_eq!(m.len(), 5);
1014    }
1015
1016    #[test]
1017    fn test_replace() {
1018        let mut m = ArcCache::new(2);
1019        assert_eq!(m.len(), 0);
1020        m.insert(2, 4);
1021        assert_eq!(m.len(), 1);
1022        m.insert(2, 6);
1023        assert_eq!(m.len(), 1);
1024        assert_eq!(*m.get(&2).unwrap(), 6);
1025    }
1026
1027    #[test]
1028    fn test_clone() {
1029        let mut m = ArcCache::new(2);
1030        assert_eq!(m.len(), 0);
1031        m.insert(1, 2);
1032        assert_eq!(m.len(), 1);
1033        m.insert(2, 4);
1034        assert_eq!(m.len(), 2);
1035        let mut m2 = m.clone();
1036        m.clear();
1037        assert_eq!(*m2.get(&1).unwrap(), 2);
1038        assert_eq!(*m2.get(&2).unwrap(), 4);
1039        assert_eq!(m2.len(), 2);
1040    }
1041
1042    #[test]
1043    fn test_empty_remove() {
1044        let mut m: ArcCache<isize, bool, DefaultHasher> = ArcCache::new(2);
1045        assert_eq!(m.remove(&0), None);
1046    }
1047
1048    #[test]
1049    fn test_empty_iter() {
1050        let mut m: ArcCache<isize, bool, DefaultHasher> = ArcCache::new(2);
1051        assert_eq!(m.iter().next(), None);
1052        assert_eq!(m.iter_mut().next(), None);
1053        assert_eq!(m.len(), 0);
1054        assert!(m.is_empty());
1055        assert_eq!(m.into_iter().next(), None);
1056    }
1057
1058    #[test]
1059    fn test_lots_of_insertions() {
1060        let mut m = ArcCache::new(1000);
1061
1062        // Try this a few times to make sure we never screw up the hashmap's
1063        // internal state.
1064        for _ in 0..10 {
1065            assert!(m.is_empty());
1066
1067            for i in 1..101 {
1068                m.insert(i, i);
1069
1070                for j in 1..i + 1 {
1071                    let r = m.get(&j);
1072                    assert_eq!(r, Some(&j));
1073                }
1074
1075                for j in i + 1..101 {
1076                    let r = m.get(&j);
1077                    assert_eq!(r, None);
1078                }
1079            }
1080
1081            for i in 101..201 {
1082                assert!(!m.contains_key(&i));
1083            }
1084
1085            // remove forwards
1086            for i in 1..101 {
1087                assert!(m.remove(&i).is_some());
1088
1089                for j in 1..i + 1 {
1090                    assert!(!m.contains_key(&j));
1091                }
1092
1093                for j in i + 1..101 {
1094                    assert!(m.contains_key(&j));
1095                }
1096            }
1097
1098            for i in 1..101 {
1099                assert!(!m.contains_key(&i));
1100            }
1101
1102            for i in 1..101 {
1103                m.insert(i, i);
1104            }
1105
1106            // remove backwards
1107            for i in (1..101).rev() {
1108                assert!(m.remove(&i).is_some());
1109
1110                for j in i..101 {
1111                    assert!(!m.contains_key(&j));
1112                }
1113
1114                for j in 1..i {
1115                    assert!(m.contains_key(&j));
1116                }
1117            }
1118        }
1119    }
1120
1121    #[test]
1122    fn test_find_mut() {
1123        let mut m = ArcCache::new(3);
1124        m.insert(1, 12);
1125        m.insert(2, 8);
1126        m.insert(5, 14);
1127        let new = 100;
1128        match m.get_mut(&5) {
1129            None => panic!(),
1130            Some(x) => *x = new,
1131        }
1132        assert_eq!(m.get(&5), Some(&new));
1133    }
1134
1135    #[test]
1136    fn test_remove() {
1137        let mut m = ArcCache::new(3);
1138        m.insert(1, 2);
1139        assert_eq!(*m.get(&1).unwrap(), 2);
1140        m.insert(5, 3);
1141        assert_eq!(*m.get(&5).unwrap(), 3);
1142        m.insert(9, 4);
1143        assert_eq!(*m.get(&1).unwrap(), 2);
1144        assert_eq!(*m.get(&5).unwrap(), 3);
1145        assert_eq!(*m.get(&9).unwrap(), 4);
1146        assert_eq!(m.remove(&1).unwrap(), (1, 2));
1147        assert_eq!(m.remove(&5).unwrap(), (5, 3));
1148        assert_eq!(m.remove(&9).unwrap(), (9, 4));
1149        assert_eq!(m.len(), 0);
1150    }
1151
1152    #[test]
1153    fn test_is_empty() {
1154        let mut m = ArcCache::new(2);
1155        m.insert(1, 2);
1156        assert!(!m.is_empty());
1157        assert!(m.remove(&1).is_some());
1158        assert!(m.is_empty());
1159    }
1160
1161    #[test]
1162    fn test_pop() {
1163        let mut m = ArcCache::new(3);
1164        m.insert(3, 6);
1165        m.insert(2, 4);
1166        m.insert(1, 2);
1167        assert_eq!(m.len(), 3);
1168        assert_eq!(m.pop_usual(), Some((1, 2)));
1169        assert_eq!(m.len(), 2);
1170        assert_eq!(m.pop_unusual(), Some((3, 6)));
1171        assert_eq!(m.len(), 1);
1172    }
1173
1174    #[test]
1175    fn test_iterate() {
1176        let mut m = ArcCache::new(32);
1177        for i in 0..32 {
1178            m.insert(i, i * 2);
1179        }
1180        assert_eq!(m.len(), 32);
1181
1182        let mut observed: u32 = 0;
1183
1184        for (k, v) in m.iter() {
1185            assert_eq!(*v, *k * 2);
1186            observed |= 1 << *k;
1187        }
1188        assert_eq!(observed, 0xFFFF_FFFF);
1189    }
1190
1191    #[test]
1192    fn test_keys() {
1193        let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1194        let map: ArcCache<_, _, _> = vec.into_iter().collect();
1195        let keys: Vec<_> = map.keys().cloned().collect();
1196        assert_eq!(keys.len(), 3);
1197        assert!(keys.contains(&1));
1198        assert!(keys.contains(&2));
1199        assert!(keys.contains(&3));
1200    }
1201
1202    #[test]
1203    fn test_values() {
1204        let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1205        let map: ArcCache<_, _, _> = vec.into_iter().collect();
1206        let values: Vec<_> = map.values().cloned().collect();
1207        assert_eq!(values.len(), 3);
1208        assert!(values.contains(&'a'));
1209        assert!(values.contains(&'b'));
1210        assert!(values.contains(&'c'));
1211    }
1212
1213    #[test]
1214    fn test_values_mut() {
1215        let vec = vec![(1, 1), (2, 2), (3, 3)];
1216        let mut map: ArcCache<_, _, _> = vec.into_iter().collect();
1217        for value in map.values_mut() {
1218            *value = (*value) * 2
1219        }
1220        let values: Vec<_> = map.values().cloned().collect();
1221        assert_eq!(values.len(), 3);
1222        assert!(values.contains(&2));
1223        assert!(values.contains(&4));
1224        assert!(values.contains(&6));
1225    }
1226
1227    #[test]
1228    fn test_find() {
1229        let mut m = ArcCache::new(2);
1230        assert!(m.get(&1).is_none());
1231        m.insert(1, 2);
1232        match m.get(&1) {
1233            None => panic!(),
1234            Some(v) => assert_eq!(*v, 2),
1235        }
1236    }
1237
1238    #[test]
1239    fn test_eq() {
1240        let mut m1 = ArcCache::new(3);
1241        m1.insert(1, 2);
1242        m1.insert(2, 3);
1243        m1.insert(3, 4);
1244
1245        let mut m2 = ArcCache::new(3);
1246        m2.insert(1, 2);
1247        m2.insert(2, 3);
1248
1249        assert!(m1 != m2);
1250
1251        m2.insert(3, 4);
1252
1253        assert_eq!(m1, m2);
1254    }
1255
1256    #[test]
1257    fn test_from_iter() {
1258        let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1259
1260        let map: ArcCache<_, _, _> = xs.iter().cloned().collect();
1261
1262        for &(k, v) in &xs {
1263            assert_eq!(map.raw_get(&k), Some(&v));
1264        }
1265    }
1266
1267    #[test]
1268    fn test_size_hint() {
1269        let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1270
1271        let map: ArcCache<_, _, _> = xs.iter().cloned().collect();
1272
1273        let mut iter = map.iter();
1274
1275        for _ in iter.by_ref().take(3) {}
1276
1277        assert_eq!(iter.size_hint(), (3, None));
1278    }
1279
1280    #[test]
1281    fn test_iter_len() {
1282        let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1283
1284        let map: ArcCache<_, _, _> = xs.iter().cloned().collect();
1285
1286        let mut iter = map.iter();
1287
1288        for _ in iter.by_ref().take(3) {}
1289
1290        assert_eq!(iter.count(), 3);
1291    }
1292
1293    #[test]
1294    fn test_mut_size_hint() {
1295        let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1296
1297        let mut map: ArcCache<_, _, _> = xs.iter().cloned().collect();
1298
1299        let mut iter = map.iter_mut();
1300
1301        for _ in iter.by_ref().take(3) {}
1302
1303        assert_eq!(iter.size_hint(), (3, None));
1304    }
1305
1306    #[test]
1307    fn test_iter_mut_len() {
1308        let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1309
1310        let mut map: ArcCache<_, _, _> = xs.iter().cloned().collect();
1311
1312        let mut iter = map.iter_mut();
1313
1314        for _ in iter.by_ref().take(3) {}
1315
1316        assert_eq!(iter.count(), 3);
1317    }
1318
1319    #[test]
1320    fn test_index() {
1321        let mut map = ArcCache::new(2);
1322
1323        map.insert(1, 2);
1324        map.insert(2, 1);
1325        map.insert(3, 4);
1326
1327        assert_eq!(map[&2], 1);
1328    }
1329
1330    #[test]
1331    #[should_panic]
1332    fn test_index_nonexistent() {
1333        let mut map = ArcCache::new(2);
1334
1335        map.insert(1, 2);
1336        map.insert(2, 1);
1337        map.insert(3, 4);
1338
1339        map[&4];
1340    }
1341
1342    #[test]
1343    fn test_extend_iter() {
1344        let mut a = ArcCache::new(2);
1345        a.insert(1, "one");
1346        let mut b = ArcCache::new(2);
1347        b.insert(2, "two");
1348        b.insert(3, "three");
1349
1350        a.extend(b.into_iter());
1351
1352        assert_eq!(a.len(), 3);
1353        assert_eq!(a[&1], "one");
1354        assert_eq!(a[&2], "two");
1355        assert_eq!(a[&3], "three");
1356    }
1357
1358    #[test]
1359    fn test_send() {
1360        use std::thread;
1361
1362        let mut cache = ArcCache::new(4);
1363        cache.insert(1, "a");
1364
1365        let handle = thread::spawn(move || {
1366            assert_eq!(cache.get(&1), Some(&"a"));
1367        });
1368
1369        assert!(handle.join().is_ok());
1370    }
1371
1372    #[test]
1373    #[cfg(feature = "ttl")]
1374    fn test_ttl_cache() {
1375        let mut lru = ArcCache::new(3);
1376        lru.insert_with_ttl("help", "ok", 1);
1377        lru.insert_with_ttl("author", "tickbh", 2);
1378        assert_eq!(lru.len(), 2);
1379        std::thread::sleep(std::time::Duration::from_secs(1));
1380        assert_eq!(lru.get("help"), None);
1381        std::thread::sleep(std::time::Duration::from_secs(1));
1382        assert_eq!(lru.get("author"), None);
1383        assert_eq!(lru.len(), 0);
1384    }
1385
1386    #[test]
1387    #[cfg(feature = "ttl")]
1388    fn test_ttl_check_cache() {
1389        let mut lru = ArcCache::new(3);
1390        lru.set_check_step(1);
1391        lru.insert_with_ttl("help", "ok", 1);
1392        lru.insert("now", "algorithm");
1393        assert_eq!(lru.len(), 2);
1394        std::thread::sleep(std::time::Duration::from_secs(1));
1395        assert_eq!(lru.len(), 2);
1396        lru.insert_with_ttl("author", "tickbh", 3);
1397        assert_eq!(lru.len(), 2);
1398        assert_eq!(lru.get("help"), None);
1399        assert_eq!(lru.len(), 2);
1400    }
1401
1402    #[test]
1403    #[cfg(feature = "ttl")]
1404    fn test_ttl_del() {
1405        let mut lru = ArcCache::new(3);
1406        lru.insert_with_ttl("help", "ok", 1);
1407        lru.insert_with_ttl("author", "tickbh", 2);
1408        assert_eq!(lru.len(), 2);
1409        std::thread::sleep(std::time::Duration::from_secs(1));
1410        assert_eq!(lru.get("help"), None);
1411        lru.del_ttl(&"author");
1412        std::thread::sleep(std::time::Duration::from_secs(1));
1413        assert_eq!(lru.get("author"), Some(&"tickbh"));
1414        assert_eq!(lru.len(), 1);
1415    }
1416
1417    #[test]
1418    #[cfg(feature = "ttl")]
1419    fn test_ttl_set() {
1420        let mut lru = ArcCache::new(3);
1421        lru.insert_with_ttl("help", "ok", 1);
1422        lru.insert_with_ttl("author", "tickbh", 2);
1423        lru.set_ttl(&"help", 3);
1424        assert_eq!(lru.len(), 2);
1425        std::thread::sleep(std::time::Duration::from_secs(1));
1426        assert_eq!(lru.get("help"), Some(&"ok"));
1427        std::thread::sleep(std::time::Duration::from_secs(1));
1428        assert_eq!(lru.get("author"), None);
1429        std::thread::sleep(std::time::Duration::from_secs(1));
1430        assert_eq!(lru.get("help"), None);
1431        assert_eq!(lru.len(), 0);
1432    }
1433
1434    #[test]
1435    #[cfg(feature = "ttl")]
1436    fn test_ttl_get() {
1437        let mut lru = ArcCache::new(3);
1438        lru.insert_with_ttl("help", "ok", 1);
1439        lru.insert_with_ttl("author", "tickbh", 2);
1440        lru.insert("now", "algorithm");
1441        assert!(lru.get_ttl(&"help").unwrap() <= 1);
1442        assert!(lru.get_ttl(&"author").unwrap() <= 2);
1443        assert_eq!(lru.get_ttl(&"now"), Some(u64::MAX));
1444    }
1445}
algorithm/cache/arc.rs

algorithm/cache/
arc.rs
