#linked-list #lru #doubly-linked-list #lru-hashmap

lru-st

A package providing a Vec based doubly linked list implementation and related data structures

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

Download history 37/week @ 2024-07-29 242/week @ 2024-09-09 35/week @ 2024-09-16 27/week @ 2024-09-23 16/week @ 2024-09-30 9/week @ 2024-10-07 276/week @ 2024-10-14 38/week @ 2024-10-21 3/week @ 2024-10-28 12/week @ 2024-11-04

330 downloads per month

Custom license

40KB
869 lines

Crates.io Version GitHub Actions Workflow Status docs.rs Crates.io MSRV

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 when collections 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