generational_lru/
lib.rs

1//! Crate providing a 100% safe, generational arena based LRUCache implementation.
2//!
3//! Usage:
4//! ```
5//! use generational_lru::lrucache::{LRUCache, CacheError};
6//!
7//! let capacity = 5;
8//!
9//! let mut lru_cache = LRUCache::<i32, i32>::with_capacity(capacity);
10//! assert_eq!(lru_cache.query(&0), Err(CacheError::CacheMiss));
11//!
12//! for ele in 0..capacity {
13//!     let x = ele as i32;
14//!     assert!(lru_cache.insert(x, x).is_ok());
15//! }
16//!
17//! for ele in 0..capacity {
18//!     let x = ele as i32;
19//!     assert_eq!(lru_cache.query(&x), Ok(&x));
20//! }
21//!
22//! let x = capacity as i32;
23//! assert!(lru_cache.insert(x, x).is_ok());
24//!
25//! assert_eq!(lru_cache.query(&x), Ok(&x));
26//!
27//! assert_eq!(lru_cache.query(&0), Err(CacheError::CacheMiss));
28//!
29//! let x = capacity as i32 / 2;
30//! assert_eq!(lru_cache.remove(&x), Ok(x));
31//!
32//! assert_eq!(lru_cache.query(&x), Err(CacheError::CacheMiss));
33//! assert_eq!(lru_cache.remove(&x), Err(CacheError::CacheMiss));
34//!
35//! // zero capacity LRUCache is unusable
36//! let mut lru_cache = LRUCache::<i32, i32>::with_capacity(0);
37//!
38//! assert!(matches!(
39//!     lru_cache.insert(0, 0),
40//!     Err(CacheError::CacheBroken(_))
41//! ));
42//!
43//! ```
44
45#[forbid(unsafe_code)]
46
47pub mod arena {
48    //! Module providing a generational arena based off a vector.
49    //!
50    //! Usage:
51    //! ```
52    //! use generational_lru::arena::Arena;
53    //!
54    //! let mut arena = Arena::<i32>::with_capacity(10); // create arena
55    //! let index = arena.insert(78).unwrap(); // allocate new element in arena
56    //! let i_ref = arena.get(&index);
57    //! assert_eq!(i_ref, Some(&78));
58    //! let i_m_ref = arena.get_mut(&index).unwrap();
59    //! *i_m_ref = -68418; // this close from greatness
60    //! assert_eq!(arena.get(&index), Some(&-68418));
61    //!
62    //! arena.remove(&index).unwrap();
63    //!
64    //! assert!(arena.get(&index).is_none());
65    //! ```
66
67    use std::fmt::Display;
68
69    /// Index in vector to allocated entry. Used to access items allocated in
70    /// the arena.
71    #[derive(Debug, PartialEq, Clone, Copy)]
72    pub struct Index {
73        pub idx: usize,
74        pub generation: u64,
75    }
76
77    /// Entry represents an arena allocation entry. It is used to track free
78    /// and Occupied blocks along with generation counters for Occupied
79    /// blocks.
80    #[derive(Debug, PartialEq)]
81    pub enum Entry<T> {
82        Free { next_free: Option<usize> },
83        Occupied { value: T, generation: u64 },
84    }
85
86    /// A generational arena for allocating memory based off a vector. Every
87    /// entry is associated with a generation counter to uniquely identify
88    /// newer allocations from older reclaimed allocations at the same
89    /// position in the vector.
90    /// This is inspired from the crate
91    /// ["generational-arena"](https://docs.rs/generational-arena)
92    pub struct Arena<T> {
93        items: Vec<Entry<T>>,
94        capacity: usize,
95
96        generation: u64,
97
98        free_list_head: Option<usize>,
99    }
100
101    /// Arena out of memory error.
102    #[derive(Debug, Clone, PartialEq)]
103    pub struct ArenaOOM;
104
105    impl Display for ArenaOOM {
106        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
107            write!(f, "Arena out of memory.")
108        }
109    }
110
111    impl<T> Default for Arena<T> {
112        fn default() -> Self {
113            Self::new()
114        }
115    }
116
117    impl<T> Arena<T> {
118        pub fn new() -> Self {
119            Arena {
120                items: Vec::new(),
121                capacity: 0,
122                generation: 0,
123                free_list_head: None,
124            }
125        }
126
127        pub fn capacity(&self) -> usize {
128            self.capacity
129        }
130
131        pub fn reserve(&mut self, capacity: usize) {
132            self.items.reserve_exact(capacity);
133            let start = self.items.len();
134            let end = start + capacity;
135            let old_free = self.free_list_head;
136            self.items.extend((start..end).map(|i| {
137                if i == end - 1 {
138                    Entry::Free {
139                        next_free: old_free,
140                    }
141                } else {
142                    Entry::Free {
143                        next_free: Some(i + 1),
144                    }
145                }
146            }));
147            self.free_list_head = Some(start);
148            self.capacity += capacity;
149        }
150
151        pub fn with_capacity(capacity: usize) -> Self {
152            let mut arena = Self::new();
153            arena.reserve(capacity);
154            arena
155        }
156
157        pub fn insert(&mut self, item: T) -> Result<Index, ArenaOOM> {
158            if self.free_list_head.is_none() {
159                return Err(ArenaOOM {});
160            }
161
162            let old_free = self.free_list_head;
163            if let Entry::Free { next_free } = self.items[old_free.unwrap()] {
164                self.free_list_head = next_free;
165            } else {
166                return Err(ArenaOOM {});
167            }
168
169            let entry = Entry::Occupied {
170                value: item,
171                generation: self.generation,
172            };
173            self.items[old_free.unwrap()] = entry;
174            self.generation += 1;
175
176            Ok(Index {
177                idx: old_free.unwrap(),
178                generation: self.generation - 1,
179            })
180        }
181
182        pub fn remove(&mut self, index: &Index) -> Option<T> {
183            if let Some(Entry::Occupied {
184                value: _,
185                generation,
186            }) = self.items.get(index.idx)
187            {
188                if &index.generation != generation {
189                    return None;
190                }
191
192                let entry = Entry::<T>::Free {
193                    next_free: self.free_list_head,
194                };
195
196                let old_entry = core::mem::replace(&mut self.items[index.idx], entry);
197
198                self.free_list_head = Some(index.idx);
199
200                if let Entry::Occupied {
201                    value,
202                    generation: _,
203                } = old_entry
204                {
205                    return Some(value);
206                }
207            }
208
209            None
210        }
211
212        pub fn get_mut(&mut self, index: &Index) -> Option<&mut T> {
213            if let Some(Entry::Occupied { value, generation }) = self.items.get_mut(index.idx) {
214                if &index.generation == generation {
215                    return Some(value);
216                }
217            }
218
219            None
220        }
221
222        pub fn get(&self, index: &Index) -> Option<&T> {
223            if let Some(Entry::Occupied { value, generation }) = self.items.get(index.idx) {
224                if &index.generation == generation {
225                    return Some(value);
226                }
227            }
228
229            None
230        }
231    }
232
233    #[cfg(test)]
234    mod tests {
235        use super::*;
236
237        #[test]
238        fn arena_new() {
239            Arena::<i32>::new();
240        }
241
242        #[test]
243        fn arena_with_capacity() {
244            let capacity = 100;
245            let arena = Arena::<i32>::with_capacity(capacity);
246            assert_eq!(arena.capacity(), capacity);
247
248            assert_eq!(arena.free_list_head, Some(0));
249            let mut i = 0;
250            for entry in &arena.items {
251                if i == capacity - 1 {
252                    assert_eq!(entry, &Entry::Free { next_free: None })
253                } else {
254                    assert_eq!(
255                        entry,
256                        &Entry::Free {
257                            next_free: Some(i + 1)
258                        }
259                    )
260                }
261
262                i += 1;
263            }
264        }
265
266        #[test]
267        fn arena_insert() {
268            let mut arena = Arena::<i32>::new();
269            assert_eq!(arena.insert(0), Err(ArenaOOM {}));
270
271            arena.reserve(1);
272            let index_0 = arena.insert(0);
273            assert_eq!(
274                index_0,
275                Ok(Index {
276                    idx: 0,
277                    generation: 0
278                })
279            );
280
281            arena.reserve(1);
282            let index_1 = arena.insert(1);
283            assert_eq!(
284                index_1,
285                Ok(Index {
286                    idx: 1,
287                    generation: 1
288                })
289            );
290
291            let index_0_val = index_0.unwrap();
292            let item_0 = arena.get(&index_0_val);
293            assert_eq!(item_0, Some(&0));
294
295            let index_1_val = index_1.unwrap();
296            let item_1 = arena.get(&index_1_val);
297            assert_eq!(item_1, Some(&1));
298
299            let item_0 = arena.get_mut(&index_0_val);
300            assert_eq!(item_0, Some(&mut 0));
301            let item_0 = item_0.unwrap();
302            *item_0 = 25;
303
304            let item_0 = arena.get(&index_0_val);
305            assert_eq!(item_0, Some(&25));
306
307            let item_1 = arena.get_mut(&index_1_val);
308            assert_eq!(item_1, Some(&mut 1));
309            let item_1 = item_1.unwrap();
310            *item_1 = -78;
311
312            let item_1 = arena.get(&index_1_val);
313            assert_eq!(item_1, Some(&-78));
314
315            assert_eq!(arena.capacity(), 2);
316            assert_eq!(arena.insert(0), Err(ArenaOOM {}));
317
318            let old_cap = arena.capacity();
319            let to_reserve = 100;
320            arena.reserve(to_reserve);
321            for ele in 0..to_reserve {
322                assert_eq!(
323                    arena.insert(0),
324                    Ok(Index {
325                        idx: old_cap + ele,
326                        generation: (old_cap + ele) as u64
327                    })
328                )
329            }
330            assert_eq!(arena.capacity(), old_cap + to_reserve);
331            assert_eq!(arena.insert(0), Err(ArenaOOM {}));
332        }
333
334        #[test]
335        fn arena_remove() {
336            let mut arena = Arena::<i32>::with_capacity(1);
337
338            let index = arena.insert(0).unwrap();
339            assert_eq!(arena.get(&index), Some(&0));
340
341            assert_eq!(arena.remove(&index).unwrap(), 0);
342
343            assert_eq!(arena.get(&index), None);
344
345            let index = arena.insert(56).unwrap();
346            assert_eq!(
347                index,
348                Index {
349                    idx: 0,
350                    generation: 1
351                }
352            );
353
354            assert_eq!(arena.remove(&index).unwrap(), 56);
355            assert!(arena.remove(&index).is_none());
356
357            let current_gen = 2;
358
359            let to_reserve = 5;
360            arena.reserve(to_reserve);
361            for ele in 0..to_reserve + 1 {
362                // free list head moves forward. list circles back to start
363                if ele == to_reserve {
364                    assert_eq!(
365                        arena.insert(0),
366                        Ok(Index {
367                            idx: 0,
368                            generation: (current_gen + ele) as u64
369                        })
370                    )
371                } else {
372                    assert_eq!(
373                        arena.insert(0),
374                        Ok(Index {
375                            idx: ele + 1,
376                            generation: (current_gen + ele) as u64
377                        })
378                    )
379                }
380            }
381        }
382    }
383}
384
385pub mod list {
386    //! Module providing a doubly linked list based deque implementation using a
387    //! generational arena.
388    //!
389    //! Usage:
390    //! ```
391    //! use generational_lru::list::*;
392    //!
393    //! let capacity = 10;
394    //! let mut list = LinkedList::<i32>::with_capacity(capacity);
395    //! for ele in 0..capacity {
396    //!     assert!(list.push_back(ele as i32).is_ok());
397    //! }
398    //!
399    //! let mut i = 0;
400    //! for ele in list.iter() {
401    //!     assert_eq!(ele, &i);
402    //!     i += 1;
403    //! }
404    //!
405    //! let capacity = 10;
406    //!
407    //! let mut list = LinkedList::<i32>::with_capacity(capacity);
408    //! assert_eq!(list.pop_front(), Err(ListError::ListEmpty));
409    //!
410    //! for ele in 0..capacity {
411    //!     assert!(list.push_back(ele as i32).is_ok());
412    //! }
413    //!
414    //! for ele in 0..capacity {
415    //!     assert_eq!(list.pop_front().unwrap(), ele as i32);
416    //! }
417    //!
418    //! assert!(list.is_empty());
419    //! assert_eq!(list.pop_front(), Err(ListError::ListEmpty));
420    //!
421    //! ```
422
423    use std::fmt::Display;
424
425    use crate::arena::{Arena, ArenaOOM, Index};
426
427    /// Analogous to a pointer to a Node for our generational arena list. A link
428    /// uniquely refers to a node in our linked list.
429    #[derive(Debug, Clone, Copy, PartialEq)]
430    pub struct Link {
431        pub index: Index,
432    }
433
434    /// A Node in our linked list. It uses `Option<Link>` to point to other nodes.
435    pub struct Node<T> {
436        pub value: T,
437        pub next: Option<Link>,
438        pub prev: Option<Link>,
439    }
440
441    /// A generational arena based doubly linked list implementation.
442    pub struct LinkedList<T> {
443        arena: Arena<Node<T>>,
444
445        head: Option<Link>,
446        tail: Option<Link>,
447
448        len: usize,
449    }
450
451    /// Iterator for our LinkedList.
452    pub struct Iter<'a, T: 'a> {
453        list: &'a LinkedList<T>,
454        current: Option<Link>,
455    }
456
457    #[derive(Debug, Clone, PartialEq)]
458    pub enum ListError {
459        LinkBroken,
460        ListOOM(ArenaOOM),
461        ListEmpty,
462    }
463
464    impl Display for ListError {
465        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
466            match &self {
467                ListError::LinkBroken => write!(f, "Link does not point to a valid location."),
468                ListError::ListOOM(arena_oom) => {
469                    write!(f, "List out of memory: ")?;
470                    arena_oom.fmt(f)
471                }
472                ListError::ListEmpty => write!(f, "List is empty."),
473            }
474        }
475    }
476
477    impl<T> Default for LinkedList<T> {
478        fn default() -> Self {
479            Self::new()
480        }
481    }
482
483    impl<T> LinkedList<T> {
484        pub fn new() -> Self {
485            LinkedList {
486                arena: Arena::new(),
487                head: None,
488                tail: None,
489                len: 0,
490            }
491        }
492
493        pub fn with_capacity(capacity: usize) -> Self {
494            LinkedList {
495                arena: Arena::with_capacity(capacity),
496                head: None,
497                tail: None,
498                len: 0,
499            }
500        }
501
502        pub fn len(&self) -> usize {
503            self.len
504        }
505
506        pub fn is_empty(&self) -> bool {
507            self.head.is_none()
508        }
509
510        pub fn is_full(&self) -> bool {
511            self.len == self.arena.capacity()
512        }
513
514        pub fn reserve(&mut self, capacity: usize) {
515            self.arena.reserve(capacity)
516        }
517
518        pub fn get_mut(&mut self, link: &Link) -> Result<&mut Node<T>, ListError> {
519            let node = self
520                .arena
521                .get_mut(&link.index)
522                .ok_or(ListError::LinkBroken)?;
523            Ok(node)
524        }
525
526        pub fn get_mut_value(&mut self, link: &Link) -> Result<&mut T, ListError> {
527            let node = self.get_mut(link)?;
528            Ok(&mut node.value)
529        }
530
531        pub fn get(&self, link: &Link) -> Result<&Node<T>, ListError> {
532            let node = self.arena.get(&link.index).ok_or(ListError::LinkBroken)?;
533            Ok(node)
534        }
535
536        pub fn push_front(&mut self, value: T) -> Result<Link, ListError> {
537            let node = Node {
538                value,
539                next: self.head,
540                prev: None,
541            };
542
543            let index = self.arena.insert(node).map_err(ListError::ListOOM)?;
544            let link = Link { index };
545            if let Some(head) = self.head {
546                let head_node = self.get_mut(&head)?;
547                head_node.prev = Some(link);
548            } else {
549                self.tail = Some(link);
550            }
551
552            self.head = Some(link);
553
554            self.len += 1;
555            Ok(link)
556        }
557
558        pub fn push_back(&mut self, value: T) -> Result<Link, ListError> {
559            let node = Node {
560                value,
561                next: None,
562                prev: self.tail,
563            };
564
565            let index = self.arena.insert(node).map_err(ListError::ListOOM)?;
566            let link = Link { index };
567            if let Some(tail) = self.tail {
568                let tail_node = self.get_mut(&tail)?;
569                tail_node.next = Some(link);
570            } else {
571                self.head = Some(link)
572            }
573
574            self.tail = Some(link);
575
576            self.len += 1;
577            Ok(link)
578        }
579
580        pub fn head(&self) -> Option<Link> {
581            self.head
582        }
583
584        pub fn tail(&self) -> Option<Link> {
585            self.tail
586        }
587
588        pub fn peek_front(&self) -> Result<&T, ListError> {
589            let head_link = self.head.ok_or(ListError::ListEmpty)?;
590            return self.get(&head_link).map(|x| &x.value);
591        }
592
593        pub fn peek_back(&self) -> Result<&T, ListError> {
594            let tail_link = self.tail.ok_or(ListError::ListEmpty)?;
595            return self.get(&tail_link).map(|x| &x.value);
596        }
597
598        pub fn pop_front(&mut self) -> Result<T, ListError> {
599            let head_link = self.head.ok_or(ListError::ListEmpty)?;
600            let node = self
601                .arena
602                .remove(&head_link.index)
603                .ok_or(ListError::LinkBroken)?;
604
605            self.head = node.next;
606
607            if let Some(link) = self.head {
608                let cur_head_node = self.get_mut(&link)?;
609                cur_head_node.prev = None;
610            } else {
611                self.tail = None;
612            }
613
614            self.len -= 1;
615            Ok(node.value)
616        }
617
618        pub fn pop_back(&mut self) -> Result<T, ListError> {
619            let tail_link = self.tail.ok_or(ListError::ListEmpty)?;
620            let node = self
621                .arena
622                .remove(&tail_link.index)
623                .ok_or(ListError::LinkBroken)?;
624
625            self.tail = node.prev;
626            if let Some(link) = self.tail {
627                let cur_tail_node = self.get_mut(&link)?;
628                cur_tail_node.next = None;
629            } else {
630                self.head = None;
631            }
632
633            self.len -= 1;
634            Ok(node.value)
635        }
636
637        pub fn remove(&mut self, link: &Link) -> Result<T, ListError> {
638            let head = self.head.ok_or(ListError::ListEmpty)?;
639            let tail = self.tail.ok_or(ListError::ListEmpty)?;
640
641            if link == &head {
642                return self.pop_front();
643            }
644
645            if link == &tail {
646                return self.pop_back();
647            }
648
649            let node = self
650                .arena
651                .remove(&link.index)
652                .ok_or(ListError::LinkBroken)?;
653            let prev_link = node.prev.ok_or(ListError::LinkBroken)?;
654            let next_link = node.next.ok_or(ListError::LinkBroken)?;
655
656            let prev = self.get_mut(&prev_link)?;
657            prev.next = Some(next_link);
658
659            let next = self.get_mut(&next_link)?;
660            next.prev = Some(prev_link);
661
662            self.len -= 1;
663            Ok(node.value)
664        }
665
666        /// Re-arranges the nodes in the linked list to make the node pointed to by the
667        /// given Link the tail node.
668        pub fn reposition_to_tail(&mut self, link: &Link) -> Result<(), ListError> {
669            let head = self.head.ok_or(ListError::ListEmpty)?;
670            let tail = self.tail.ok_or(ListError::ListEmpty)?;
671
672            if link == &tail {
673                return Ok(());
674            }
675
676            // list has >= 2 nodes
677
678            let head_node = self.get_mut(&head)?;
679            if link == &head {
680                self.head = head_node.next;
681            }
682
683            let node = self.get_mut(link)?;
684
685            let prev_link = node.prev;
686            let next_link = node.next;
687
688            node.prev = Some(tail);
689            node.next = None;
690
691            if let Some(link) = prev_link {
692                let prev = self.get_mut(&link)?;
693                prev.next = next_link;
694            }
695
696            if let Some(link) = next_link {
697                let next = self.get_mut(&link)?;
698                next.prev = prev_link;
699            }
700
701            let tail_node = self.get_mut(&tail)?;
702            tail_node.next = Some(*link);
703            self.tail = Some(*link);
704
705            Ok(())
706        }
707
708        pub fn iter(&self) -> Iter<T> {
709            Iter {
710                list: self,
711                current: self.head(),
712            }
713        }
714    }
715
716    impl<'a, T: 'a> Iterator for Iter<'a, T> {
717        type Item = &'a T;
718
719        fn next(&mut self) -> Option<Self::Item> {
720            if let Some(link) = self.current {
721                if let Ok(node) = self.list.get(&link) {
722                    self.current = node.next;
723                    return Some(&node.value);
724                }
725            }
726
727            None
728        }
729    }
730
731    #[cfg(test)]
732    mod tests {
733        use super::*;
734
735        #[test]
736        fn list_new() {
737            let mut list = LinkedList::<i32>::new();
738            assert!(list.is_empty());
739            assert!(list.is_full());
740
741            assert_eq!(list.peek_front(), Err(ListError::ListEmpty));
742            assert_eq!(list.peek_back(), Err(ListError::ListEmpty));
743
744            assert_eq!(list.push_back(0), Err(ListError::ListOOM(ArenaOOM {})));
745        }
746
747        #[test]
748        fn list_with_capacity() {
749            let capacity = 5;
750            let mut list = LinkedList::<i32>::with_capacity(capacity);
751            assert!(list.is_empty());
752            for _ in 0..capacity {
753                assert!(list.push_back(0).is_ok())
754            }
755            assert!(list.is_full());
756            assert_eq!(list.push_back(0), Err(ListError::ListOOM(ArenaOOM {})));
757        }
758
759        #[test]
760        fn list_push_back() {
761            let capacity = 10;
762            let mut list = LinkedList::<i32>::with_capacity(capacity);
763            for ele in 0..capacity {
764                assert!(list.push_back(ele as i32).is_ok());
765            }
766
767            let mut i = 0;
768            for ele in list.iter() {
769                assert_eq!(ele, &i);
770                i += 1;
771            }
772        }
773
774        #[test]
775        fn list_push_front() {
776            let capacity = 10;
777            let mut list = LinkedList::<i32>::with_capacity(capacity);
778            for ele in 0..capacity {
779                assert!(list.push_front(ele as i32).is_ok());
780            }
781
782            let mut i = capacity as i32 - 1;
783            for ele in list.iter() {
784                assert_eq!(ele, &i);
785                i -= 1;
786            }
787        }
788
789        #[test]
790        fn list_pop_front() {
791            let capacity = 10;
792            let mut list = LinkedList::<i32>::with_capacity(capacity);
793
794            assert_eq!(list.pop_front(), Err(ListError::ListEmpty));
795
796            for ele in 0..capacity {
797                assert!(list.push_back(ele as i32).is_ok());
798            }
799
800            for ele in 0..capacity {
801                assert_eq!(list.pop_front().unwrap(), ele as i32);
802            }
803
804            assert!(list.is_empty());
805            assert_eq!(list.pop_front(), Err(ListError::ListEmpty));
806        }
807
808        #[test]
809        fn list_pop_back() {
810            let capacity = 10;
811            let mut list = LinkedList::<i32>::with_capacity(capacity);
812
813            assert_eq!(list.pop_back(), Err(ListError::ListEmpty));
814
815            for ele in 0..capacity {
816                assert!(list.push_front(ele as i32).is_ok());
817            }
818
819            for ele in 0..capacity {
820                assert_eq!(list.pop_back().unwrap(), ele as i32);
821            }
822
823            assert!(list.is_empty());
824            assert_eq!(list.pop_back(), Err(ListError::ListEmpty));
825        }
826
827        #[test]
828        fn list_remove() {
829            let mut list = LinkedList::<i32>::with_capacity(5);
830            assert!(list.is_empty());
831
832            let link_0 = list.push_back(0).unwrap();
833            let _link_1 = list.push_back(1).unwrap();
834            let link_2 = list.push_back(2).unwrap();
835            let _link_3 = list.push_back(3).unwrap();
836            let link_4 = list.push_back(4).unwrap();
837
838            assert!(list.is_full());
839
840            assert_eq!(list.peek_front().unwrap(), &0);
841            assert_eq!(list.peek_back().unwrap(), &4);
842
843            assert!(list.remove(&link_0).is_ok());
844            assert_eq!(list.len(), 4);
845
846            assert_eq!(list.peek_front().unwrap(), &1);
847            assert_eq!(list.peek_back().unwrap(), &4);
848
849            assert!(list.remove(&link_4).is_ok());
850            assert_eq!(list.len(), 3);
851
852            assert_eq!(list.peek_front().unwrap(), &1);
853            assert_eq!(list.peek_back().unwrap(), &3);
854
855            assert!(list.remove(&link_2).is_ok());
856            assert_eq!(list.len(), 2);
857
858            assert!(list.iter().eq([1, 3].iter()));
859        }
860
861        #[test]
862        fn list_reposition_to_tail() {
863            let capacity = 5;
864
865            let mut list = LinkedList::<i32>::with_capacity(capacity);
866            assert!(list.is_empty());
867
868            for ele in 0..capacity {
869                list.push_back(ele as i32).unwrap();
870            }
871
872            for _ in 0..(capacity / 2) {
873                list.reposition_to_tail(&list.head().unwrap()).unwrap();
874            }
875
876            let mut i = 0;
877            let mut lh = 0 as i32;
878            let mut rh = capacity as i32 / 2;
879            for ele in list.iter() {
880                if i <= (capacity / 2) {
881                    assert_eq!(ele, &rh);
882                    rh += 1;
883                } else {
884                    assert_eq!(ele, &lh);
885                    lh += 1;
886                }
887                i += 1
888            }
889
890            let mut list = LinkedList::<i32>::with_capacity(2);
891            let link_0 = list.push_back(0).unwrap();
892            list.reposition_to_tail(&link_0).unwrap();
893            assert_eq!(Some(link_0), list.head());
894            assert_eq!(Some(link_0), list.tail());
895
896            let link_1 = list.push_back(1).unwrap();
897
898            list.reposition_to_tail(&link_0).unwrap();
899            assert_eq!(list.get_mut_value(&link_0), Ok(&mut 0));
900
901            assert_eq!(list.head(), Some(link_1));
902            assert_eq!(list.tail(), Some(link_0));
903
904            list.reserve(1);
905            list.push_back(2).unwrap();
906            list.reposition_to_tail(&link_0).unwrap();
907
908            assert!(list.iter().eq([1, 2, 0].iter()));
909        }
910    }
911}
912
913pub mod lrucache {
914    //! Module providing a Least-Recently-Used (LRU) Cache implementation.
915    //!
916    //! Usage:
917    //! ```
918    //! use generational_lru::lrucache::{LRUCache, CacheError};
919    //!
920    //! let capacity = 5;
921    //!
922    //! let mut lru_cache = LRUCache::<i32, i32>::with_capacity(capacity);
923    //! assert_eq!(lru_cache.query(&0), Err(CacheError::CacheMiss));
924    //!
925    //! for ele in 0..capacity {
926    //!     let x = ele as i32;
927    //!     assert!(lru_cache.insert(x, x).is_ok());
928    //! }
929    //!
930    //! for ele in 0..capacity {
931    //!     let x = ele as i32;
932    //!     assert_eq!(lru_cache.query(&x), Ok(&x));
933    //! }
934    //!
935    //! let x = capacity as i32;
936    //! assert!(lru_cache.insert(x, x).is_ok());
937    //!
938    //! assert_eq!(lru_cache.query(&x), Ok(&x));
939    //!
940    //! assert_eq!(lru_cache.query(&0), Err(CacheError::CacheMiss));
941    //!
942    //! let x = capacity as i32 / 2;
943    //! assert_eq!(lru_cache.remove(&x), Ok(x));
944    //!
945    //! assert_eq!(lru_cache.query(&x), Err(CacheError::CacheMiss));
946    //! assert_eq!(lru_cache.remove(&x), Err(CacheError::CacheMiss));
947    //!
948    //! // zero capacity LRUCache is unusable
949    //! let mut lru_cache = LRUCache::<i32, i32>::with_capacity(0);
950    //!
951    //! assert!(matches!(
952    //!     lru_cache.insert(0, 0),
953    //!     Err(CacheError::CacheBroken(_))
954    //! ));
955    //!
956    //! ```
957
958    use crate::list::{Link, LinkedList, ListError};
959    use std::{collections::HashMap, fmt::Display, hash::Hash};
960
961    /// Cache block storing some key and value.
962    pub struct Block<K, V> {
963        pub key: K,
964        pub value: V,
965    }
966
967    /// A Least-Recently-Used (LRU) Cache implemented using a generational arena
968    /// based linked list and a hash map.
969    pub struct LRUCache<K, V>
970    where
971        K: Eq + Hash,
972    {
973        blocks: LinkedList<Block<K, V>>,
974        block_refs: HashMap<K, Link>,
975    }
976
977    #[derive(Debug, Clone, PartialEq)]
978    pub enum CacheError {
979        CacheBroken(ListError),
980        CacheMiss,
981    }
982
983    impl Display for CacheError {
984        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
985            match &self {
986                CacheError::CacheBroken(list_error) => {
987                    write!(f, "Cache storage is broken: ")?;
988                    list_error.fmt(f)
989                }
990                CacheError::CacheMiss => write!(f, "Key not found in cache."),
991            }
992        }
993    }
994
995    impl<K, V> LRUCache<K, V>
996    where
997        K: Eq + Hash + Copy,
998    {
999        /// Creates an LRUCache instance with the given capacity. A zero capacity LRUCache is
1000        /// unusable.
1001        pub fn with_capacity(capacity: usize) -> Self {
1002            LRUCache {
1003                blocks: LinkedList::with_capacity(capacity),
1004                block_refs: HashMap::new(),
1005            }
1006        }
1007
1008        /// Returns a reference to the value associated with the given key. If the key is not
1009        /// present in the cache, we return a "cache-miss" error. If the entry is found but
1010        /// cannot be fetched from the underlying storage, we return a "cache-broken" error.
1011        pub fn query(&mut self, key: &K) -> Result<&V, CacheError> {
1012            let link = self.block_refs.get(key).ok_or(CacheError::CacheMiss)?;
1013            self.blocks
1014                .reposition_to_tail(link)
1015                .map_err(CacheError::CacheBroken)?;
1016            let node = self.blocks.get(link).map_err(CacheError::CacheBroken)?;
1017            Ok(&node.value.value)
1018        }
1019
1020        /// Removes the associated key value pair for the given key from this cache. If no
1021        /// entry is found, we return a "cache-miss" error. If the entry is found but cannot
1022        /// be fetched from the underlying in-memory storage, we return a "cache-broken" error.
1023        /// Returns the value associated, after removal with ownership.
1024        pub fn remove(&mut self, key: &K) -> Result<V, CacheError> {
1025            let link = self.block_refs.remove(key).ok_or(CacheError::CacheMiss)?;
1026            let block = self.blocks.remove(&link).map_err(CacheError::CacheBroken)?;
1027            Ok(block.value)
1028        }
1029
1030        /// Inserts a new key value pair into this cache. If this cache is full, the least
1031        /// recently used entry is removed.
1032        pub fn insert(&mut self, key: K, value: V) -> Result<(), CacheError> {
1033            if let Some(link) = self.block_refs.get(&key) {
1034                self.blocks
1035                    .reposition_to_tail(link)
1036                    .map_err(CacheError::CacheBroken)?;
1037                let block_ref = self
1038                    .blocks
1039                    .get_mut_value(link)
1040                    .map_err(CacheError::CacheBroken)?;
1041                block_ref.value = value;
1042                return Ok(());
1043            }
1044
1045            if self.blocks.is_full() {
1046                let block = self.blocks.pop_front().map_err(CacheError::CacheBroken)?;
1047                self.block_refs.remove(&block.key);
1048            }
1049
1050            let link = self
1051                .blocks
1052                .push_back(Block { key, value })
1053                .map_err(CacheError::CacheBroken)?;
1054            self.block_refs.insert(key, link);
1055
1056            Ok(())
1057        }
1058    }
1059
1060    #[cfg(test)]
1061    mod tests {
1062        use super::*;
1063
1064        #[test]
1065        fn lru_cache_consistency() {
1066            let mut lru_cache = LRUCache::<i32, i32>::with_capacity(0);
1067            assert_eq!(
1068                lru_cache.insert(0, 0),
1069                Err(CacheError::CacheBroken(ListError::ListEmpty))
1070            );
1071
1072            let mut lru_cache = LRUCache::<i32, i32>::with_capacity(2);
1073            assert!(lru_cache.insert(1, 1).is_ok());
1074            assert!(lru_cache.insert(2, 2).is_ok());
1075            assert_eq!(lru_cache.query(&1), Ok(&1));
1076            assert!(lru_cache.insert(3, 3).is_ok());
1077            assert_eq!(lru_cache.query(&2), Err(CacheError::CacheMiss));
1078            assert!(lru_cache.insert(1, -1).is_ok());
1079            assert_eq!(lru_cache.query(&1), Ok(&-1));
1080            assert!(lru_cache.insert(4, 4).is_ok());
1081            assert_eq!(lru_cache.query(&3), Err(CacheError::CacheMiss));
1082
1083            let capacity = 5;
1084
1085            let mut lru_cache = LRUCache::<i32, i32>::with_capacity(capacity);
1086            assert_eq!(lru_cache.query(&0), Err(CacheError::CacheMiss));
1087
1088            for ele in 0..capacity {
1089                let x = ele as i32;
1090                assert!(lru_cache.insert(x, x).is_ok());
1091            }
1092
1093            for ele in 0..capacity {
1094                let x = ele as i32;
1095                assert_eq!(lru_cache.query(&x), Ok(&x));
1096            }
1097
1098            let x = capacity as i32;
1099            assert!(lru_cache.insert(x, x).is_ok());
1100
1101            assert_eq!(lru_cache.query(&x), Ok(&x));
1102
1103            assert_eq!(lru_cache.query(&0), Err(CacheError::CacheMiss));
1104
1105            let x = capacity as i32 / 2;
1106            assert_eq!(lru_cache.remove(&x), Ok(x));
1107
1108            assert_eq!(lru_cache.query(&x), Err(CacheError::CacheMiss));
1109            assert_eq!(lru_cache.remove(&x), Err(CacheError::CacheMiss));
1110        }
1111    }
1112}
generational_lru/lib.rs

generational_lru/
lib.rs
