Crate cdll

Circular doubly linked list. The implementation is inspired by the linux implementation in C .

Basic usage

use cdll::CircularList;

let mut my_list = CircularList::default();
for x in 1..=5 {
    my_list.add(x);
}

assert_eq!(my_list.remove(), Some(1));
assert_eq!(my_list.pop(), Some(5));

my_list.iter_mut().for_each(|x: &mut i32| *x -= 1);
assert_eq!(my_list.into_iter().collect::<Vec<i32>>(), &[1, 2, 3])

Safety considerations

This crate uses unsafe code to dereference raw pointers. In order for it to be sound, one has to preserve some invariants (e.g. pointers must be valid). To achieve this, the source code is commented with careful justifications to prove correctness (at least it is a try).

Macros

list

Create a list with provided elements.

Structs

CircularList

A circular doubly linked list.

Cursor

A Cursor is like an iterator, except that it can freely seek back-and-forth. This struct is constructed by the CircularList::cursor function.

CursorMut

Like a Cursor but with mutative operations on the list. This struct is constructed by the CircularList::cursor_mut function.

DoubleCursor

A DoubleCursor is a struct that points to 2 elements ‘a’ and ‘b’ of a CircularList. One can then swap the 2 elements or put the first after the second etc.

IntoIter

An owning iterator over the elements of a CircularList. This struct is created by CircularList::into_iter().