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

timed_map/
map.rs
