Crate deque

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.