17 releases (7 breaking)
0.8.5 | Sep 14, 2023 |
---|---|
0.7.0 | Sep 9, 2023 |
#324 in Data structures
74 downloads per month
145KB
2K
SLoC
orx-linked-list
Implements a doubly-linked list.
As opposed to the note of std::collections::LinkedList
, orx_linked_list::LinkedList
provides the main theoretical benefits of a linked list; i.e.,
- efficient insertion and removal of elements,
while aiming to avoid the practical drawbacks related with allocations and CPU cache due to the following:
LinkedList
uses anImpVec
as the underlying data structure which allows for defining inter-element relationships by thin references;next
andprev
relationships are defined by thin&
references:- without any additional heap allocations since smart pointers such as
Box
orRc
per element are not necessary; - or without the need to use plain index numbers to mimic references.
- without any additional heap allocations since smart pointers such as
- All elements are stored in the underlying
PinnedVec
of theImpVec
; which might either be aFixedVec
orSplitVec
. In either case, the elements will be stored close to each other in a vec-like structure. Although the order of elements in this vector will not be in the correct order as expected in a linked list, they will be pointing to other elements of the same vector. Therefore, unlike classical implementations by arbitrary heap allocations, theLinkedList
implementation provides better cache locality.
Usage
Basic usage of the linked list is demonstrated below.
use orx_linked_list::prelude::*;
let mut list = LinkedList::new();
list.push_back('y');
list.push_front('x');
list.push_back('z');
assert_eq!(vec!['x', 'y', 'z'], list);
assert_eq!(list.pop_back(), Some('z'));
assert_eq!(list.pop_front(), Some('x'));
assert_eq!(vec!['y'], list);
list.push_front('x');
list.push_back('z');
assert_eq!(vec!['x', 'y', 'z'], list);
list.insert_at(1, '?');
assert_eq!(vec!['x', '?', 'y', 'z'], list);
assert_eq!(Some(&'?'), list.get_at(1));
*list.get_mut_at(1).unwrap() = '!';
assert_eq!('!', list.remove_at(1));
assert_eq!(vec!['x', 'y', 'z'], list);
Memory
LinkedList
provides different levels of control on memory strategies; it can be used by the simplest type signature relying on the defaults or as detailed as possible by determining the tradeoff between time complexity and memory utilization, as well as, the growth stretegies of the backing storage.
Defaults
The list can be directly used by the default memory management settings by only specifying the element data type.
use orx_linked_list::prelude::*;
// char list
let mut list = LinkedList::new();
list.push_back('x');
// i32 list with an initial capacity
let mut list = LinkedList::with_initial_capacity(42);
list.push_back(42);
Default values of the configurable settings defined in the following subsections are as follows:
memory_utilization
:MemoryUtilization::WithThreshold(0.6)
;- underlying
PinnedVec
: defaultSplitVec
which uses aDoubling
growth strategy.
Tradeoff between Memory Utilization & Time Complexity
LinkedList
holds all elements close to each other in a PinnedVec
aiming for better cache locality while using thin references rather than wide pointers and to reduce heap allocations. In order to achieve O(1) time complexity while avoiding smart pointers, remove and pop operations are designed to be semi-lazy.
In the lazy case; i.e., when the strategy is set to MemoryReclaimStrategy::Lazy
, every pop_back
, pop_front
or remove_at
operation leaves a gap in the underlying vector. Status of utilization of the underlying vector can be queried using the memory_status
method and the gaps can completely be reclaimed by manually calling the memory_reclaim
method which has a time complexity of O(n) where n is the length of the underlying vector.
Being able to be lazy and to reclaim the gaps, it is possible to define and use different automated strategies which would fit better in different situations:
Lazy
:memory_reclaim
is never called automatically:- leads to the cheapest possible
pop_back
,pop_front
orremove_at
operations, - however, the utilization of the vector can be low especially when a large number of elements enter and exit the linked list.
- would be a good fit when it is important keeping the above mentioned operations at as fast as possible; or when utilization is not expected to drop very low.
- leads to the cheapest possible
Eager
: everypop_back
,pop_front
orremove_at
method call is automatically followed by amemory_reclaim
call:- this strategy continuously keeps the vector without gaps at 100% utilization;
- however, abovementioned operations require O(n) time complexity;
- might be a good fit when memory is scarce and more important than the increased time-complexity of these methods.
WithThreshold(threshold)
:pop_back
,pop_front
orremove_at
method call is followed by an automaticmemory_reclaim
call only if the memory utilization drops below a pre-determinedthreshold
:- it is a generalization of
Lazy
andEager
allowing to select the required threshold level between memory utilization and amortized time complexity of these methods.
- it is a generalization of
Memory utilization stategy is defined by a field which can be modified any time.
use orx_linked_list::prelude::*;
let list = LinkedList::<u32>::new()
.with_memory_utilization(MemoryUtilization::Eager)
.with_memory_utilization(MemoryUtilization::Lazy)
.with_memory_utilization(MemoryUtilization::WithThreshold(0.5));
Underlying PinnedVec
LinkedList
uses an ImpVec to establish and maintain the interconnections among elements of the list. An ImpVec
can use any vector implementing PinnedVec which guarantees that the memory locations of elements stay intact. There are two major implementations of PinnedVec
: a FixedVec and a SplitVec. Finally, a split vec can be created with different Growth
strategies.
This means that a LinkedList
can use a variety of backing storage. This is apparent from the complete signature without the default type paremeter value:
LinkedList<'a, T, P> where P: PinnedVec<LinkedListNode<'a, T>>
Please see the relevant crates for details; however, below are brief rules of thumbs:
FixedVec
has a hard limit on capacity; however, provides complexity and performance of standard vector;SplitVec
allows for a dynamic capacity with different growth strategies:SplitVec<T, Doubling>
: every time the vector requires new room, a new chunk of memory is allocated which is double the capacity of the prior chunk;SplitVec<T, Linear>
: every chunk has the same capacity;SplitVec<T, Exponential>
: this is a generalization of the prior two strategies allowing to define any exponential growth function in between them with a slightly increased access cost.SplitVec<T, G>
: actually, any growth strategy can be defined by implementingG: Growth
.
The following type aliases are defined for convenience to simplify the type signatures:
pub type LinkedListFixed<'a, T>
= LinkedList<'a, T, FixedVec<LinkedListNode<'a, T>>>;
pub type LinkedListLinear<'a, T>
= LinkedList<'a, T, SplitVec<LinkedListNode<'a, T>, Linear>>;
pub type LinkedListDoubling<'a, T>
= LinkedList<'a, T, SplitVec<LinkedListNode<'a, T>, Doubling>>;
pub type LinkedListExponential<'a, T>
= LinkedList<'a, T, SplitVec<LinkedListNode<'a, T>, Exponential>>;
These variants can be constructed with corresponding associated functions:
use orx_linked_list::prelude::*;
let list: LinkedListFixed<char> = LinkedList::with_fixed_capacity(100);
let list: LinkedListLinear<char> = LinkedList::with_linear_growth(32);
let list: LinkedListDoubling<char> = LinkedList::with_doubling_growth(4);
let list: LinkedListExponential<char> = LinkedList::with_exponential_growth(4, 1.5);
Dependencies
~275KB