lru_st/collections/hashmap.rs
1use crate::{Cursor, DoublyLinkedList, DoublyLinkedListIter};
2
3use std::{collections::HashMap, fmt::Display, hash::Hash};
4
5#[cfg(not(feature = "sync"))]
6use std::rc::{Rc, Weak};
7
8#[cfg(feature = "sync")]
9use {std::sync::Arc as Rc, std::sync::Weak};
10
11/// An iterator over the entries of an `LruHashMap`, in order from most recently used to least recently used.
12///
13/// This iterator yields references to the key-value pairs stored in the `LruHashMap`.
14/// The keys are returned as `Rc<K>`, and the values as `&V`.
15///
16/// # Type Parameters
17/// - `'a`: The lifetime of the `LruHashMap` being iterated over.
18/// - `K`: The type of keys in the `LruHashMap`.
19/// - `V`: The type of values in the `LruHashMap`.
20/// ```
21pub struct LruHashmapIter<'a, K, V> {
22 it: DoublyLinkedListIter<'a, (Weak<K>, V)>,
23}
24
25impl<'a, K, V> LruHashmapIter<'a, K, V> {
26 fn from_lru_hashmap(map: &'a LruHashMap<K, V>) -> LruHashmapIter<'a, K, V> {
27 Self { it: map.lru.iter() }
28 }
29}
30
31impl<'a, K, V> Iterator for LruHashmapIter<'a, K, V> {
32 type Item = (Rc<K>, &'a V);
33 fn next(&mut self) -> Option<Self::Item> {
34 let item = self.it.next()?;
35 // Safe to unwrap because the key is guaranteed to exist in the map
36 let k = item
37 .0
38 .upgrade()
39 .expect("weak reference must be valid because the key exists in the map");
40 Some((k, &(item.1)))
41 }
42}
43
44impl<'a, K, V> DoubleEndedIterator for LruHashmapIter<'a, K, V> {
45 fn next_back(&mut self) -> Option<Self::Item> {
46 let item = self.it.next_back()?;
47 // Safe to unwrap because the key is guaranteed to exist in the map
48 let k = item
49 .0
50 .upgrade()
51 .expect("weak reference must be valid because the key exists in the map");
52 Some((k, &(item.1)))
53 }
54}
55
56/// A Least Recently Used (LRU) cache implemented on top of [`HashMap`] and [`DoublyLinkedList`] list.
57///
58/// The `LruHashMap` maintains a maximum number of entries. When the cache is full and a new
59/// entry is inserted, the least recently used entry is removed.
60///
61/// # Type Parameters
62/// - `K`: The type of keys in the cache. Must implement `Hash` and `Eq`.
63/// - `V`: The type of values in the cache.
64///
65/// # Examples
66/// ```
67/// use lru_st::collections::LruHashMap;
68///
69/// let mut cache = LruHashMap::with_max_entries(2);
70/// cache.insert("a", 1);
71/// cache.insert("b", 2);
72/// assert_eq!(cache.get(&"a"), Some(&1));
73/// cache.insert("c", 3);
74/// assert_eq!(cache.get(&"a"), Some(&1));
75/// assert_eq!(cache.get(&"b"), None); // "b" was evicted
76/// ```
77pub struct LruHashMap<K, V> {
78 map: HashMap<Rc<K>, Cursor>,
79 lru: DoublyLinkedList<(Weak<K>, V)>,
80 max_entries: usize,
81}
82
83impl<K, V> LruHashMap<K, V>
84where
85 K: Hash + Eq,
86{
87 /// Creates a new, empty `LruHashMap` with the specified maximum number of entries.
88 ///
89 /// # Arguments
90 /// * `max_entries` - The maximum number of entries the cache can hold.
91 ///
92 /// # Examples
93 /// ```
94 /// use lru_st::collections::LruHashMap;
95 ///
96 /// let mut cache = LruHashMap::with_max_entries(2);
97 /// cache.insert("a", 1);
98 /// cache.insert("b", 2);
99 /// assert_eq!(cache.get(&"a"), Some(&1));
100 /// cache.insert("c", 3);
101 /// assert_eq!(cache.get(&"a"), Some(&1));
102 /// assert_eq!(cache.get(&"b"), None); // "b" was evicted
103 /// ```
104 pub fn with_max_entries(max_entries: usize) -> Self {
105 LruHashMap {
106 map: HashMap::with_capacity(max_entries),
107 lru: DoublyLinkedList::with_capacity(max_entries),
108 max_entries,
109 }
110 }
111
112 /// Returns a reference to the value associated with the given key,
113 /// if it exists. The key is moved to the front of the LRU list.
114 ///
115 /// # Arguments
116 /// * `k` - The key to look up.
117 ///
118 /// # Returns
119 /// `Some(&V)` if the key exists, `None` otherwise.
120 ///
121 /// # Examples
122 /// ```
123 /// use lru_st::collections::LruHashMap;
124 ///
125 /// let mut cache = LruHashMap::with_max_entries(2);
126 /// cache.insert("a", 1);
127 /// assert_eq!(cache.get(&"a"), Some(&1));
128 /// ```
129 #[inline]
130 pub fn get(&mut self, k: &K) -> Option<&V> {
131 if let Some((_k, v)) = self.map.get(k).and_then(|cursor| {
132 self.lru.move_front(*cursor).unwrap();
133 self.lru.front()
134 }) {
135 return Some(v);
136 }
137 None
138 }
139
140 /// Returns a mutable reference to the value associated with the given key,
141 /// if it exists. The key is moved to the front of the LRU list.
142 ///
143 /// # Arguments
144 /// * `k` - The key to look up.
145 ///
146 /// # Returns
147 /// `Some(&mut V)` if the key exists, `None` otherwise.
148 ///
149 /// # Examples
150 /// ```
151 /// use lru_st::collections::LruHashMap;
152 ///
153 /// let mut cache = LruHashMap::with_max_entries(2);
154 /// cache.insert("a", 1);
155 /// if let Some(v) = cache.get_mut(&"a") {
156 /// *v = 2;
157 /// }
158 /// assert_eq!(cache.get(&"a"), Some(&2));
159 /// ```
160 #[inline]
161 pub fn get_mut(&mut self, k: &K) -> Option<&mut V> {
162 if let Some((_k, v)) = self.map.get(k).and_then(|cursor| {
163 self.lru.move_front(*cursor).unwrap();
164 self.lru.front_mut()
165 }) {
166 return Some(v);
167 }
168 None
169 }
170
171 /// Returns an iterator over the key-value pairs in the `LruHashMap`,
172 /// ordered from most recently used to least recently used.
173 ///
174 /// # Returns
175 /// An iterator yielding `(Rc<K>, &V)` pairs.
176 ///
177 /// # Examples
178 /// ```
179 /// use lru_st::collections::LruHashMap;
180 ///
181 /// #[cfg(not(feature = "sync"))]
182 /// use std::rc::Rc;
183 ///
184 /// #[cfg(feature = "sync")]
185 /// use std::sync::Arc as Rc;
186 ///
187 /// let mut cache = LruHashMap::with_max_entries(2);
188 /// cache.insert("a", 1);
189 /// cache.insert("b", 2);
190 ///
191 /// let mut iter = cache.items();
192 /// assert_eq!(iter.next(), Some((Rc::new("b"), &2)));
193 /// assert_eq!(iter.next(), Some((Rc::new("a"), &1)));
194 /// assert_eq!(iter.next(), None);
195 /// ```
196 #[inline]
197 pub fn items(&self) -> LruHashmapIter<'_, K, V> {
198 LruHashmapIter::from_lru_hashmap(self)
199 }
200
201 /// Returns an iterator over the keys in the `LruHashMap`,
202 /// ordered from most recently used to least recently used.
203 ///
204 /// # Returns
205 /// An iterator yielding `Rc<K>` keys.
206 ///
207 /// # Examples
208 /// ```
209 /// use lru_st::collections::LruHashMap;
210 /// #[cfg(not(feature = "sync"))]
211 /// use std::rc::Rc;
212 ///
213 /// #[cfg(feature = "sync")]
214 /// use std::sync::Arc as Rc;
215 ///
216 /// let mut cache = LruHashMap::with_max_entries(2);
217 /// cache.insert("a", 1);
218 /// cache.insert("b", 2);
219 ///
220 /// let mut keys = cache.keys();
221 /// assert_eq!(keys.next(), Some(Rc::new("b")));
222 /// assert_eq!(keys.next(), Some(Rc::new("a")));
223 /// assert_eq!(keys.next(), None);
224 #[inline]
225 pub fn keys(&self) -> impl DoubleEndedIterator<Item = Rc<K>> + use<'_, K, V> {
226 self.items().map(|(k, _)| k)
227 }
228
229 /// Returns an iterator over the values in the `LruHashMap`,
230 /// ordered from most recently used to least recently used.
231 ///
232 /// # Returns
233 /// An iterator yielding `&V` values.
234 ///
235 /// # Examples
236 /// ```
237 /// use lru_st::collections::LruHashMap;
238 ///
239 /// let mut cache = LruHashMap::with_max_entries(2);
240 /// cache.insert("a", 1);
241 /// cache.insert("b", 2);
242 ///
243 /// let mut values = cache.values();
244 /// assert_eq!(values.next(), Some(&2));
245 /// assert_eq!(values.next(), Some(&1));
246 /// assert_eq!(values.next(), None);
247 /// ```
248 #[inline]
249 pub fn values(&self) -> impl DoubleEndedIterator<Item = &V> + use<'_, K, V> {
250 self.items().map(|(_, v)| v)
251 }
252
253 /// Checks if the cache contains the given key.
254 ///
255 /// # Arguments
256 /// * `k` - The key to check.
257 ///
258 /// # Returns
259 /// `true` if the key exists, `false` otherwise.
260 ///
261 /// # Examples
262 /// ```
263 /// use lru_st::collections::LruHashMap;
264 ///
265 /// let mut cache = LruHashMap::with_max_entries(2);
266 /// cache.insert("a", 1);
267 /// assert!(cache.contains_key(&"a"));
268 /// assert!(!cache.contains_key(&"b"));
269 /// ```
270 #[inline]
271 pub fn contains_key(&mut self, k: &K) -> bool {
272 self.get(k).is_some()
273 }
274
275 /// Inserts a key-value pair into the cache. If the cache is full,
276 /// the least recently used entry is removed and returned.
277 ///
278 /// # Arguments
279 /// * `k` - The key to insert.
280 /// * `v` - The value to insert.
281 ///
282 /// # Returns
283 /// `Some((K, V))` if an entry was evicted, `None` otherwise.
284 ///
285 /// # Examples
286 /// ```
287 /// use lru_st::collections::LruHashMap;
288 ///
289 /// let mut cache = LruHashMap::with_max_entries(1);
290 /// cache.insert("a", 1);
291 /// let evicted = cache.insert("b", 2);
292 /// assert_eq!(evicted, Some(("a", 1)));
293 /// ```
294 #[inline]
295 pub fn insert(&mut self, k: K, v: V) -> Option<(K, V)> {
296 let mut removed = None;
297 // we update value if already there
298 if self.map.contains_key(&k) {
299 let old = self.get_mut(&k).expect("value must exist");
300 *old = v;
301 return removed;
302 }
303 // if we arrive here the key/value needs to be inserted
304 // if we reached capacity, we must delete the last used entry first
305 if self.map.len() == self.max_entries {
306 removed = self.pop_lru();
307 }
308 let k = Rc::new(k);
309 let cursor = self.lru.push_front((Rc::downgrade(&k), v));
310 self.map.insert(k, cursor);
311 removed
312 }
313
314 /// Removes the entry associated with the given key from the cache.
315 ///
316 /// # Arguments
317 /// * `k` - The key to remove.
318 ///
319 /// # Returns
320 /// `Some(V)` if the key existed, `None` otherwise.
321 ///
322 /// # Examples
323 /// ```
324 /// use lru_st::collections::LruHashMap;
325 ///
326 /// let mut cache = LruHashMap::with_max_entries(2);
327 /// cache.insert("a", 1);
328 /// assert_eq!(cache.remove(&"a"), Some(1));
329 /// assert_eq!(cache.remove(&"b"), None);
330 /// ```
331 #[inline]
332 pub fn remove(&mut self, k: &K) -> Option<V> {
333 if let Some(c) = self.map.remove(k) {
334 if let Some((_k, v)) = self.lru.pop(c) {
335 return Some(v);
336 }
337 }
338 None
339 }
340
341 /// Removes and returns the least recently used entry from the cache.
342 ///
343 /// This function removes the key-value pair at the back of the LRU list (the least recently used entry)
344 /// and returns it. If the cache is empty, it returns `None`.
345 ///
346 /// # Returns
347 /// `Some((K, V))` if an entry was removed, `None` if the cache is empty.
348 ///
349 /// # Examples
350 /// ```
351 /// use lru_st::collections::LruHashMap;
352 ///
353 /// let mut cache = LruHashMap::with_max_entries(2);
354 /// cache.insert("a", 1);
355 /// cache.insert("b", 2);
356 /// assert_eq!(cache.pop_lru(), Some(("a", 1)));
357 /// assert_eq!(cache.len(), 1);
358 /// assert_eq!(cache.pop_lru(), Some(("b", 2)));
359 /// assert_eq!(cache.pop_lru(), None);
360 /// ```
361 pub fn pop_lru(&mut self) -> Option<(K, V)> {
362 let mut removed = None;
363 if let Some((k, v)) = self.lru.pop_back() {
364 // we put this in a block so that we can debug_assert latter
365 {
366 // Safe to unwrap because the key is guaranteed to exist in the map
367 let key = k.upgrade().expect("weak reference must be valid");
368 self.map.remove(&key);
369
370 // it cannot be None as key is a strong reference
371 if let Some(inner_key) = Rc::into_inner(key) {
372 removed = Some((inner_key, v));
373 }
374 }
375 // Rc should have been dropped now because we have removed item from map
376 debug_assert!(k.upgrade().is_none());
377 };
378 removed
379 }
380
381 /// Returns the number of entries in the cache.
382 ///
383 /// # Examples
384 /// ```
385 /// use lru_st::collections::LruHashMap;
386 ///
387 /// let mut cache = LruHashMap::with_max_entries(2);
388 /// assert_eq!(cache.len(), 0);
389 /// cache.insert("a", 1);
390 /// assert_eq!(cache.len(), 1);
391 /// ```
392 #[inline(always)]
393 pub fn len(&self) -> usize {
394 self.map.len()
395 }
396
397 /// Returns the maximum number of entries the cache can hold.
398 ///
399 /// # Examples
400 /// ```
401 /// use lru_st::collections::LruHashMap;
402 ///
403 /// let mut cache = LruHashMap::with_max_entries(2);
404 /// cache.insert("a", 1);
405 /// assert_eq!(cache.cap(), 2);
406 /// ```
407 #[inline(always)]
408 pub fn cap(&self) -> usize {
409 self.max_entries
410 }
411
412 /// Checks if the cache is empty.
413 ///
414 /// # Examples
415 /// ```
416 /// use lru_st::collections::LruHashMap;
417 ///
418 /// let mut cache = LruHashMap::with_max_entries(2);
419 /// assert!(cache.is_empty());
420 /// cache.insert("a", 1);
421 /// assert!(!cache.is_empty());
422 /// ```
423 #[inline(always)]
424 pub fn is_empty(&self) -> bool {
425 self.map.is_empty()
426 }
427}
428
429impl<K, V> Display for LruHashMap<K, V>
430where
431 K: Display,
432 V: Display,
433{
434 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
435 let mut first = true;
436 write!(f, "{{")?;
437 for v in self.lru.iter() {
438 let key = v.0.upgrade().expect("weak reference must be valid");
439 if !first {
440 write!(f, ", ")?;
441 }
442 write!(f, "{}:{}", key, v.1)?;
443 first = false;
444 }
445 write!(f, "}}")?;
446 Ok(())
447 }
448}
449
450#[cfg(test)]
451mod tests {
452 use super::*;
453
454 #[test]
455 fn test_with_max_entries() {
456 let cache: LruHashMap<(), ()> = LruHashMap::with_max_entries(10);
457 assert_eq!(cache.cap(), 10);
458 assert!(cache.is_empty());
459 }
460
461 #[test]
462 fn test_insert_and_get() {
463 let mut cache = LruHashMap::with_max_entries(2);
464 cache.insert("a", 1);
465 cache.insert("b", 2);
466
467 assert_eq!(cache.get(&"a"), Some(&1));
468 assert_eq!(cache.get(&"b"), Some(&2));
469 assert_eq!(cache.len(), 2);
470 }
471
472 #[test]
473 fn test_get_mut() {
474 let mut cache = LruHashMap::with_max_entries(2);
475 cache.insert("a", 1);
476 if let Some(v) = cache.get_mut(&"a") {
477 *v = 2;
478 }
479 assert_eq!(cache.get(&"a"), Some(&2));
480 }
481
482 #[test]
483 fn test_contains_key() {
484 let mut cache = LruHashMap::with_max_entries(2);
485 cache.insert("a", 1);
486 assert!(cache.contains_key(&"a"));
487 assert!(!cache.contains_key(&"b"));
488 }
489
490 #[test]
491 fn test_insert_evicts_lru() {
492 let mut cache = LruHashMap::with_max_entries(2);
493 cache.insert("a", 1);
494 cache.insert("b", 2);
495 assert_eq!(cache.insert("c", 3), Some(("a", 1)));
496 assert_eq!(cache.get(&"a"), None);
497 assert_eq!(cache.get(&"b"), Some(&2));
498 assert_eq!(cache.get(&"c"), Some(&3));
499 }
500
501 #[test]
502 fn test_get_updates_lru_order() {
503 let mut cache = LruHashMap::with_max_entries(2);
504 cache.insert("a", 1);
505 cache.insert("b", 2);
506 assert_eq!(cache.get(&"a"), Some(&1)); // "a" is now most recently used
507 assert_eq!(cache.insert("c", 3), Some(("b", 2))); // "b" is evicted, not "a"
508 assert_eq!(cache.get(&"a"), Some(&1));
509 assert_eq!(cache.get(&"b"), None);
510 assert_eq!(cache.get(&"c"), Some(&3));
511 }
512
513 #[test]
514 fn test_remove() {
515 let mut cache = LruHashMap::with_max_entries(2);
516 cache.insert("a", 1);
517 cache.insert("b", 2);
518 assert_eq!(cache.remove(&"a"), Some(1));
519 assert_eq!(cache.remove(&"b"), Some(2));
520 assert_eq!(cache.remove(&"c"), None);
521 assert!(cache.is_empty());
522 }
523
524 #[test]
525 fn test_remove_lru() {
526 let mut cache = LruHashMap::with_max_entries(2);
527 cache.insert("a", 1);
528 cache.insert("b", 2);
529 assert_eq!(cache.pop_lru(), Some(("a", 1)));
530 assert_eq!(cache.len(), 1);
531 assert_eq!(cache.pop_lru(), Some(("b", 2)));
532 assert_eq!(cache.pop_lru(), None);
533 assert!(cache.is_empty());
534 }
535
536 #[test]
537 fn test_len_and_is_empty() {
538 let mut cache = LruHashMap::with_max_entries(2);
539 assert!(cache.is_empty());
540 cache.insert("a", 1);
541 assert!(!cache.is_empty());
542 assert_eq!(cache.len(), 1);
543 cache.insert("b", 2);
544 assert_eq!(cache.len(), 2);
545 cache.remove(&"a");
546 assert_eq!(cache.len(), 1);
547 cache.remove(&"b");
548 assert!(cache.is_empty());
549 }
550
551 #[test]
552 fn test_insert_updates_existing_key() {
553 let mut cache = LruHashMap::with_max_entries(2);
554 cache.insert("a", 1);
555 cache.insert("a", 2);
556 assert_eq!(cache.get(&"a"), Some(&2));
557 assert_eq!(cache.len(), 1);
558 }
559
560 #[test]
561 fn test_lru_order_with_multiple_operations() {
562 let mut cache = LruHashMap::with_max_entries(3);
563 cache.insert("a", 1);
564 cache.insert("b", 2);
565 cache.insert("c", 3);
566 assert_eq!(cache.get(&"a"), Some(&1)); // "a" is now most recently used
567 cache.insert("d", 4); // "b" should be evicted
568 assert_eq!(cache.get(&"a"), Some(&1));
569 assert_eq!(cache.get(&"b"), None);
570 assert_eq!(cache.get(&"c"), Some(&3));
571 assert_eq!(cache.get(&"d"), Some(&4));
572 }
573
574 #[test]
575 fn test_remove_lru_after_get() {
576 let mut cache = LruHashMap::with_max_entries(3);
577 cache.insert("a", 1);
578 cache.insert("b", 2);
579 cache.insert("c", 3);
580 assert_eq!(cache.get(&"a"), Some(&1)); // "a" is now most recently used
581 assert_eq!(cache.pop_lru(), Some(("b", 2))); // "b" is the LRU
582 assert_eq!(cache.len(), 2);
583 assert_eq!(cache.get(&"a"), Some(&1));
584 assert_eq!(cache.get(&"c"), Some(&3));
585 }
586
587 #[test]
588 fn test_iter_forward() {
589 let mut cache = LruHashMap::with_max_entries(3);
590 cache.insert("a", 1);
591 cache.insert("b", 2);
592 cache.insert("c", 3);
593
594 // Access "a" to make it the most recently used
595 assert_eq!(cache.get(&"a"), Some(&1));
596
597 let mut iter = cache.items();
598 // Should iterate from most recently used ("a") to least recently used ("b")
599 assert_eq!(iter.next(), Some((Rc::new("a"), &1)));
600 assert_eq!(iter.next(), Some((Rc::new("c"), &3)));
601 assert_eq!(iter.next(), Some((Rc::new("b"), &2)));
602 assert_eq!(iter.next(), None);
603 }
604
605 #[test]
606 fn test_iter_backward() {
607 let mut cache = LruHashMap::with_max_entries(3);
608 cache.insert("a", 1);
609 cache.insert("b", 2);
610 cache.insert("c", 3);
611
612 // Access "a" to make it the most recently used
613 assert_eq!(cache.get(&"a"), Some(&1));
614
615 let mut iter = cache.items();
616 // Should iterate backward from least recently used ("b") to most recently used ("a")
617 assert_eq!(iter.next_back(), Some((Rc::new("b"), &2)));
618 assert_eq!(iter.next_back(), Some((Rc::new("c"), &3)));
619 assert_eq!(iter.next_back(), Some((Rc::new("a"), &1)));
620 assert_eq!(iter.next_back(), None);
621 }
622
623 #[test]
624 fn test_iter_mixed_direction() {
625 let mut cache = LruHashMap::with_max_entries(3);
626 cache.insert("a", 1);
627 cache.insert("b", 2);
628 cache.insert("c", 3);
629
630 // Access "a" to make it the most recently used
631 assert_eq!(cache.get(&"a"), Some(&1));
632
633 let mut iter = cache.items();
634 // Forward
635 assert_eq!(iter.next(), Some((Rc::new("a"), &1)));
636 // Backward
637 assert_eq!(iter.next_back(), Some((Rc::new("b"), &2)));
638 // Forward again
639 assert_eq!(iter.next(), Some((Rc::new("c"), &3)));
640 assert_eq!(iter.next(), None);
641 assert_eq!(iter.next_back(), None);
642 }
643
644 #[test]
645 fn test_keys_iter_forward() {
646 let mut cache = LruHashMap::with_max_entries(3);
647 cache.insert("a", 1);
648 cache.insert("b", 2);
649 cache.insert("c", 3);
650
651 // Access "a" to make it the most recently used
652 assert_eq!(cache.get(&"a"), Some(&1));
653
654 let mut keys = cache.keys();
655 assert_eq!(keys.next(), Some(Rc::new("a")));
656 assert_eq!(keys.next(), Some(Rc::new("c")));
657 assert_eq!(keys.next(), Some(Rc::new("b")));
658 assert_eq!(keys.next(), None);
659 }
660
661 #[test]
662 fn test_keys_iter_backward() {
663 let mut cache = LruHashMap::with_max_entries(3);
664 cache.insert("a", 1);
665 cache.insert("b", 2);
666 cache.insert("c", 3);
667
668 // Access "a" to make it the most recently used
669 assert_eq!(cache.get(&"a"), Some(&1));
670
671 let mut keys = cache.keys();
672 assert_eq!(keys.next_back(), Some(Rc::new("b")));
673 assert_eq!(keys.next_back(), Some(Rc::new("c")));
674 assert_eq!(keys.next_back(), Some(Rc::new("a")));
675 assert_eq!(keys.next_back(), None);
676 }
677
678 #[test]
679 fn test_values_iter_forward() {
680 let mut cache = LruHashMap::with_max_entries(3);
681 cache.insert("a", 1);
682 cache.insert("b", 2);
683 cache.insert("c", 3);
684
685 // Access "a" to make it the most recently used
686 assert_eq!(cache.get(&"a"), Some(&1));
687
688 let mut values = cache.values();
689 assert_eq!(values.next(), Some(&1));
690 assert_eq!(values.next(), Some(&3));
691 assert_eq!(values.next(), Some(&2));
692 assert_eq!(values.next(), None);
693 }
694
695 #[test]
696 fn test_values_iter_backward() {
697 let mut cache = LruHashMap::with_max_entries(3);
698 cache.insert("a", 1);
699 cache.insert("b", 2);
700 cache.insert("c", 3);
701
702 // Access "a" to make it the most recently used
703 assert_eq!(cache.get(&"a"), Some(&1));
704
705 let mut values = cache.values();
706 assert_eq!(values.next_back(), Some(&2));
707 assert_eq!(values.next_back(), Some(&3));
708 assert_eq!(values.next_back(), Some(&1));
709 assert_eq!(values.next_back(), None);
710 }
711
712 #[test]
713 fn test_empty_iter() {
714 let cache: LruHashMap<&str, i32> = LruHashMap::with_max_entries(3);
715 let mut iter = cache.items();
716 assert_eq!(iter.next(), None);
717 assert_eq!(iter.next_back(), None);
718 }
719}