timed_map/
map.rs

1use super::*;
2
3macro_rules! cfg_std_feature {
4    ($($item:item)*) => {
5        $(
6            #[cfg(feature = "std")]
7            $item
8        )*
9    };
10}
11
12macro_rules! cfg_not_std_feature {
13    ($($item:item)*) => {
14        $(
15            #[cfg(not(feature = "std"))]
16            $item
17        )*
18    };
19}
20
21cfg_not_std_feature! {
22    /// Generic trait for `no_std` keys that is gated by the `std` feature
23    /// and handled at compile time.
24    pub trait GenericKey: Clone + Eq + Ord {}
25    impl<T: Clone + Eq + Ord> GenericKey for T {}
26}
27
28cfg_std_feature! {
29    /// Generic trait for `std` keys that is gated by the `std` feature
30    /// and handled at compile time.
31    pub trait GenericKey: Clone + Eq + Ord + Hash {}
32    impl<T: Clone + Eq + Ord + Hash> GenericKey for T {}
33}
34
35/// Wraps different map implementations and provides a single interface to access them.
36#[allow(clippy::enum_variant_names)]
37#[derive(Debug)]
38enum GenericMap<K, V> {
39    BTreeMap(BTreeMap<K, V>),
40    #[cfg(feature = "std")]
41    HashMap(HashMap<K, V>),
42    #[cfg(all(feature = "std", feature = "rustc-hash"))]
43    FxHashMap(FxHashMap<K, V>),
44}
45
46impl<K, V> Default for GenericMap<K, V> {
47    fn default() -> Self {
48        Self::BTreeMap(BTreeMap::default())
49    }
50}
51
52impl<K, V> GenericMap<K, V>
53where
54    K: GenericKey,
55{
56    #[inline(always)]
57    fn get(&self, k: &K) -> Option<&V> {
58        match self {
59            Self::BTreeMap(inner) => inner.get(k),
60            #[cfg(feature = "std")]
61            Self::HashMap(inner) => inner.get(k),
62            #[cfg(all(feature = "std", feature = "rustc-hash"))]
63            Self::FxHashMap(inner) => inner.get(k),
64        }
65    }
66
67    #[inline(always)]
68    fn get_mut(&mut self, k: &K) -> Option<&mut V> {
69        match self {
70            Self::BTreeMap(inner) => inner.get_mut(k),
71            #[cfg(feature = "std")]
72            Self::HashMap(inner) => inner.get_mut(k),
73            #[cfg(all(feature = "std", feature = "rustc-hash"))]
74            Self::FxHashMap(inner) => inner.get_mut(k),
75        }
76    }
77
78    #[inline(always)]
79    fn len(&self) -> usize {
80        match self {
81            Self::BTreeMap(inner) => inner.len(),
82            #[cfg(feature = "std")]
83            Self::HashMap(inner) => inner.len(),
84            #[cfg(all(feature = "std", feature = "rustc-hash"))]
85            Self::FxHashMap(inner) => inner.len(),
86        }
87    }
88
89    #[inline(always)]
90    fn keys(&self) -> Vec<K> {
91        match self {
92            Self::BTreeMap(inner) => inner.keys().cloned().collect(),
93            #[cfg(feature = "std")]
94            Self::HashMap(inner) => inner.keys().cloned().collect(),
95            #[cfg(all(feature = "std", feature = "rustc-hash"))]
96            Self::FxHashMap(inner) => inner.keys().cloned().collect(),
97        }
98    }
99
100    #[inline(always)]
101    fn is_empty(&self) -> bool {
102        match self {
103            Self::BTreeMap(inner) => inner.is_empty(),
104            #[cfg(feature = "std")]
105            Self::HashMap(inner) => inner.is_empty(),
106            #[cfg(all(feature = "std", feature = "rustc-hash"))]
107            Self::FxHashMap(inner) => inner.is_empty(),
108        }
109    }
110
111    #[inline(always)]
112    fn insert(&mut self, k: K, v: V) -> Option<V> {
113        match self {
114            Self::BTreeMap(inner) => inner.insert(k, v),
115            #[cfg(feature = "std")]
116            Self::HashMap(inner) => inner.insert(k, v),
117            #[cfg(all(feature = "std", feature = "rustc-hash"))]
118            Self::FxHashMap(inner) => inner.insert(k, v),
119        }
120    }
121
122    #[inline(always)]
123    fn clear(&mut self) {
124        match self {
125            Self::BTreeMap(inner) => inner.clear(),
126            #[cfg(feature = "std")]
127            Self::HashMap(inner) => inner.clear(),
128            #[cfg(all(feature = "std", feature = "rustc-hash"))]
129            Self::FxHashMap(inner) => inner.clear(),
130        }
131    }
132
133    #[inline(always)]
134    fn remove(&mut self, k: &K) -> Option<V> {
135        match self {
136            Self::BTreeMap(inner) => inner.remove(k),
137            #[cfg(feature = "std")]
138            Self::HashMap(inner) => inner.remove(k),
139            #[cfg(all(feature = "std", feature = "rustc-hash"))]
140            Self::FxHashMap(inner) => inner.remove(k),
141        }
142    }
143}
144
145/// Specifies the inner map implementation for `TimedMap`.
146#[cfg(feature = "std")]
147#[allow(clippy::enum_variant_names)]
148pub enum MapKind {
149    BTreeMap,
150    HashMap,
151    #[cfg(feature = "rustc-hash")]
152    FxHashMap,
153}
154
155/// Associates keys of type `K` with values of type `V`. Each entry may optionally expire after a
156/// specified duration.
157///
158/// Mutable functions automatically clears expired entries when called.
159///
160/// If no expiration is set, the entry remains constant.
161#[derive(Debug)]
162pub struct TimedMap<K, V, #[cfg(feature = "std")] C = StdClock, #[cfg(not(feature = "std"))] C> {
163    clock: C,
164
165    map: GenericMap<K, ExpirableEntry<V>>,
166    expiries: BTreeMap<u64, BTreeSet<K>>,
167
168    expiration_tick: u16,
169    expiration_tick_cap: u16,
170}
171
172#[cfg(feature = "serde")]
173impl<K: serde::Serialize + Ord, V: serde::Serialize, C> serde::Serialize for TimedMap<K, V, C> {
174    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
175    where
176        S: serde::Serializer,
177    {
178        match &self.map {
179            GenericMap::BTreeMap(inner) => serializer.collect_map(inner),
180            #[cfg(feature = "std")]
181            GenericMap::HashMap(inner) => serializer.collect_map(inner),
182            #[cfg(all(feature = "std", feature = "rustc-hash"))]
183            GenericMap::FxHashMap(inner) => serializer.collect_map(inner),
184        }
185    }
186}
187
188impl<K, V, C> Default for TimedMap<K, V, C>
189where
190    C: Default,
191{
192    fn default() -> Self {
193        Self {
194            clock: Default::default(),
195
196            map: GenericMap::default(),
197            expiries: BTreeMap::default(),
198
199            expiration_tick: 0,
200            expiration_tick_cap: 1,
201        }
202    }
203}
204
205#[cfg(feature = "std")]
206impl<K, V> TimedMap<K, V, StdClock>
207where
208    K: GenericKey,
209{
210    /// Creates an empty map.
211    pub fn new() -> Self {
212        Self::default()
213    }
214
215    /// Creates an empty map based on the chosen map implementation specified by `MapKind`.
216    pub fn new_with_map_kind(map_kind: MapKind) -> Self {
217        let map = match map_kind {
218            MapKind::BTreeMap => GenericMap::<K, ExpirableEntry<V>>::BTreeMap(BTreeMap::default()),
219            MapKind::HashMap => GenericMap::HashMap(HashMap::default()),
220            #[cfg(feature = "rustc-hash")]
221            MapKind::FxHashMap => GenericMap::FxHashMap(FxHashMap::default()),
222        };
223
224        Self {
225            map,
226
227            clock: StdClock::default(),
228            expiries: BTreeMap::default(),
229
230            expiration_tick: 0,
231            expiration_tick_cap: 1,
232        }
233    }
234}
235
236impl<K, V, C> TimedMap<K, V, C>
237where
238    C: Clock,
239    K: GenericKey,
240{
241    /// Creates an empty `TimedMap`.
242    ///
243    /// Uses the provided `clock` to handle expiration times.
244    #[cfg(not(feature = "std"))]
245    pub fn new(clock: C) -> Self {
246        Self {
247            clock,
248            map: GenericMap::default(),
249            expiries: BTreeMap::default(),
250            expiration_tick: 0,
251            expiration_tick_cap: 1,
252        }
253    }
254
255    /// Configures `expiration_tick_cap`, which sets how often `TimedMap::drop_expired_entries`
256    /// is automatically called. The default value is 1.
257    ///
258    /// On each insert (excluding `unchecked` ones), an internal counter `expiration_tick` is incremented.
259    /// When `expiration_tick` meets or exceeds `expiration_tick_cap`, `TimedMap::drop_expired_entries` is
260    /// triggered to remove expired entries.
261    ///
262    /// Use this to control cleanup frequency and optimize performance. For example, if your workload
263    /// involves about 100 inserts within couple seconds, setting `expiration_tick_cap` to 100 can improve
264    /// the performance significantly.
265    #[inline(always)]
266    pub fn expiration_tick_cap(mut self, expiration_tick_cap: u16) -> Self {
267        self.expiration_tick_cap = expiration_tick_cap;
268        self
269    }
270
271    /// Returns the associated value if present and not expired.
272    ///
273    /// To retrieve the value without checking expiration, use `TimedMap::get_unchecked`.
274    pub fn get(&self, k: &K) -> Option<&V> {
275        self.map
276            .get(k)
277            .filter(|v| !v.is_expired(self.clock.elapsed_seconds_since_creation()))
278            .map(|v| v.value())
279    }
280
281    /// Returns a mutable reference to the value corresponding to the key.
282    ///
283    /// To retrieve the value without checking expiration, use `TimedMap::get_mut_unchecked`.
284    pub fn get_mut(&mut self, k: &K) -> Option<&mut V> {
285        self.map
286            .get_mut(k)
287            .filter(|v| !v.is_expired(self.clock.elapsed_seconds_since_creation()))
288            .map(|v| v.value_mut())
289    }
290
291    /// Returns the associated value if present, regardless of whether it is expired.
292    ///
293    /// If you only want non-expired entries, use `TimedMap::get` instead.
294    #[inline(always)]
295    pub fn get_unchecked(&self, k: &K) -> Option<&V> {
296        self.map.get(k).map(|v| v.value())
297    }
298
299    /// Returns a mutable reference to the associated value if present, regardless of
300    /// whether it is expired.
301    ///
302    /// If you only want non-expired entries, use `TimedMap::get_mut` instead.
303    #[inline(always)]
304    pub fn get_mut_unchecked(&mut self, k: &K) -> Option<&mut V> {
305        self.map.get_mut(k).map(|v| v.value_mut())
306    }
307
308    /// Returns the associated value's `Duration` if present and not expired.
309    ///
310    /// Returns `None` if the entry does not exist or is constant.
311    pub fn get_remaining_duration(&self, k: &K) -> Option<Duration> {
312        match self.map.get(k) {
313            Some(v) => {
314                let now = self.clock.elapsed_seconds_since_creation();
315                if v.is_expired(now) {
316                    return None;
317                }
318
319                v.remaining_duration(now)
320            }
321            None => None,
322        }
323    }
324
325    /// Returns the number of unexpired elements in the map.
326    ///
327    /// See `TimedMap::len_expired` and `TimedMap::len_unchecked` for other usages.
328    #[inline(always)]
329    pub fn len(&self) -> usize {
330        self.map.len() - self.len_expired()
331    }
332
333    /// Returns the number of expired elements in the map.
334    ///
335    /// See `TimedMap::len` and `TimedMap::len_unchecked` for other usages.
336    #[inline(always)]
337    pub fn len_expired(&self) -> usize {
338        let now = self.clock.elapsed_seconds_since_creation();
339        self.expiries
340            .iter()
341            .filter_map(
342                |(exp, keys)| {
343                    if exp <= &now {
344                        Some(keys.len())
345                    } else {
346                        None
347                    }
348                },
349            )
350            .sum()
351    }
352
353    /// Returns the total number of elements (including expired ones) in the map.
354    ///
355    /// See `TimedMap::len` and `TimedMap::len_expired` for other usages.
356    #[inline(always)]
357    pub fn len_unchecked(&self) -> usize {
358        self.map.len()
359    }
360
361    /// Returns keys of the map
362    #[inline(always)]
363    pub fn keys(&self) -> Vec<K> {
364        self.map.keys()
365    }
366
367    /// Returns true if the map contains no elements.
368    #[inline(always)]
369    pub fn is_empty(&self) -> bool {
370        self.map.is_empty()
371    }
372
373    /// Inserts a key-value pair with an expiration duration. If duration is `None`,
374    /// entry will be stored in a non-expirable way.
375    ///
376    /// If a value already exists for the given key, it will be updated and then
377    /// the old one will be returned.
378    #[inline(always)]
379    fn insert(&mut self, k: K, v: V, expires_at: Option<u64>) -> Option<V> {
380        let entry = ExpirableEntry::new(v, expires_at);
381        match self.map.insert(k.clone(), entry) {
382            Some(old) => {
383                // Remove the old expiry record
384                if let EntryStatus::ExpiresAtSeconds(e) = old.status() {
385                    self.drop_key_from_expiry(e, &k)
386                }
387
388                Some(old.owned_value())
389            }
390            None => None,
391        }
392    }
393
394    /// Inserts a key-value pair with an expiration duration, and then drops the
395    /// expired entries.
396    ///
397    /// If a value already exists for the given key, it will be updated and then
398    /// the old one will be returned.
399    ///
400    /// If you don't want to the check expired entries, consider using `TimedMap::insert_expirable_unchecked`
401    /// instead.
402    pub fn insert_expirable(&mut self, k: K, v: V, duration: Duration) -> Option<V> {
403        self.expiration_tick += 1;
404
405        let now = self.clock.elapsed_seconds_since_creation();
406        if self.expiration_tick >= self.expiration_tick_cap {
407            self.drop_expired_entries_inner(now);
408            self.expiration_tick = 0;
409        }
410
411        let expires_at = now + duration.as_secs();
412
413        let res = self.insert(k.clone(), v, Some(expires_at));
414
415        self.expiries.entry(expires_at).or_default().insert(k);
416
417        res
418    }
419
420    /// Inserts a key-value pair with an expiration duration, without checking the expired
421    /// entries.
422    ///
423    /// If a value already exists for the given key, it will be updated and then
424    /// the old one will be returned.
425    ///
426    /// If you want to check the expired entries, consider using `TimedMap::insert_expirable`
427    /// instead.
428    pub fn insert_expirable_unchecked(&mut self, k: K, v: V, duration: Duration) -> Option<V> {
429        let now = self.clock.elapsed_seconds_since_creation();
430        let expires_at = now + duration.as_secs();
431
432        let res = self.insert(k.clone(), v, Some(expires_at));
433
434        self.expiries.entry(expires_at).or_default().insert(k);
435
436        res
437    }
438
439    /// Inserts a key-value pair with that doesn't expire, and then drops the
440    /// expired entries.
441    ///
442    /// If a value already exists for the given key, it will be updated and then
443    /// the old one will be returned.
444    ///
445    /// If you don't want to check the expired entries, consider using `TimedMap::insert_constant_unchecked`
446    /// instead.
447    pub fn insert_constant(&mut self, k: K, v: V) -> Option<V> {
448        self.expiration_tick += 1;
449
450        let now = self.clock.elapsed_seconds_since_creation();
451        if self.expiration_tick >= self.expiration_tick_cap {
452            self.drop_expired_entries_inner(now);
453            self.expiration_tick = 0;
454        }
455
456        self.insert(k, v, None)
457    }
458
459    /// Inserts a key-value pair with that doesn't expire without checking the expired
460    /// entries.
461    ///
462    /// If a value already exists for the given key, it will be updated and then
463    /// the old one will be returned.
464    ///
465    /// If you want to check the expired entries, consider using `TimedMap::insert_constant`
466    /// instead.
467    pub fn insert_constant_unchecked(&mut self, k: K, v: V) -> Option<V> {
468        self.expiration_tick += 1;
469        self.insert(k, v, None)
470    }
471
472    /// Removes a key-value pair from the map and returns the associated value if present
473    /// and not expired.
474    ///
475    /// If you want to retrieve the entry after removal even if it is expired, consider using
476    /// `TimedMap::remove_unchecked`.
477    #[inline(always)]
478    pub fn remove(&mut self, k: &K) -> Option<V> {
479        self.map
480            .remove(k)
481            .filter(|v| {
482                if let EntryStatus::ExpiresAtSeconds(expires_at_seconds) = v.status() {
483                    self.drop_key_from_expiry(expires_at_seconds, k);
484                }
485
486                !v.is_expired(self.clock.elapsed_seconds_since_creation())
487            })
488            .map(|v| v.owned_value())
489    }
490
491    /// Removes a key-value pair from the map and returns the associated value if present,
492    /// regardless of expiration status.
493    ///
494    /// If you only want the entry when it is not expired, consider using `TimedMap::remove`.
495    #[inline(always)]
496    pub fn remove_unchecked(&mut self, k: &K) -> Option<V> {
497        self.map
498            .remove(k)
499            .filter(|v| {
500                if let EntryStatus::ExpiresAtSeconds(expires_at_seconds) = v.status() {
501                    self.drop_key_from_expiry(expires_at_seconds, k);
502                }
503
504                true
505            })
506            .map(|v| v.owned_value())
507    }
508
509    /// Clears the map, removing all elements.
510    #[inline(always)]
511    pub fn clear(&mut self) {
512        self.map.clear()
513    }
514
515    /// Updates the expiration status of an entry and returns the old status.
516    ///
517    /// If the entry does not exist, returns Err.
518    /// If the entry's old status is `EntryStatus::Constant`, returns None.
519    pub fn update_expiration_status(
520        &mut self,
521        key: K,
522        duration: Duration,
523    ) -> Result<Option<EntryStatus>, &'static str> {
524        match self.map.get_mut(&key) {
525            Some(entry) => {
526                let old_status = *entry.status();
527                let now = self.clock.elapsed_seconds_since_creation();
528                let expires_at = now + duration.as_secs();
529
530                entry.update_status(EntryStatus::ExpiresAtSeconds(expires_at));
531
532                if let EntryStatus::ExpiresAtSeconds(t) = &old_status {
533                    self.drop_key_from_expiry(t, &key);
534                }
535                self.expiries
536                    .entry(expires_at)
537                    .or_default()
538                    .insert(key.clone());
539
540                Ok(Some(old_status))
541            }
542            None => Err("entry not found"),
543        }
544    }
545
546    /// Clears expired entries from the map.
547    ///
548    /// Call this function when using `*_unchecked` inserts, as these do not
549    /// automatically clear expired entries.
550    #[inline(always)]
551    pub fn drop_expired_entries(&mut self) {
552        let now = self.clock.elapsed_seconds_since_creation();
553        self.drop_expired_entries_inner(now);
554    }
555
556    fn drop_expired_entries_inner(&mut self, now: u64) {
557        // Iterates through `expiries` in order and drops expired ones.
558        while let Some((exp, keys)) = self.expiries.pop_first() {
559            // It's safe to do early-break here as keys are sorted by expiration.
560            if exp > now {
561                self.expiries.insert(exp, keys);
562                break;
563            }
564
565            for key in keys {
566                self.map.remove(&key);
567            }
568        }
569    }
570
571    fn drop_key_from_expiry(&mut self, expiry_key: &u64, map_key: &K) {
572        if let Some(list) = self.expiries.get_mut(expiry_key) {
573            list.remove(map_key);
574
575            if list.is_empty() {
576                self.expiries.remove(expiry_key);
577            }
578        }
579    }
580
581    /// Returns `true` if the map contains a non-expired value for the given key.
582    ///
583    /// To include expired entries as well, use [`TimedMap::contains_key_unchecked`].
584    #[inline(always)]
585    pub fn contains_key(&self, k: &K) -> bool {
586        self.get(k).is_some()
587    }
588
589    /// Returns `true` if the map contains a value for the given key regardless of expiration status.
590    ///
591    /// To exclude expired entries, use [`TimedMap::contains_key`] instead.
592    #[inline(always)]
593    pub fn contains_key_unchecked(&self, k: &K) -> bool {
594        self.map.keys().contains(k)
595    }
596}
597
598#[cfg(test)]
599#[cfg(not(feature = "std"))]
600mod tests {
601    use super::*;
602
603    struct MockClock {
604        current_time: u64,
605    }
606
607    impl Clock for MockClock {
608        fn elapsed_seconds_since_creation(&self) -> u64 {
609            self.current_time
610        }
611    }
612
613    #[test]
614    fn nostd_insert_and_get_constant_entry() {
615        let clock = MockClock { current_time: 1000 };
616        let mut map = TimedMap::new(clock);
617
618        map.insert_constant(1, "constant value");
619
620        assert_eq!(map.get(&1), Some(&"constant value"));
621        assert_eq!(map.get_remaining_duration(&1), None);
622    }
623
624    #[test]
625    fn nostd_insert_and_get_expirable_entry() {
626        let clock = MockClock { current_time: 1000 };
627        let mut map = TimedMap::new(clock);
628        let duration = Duration::from_secs(60);
629
630        map.insert_expirable(1, "expirable value", duration);
631
632        assert_eq!(map.get(&1), Some(&"expirable value"));
633        assert_eq!(map.get_remaining_duration(&1), Some(duration));
634    }
635
636    #[test]
637    fn nostd_expired_entry() {
638        let clock = MockClock { current_time: 1000 };
639        let mut map = TimedMap::new(clock);
640        let duration = Duration::from_secs(60);
641
642        // Insert entry that expires in 60 seconds
643        map.insert_expirable(1, "expirable value", duration);
644
645        // Simulate time passage beyond expiration
646        let clock = MockClock { current_time: 1070 };
647        map.clock = clock;
648
649        // The entry should be considered expired
650        assert_eq!(map.get(&1), None);
651        assert_eq!(map.get_remaining_duration(&1), None);
652    }
653
654    #[test]
655    fn nostd_remove_entry() {
656        let clock = MockClock { current_time: 1000 };
657        let mut map = TimedMap::new(clock);
658
659        map.insert_constant(1, "constant value");
660
661        assert_eq!(map.remove(&1), Some("constant value"));
662        assert_eq!(map.get(&1), None);
663    }
664
665    #[test]
666    fn nostd_drop_expired_entries() {
667        let clock = MockClock { current_time: 1000 };
668        let mut map = TimedMap::new(clock);
669
670        // Insert one constant and 2 expirable entries
671        map.insert_expirable(1, "expirable value1", Duration::from_secs(50));
672        map.insert_expirable(2, "expirable value2", Duration::from_secs(70));
673        map.insert_constant(3, "constant value");
674
675        // Simulate time passage beyond the expiration of the first entry
676        let clock = MockClock { current_time: 1055 };
677        map.clock = clock;
678
679        // Entry 1 should be removed and entry 2 and 3 should still exist
680        assert_eq!(map.get(&1), None);
681        assert_eq!(map.get(&2), Some(&"expirable value2"));
682        assert_eq!(map.get(&3), Some(&"constant value"));
683
684        // Simulate time passage again to expire second expirable entry
685        let clock = MockClock { current_time: 1071 };
686        map.clock = clock;
687
688        assert_eq!(map.get(&1), None);
689        assert_eq!(map.get(&2), None);
690        assert_eq!(map.get(&3), Some(&"constant value"));
691    }
692
693    #[test]
694    fn nostd_update_existing_entry() {
695        let clock = MockClock { current_time: 1000 };
696        let mut map = TimedMap::new(clock);
697
698        map.insert_constant(1, "initial value");
699        assert_eq!(map.get(&1), Some(&"initial value"));
700
701        // Update the value of the existing key and make it expirable
702        map.insert_expirable(1, "updated value", Duration::from_secs(15));
703        assert_eq!(map.get(&1), Some(&"updated value"));
704
705        // Simulate time passage and expire the updated entry
706        let clock = MockClock { current_time: 1016 };
707        map.clock = clock;
708
709        assert_eq!(map.get(&1), None);
710    }
711
712    #[test]
713    fn nostd_update_expirable_entry_status() {
714        let clock = MockClock { current_time: 1000 };
715        let mut map = TimedMap::new(clock);
716
717        map.insert_constant(1, "initial value");
718        assert_eq!(map.get(&1), Some(&"initial value"));
719
720        // Update the value of the existing key and make it expirable
721        map.update_expiration_status(1, Duration::from_secs(16))
722            .expect("entry update shouldn't fail");
723        assert_eq!(map.get(&1), Some(&"initial value"));
724
725        // Simulate time passage and expire the updated entry
726        let clock = MockClock { current_time: 1017 };
727        map.clock = clock;
728        assert_eq!(map.get(&1), None);
729    }
730
731    #[test]
732    fn nostd_update_expirable_entry_status_with_previou_time() {
733        let clock = MockClock { current_time: 1000 };
734        let mut map = TimedMap::new(clock);
735
736        // Insert map entry followed by immediately updating expiration time
737        map.insert_expirable(1, "expirable value", Duration::from_secs(15));
738        map.update_expiration_status(1, Duration::from_secs(15))
739            .expect("entry update shouldn't fail");
740
741        // We should still have our entry.
742        assert_eq!(map.get(&1), Some(&"expirable value"));
743        assert!(map.expiries.contains_key(&1015));
744    }
745
746    #[test]
747    fn nostd_contains_key() {
748        let clock = MockClock { current_time: 1000 };
749        let mut map = TimedMap::new(clock);
750
751        // Insert map entry and check if exists
752        map.insert_expirable(1, "expirable value", Duration::from_secs(5));
753        assert!(map.contains_key(&1));
754    }
755}
756
757#[cfg(feature = "std")]
758#[cfg(test)]
759mod std_tests {
760    use core::ops::Add;
761
762    use super::*;
763
764    #[test]
765    fn std_expirable_and_constant_entries() {
766        let mut map = TimedMap::new();
767
768        map.insert_constant(1, "constant value");
769        map.insert_expirable(2, "expirable value", Duration::from_secs(2));
770
771        assert_eq!(map.get(&1), Some(&"constant value"));
772        assert_eq!(map.get(&2), Some(&"expirable value"));
773
774        assert_eq!(map.get_remaining_duration(&1), None);
775        assert!(map.get_remaining_duration(&2).is_some());
776    }
777
778    #[test]
779    fn std_expired_entry_removal() {
780        let mut map = TimedMap::new();
781        let duration = Duration::from_secs(2);
782
783        map.insert_expirable(1, "expirable value", duration);
784
785        // Wait for expiration
786        std::thread::sleep(Duration::from_secs(3));
787
788        // Entry should now be expired
789        assert_eq!(map.get(&1), None);
790        assert_eq!(map.get_remaining_duration(&1), None);
791    }
792
793    #[test]
794    fn std_remove_entry() {
795        let mut map = TimedMap::new();
796
797        map.insert_constant(1, "constant value");
798        map.insert_expirable(2, "expirable value", Duration::from_secs(2));
799
800        assert_eq!(map.remove(&1), Some("constant value"));
801        assert_eq!(map.remove(&2), Some("expirable value"));
802
803        assert_eq!(map.get(&1), None);
804        assert_eq!(map.get(&2), None);
805    }
806
807    #[test]
808    fn std_drop_expired_entries() {
809        let mut map = TimedMap::new();
810
811        map.insert_expirable(1, "expirable value1", Duration::from_secs(2));
812        map.insert_expirable(2, "expirable value2", Duration::from_secs(4));
813
814        // Wait for expiration
815        std::thread::sleep(Duration::from_secs(3));
816
817        // Entry 1 should be removed and entry 2 should still exist
818        assert_eq!(map.get(&1), None);
819        assert_eq!(map.get(&2), Some(&"expirable value2"));
820    }
821
822    #[test]
823    fn std_update_existing_entry() {
824        let mut map = TimedMap::new();
825
826        map.insert_constant(1, "initial value");
827        assert_eq!(map.get(&1), Some(&"initial value"));
828
829        // Update the value of the existing key and make it expirable
830        map.insert_expirable(1, "updated value", Duration::from_secs(1));
831        assert_eq!(map.get(&1), Some(&"updated value"));
832
833        std::thread::sleep(Duration::from_secs(2));
834
835        // Should be expired now
836        assert_eq!(map.get(&1), None);
837    }
838
839    #[test]
840    fn std_insert_constant_and_expirable_combined() {
841        let mut map = TimedMap::new();
842
843        // Insert a constant entry and an expirable entry
844        map.insert_constant(1, "constant value");
845        map.insert_expirable(2, "expirable value", Duration::from_secs(2));
846
847        // Check both entries exist
848        assert_eq!(map.get(&1), Some(&"constant value"));
849        assert_eq!(map.get(&2), Some(&"expirable value"));
850
851        // Simulate passage of time beyond expiration
852        std::thread::sleep(Duration::from_secs(3));
853
854        // Constant entry should still exist, expirable should be expired
855        assert_eq!(map.get(&1), Some(&"constant value"));
856        assert_eq!(map.get(&2), None);
857    }
858
859    #[test]
860    fn std_expirable_entry_still_valid_before_expiration() {
861        let mut map = TimedMap::new();
862
863        // Insert an expirable entry with a duration of 3 seconds
864        map.insert_expirable(1, "expirable value", Duration::from_secs(3));
865
866        // Simulate a short sleep of 2 seconds (still valid)
867        std::thread::sleep(Duration::from_secs(2));
868
869        // The entry should still be valid
870        assert_eq!(map.get(&1), Some(&"expirable value"));
871        assert!(map.get_remaining_duration(&1).unwrap().as_secs() == 1);
872    }
873
874    #[test]
875    fn std_length_functions() {
876        let mut map = TimedMap::new();
877
878        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
879        map.insert_expirable(2, "expirable value", Duration::from_secs(1));
880        map.insert_expirable(3, "expirable value", Duration::from_secs(3));
881        map.insert_expirable(4, "expirable value", Duration::from_secs(3));
882        map.insert_expirable(5, "expirable value", Duration::from_secs(3));
883        map.insert_expirable(6, "expirable value", Duration::from_secs(3));
884
885        std::thread::sleep(Duration::from_secs(2).add(Duration::from_millis(1)));
886
887        assert_eq!(map.len(), 4);
888        assert_eq!(map.len_expired(), 2);
889        assert_eq!(map.len_unchecked(), 6);
890    }
891
892    #[test]
893    fn std_update_expirable_entry() {
894        let mut map = TimedMap::new();
895
896        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
897        map.insert_expirable(1, "expirable value", Duration::from_secs(5));
898
899        std::thread::sleep(Duration::from_secs(2));
900
901        assert!(!map.expiries.contains_key(&1));
902        assert!(map.expiries.contains_key(&5));
903        assert_eq!(map.get(&1), Some(&"expirable value"));
904    }
905
906    #[test]
907    fn std_update_expirable_entry_status() {
908        let mut map = TimedMap::new();
909
910        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
911        map.update_expiration_status(1, Duration::from_secs(5))
912            .expect("entry update shouldn't fail");
913
914        std::thread::sleep(Duration::from_secs(3));
915        assert!(!map.expiries.contains_key(&1));
916        assert!(map.expiries.contains_key(&5));
917        assert_eq!(map.get(&1), Some(&"expirable value"));
918    }
919
920    #[test]
921    fn std_update_expirable_entry_status_with_previou_time() {
922        let mut map = TimedMap::new();
923
924        // Insert map entry followed by immediately updating expiration time
925        map.insert_expirable(1, "expirable value", Duration::from_secs(5));
926        map.update_expiration_status(1, Duration::from_secs(5))
927            .expect("entry update shouldn't fail");
928
929        // We should still have our entry.
930        assert_eq!(map.get(&1), Some(&"expirable value"));
931        assert!(map.expiries.contains_key(&5));
932    }
933
934    #[test]
935    fn std_contains_key() {
936        let mut map = TimedMap::new();
937
938        // Insert map entry and check if exists
939        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
940        assert!(map.contains_key(&1));
941    }
942
943    #[test]
944    fn std_does_not_contain_key_anymore() {
945        let mut map = TimedMap::new();
946
947        // Insert map entry and check if still exists after expiry
948        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
949        std::thread::sleep(Duration::from_secs(2));
950        assert!(!map.contains_key(&1));
951    }
952
953    #[test]
954    fn std_contains_key_unchecked() {
955        let mut map = TimedMap::new();
956
957        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
958        std::thread::sleep(Duration::from_secs(2));
959        assert!(map.contains_key_unchecked(&1));
960    }
961}
timed_map/map.rs

timed_map/
map.rs
