clist/
lib.rs

1//! This crate contains a circularly and singly linked list implementation.
2//!
3//! Its operations are:
4//!
5//! operation             | runtime | description
6//! ----------------------|---------|---------------
7//! clist::lpush()        | O(1)    | insert as head (leftmost node)
8//! clist::lpeek()        | O(1)    | get the head without removing it
9//! clist::lpop()         | O(1)    | remove and return head (leftmost node)
10//! clist::rpush()        | O(1)    | append as tail (rightmost node)
11//! clist::rpeek()        | O(1)    | get the tail without removing it
12//! clist::rpop()         | O(n)    | remove and return tail (rightmost node)
13//! clist::lpoprpush()    | O(1)    | move first element to the end of the list
14//! clist::contains(      | O(n)    | check if list contains element
15//! clist::find()         | O(n)    | find and return node
16//! clist::find_before()  | O(n)    | find node return node pointing to node
17//! clist::remove()       | O(n)    | remove and return node
18//! clist::sort()         | O(NlogN)| sort list (stable)
19//! clist::count()        | O(n)    | count the number of elements in a list
20//!
21//! clist can be used as a traditional list, a queue (FIFO) and a stack (LIFO) using
22//! fast O(1) operations.
23//!
24
25#![cfg_attr(not(test), no_std)]
26// features needed by our use of memoffset
27#![feature(const_ptr_offset_from)]
28#![feature(const_refs_to_cell)]
29
30use core::cell::UnsafeCell;
31use core::marker::PhantomPinned;
32
33extern crate memoffset;
34pub use memoffset::offset_of;
35
36#[derive(Debug)]
37pub struct Link {
38    next: UnsafeCell<*const Link>,
39    _pin: PhantomPinned,
40}
41
42pub struct List {
43    last: Option<Link>,
44}
45
46unsafe impl Sync for List {}
47unsafe impl Send for List {}
48unsafe impl Sync for Link {}
49unsafe impl Send for Link {}
50
51impl Link {
52    pub const fn new() -> Link {
53        Link {
54            next: UnsafeCell::new(core::ptr::null()),
55            _pin: PhantomPinned,
56        }
57    }
58
59    pub const unsafe fn new_linked(link: *const Link) -> Link {
60        Link {
61            next: UnsafeCell::new(link),
62            _pin: PhantomPinned,
63        }
64    }
65
66    /// check if this Link is currently part of a list.
67    pub fn is_linked(&self) -> bool {
68        self.next.get() == core::ptr::null_mut()
69    }
70
71    unsafe fn link(&self, next: &Link) {
72        *self.next.get() = next as *const Link;
73    }
74
75    unsafe fn next_ptr(&self) -> *const Link {
76        *self.next.get()
77    }
78
79    unsafe fn next(&self) -> &Link {
80        &*self.next_ptr()
81    }
82}
83
84// public
85impl List {
86    /// creates a new, empty list
87    pub const fn new() -> Self {
88        List { last: None }
89    }
90
91    /// returns true if list does not contain any elements
92    pub fn is_empty(&self) -> bool {
93        self.last.is_none()
94    }
95
96    /// Inserts element at the beginning of the list
97    /// Complexity: O(1)
98    pub fn lpush(&mut self, element: &mut Link) {
99        if self.is_empty() {
100            unsafe { self.push_initial_element(element) };
101        } else {
102            unsafe {
103                element.link(self.head());
104                self.tail().link(element);
105            };
106        }
107    }
108
109    /// Remove and return element from the beginning of the list
110    /// Complexity: O(1)
111    pub fn lpop(&mut self) -> Option<&Link> {
112        if self.is_empty() {
113            None
114        } else {
115            unsafe {
116                let head = self.head_ptr();
117                if self.tail_ptr() == head {
118                    self.last = None;
119                } else {
120                    self.tail().link(self.head().next());
121                }
122
123                Some(&*head)
124            }
125        }
126    }
127
128    /// Returns the first element in the list without removing it
129    /// Complexity: O(1)
130    pub fn lpeek(&self) -> Option<&Link> {
131        if self.is_empty() {
132            None
133        } else {
134            Some(unsafe { self.head() })
135        }
136    }
137
138    /// Inserts element at the end of the list
139    /// Complexity: O(1)
140    pub fn rpush(&mut self, element: &mut Link) {
141        self.lpush(element);
142        self.last = Some(unsafe { Link::new_linked(element) });
143    }
144
145    /// Remove and return element from the end of the list
146    /// Complexity: O(1)
147    pub fn rpop(&mut self) -> Option<&Link> {
148        if self.is_empty() {
149            None
150        } else {
151            let tail = unsafe { &*self.tail_ptr() };
152            self.remove(tail)
153        }
154    }
155
156    /// Returns the last element in the list without removing it
157    /// Complexity: O(1)
158    pub fn rpeek(&self) -> Option<&Link> {
159        if self.is_empty() {
160            None
161        } else {
162            Some(unsafe { self.tail() })
163        }
164    }
165
166    /// Rotates list (first becomes last, second becomes first)
167    /// Complexity: O(1)
168    pub fn lpoprpush(&mut self) {
169        if !self.is_empty() {
170            unsafe { self.last().link(self.head()) };
171        }
172    }
173
174    /// Find element
175    /// Complexity: O(n)
176    pub fn find(&self, element: &Link) -> Option<&Link> {
177        unsafe { self.find_previous(element).and_then(|x| Some(x.next())) }
178    }
179
180    /// Remove and return element
181    /// Complexity: O(n)
182    pub fn remove(&mut self, element: &Link) -> Option<&Link> {
183        if self.is_empty() {
184            None
185        } else if unsafe { self.head_ptr() } == element as *const _ {
186            // this deals with the case of removing the only element,
187            // at the cost of comparing head to element twice
188            self.lpop()
189        } else {
190            unsafe {
191                // storing element here so we can return it from the closure
192                let res = element as *const _;
193                if let Some(prev) = self.find_previous(element) {
194                    prev.link(prev.next().next());
195                    if self.tail_ptr() == res {
196                        self.last().link(prev);
197                    }
198                    Some(&*res)
199                } else {
200                    None
201                }
202            }
203        }
204    }
205
206    pub fn contains(&mut self, element: &Link) -> bool {
207        unsafe { self.find_previous(element).is_some() }
208    }
209
210    pub fn iter(&self) -> Iter {
211        let empty = self.is_empty();
212        Iter {
213            list: self,
214            pos: if empty {
215                core::ptr::null()
216            } else {
217                unsafe { self.head_ptr() }
218            },
219            stop: empty,
220        }
221    }
222
223    pub fn iter_mut(&self) -> IterMut {
224        let empty = self.is_empty();
225        IterMut {
226            list: self,
227            pos: if empty {
228                core::ptr::null()
229            } else {
230                unsafe { self.head_ptr() }
231            },
232            stop: empty,
233        }
234    }
235}
236
237impl core::fmt::Debug for List {
238    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
239        if self.is_empty() {
240            write!(f, "List {{}}")
241        } else {
242            unsafe {
243                write!(
244                    f,
245                    "List {{ {:x} {:x}:{:x} {:x}:{:x}",
246                    self.last().next_ptr() as usize,
247                    self.tail() as *const _ as usize,
248                    self.tail().next_ptr() as usize,
249                    self.head() as *const _ as usize,
250                    self.head().next_ptr() as usize,
251                )
252            }
253        }
254    }
255}
256
257/// internal
258impl List {
259    unsafe fn last(&self) -> &Link {
260        &self.last.as_ref().unwrap_unchecked()
261    }
262
263    unsafe fn tail(&self) -> &Link {
264        self.last().next()
265    }
266
267    unsafe fn tail_ptr(&self) -> *const Link {
268        self.last().next_ptr()
269    }
270
271    unsafe fn head(&self) -> &Link {
272        self.tail().next()
273    }
274
275    unsafe fn head_ptr(&self) -> *const Link {
276        self.tail().next()
277    }
278
279    unsafe fn push_initial_element(&mut self, element: &mut Link) {
280        element.link(element);
281        self.last = Some(Link::new_linked(element));
282    }
283
284    unsafe fn find_previous(&self, element: &Link) -> Option<&Link> {
285        if self.is_empty() {
286            return None;
287        }
288        let mut pos = self.tail();
289        let tail_ptr = pos as *const Link;
290        let element_ptr = element as *const Link;
291        loop {
292            let next_ptr = pos.next_ptr();
293            if next_ptr == element_ptr {
294                return Some(pos);
295            }
296            if next_ptr == tail_ptr {
297                return None;
298            }
299            pos = pos.next();
300        }
301    }
302}
303
304pub struct Iter<'a> {
305    list: &'a List,
306    pos: *const Link,
307    stop: bool,
308}
309
310pub struct IterMut<'a> {
311    list: &'a List,
312    pos: *const Link,
313    stop: bool,
314}
315
316impl<'a> Iterator for Iter<'a> {
317    type Item = &'a Link;
318    fn next(&mut self) -> Option<&'a Link> {
319        if self.stop {
320            None
321        } else {
322            unsafe {
323                if self.list.tail_ptr() as *const _ == self.pos {
324                    self.stop = true;
325                }
326                let res = &*self.pos;
327                self.pos = res.next_ptr();
328                Some(res)
329            }
330        }
331    }
332}
333
334impl<'a> Iterator for IterMut<'a> {
335    type Item = &'a Link;
336    fn next(&mut self) -> Option<&'a Link> {
337        if self.stop {
338            None
339        } else {
340            unsafe {
341                if self.list.tail_ptr() as *const _ == self.pos {
342                    self.stop = true;
343                }
344                let res = &*self.pos;
345                self.pos = res.next_ptr();
346                Some(res)
347            }
348        }
349    }
350}
351
352#[derive(Debug)]
353pub struct TypedList<T, const OFFSET: usize> {
354    list: List,
355    _phantom: core::marker::PhantomData<T>,
356}
357
358impl<T, const OFFSET: usize> TypedList<T, { OFFSET }> {
359    pub const fn new() -> Self {
360        Self {
361            list: List::new(),
362            _phantom: core::marker::PhantomData {},
363        }
364    }
365
366    pub fn is_empty(&mut self) -> bool {
367        self.list.is_empty()
368    }
369
370    pub fn lpush(&mut self, element: &mut T) {
371        let element = ((element as *mut T) as usize + OFFSET) as *mut Link;
372        self.list.lpush(unsafe { &mut *element })
373    }
374
375    pub fn rpush(&mut self, element: &mut T) {
376        let element = ((element as *mut T) as usize + OFFSET) as *mut Link;
377        self.list.rpush(unsafe { &mut *element })
378    }
379
380    pub fn lpop(&mut self) -> Option<&mut T> {
381        match self.list.lpop() {
382            None => None,
383            Some(link) => {
384                Some(unsafe { &mut *((link as *const Link as usize - OFFSET) as *mut T) })
385            }
386        }
387    }
388
389    pub fn rpop(&mut self) -> Option<&mut T> {
390        match self.list.rpop() {
391            None => None,
392            Some(link) => {
393                Some(unsafe { &mut *((link as *const Link as usize - OFFSET) as *mut T) })
394            }
395        }
396    }
397
398    pub fn lpoprpush(&mut self) {
399        self.list.lpoprpush()
400    }
401
402    pub fn remove(&mut self, element: &mut T) -> Option<&T> {
403        let element = ((element as *mut T) as usize + OFFSET) as *mut Link;
404        self.list
405            .remove(unsafe { &mut *element })
406            .and_then(|x| Some(unsafe { &*((x as *const Link as usize - OFFSET) as *mut T) }))
407    }
408
409    pub fn lpeek(&mut self) -> Option<&T> {
410        match self.list.lpeek() {
411            None => None,
412            Some(link) => Some(unsafe { &*((link as *const Link as usize - OFFSET) as *mut T) }),
413        }
414    }
415
416    pub fn rpeek(&mut self) -> Option<&T> {
417        match self.list.rpeek() {
418            None => None,
419            Some(link) => Some(unsafe { &*((link as *const Link as usize - OFFSET) as *mut T) }),
420        }
421    }
422
423    pub fn iter(&self) -> TypedIter<T> {
424        TypedIter::<T> {
425            iterator: self.list.iter(),
426            offset: OFFSET,
427            _phantom: core::marker::PhantomData::<T> {},
428        }
429    }
430
431    pub fn iter_mut(&self) -> TypedIterMut<T> {
432        TypedIterMut::<T> {
433            iterator: self.list.iter(),
434            offset: OFFSET,
435            _phantom: core::marker::PhantomData::<T> {},
436        }
437    }
438}
439
440pub struct TypedIter<'a, T> {
441    iterator: Iter<'a>,
442    offset: usize,
443    _phantom: core::marker::PhantomData<T>,
444}
445
446pub struct TypedIterMut<'a, T> {
447    iterator: Iter<'a>,
448    offset: usize,
449    _phantom: core::marker::PhantomData<T>,
450}
451
452impl<'a, T: 'a> Iterator for TypedIter<'a, T> {
453    type Item = &'a T;
454
455    fn next(&mut self) -> Option<&'a T> {
456        if let Some(link) = self.iterator.next() {
457            Some(unsafe { &*((link as *const Link as usize - self.offset) as *mut T) })
458        } else {
459            None
460        }
461    }
462}
463
464impl<'a, T: 'a> Iterator for TypedIterMut<'a, T> {
465    type Item = &'a mut T;
466
467    fn next(&mut self) -> Option<&'a mut T> {
468        if let Some(link) = self.iterator.next() {
469            Some(unsafe { &mut *((link as *const Link as usize - self.offset) as *mut T) })
470        } else {
471            None
472        }
473    }
474}
475
476// pub struct TypedIter<'a, T, const OFFSET: usize> {
477//     iterator: Iter<'a>,
478//     _phantom: core::marker::PhantomData<T>,
479// }
480
481// impl<'a, T: 'a, const OFFSET: usize> Iterator for TypedIter<'a, T, OFFSET> {
482//     type Item = &'a T;
483
484//     fn next(&mut self) -> Option<&'a T> {
485//         if let Some(link) = self.iterator.next() {
486//             Some(unsafe { &*((link as *const Link as usize - OFFSET) as *const T) })
487//         } else {
488//             None
489//         }
490//     }
491// }
492
493#[cfg(test)]
494mod tests {
495    use super::*;
496
497    #[test]
498    fn test_lpush_lpop_1() {
499        let mut list = List::new();
500        assert!(list.lpop().is_none());
501
502        let mut node = Link::new();
503
504        list.lpush(&mut node);
505
506        assert!(unsafe { node.next_ptr() } == &node as *const Link);
507        assert!(list.lpop().unwrap() as *const Link == &node as *const Link);
508        assert!(list.lpop().is_none());
509    }
510
511    #[test]
512    fn test_lpush_lpop_2() {
513        let mut list = List::new();
514        assert!(list.lpop().is_none());
515
516        let mut node = Link::new();
517        list.lpush(&mut node);
518        assert!(unsafe { node.next_ptr() } == &node as *const Link);
519
520        let mut node2 = Link::new();
521        list.lpush(&mut node2);
522
523        assert!(unsafe { node2.next_ptr() } == &node as *const Link);
524        assert!(unsafe { node.next_ptr() } == &node2 as *const Link);
525        assert!(unsafe { list.last().next_ptr() == &node as *const Link });
526
527        assert!(list.lpop().unwrap() as *const Link == &node2 as *const Link);
528        assert!(list.lpop().unwrap() as *const Link == &node as *const Link);
529        assert!(list.lpop().is_none());
530    }
531
532    #[test]
533    fn test_lpush_lpop_3() {
534        let mut list = List::new();
535        assert!(list.lpop().is_none());
536
537        let mut node = Link::new();
538        list.lpush(&mut node);
539        assert!(unsafe { node.next_ptr() } == &node as *const Link);
540
541        let mut node2 = Link::new();
542        list.lpush(&mut node2);
543
544        let mut node3 = Link::new();
545        list.lpush(&mut node3);
546
547        assert!(unsafe { node.next_ptr() } == &node3 as *const Link);
548        assert!(unsafe { node2.next_ptr() } == &node as *const Link);
549        assert!(unsafe { node3.next_ptr() } == &node2 as *const Link);
550        assert!(unsafe { list.tail_ptr() == &node as *const Link });
551
552        assert!(list.lpop().unwrap() as *const Link == &node3 as *const Link);
553        assert!(unsafe { node.next_ptr() } == &node2 as *const Link);
554        assert!(unsafe { node2.next_ptr() } == &node as *const Link);
555        assert!(unsafe { list.tail_ptr() == &node as *const Link });
556        //assert!(unsafe { node3.next_ptr() } == core::ptr::null());
557
558        assert!(list.lpop().unwrap() as *const Link == &node2 as *const Link);
559        assert!(unsafe { node.next_ptr() } == &node as *const Link);
560        assert!(unsafe { list.tail_ptr() == &node as *const Link });
561        //assert!(unsafe { node2.next_ptr() } == core::ptr::null());
562
563        assert!(list.lpop().unwrap() as *const Link == &node as *const Link);
564        //assert!(unsafe { node.next_ptr() } == core::ptr::null());
565        assert!(list.last.is_none());
566
567        assert!(list.lpop().is_none());
568    }
569
570    #[test]
571    fn test_lpoprpush() {
572        let mut list = List::new();
573
574        let mut node = Link::new();
575        let mut node2 = Link::new();
576
577        list.lpush(&mut node);
578        list.lpush(&mut node2);
579        list.lpoprpush();
580
581        assert!(list.lpop().unwrap() as *const _ == &node as *const _);
582        assert!(list.lpop().unwrap() as *const _ == &node2 as *const _);
583        assert!(list.lpop().is_none());
584    }
585
586    #[test]
587    fn test_rpush() {
588        let mut list = List::new();
589
590        let mut node = Link::new();
591        let mut node2 = Link::new();
592
593        list.rpush(&mut node);
594        list.rpush(&mut node2);
595
596        assert!(list.lpop().unwrap() as *const _ == &mut node as *const _);
597        assert!(list.lpop().unwrap() as *const _ == &mut node2 as *const _);
598        assert!(list.lpop().is_none());
599    }
600
601    #[test]
602    fn test_rpop() {
603        let mut list = List::new();
604
605        let mut node = Link::new();
606        let mut node2 = Link::new();
607        let mut node3 = Link::new();
608
609        list.rpush(&mut node);
610        list.rpush(&mut node2);
611        list.rpush(&mut node3);
612
613        assert!(unsafe { node.next_ptr() } == &node2 as *const Link);
614        assert!(unsafe { node2.next_ptr() } == &node3 as *const Link);
615        assert!(unsafe { node3.next_ptr() } == &node as *const Link);
616        assert!(unsafe { list.tail_ptr() == &node3 as *const Link });
617
618        assert!(list.rpop().unwrap() as *const _ == &mut node3 as *const _);
619        assert!(unsafe { node.next_ptr() } == &node2 as *const Link);
620        assert!(unsafe { node2.next_ptr() } == &node as *const Link);
621        assert!(unsafe { list.tail_ptr() == &node2 as *const Link });
622
623        assert!(list.rpop().unwrap() as *const _ == &mut node2 as *const _);
624        assert!(unsafe { node.next_ptr() } == &node as *const Link);
625        assert!(unsafe { list.tail_ptr() == &node as *const Link });
626
627        assert!(list.rpop().unwrap() as *const _ == &mut node as *const _);
628        assert!(list.is_empty());
629        assert!(list.rpop().is_none());
630    }
631
632    #[test]
633    fn test_remove_first() {
634        let mut list = List::new();
635
636        let mut node = Link::new();
637        let mut node2 = Link::new();
638        let mut node3 = Link::new();
639
640        list.rpush(&mut node);
641        list.rpush(&mut node2);
642        list.rpush(&mut node3);
643
644        assert!(list.remove(&node).is_some());
645
646        assert!(list.rpop().unwrap() as *const _ == &mut node3 as *const _);
647        assert!(list.rpop().unwrap() as *const _ == &mut node2 as *const _);
648        assert!(list.rpop().is_none());
649        assert!(list.lpop().is_none());
650    }
651
652    #[test]
653    fn test_remove_mid() {
654        let mut list = List::new();
655
656        let mut node = Link::new();
657        let mut node2 = Link::new();
658        let mut node3 = Link::new();
659
660        list.rpush(&mut node);
661        list.rpush(&mut node2);
662        list.rpush(&mut node3);
663
664        assert!(list.remove(&node2).is_some());
665
666        assert!(list.rpop().unwrap() as *const _ == &mut node3 as *const _);
667        assert!(list.rpop().unwrap() as *const _ == &mut node as *const _);
668        assert!(list.rpop().is_none());
669        assert!(list.lpop().is_none());
670    }
671
672    #[test]
673    fn test_remove_last() {
674        let mut list = List::new();
675
676        let mut node = Link::new();
677        let mut node2 = Link::new();
678        let mut node3 = Link::new();
679
680        list.rpush(&mut node);
681        list.rpush(&mut node2);
682        list.rpush(&mut node3);
683
684        assert!(list.remove(&node3).is_some());
685
686        assert!(list.rpop().unwrap() as *const _ == &mut node2 as *const _);
687        assert!(list.rpop().unwrap() as *const _ == &mut node as *const _);
688        assert!(list.rpop().is_none());
689        assert!(list.lpop().is_none());
690    }
691
692    #[test]
693    fn test_iterator() {
694        let mut list = List::new();
695
696        let mut node = Link::new();
697        let mut node2 = Link::new();
698        let mut node3 = Link::new();
699
700        list.rpush(&mut node);
701        list.rpush(&mut node2);
702        list.rpush(&mut node3);
703
704        let pointers = [
705            &mut node as *const Link,
706            &mut node2 as *const Link,
707            &mut node3 as *const Link,
708        ];
709
710        println!("pointers:");
711        for entry in pointers.iter() {
712            println!("{:x}", *entry as usize);
713        }
714
715        println!("list entries:");
716        let mut i = 0;
717        for entry in list.iter() {
718            println!("{:x}", entry as *const Link as usize);
719            assert_eq!(entry as *const Link, pointers[i]);
720            i += 1;
721        }
722        assert_eq!(i, 3);
723    }
724
725    #[test]
726    fn test_iterator_mut() {
727        let mut list = List::new();
728
729        let mut node = Link::new();
730        let mut node2 = Link::new();
731        let mut node3 = Link::new();
732
733        list.rpush(&mut node);
734        list.rpush(&mut node2);
735        list.rpush(&mut node3);
736
737        let pointers = [
738            &mut node as *const Link,
739            &mut node2 as *const Link,
740            &mut node3 as *const Link,
741        ];
742
743        println!("pointers:");
744        for entry in pointers.iter() {
745            println!("{:x}", *entry as usize);
746        }
747
748        println!("list entries:");
749        let mut i = 0;
750        for entry in list.iter_mut() {
751            println!("{:x}", entry as *const Link as usize);
752            assert_eq!(entry as *const Link, pointers[i]);
753            i += 1;
754        }
755        assert_eq!(i, 3);
756    }
757
758    #[test]
759    fn test_iterator_empty() {
760        let list = List::new();
761
762        for _ in list.iter() {
763            assert!(false);
764        }
765    }
766
767    #[test]
768    fn test_typed_iterator() {
769        struct Data {
770            data: u32,
771            list_entry: Link,
772        }
773
774        let mut list: TypedList<Data, { offset_of!(Data, list_entry) }> = TypedList::new();
775
776        let mut node = Data {
777            data: 0,
778            list_entry: Link::new(),
779        };
780
781        let mut node2 = Data {
782            data: 1,
783            list_entry: Link::new(),
784        };
785
786        let mut node3 = Data {
787            data: 2,
788            list_entry: Link::new(),
789        };
790
791        list.rpush(&mut node);
792        list.rpush(&mut node2);
793        list.rpush(&mut node3);
794
795        let expected = [0 as u32, 1, 2];
796
797        println!("list entries:");
798        let mut i = 0;
799        for entry in list.iter() {
800            println!("{}", entry.data);
801            assert_eq!(entry.data, expected[i]);
802            i += 1;
803        }
804        assert_eq!(i, 3);
805    }
806}
clist/lib.rs

clist/
lib.rs
