unrolled_linked_list/
lib.rs

1//! # Unrolled linked list
2//! An [`wiki`] is a linear data structure that is a variant on the linked list.
3//! Instead of just storing 1 element at each node, unrolled linked lists store an entire array at each node.
4//!
5//! Unrolled linked lists combine the advantages of the array (small memory overhead) with the benefits of linked lists (fast insertion and deletion) to produce vastly better performance.
6//! By storing multiple elements at each node, unrolled linked lists effectively spread out the overhead of linked lists across multiple elements.
7//! So, if an unrolled linked list stores an array of 4 elements at each node, its spreading the linked list overhead (pointers) across those 4 elements.
8//!
9//! The true benefits of the unrolled linked list come in the form of caching. The unrolled linked list takes advantage of this when it comes to indexing.
10//!
11//! # Example
12//! Let's suppose we have a following json:
13//! ```rust
14//!  use unrolled_linked_list::UnrolledLinkedList;
15//!
16//! fn main(){
17//!   let mut list = UnrolledLinkedList::new();
18//!   list.insert(0, 1);
19//!   list.push(2);
20//!   list.push(3);
21//!   list.insert(3,4);
22//!   if let Some(four) =  list.pop() { println!(" should be {}", four)}
23//!
24//!   let one_opt = list.get(0);
25//!   let one_mut_opt = list.get_mut(0);
26//!
27//!   list.remove(0);
28//!
29//!   for el in list.iter(){
30//!     println!("elem {}",el);
31//!   }
32//!
33//! }
34//! ```
35//
36//! [`wiki`]: https://en.wikipedia.org/wiki/Unrolled_linked_list/
37
38use std::ptr::NonNull;
39use std::fmt::{Display, Formatter, Debug};
40use std::fmt;
41
42pub mod iters;
43
44/// The unrolled linked list. The list that acts like a linked list but has the node structure inside.
45pub struct UnrolledLinkedList<T> {
46    len: usize,
47    cap: usize,
48    head: Option<NonNull<Node<T>>>,
49    tail: Option<NonNull<Node<T>>>,
50}
51
52
53impl<T> Display for UnrolledLinkedList<T> {
54    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
55        write!(f, "unrolled linked list: len:{}, cap:{}", self.len, self.cap)
56    }
57}
58
59impl<T: fmt::Debug> Debug for UnrolledLinkedList<T> {
60    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
61        f.debug_list().entries(self).finish()
62    }
63}
64
65impl<T> Default for UnrolledLinkedList<T> {
66    #[inline]
67    fn default() -> Self {
68        Self::new()
69    }
70}
71
72impl<T> UnrolledLinkedList<T> {
73    /// The default initiation, setting the size of node to 8.
74    /// # Examples
75    ///
76    /// ```
77    /// use unrolled_linked_list::UnrolledLinkedList;
78    ///
79    /// let list: UnrolledLinkedList<u32> = UnrolledLinkedList::new();
80    /// ```
81    pub fn new() -> Self {
82        UnrolledLinkedList::with_capacity(8)
83    }
84    /// Capacity defines the size of the node.
85    /// # Examples
86    ///
87    /// ```
88    /// use unrolled_linked_list::UnrolledLinkedList;
89    ///
90    /// let list: UnrolledLinkedList<u32> = UnrolledLinkedList::with_capacity(4);
91    /// ```
92    pub fn with_capacity(cap: usize) -> Self {
93        UnrolledLinkedList {
94            cap,
95            len: 0,
96            head: None,
97            tail: None,
98        }
99    }
100}
101
102impl<T> UnrolledLinkedList<T> {
103    /// Adds an element last in the list.
104    ///
105    /// # Examples
106    ///
107    /// ```
108    ///
109    /// use unrolled_linked_list::UnrolledLinkedList;
110    /// let mut dl = UnrolledLinkedList::new();
111    ///
112    /// dl.push(2);
113    /// assert_eq!(dl.pop().unwrap(), 2);
114    ///
115    /// dl.push(1);
116    /// assert_eq!(dl.pop().unwrap(), 1);
117    /// ```
118    pub fn push(&mut self, el: T) {
119        match (self.head, self.tail) {
120            (_, Some(mut node)) | (Some(mut node), None) => {
121                unsafe {
122                    let node = node.as_mut();
123                    if node.is_full(self.cap) {
124                        self.tail = Some(node.split_and_push(el));
125                    } else { node.data.push(el); }
126                }
127            }
128            (None, None) => {
129                let mut node = Box::new(Node::new());
130                node.data.push(el);
131                self.head = Some(Box::leak(node).into())
132            }
133        }
134        self.len += 1;
135    }
136    /// Adds an element last in the list.
137    /// # Panics
138    /// Panics if `index > len`.
139    ///
140    /// # Examples
141    ///
142    /// ```
143    ///
144    /// use unrolled_linked_list::UnrolledLinkedList;
145    /// let mut dl = UnrolledLinkedList::new();
146    ///
147    /// dl.insert(0,0);
148    /// assert_eq!(dl.pop().unwrap(), 0);
149    /// ```
150    pub fn insert(&mut self, index: usize, el: T) {
151        if index > self.len {
152            panic!("index {} should be less or equal the len {}", index, self.len)
153        }
154
155        if let (Some(mut node_ptr), start_idx) = self.find_node(index) {
156            unsafe {
157                let local_idx = index - start_idx;
158                let node = node_ptr.as_mut();
159                if node.is_full(self.cap) {
160                    let next_node = node.split_and_insert(el, local_idx);
161                    if self.tail.is_none() { self.tail = Some(next_node); }
162                } else {
163                    node.data.insert(local_idx, el);
164                }
165            }
166        } else {
167            let mut first_node = Box::new(Node::new());
168            first_node.data.insert(index, el);
169            self.head = Some(Box::leak(first_node).into())
170        }
171        self.len += 1;
172    }
173    /// removes the last element from the list and returns it.
174    ///
175    /// # Examples
176    ///
177    /// ```
178    ///
179    /// use unrolled_linked_list::UnrolledLinkedList;
180    /// let mut dl = UnrolledLinkedList::new();
181    ///
182    /// dl.insert(0,0);
183    /// assert_eq!(dl.pop().unwrap(), 0);
184    /// ```
185    pub fn pop(&mut self) -> Option<T> {
186        unsafe {
187            return match (self.head, self.tail) {
188                (Some(mut f), None) => {
189                    let first = f.as_mut();
190                    if first.data.is_empty() {
191                        None
192                    } else {
193                        self.len -= 1;
194                        first.data.pop()
195                    }
196                }
197                (_, Some(mut l)) => {
198                    let last = l.as_mut();
199                    let popped_value = last.data.pop();
200                    if last.data.is_empty() { self.unlink_last(); }
201                    self.len -= 1;
202                    popped_value
203                }
204                _ => None
205            };
206        }
207    }
208    /// removes the custom element from the list accordign to the index and returns it.
209    /// # Panics
210    /// Panics if `index >= len`.
211    /// # Examples
212    ///
213    /// ```
214    ///
215    /// use unrolled_linked_list::UnrolledLinkedList;
216    /// let mut dl = UnrolledLinkedList::new();
217    ///
218    /// dl.insert(0,0);
219    /// assert_eq!(dl.remove(0), 0);
220    /// ```
221    pub fn remove(&mut self, index: usize) -> T {
222        if index >= self.len {
223            panic!("index {} should be less then len {}", index, self.len)
224        }
225        unsafe {
226            if let (Some(mut n), start_idx) = self.find_node(index) {
227                let node = n.as_mut();
228                let rem_element = node.data.remove(index - start_idx);
229                node.steal_some(self.cap);
230                self.len -= 1;
231                rem_element
232            } else {
233                unreachable!("the node should exist");
234            }
235        }
236    }
237    /// retrieves the custom element from the list according to the index and returns it.
238    /// # Examples
239    ///
240    /// ```
241    ///
242    /// use unrolled_linked_list::UnrolledLinkedList;
243    /// let mut dl = UnrolledLinkedList::new();
244    ///
245    /// dl.insert(0,0);
246    /// dl.insert(1,1);
247    /// assert_eq!(dl.get(1), Some(&1));
248    /// assert_eq!(dl.get(0), Some(&0));
249    /// ```
250    pub fn get(&self, index: usize) -> Option<&T> {
251        unsafe {
252            if let (Some(n), start_idx) = self.find_node(index) {
253                (*n.as_ptr()).data.get(index - start_idx)
254            } else { None }
255        }
256    }
257    /// retrieves the custom element from the list according to the index and returns the mutable reference.
258    /// # Examples
259    ///
260    /// ```
261    ///
262    /// use unrolled_linked_list::UnrolledLinkedList;
263    /// let mut dl = UnrolledLinkedList::new();
264    ///
265    /// dl.insert(0,0);
266    /// dl.insert(1,1);
267    /// assert_eq!(dl.get_mut(1), Some(&mut 1));
268    /// assert_eq!(dl.get_mut(0), Some(&mut 0));
269    /// ```
270    pub fn get_mut(&self, index: usize) -> Option<&mut T> {
271        unsafe {
272            if let (Some(n), start_idx) = self.find_node(index) {
273                let node = &mut *n.as_ptr();
274                node.data.get_mut(index - start_idx)
275            } else { None }
276        }
277    }
278
279    /// Returns `true` if the `UnrolledLinkedList` is empty.
280    ///
281    /// This operation should compute in *O*(1) time.
282    pub fn is_empty(&self) -> bool {
283        self.len == 0
284    }
285
286    /// Returns the length of the `UnrolledLinkedList`.
287    ///
288    /// This operation should compute in *O*(1) time.
289    pub fn len(&self) -> usize {
290        self.len
291    }
292
293    /// Removes all elements from the `LinkedList`.
294    ///
295    /// This operation should compute in *O*(*n*) time.
296    pub fn clear(&mut self) {
297        *self = Self::with_capacity(self.cap);
298    }
299
300    /// Returns `true` if the `LinkedList` contains an element equal to the
301    /// given value.
302    pub fn contains(&self, x: &T) -> bool
303        where
304            T: PartialEq<T>,
305    {
306        self.iter().any(|e| e == x)
307    }
308}
309
310impl<T> UnrolledLinkedList<T> {
311    #[inline]
312    unsafe fn unlink_last(&mut self) {
313        if let Some(mut f) = self.head {
314            let first = f.as_mut();
315            if first.next == self.tail {
316                first.unlink_next();
317                self.tail = None;
318            } else if let Some(mut p) = self.tail.and_then(|mut e| e.as_mut().prev) {
319                let prev_node = p.as_mut();
320                prev_node.unlink_next();
321                self.tail = Some(p);
322            }
323        }
324    }
325    fn find_node(&self, idx: usize) -> (Option<NonNull<Node<T>>>, usize) {
326        let mut shift = 0;
327        let mut next_node = self.head;
328
329        unsafe {
330            while next_node.is_some() {
331                if let Some(n) = next_node {
332                    let node = n.as_ref();
333                    let shift_end = shift + node.data.len();
334                    if idx >= shift && idx <= shift_end {
335                        return (Some(n), shift);
336                    }
337                    shift = shift_end;
338                    next_node = node.next;
339                }
340            }
341        }
342        (None, 0)
343    }
344}
345
346struct Node<T> {
347    next: Option<NonNull<Node<T>>>,
348    prev: Option<NonNull<Node<T>>>,
349    data: Vec<T>,
350}
351
352impl<T> Node<T> {
353    fn new() -> Self {
354        Node {
355            next: None,
356            prev: None,
357            data: vec![],
358        }
359    }
360
361    unsafe fn unlink_next(&mut self) {
362        if let Some(next) = self.next {
363            let old_next = Box::from_raw(next.as_ptr());
364            let new_next = old_next.next;
365            if let Some(mut new) = new_next {
366                new.as_mut().prev = NonNull::new(self as *mut Node<T>);
367            }
368            self.next = new_next;
369        }
370    }
371    unsafe fn split(&mut self, mut next: NonNull<Node<T>>) {
372        let len = self.data.len();
373        self.link_next(next);
374        next.as_mut().data = self.data.split_off(len / 2);
375    }
376
377    fn is_full(&self, cap: usize) -> bool {
378        self.data.len() >= cap
379    }
380    #[inline]
381    fn link_next(&mut self, mut next: NonNull<Node<T>>) {
382        unsafe {
383            if let Some(mut old_next) = self.next {
384                old_next.as_mut().prev = Some(next);
385                next.as_mut().next = Some(old_next);
386            }
387            self.next = Some(next);
388            next.as_mut().prev = NonNull::new(self as *mut Node<T>);
389        }
390    }
391
392    #[inline]
393    unsafe fn steal_some(&mut self, cap: usize) {
394        if self.data.len() < cap / 2 {
395            if let Some(mut n) = self.next {
396                let next = n.as_mut();
397                if self.data.len() + next.data.len() >= cap {
398                    let diff = cap / 2 - self.data.len();
399                    let mut right = next.data.split_off(diff);
400                    self.data.append(&mut next.data);
401                    next.data.clear();
402                    next.data.append(&mut right);
403                } else {
404                    self.data.append(&mut next.data);
405                    self.unlink_next();
406                }
407            }
408        }
409    }
410    #[inline]
411    unsafe fn split_and_push(&mut self, el: T) -> NonNull<Node<T>> {
412        let mut next_node = Box::leak(Box::new(Node::new())).into();
413        self.split(next_node);
414        next_node.as_mut().data.push(el);
415        next_node
416    }
417    #[inline]
418    unsafe fn split_and_insert(&mut self, el: T, idx: usize) -> NonNull<Node<T>> {
419        let mut next_node = Box::leak(Box::new(Node::new())).into();
420        self.split(next_node);
421        let data_len = self.data.len();
422        if idx > data_len {
423            next_node.as_mut().data.insert(idx - data_len, el);
424        } else {
425            self.data.insert(idx, el);
426        }
427        next_node
428    }
429}
430
431
432#[cfg(test)]
433mod tests {
434    use crate::UnrolledLinkedList;
435
436    #[test]
437    fn push_test() {
438        let mut list = UnrolledLinkedList::with_capacity(4);
439        list.push(1);
440        list.push(2);
441        list.push(3);
442        list.push(4);
443        list.push(5);
444        list.push(6);
445        list.push(7);
446        list.push(8);
447        list.push(9);
448        list.push(10);
449        list.push(11);
450        list.push(12);
451        list.push(13);
452
453        unsafe {
454            let vec = list.tail.unwrap().as_ref().data.clone();
455            assert_eq!(vec, vec![11, 12, 13]);
456        }
457    }
458
459    #[test]
460    fn pop_test() {
461        let mut list = UnrolledLinkedList::with_capacity(4);
462
463        assert_eq!(list.pop(), None);
464
465        list.push(1);
466        list.push(2);
467        list.push(3);
468        list.push(4);
469
470        assert_eq!(list.pop(), Some(4));
471        assert_eq!(list.pop(), Some(3));
472        assert_eq!(list.pop(), Some(2));
473        assert_eq!(list.pop(), Some(1));
474
475        list.push(1);
476        list.push(2);
477        list.push(3);
478        list.push(4);
479        list.push(5);
480        list.push(6);
481        list.push(7);
482        list.push(8);
483
484        assert_eq!(list.pop(), Some(8));
485        assert_eq!(list.pop(), Some(7));
486        assert_eq!(list.pop(), Some(6));
487        assert_eq!(list.pop(), Some(5));
488
489        list.push(5);
490        list.push(6);
491        list.push(7);
492        list.push(8);
493        list.push(9);
494
495
496        assert_eq!(list.pop(), Some(9));
497        assert_eq!(list.pop(), Some(8));
498        assert_eq!(list.pop(), Some(7));
499        assert_eq!(list.pop(), Some(6));
500        assert_eq!(list.pop(), Some(5));
501        assert_eq!(list.pop(), Some(4));
502        assert_eq!(list.pop(), Some(3));
503        assert_eq!(list.pop(), Some(2));
504        assert_eq!(list.pop(), Some(1));
505        assert!(list.is_empty());
506
507        list.push(1);
508        list.push(2);
509        list.push(3);
510        list.push(4);
511        assert_eq!(list.pop(), Some(4));
512        list.push(5);
513        assert_eq!(list.pop(), Some(5));
514        list.push(6);
515        list.push(7);
516        list.push(8);
517        assert_eq!(list.pop(), Some(8));
518    }
519
520    #[test]
521    fn remove_test() {
522        let mut list = UnrolledLinkedList::with_capacity(4);
523
524
525        list.push(1);
526        list.push(2);
527        list.push(3);
528        list.push(4);
529
530        assert_eq!(list.remove(0), 1);
531        assert_eq!(list.remove(0), 2);
532        assert_eq!(list.remove(0), 3);
533        assert_eq!(list.remove(0), 4);
534
535        list.push(1);
536        list.push(2);
537        list.push(3);
538        list.push(4);
539
540        assert_eq!(list.remove(3), 4);
541        assert_eq!(list.remove(2), 3);
542        assert_eq!(list.remove(1), 2);
543        assert_eq!(list.remove(0), 1);
544
545        list.push(1);
546        list.push(2);
547        list.push(3);
548        list.push(4);
549        list.push(5);
550        list.push(6);
551        list.push(7);
552        list.push(8);
553        list.push(9);
554
555        assert_eq!(list.remove(0), 1);
556        assert_eq!(list.remove(0), 2);
557        assert_eq!(list.remove(0), 3);
558        assert_eq!(list.remove(0), 4);
559        assert_eq!(list.remove(0), 5);
560        assert_eq!(list.remove(0), 6);
561        assert_eq!(list.remove(0), 7);
562        assert_eq!(list.remove(0), 8);
563        assert_eq!(list.remove(0), 9);
564    }
565
566    #[test]
567    fn remove_loop_test() {
568        let mut list = UnrolledLinkedList::new();
569        for el in (0..1000).into_iter() {
570            list.push(el);
571        }
572        for _ in (0..1000).into_iter() {
573            let _ = list.remove(0);
574        }
575        assert!(list.is_empty())
576    }
577
578    #[test]
579    fn insert_test() {
580        let mut list = UnrolledLinkedList::with_capacity(4);
581        list.insert(0, 1);
582        list.insert(0, 2);
583        list.insert(0, 3);
584        list.insert(0, 4);
585        list.insert(0, 5);
586        list.insert(0, 6);
587        list.insert(0, 7);
588
589        unsafe {
590            let vec = list.tail.unwrap().as_ref().data.clone();
591            assert_eq!(vec, vec![2, 1]);
592            let vec = list.head.unwrap().as_ref().data.clone();
593            assert_eq!(vec, vec![7, 6, 5]);
594        }
595    }
596
597    #[test]
598    fn insert2_test() {
599        let mut list = UnrolledLinkedList::with_capacity(4);
600        list.insert(0, 0);
601        list.insert(1, 1);
602        assert_eq!(list.get(1), Some(&1));
603        assert_eq!(list.get(0), Some(&0));
604    }
605
606    #[test]
607    fn find_node_test() {
608        let mut list = UnrolledLinkedList::with_capacity(4);
609        list.push(1);
610        list.push(2);
611        list.push(3);
612        list.push(4);
613        list.push(5);
614        list.push(6);
615        list.push(7);
616        list.push(8);
617        list.push(9);
618        list.push(10);
619        list.push(11);
620        list.push(12);
621        list.push(13);
622
623        unsafe {
624            let (node, start_idx) = list.find_node(5);
625            let data = node.expect("").as_ref().data.clone();
626            assert_eq!(data, vec![5, 6]);
627            assert_eq!(5 - start_idx, 1);
628        }
629    }
630
631    #[test]
632    fn get_test() {
633        let mut list = UnrolledLinkedList::with_capacity(4);
634        list.push(1);
635        list.push(1);
636        list.push(1);
637        list.push(4);
638        list.push(1);
639
640        assert_eq!(list.get(3), Some(&4));
641        assert_eq!(list.get_mut(4), Some(&mut 1));
642    }
643}
unrolled_linked_list/lib.rs

unrolled_linked_list/
lib.rs
