Trait scc::LinkedList
source · [−]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 Self::mark
or Self::delete_self
has been
invoked.
Provided methods
Returns true
if self
is reachable and not marked.
Examples
use scc::LinkedList;
use scc::ebr::{AtomicArc, Tag};
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 a flag has already been marked on self
.
Examples
use scc::LinkedList;
use scc::ebr::AtomicArc;
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 no flag has been marked on self
.
Examples
use scc::LinkedList;
use scc::ebr::AtomicArc;
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::LinkedList;
use scc::ebr::AtomicArc;
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));
fn delete_self(&self, order: Ordering) -> bool
fn delete_self(&self, order: Ordering) -> bool
Deletes self
.
It returns false
if self
already has deleted
marked on it.
Examples
use scc::LinkedList;
use scc::ebr::{Arc, AtomicArc, Barrier};
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());
fn is_deleted(&self, order: Ordering) -> bool
fn is_deleted(&self, order: Ordering) -> bool
Returns true
if self
has been deleted.
Examples
use scc::LinkedList;
use scc::ebr::AtomicArc;
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::LinkedList;
use scc::ebr::{Arc, AtomicArc, Barrier};
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::LinkedList;
use scc::ebr::{Arc, AtomicArc, Barrier};
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));