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 pseudocode found in the paper.

This implementation does not want to have the restriction of a garbage collector for reclamation of buffers, and instead it uses a shared pool of buffers. This shared pool is required for correctness in this implementation.

The only lock-synchronized portions of this deque are the buffer allocation and deallocation portions. Otherwise all operations are lock-free.

Example

use deque::BufferPool;

let mut pool = BufferPool::new();
let (mut worker, mut stealer) = pool.deque();

// 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 mut stealer2 = stealer.clone();
stealer2.steal();