Struct kalloc::list::List

pub struct List<T> { /* fields omitted */ }

A doubly-linked list with owned nodes.

The List allows pushing and popping elements at either end in constant time.

NOTE: It is almost always better to use Vec or Vecque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache.

Implementations

impl<T> List<T>

pub const fn new() -> Self

Creates an empty List.

Examples

use kalloc::list::List;

let list: List<u32> = List::new();

pub fn append(&mut self, other: &mut Self)

Moves all elements from other to the end of the list.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

This operation should compute in O(1) time and O(1) memory.

Examples

use kalloc::list::List;

let mut list1 = List::new();
list1.push_back('a');

let mut list2 = List::new();
list2.push_back('b');
list2.push_back('c');

list1.append(&mut list2);

let mut iter = list1.iter();
assert_eq!(iter.next(), Some(&'a'));
assert_eq!(iter.next(), Some(&'b'));
assert_eq!(iter.next(), Some(&'c'));
assert!(iter.next().is_none());

assert!(list2.is_empty());

pub fn prepend(&mut self, other: &mut Self)

Moves all elements from other to the begin of the list.

pub fn iter(&self) -> Iter<'_, T>

Provides a forward iterator.

Examples

use kalloc::list::List;

let mut list: List<u32> = List::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), None);

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Provides a forward iterator with mutable references.

Examples

use kalloc::list::List;

let mut list: List<u32> = List::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

for element in list.iter_mut() {
    *element += 10;
}

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), Some(&11));
assert_eq!(iter.next(), Some(&12));
assert_eq!(iter.next(), None);

pub fn cursor_front(&self) -> Cursor<'_, T>

Provides a cursor at the front element.

The cursor is pointing to the “ghost” non-element if the list is empty.

pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T>

Provides a cursor with editing operations at the front element.

The cursor is pointing to the “ghost” non-element if the list is empty.

pub fn cursor_back(&self) -> Cursor<'_, T>

Provides a cursor at the back element.

The cursor is pointing to the “ghost” non-element if the list is empty.

pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T>

Provides a cursor with editing operations at the back element.

The cursor is pointing to the “ghost” non-element if the list is empty.

pub fn is_empty(&self) -> bool

Returns true if the List is empty.

This operation should compute in O(1) time.

Examples

use kalloc::list::List;

let mut dl = List::new();
assert!(dl.is_empty());

dl.push_front("foo");
assert!(!dl.is_empty());

pub fn len(&self) -> usize

Returns the length of the List.

This operation should compute in O(1) time.

Examples

use kalloc::list::List;

let mut dl = List::new();

dl.push_front(2);
assert_eq!(dl.len(), 1);

dl.push_front(1);
assert_eq!(dl.len(), 2);

dl.push_back(3);
assert_eq!(dl.len(), 3);

pub fn clear(&mut self)

Removes all elements from the List.

This operation should compute in O(n) time.

Examples

use kalloc::list::List;

let mut dl = List::new();

dl.push_front(2);
dl.push_front(1);
assert_eq!(dl.len(), 2);
assert_eq!(dl.front(), Some(&1));

dl.clear();
assert_eq!(dl.len(), 0);
assert_eq!(dl.front(), None);

pub fn contains(&self, x: &T) -> bool where
    T: PartialEq<T>, 

Returns true if the List contains an element equal to the given value.

Examples

use kalloc::list::List;

let mut list: List<u32> = List::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

assert_eq!(list.contains(&0), true);
assert_eq!(list.contains(&10), false);

pub fn front(&self) -> Option<&T>

Provides a reference to the front element, or None if the list is empty.

Examples

use kalloc::list::List;

let mut dl = List::new();
assert_eq!(dl.front(), None);

dl.push_front(1);
assert_eq!(dl.front(), Some(&1));

pub fn front_mut(&mut self) -> Option<&mut T>

Provides a mutable reference to the front element, or None if the list is empty.

Examples

use kalloc::list::List;

let mut dl = List::new();
assert_eq!(dl.front(), None);

dl.push_front(1);
assert_eq!(dl.front(), Some(&1));

match dl.front_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(dl.front(), Some(&5));

pub fn back(&self) -> Option<&T>

Provides a reference to the back element, or None if the list is empty.

Examples

use kalloc::list::List;

let mut dl = List::new();
assert_eq!(dl.back(), None);

dl.push_back(1);
assert_eq!(dl.back(), Some(&1));

pub fn back_mut(&mut self) -> Option<&mut T>

Provides a mutable reference to the back element, or None if the list is empty.

Examples

use kalloc::list::List;

let mut dl = List::new();
assert_eq!(dl.back(), None);

dl.push_back(1);
assert_eq!(dl.back(), Some(&1));

match dl.back_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(dl.back(), Some(&5));

pub fn push_front(&mut self, elt: T) -> Result<(), AllocError>

Adds an element first in the list.

This operation should compute in O(1) time.

Examples

use kalloc::list::List;

let mut dl = List::new();

dl.push_front(2);
assert_eq!(dl.front().unwrap(), &2);

dl.push_front(1);
assert_eq!(dl.front().unwrap(), &1);

pub fn pop_front(&mut self) -> Option<T>

Removes the first element and returns it, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use kalloc::list::List;

let mut d = List::new();
assert_eq!(d.pop_front(), None);

d.push_front(1);
d.push_front(3);
assert_eq!(d.pop_front(), Some(3));
assert_eq!(d.pop_front(), Some(1));
assert_eq!(d.pop_front(), None);

pub fn push_back(&mut self, elt: T) -> Result<(), AllocError>

Appends an element to the back of a list.

This operation should compute in O(1) time.

Examples

use kalloc::list::List;

let mut d = List::new();
d.push_back(1);
d.push_back(3);
assert_eq!(3, *d.back().unwrap());

pub fn pop_back(&mut self) -> Option<T>

Removes the last element from a list and returns it, or None if it is empty.

This operation should compute in O(1) time.

Examples

use kalloc::list::List;

let mut d = List::new();
assert_eq!(d.pop_back(), None);
d.push_back(1);
d.push_back(3);
assert_eq!(d.pop_back(), Some(3));

pub fn split_off(&mut self, at: usize) -> List<T>

Splits the list into two at the given index. Returns everything after the given index, including the index.

This operation should compute in O(n) time.

Panics

Panics if at > len.

Examples

use kalloc::list::List;

let mut d = List::new();

d.push_front(1);
d.push_front(2);
d.push_front(3);

let mut split = d.split_off(2);

assert_eq!(split.pop_front(), Some(1));
assert_eq!(split.pop_front(), None);

pub fn remove(&mut self, at: usize) -> T

Removes the element at the given index and returns it.

This operation should compute in O(n) time.

Panics

Panics if at >= len

Examples

#![feature(linked_list_remove)]
use kalloc::list::List;

let mut d = List::new();

d.push_front(1);
d.push_front(2);
d.push_front(3);

assert_eq!(d.remove(1), 2);
assert_eq!(d.remove(0), 3);
assert_eq!(d.remove(0), 1);

Trait Implementations

impl<T: Debug> Debug for List<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for List<T>

fn default() -> Self

Creates an empty List<T>.

impl<T> Drop for List<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T: Hash> Hash for List<T>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<T> IntoIterator for List<T>

fn into_iter(self) -> IntoIter<T>

Consumes the list into an iterator yielding elements by value.

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

impl<'a, T> IntoIterator for &'a List<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut List<T>

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IterMut<'a, T>

Creates an iterator from a value.

impl<T: Ord> Ord for List<T>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

#[must_use]

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]

fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq<List<T>> for List<T>

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Self) -> bool

This method tests for !=.

impl<T: PartialOrd> PartialOrd<List<T>> for List<T>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use]

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use]

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use]

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use]

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T: Eq> Eq for List<T>

impl<T: Send> Send for List<T>

impl<T: Sync> Sync for List<T>