Struct drone_core::sync::linked_list::LinkedList

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

A lock-free singly-linked list.

Implementations

impl<T> LinkedList<T>

pub const fn new() -> Self

Creates an empty LinkedList.

Examples

use drone_core::sync::LinkedList;

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

pub fn is_empty(&self) -> bool

Returns true if the LinkedList is empty.

This operation should compute in O(1) time.

Examples

use drone_core::sync::LinkedList;

let list = LinkedList::new();
assert!(list.is_empty());

list.push("foo");
assert!(!list.is_empty());

pub fn push(&self, data: T)

Adds an element first in the list.

This operation should compute in O(1) time.

Examples

use drone_core::sync::LinkedList;

let list = LinkedList::new();

list.push(2);
list.push(1);
assert_eq!(list.pop().unwrap(), 1);
assert_eq!(list.pop().unwrap(), 2);

pub unsafe fn push_raw(&self, node: *mut Node<T>)

Adds a pre-allocated element first in the list.

This operation should compute in O(1) time.

Examples

use drone_core::sync::linked_list::{LinkedList, Node};

let list = LinkedList::new();

let foo = Box::into_raw(Box::new(Node::from("foo")));
unsafe { list.push_raw(foo) };
assert_eq!(unsafe { **foo }, "foo");

Safety

The node parameter must point to a valid allocation. Other list methods, which drop nodes in-place, assume that node is created using Box::from_raw.

pub fn pop(&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 drone_core::sync::LinkedList;

let d = LinkedList::new();
assert_eq!(d.pop(), None);

d.push(1);
d.push(3);
assert_eq!(d.pop(), Some(3));
assert_eq!(d.pop(), Some(1));
assert_eq!(d.pop(), None);

pub unsafe fn pop_raw(&self) -> Option<*mut Node<T>>

Removes the first element and returns a raw pointer to it, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use drone_core::sync::linked_list::{LinkedList, Node};

let list = LinkedList::new();

let foo = Box::into_raw(Box::new(Node::from("foo")));
unsafe {
    list.push_raw(foo);
    let foo = list.pop_raw().unwrap();
    list.push_raw(foo);
}

assert_eq!(unsafe { **foo }, "foo");

Safety

It’s responsibility of the caller to de-allocate the node.

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

Provides a forward iterator with mutable references.

Examples

use drone_core::sync::LinkedList;

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

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

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

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

pub unsafe fn iter_mut_unchecked(&self) -> IterMut<'_, T>

Unsafe variant of [iter_mut] with non-mutable self.

Safety

While the returned iterator is alive:

• Nodes shouldn’t be removed.
• No other methods that produce mutable references (including this method) should be called.

pub fn drain_filter<'a, F: 'a>(
    &'a mut self,
    filter: F
) -> DrainFilter<'_, T, impl FnMut(*mut Node<T>) -> bool> where
    F: FnMut(&mut T) -> bool, 

Creates an iterator which uses a closure to determine if an element should be removed.

If the closure returns true, then the element is removed and yielded. If the closure returns false, the element will remain in the list and will not be yielded by the iterator.

Note that drain_filter lets you mutate every element in the filter closure, regardless of whether you choose to keep or remove it.

Examples

Splitting a list into evens and odds, reusing the original list:

use drone_core::sync::LinkedList;

let mut numbers: LinkedList<u32> = LinkedList::new();
numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);

let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>();
let odds = numbers;

assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]);
assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![15, 13, 11, 9, 5, 3, 1]);

pub unsafe fn drain_filter_raw<F>(
    &self,
    filter: F
) -> DrainFilterRaw<'_, T, impl FnMut(*mut Node<T>) -> bool> where
    F: FnMut(*mut Node<T>) -> bool, 

Raw variant of [drain_filter].

Safety

It’s responsibility of the caller to de-allocate returned nodes.

While the returned iterator is alive:

• Nodes shouldn’t be removed.
• No other methods that produce mutable references (including this method) should be called.

Trait Implementations

impl<T> Drop for LinkedList<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T>

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> Extend<T> for LinkedList<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> FromIterator<T> for LinkedList<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T> IntoIterator for LinkedList<T>

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Sync for LinkedList<T>