7 releases
0.2.3 | Oct 18, 2024 |
---|---|
0.2.2 | Oct 18, 2024 |
0.2.1 | Sep 11, 2024 |
0.1.2 | Apr 11, 2024 |
#660 in Data structures
330 downloads per month
40KB
869 lines
lru-st
This crate provides a Vec based doubly linked list implementation. It also aims at providing data structures built on top of doubly linked list such as LRU HashMap.
Features
sync
: to enable whencollections
structures needs to be used in threads
Example: DoublyLinkedList
use lru_st::{dll, Cursor};
let mut dll = dll![1, 2, 3, 4];
assert_eq!(dll.len(), 4);
let c = dll.push_front(0);
// even though the element has been pushed
// at front (i.e. 0th position in the list)
// its [Cursor] is 4. This is because the
// Cursor is a reference to the item not
// related to its position in the list.
assert_eq!(c, Cursor(4));
// first element is 0
assert_eq!(dll.front(), Some(&0));
assert_eq!(dll.get(Cursor(4)), Some(&0));
// we move item with value 4 at front of
// the list
dll.move_front(Cursor(3)).unwrap();
assert_eq!(dll.get_nth(0), Some(&4));
assert_eq!(dll.get_nth(1), Some(&0));
// even if order of list items changed cursors
// are never affected by those changes
assert_eq!(dll.get(Cursor(4)), Some(&0));
Example: LRU HashMap
use lru_st::collections::LruHashMap;
let mut lru_map = LruHashMap::with_max_entries(10);
lru_map.insert(42, "test");
assert_eq!(lru_map.get(&42), Some("test").as_ref());
assert_eq!(lru_map.len(), 1);
// we fill the map entirely
for i in 0..lru_map.cap(){
lru_map.insert(i, "fill");
}
assert_eq!(lru_map.len(), 10);
// this element disapeared from the map as we filled
// all the map without fetching it
assert_eq!(lru_map.get(&42), None);
Example: LRU HashSet
use lru_st::collections::LruHashSet;
let mut lru_set = LruHashSet::with_max_entries(10);
assert_eq!(lru_set.insert("test"), true);
assert_eq!(lru_set.insert("test"), false);
assert_eq!(lru_set.contains(&"test"), true);
// we remove one element
assert_eq!(lru_set.remove(&"test"), true);
assert_eq!(lru_set.remove(&"test"), false);
assert!(lru_set.is_empty());
let mut lru_set = LruHashSet::with_max_entries(10);
assert_eq!(lru_set.insert(String::from("will_be_erased")), true);
for i in 0..10{
assert_eq!(lru_set.insert(format!("erase_{i}")), true);
}
// the item vanished as the LRU got full
assert_eq!(lru_set.contains(&String::from("will_be_erased")), false);
assert!(lru_set.is_full());
License
GNU General Public License v3.0
Permissions of this strong copyleft license are conditioned on making available complete source code of licensed works and modifications, which include larger works using a licensed work, under the same license. Copyright and license notices must be preserved. Contributors provide an express grant of patent rights.
Dependencies
~245–700KB
~16K SLoC