Trait scc::LinkedList[−][src]

pub trait LinkedList: 'static + Sized {
    fn link_ref(&self) -> &AtomicArc<Self>;

    fn is_clear(&self, order: Ordering) -> bool { ... }

    fn mark(&self, order: Ordering) -> bool { ... }

    fn unmark(&self, order: Ordering) -> bool { ... }

    fn is_marked(&self, order: Ordering) -> bool { ... }

    fn delete_self(&self, order: Ordering) -> bool { ... }

    fn is_deleted(&self, order: Ordering) -> bool { ... }

    fn push_back<'b>(
        &self, 
        entry: Arc<Self>, 
        mark: bool, 
        order: Ordering, 
        barrier: &'b Barrier
    ) -> Result<Ptr<'b, Self>, Arc<Self>> { ... }

    fn next_ptr<'b>(
        &self, 
        order: Ordering, 
        barrier: &'b Barrier
    ) -> Ptr<'b, Self> { ... }
}
Expand description

LinkedList is a wait-free self-referential singly linked list.

Required methods

Returns a reference to the forward link.

The pointer value may be tagged if the entry is no longer a member of the linked list.

Provided methods

Returns true if self is reachable, and not marked.

Examples

use scc::ebr::{AtomicArc, Tag};
use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicArc<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicArc<L> {
        &self.0
    }
}

let head: L = L::default();
assert!(head.is_clear(Relaxed));
assert!(head.mark(Relaxed));
assert!(!head.is_clear(Relaxed));
assert!(head.delete_self(Relaxed));
assert!(!head.is_clear(Relaxed));

Marks self with an internal flag to denote that self is in a special state.

It returns false if nothing is marked on self.

Examples

use scc::ebr::AtomicArc;
use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicArc<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicArc<L> {
        &self.0
    }
}

let head: L = L::default();
assert!(head.mark(Relaxed));

Removes marks from self.

It returns false if nothing is marked on self.

Examples

use scc::ebr::AtomicArc;
use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicArc<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicArc<L> {
        &self.0
    }
}

let head: L = L::default();
assert!(!head.unmark(Relaxed));
assert!(head.mark(Relaxed));
assert!(head.unmark(Relaxed));
assert!(!head.is_marked(Relaxed));

Returns true if self has a mark on it.

Examples

use scc::ebr::AtomicArc;
use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicArc<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicArc<L> {
        &self.0
    }
}

let head: L = L::default();
assert!(!head.is_marked(Relaxed));
assert!(head.mark(Relaxed));
assert!(head.is_marked(Relaxed));

Deletes self.

It returns false if self already has deleted marked on it.

Examples

use scc::ebr::{Arc, AtomicArc, Barrier};
use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicArc<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicArc<L> {
        &self.0
    }
}

let barrier = Barrier::new();

let head: L = L::default();
let tail: Arc<L> = Arc::new(L::default());
assert!(head.push_back(tail.clone(), false, Relaxed, &barrier).is_ok());

tail.delete_self(Relaxed);
assert!(head.next_ptr(Relaxed, &barrier).as_ref().is_none());

Returns true if self has been deleted.

Examples

use scc::ebr::AtomicArc;
use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicArc<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicArc<L> {
        &self.0
    }
}

let entry: L = L::default();
assert!(!entry.is_deleted(Relaxed));
entry.delete_self(Relaxed);
assert!(entry.is_deleted(Relaxed));

Appends the given entry after self, and returns a pointer to the entry.

If mark is given true, it atomically marks an internal flag on self when updating the linked list, otherwise it removes marks.

Errors

It returns the supplied Arc when it finds self deleted.

Examples

use scc::ebr::{Arc, AtomicArc, Barrier};
use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicArc<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicArc<L> {
        &self.0
    }
}

let barrier = Barrier::new();

let head: L = L::default();
assert!(head.push_back(Arc::new(L::default()), true, Relaxed, &barrier).is_ok());
assert!(head.is_marked(Relaxed));
assert!(head.push_back(Arc::new(L::default()), false, Relaxed, &barrier).is_ok());
assert!(!head.is_marked(Relaxed));

head.delete_self(Relaxed);
assert!(!head.is_marked(Relaxed));
assert!(head.push_back(Arc::new(L::default()), false, Relaxed, &barrier).is_err());

Returns the closest next valid entry.

It unlinks deleted entries until it reaches a valid one.

Examples

use scc::ebr::{Arc, AtomicArc, Barrier};
use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicArc<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicArc<L> {
        &self.0
    }
}

let barrier = Barrier::new();

let head: L = L::default();
assert!(head.push_back(Arc::new(L(AtomicArc::null(), 1)), false, Relaxed, &barrier).is_ok());
head.mark(Relaxed);

let next_ptr = head.next_ptr(Relaxed, &barrier);
assert_eq!(next_ptr.as_ref().unwrap().1, 1);
assert!(head.is_marked(Relaxed));

Implementors