Crate deque

Source
Expand description

A (mostly) lock-free concurrent work-stealing deque

This module contains an implementation of the Chase-Lev work stealing deque described in “Dynamic Circular Work-Stealing Deque”. The implementation is heavily based on the implementation using C11 atomics in “Correct and Efficient Work Stealing for Weak Memory Models”.

The only potentially lock-synchronized portion of this deque is the occasional call to the memory allocator when growing the deque. Otherwise all operations are lock-free.

§Example

use deque;

let (worker, stealer) = deque::new();

// Only the worker may push/pop
worker.push(1);
worker.pop();

// Stealers take data from the other end of the deque
worker.push(1);
stealer.steal();

// Stealers can be cloned to have many stealers stealing in parallel
worker.push(1);
let stealer2 = stealer.clone();
stealer2.steal();

Re-exports§

pub use self::Stolen::*;

Structs§

Stealer
The stealing half of the work-stealing deque. Stealers have access to the opposite end of the deque from the worker, and they only have access to the steal method.
Worker
Worker half of the work-stealing deque. This worker has exclusive access to one side of the deque, and uses push and pop method to manipulate it.

Enums§

Stolen
When stealing some data, this is an enumeration of the possible outcomes.

Functions§

new
Allocates a new work-stealing deque.