Module coco::deque [−] [src]

A lock-free work-stealing deque.

There is one worker and possibly multiple stealers per deque. The worker has exclusive access to one side of the deque and may push and pop elements. Stealers can only steal (i.e. pop) elements from the other side.

The implementation is based on the following papers:

  1. Dynamic Circular Work-Stealing Deque pdf
  2. Correct and Efficient Work-Stealing for Weak Memory Models pdf
  3. CDSChecker: Checking Concurrent Data Structures Written with C/C++ Atomics pdf code

Examples

use coco::deque;

let (w, s) = deque::new();

// Create some work.
for i in 0..1000 {
    w.push(i);
}

let threads = (0..4).map(|_| {
    let s = s.clone();
    std::thread::spawn(move || {
        while let Some(x) = s.steal() {
            // Do something with `x`...
        }
    })
}).collect::<Vec<_>>();

while let Some(x) = w.pop() {
    // Do something with `x`...
    // Or create even more work...
    if x > 1 {
        w.push(x / 2);
        w.push(x / 2);
    }
}

for t in threads {
    t.join().unwrap();
}

Structs

Stealer

Stealer side of a work-stealing deque.
Worker

Worker side of a work-stealing deque.

Enums

Steal

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

Functions

new

Returns a new work-stealing deque.