      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181

    // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
    // file at the top-level directory of this distribution and at
    // http://rust-lang.org/COPYRIGHT.
    //
    // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
    // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
    // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
    // option. This file may not be copied, modified, or distributed
    // except according to those terms.

    //! A mostly lock-free multi-producer, single consumer queue.
    //!
    //! This module contains an implementation of a concurrent MPSC queue. This
    //! queue can be used to share data between threads, and is also used as the
    //! building block of channels in rust.
    //!
    //! Note that the current implementation of this queue has a caveat of the `pop`
    //! method, and see the method for more information about it. Due to this
    //! caveat, this queue may not be appropriate for all use-cases.

    // http://www.1024cores.net/home/lock-free-algorithms
    //                         /queues/non-intrusive-mpsc-node-based-queue

    pub use self::PopResult::*;

    use alloc::boxed::Box;
    use core::ptr;
    use core::cell::UnsafeCell;

    use sync::atomic::{AtomicPtr, Ordering};

    /// A result of the `pop` function.
    pub enum PopResult<T> {
        /// Some data has been popped
        Data(T),
        /// The queue is empty
        Empty,
        /// The queue is in an inconsistent state. Popping data should succeed, but
        /// some pushers have yet to make enough progress in order allow a pop to
        /// succeed. It is recommended that a pop() occur "in the near future" in
        /// order to see if the sender has made progress or not
        Inconsistent,
    }

    struct Node<T> {
        next: AtomicPtr<Node<T>>,
        value: Option<T>,
    }

    /// The multi-producer single-consumer structure. This is not cloneable, but it
    /// may be safely shared so long as it is guaranteed that there is only one
    /// popper at a time (many pushers are allowed).
    pub struct Queue<T> {
        head: AtomicPtr<Node<T>>,
        tail: UnsafeCell<*mut Node<T>>,
    }

    unsafe impl<T: Send> Send for Queue<T> { }
    unsafe impl<T: Send> Sync for Queue<T> { }

    impl<T> Node<T> {
        unsafe fn new(v: Option<T>) -> *mut Node<T> {
            Box::into_raw(box Node {
                next: AtomicPtr::new(ptr::null_mut()),
                value: v,
            })
        }
    }

    impl<T> Queue<T> {
        /// Creates a new queue that is safe to share among multiple producers and
        /// one consumer.
        pub fn new() -> Queue<T> {
            let stub = unsafe { Node::new(None) };
            Queue {
                head: AtomicPtr::new(stub),
                tail: UnsafeCell::new(stub),
            }
        }

        /// Pushes a new value onto this queue.
        pub fn push(&self, t: T) {
            unsafe {
                let n = Node::new(Some(t));
                let prev = self.head.swap(n, Ordering::AcqRel);
                (*prev).next.store(n, Ordering::Release);
            }
        }

        /// Pops some data from this queue.
        ///
        /// Note that the current implementation means that this function cannot
        /// return `Option<T>`. It is possible for this queue to be in an
        /// inconsistent state where many pushes have succeeded and completely
        /// finished, but pops cannot return `Some(t)`. This inconsistent state
        /// happens when a pusher is pre-empted at an inopportune moment.
        ///
        /// This inconsistent state means that this queue does indeed have data, but
        /// it does not currently have access to it at this time.
        pub fn pop(&self) -> PopResult<T> {
            unsafe {
                let tail = *self.tail.get();
                let next = (*tail).next.load(Ordering::Acquire);

                if !next.is_null() {
                    *self.tail.get() = next;
                    assert!((*tail).value.is_none());
                    assert!((*next).value.is_some());
                    let ret = (*next).value.take().unwrap();
                    let _: Box<Node<T>> = Box::from_raw(tail);
                    return Data(ret);
                }

                if self.head.load(Ordering::Acquire) == tail {Empty} else {Inconsistent}
            }
        }
    }

    impl<T> Drop for Queue<T> {
        fn drop(&mut self) {
            unsafe {
                let mut cur = *self.tail.get();
                while !cur.is_null() {
                    let next = (*cur).next.load(Ordering::Relaxed);
                    let _: Box<Node<T>> = Box::from_raw(cur);
                    cur = next;
                }
            }
        }
    }

    #[cfg(all(test, not(target_os = "emscripten")))]
    mod tests {
        use sync::mpsc::channel;
        use super::{Queue, Data, Empty, Inconsistent};
        use sync::Arc;
        use thread;

        #[test]
        fn test_full() {
            let q: Queue<Box<_>> = Queue::new();
            q.push(box 1);
            q.push(box 2);
        }

        #[test]
        fn test() {
            let nthreads = 8;
            let nmsgs = 1000;
            let q = Queue::new();
            match q.pop() {
                Empty => {}
                Inconsistent | Data(..) => panic!()
            }
            let (tx, rx) = channel();
            let q = Arc::new(q);

            for _ in 0..nthreads {
                let tx = tx.clone();
                let q = q.clone();
                thread::spawn(move|| {
                    for i in 0..nmsgs {
                        q.push(i);
                    }
                    tx.send(()).unwrap();
                });
            }

            let mut i = 0;
            while i < nthreads * nmsgs {
                match q.pop() {
                    Empty | Inconsistent => {},
                    Data(_) => { i += 1 }
                }
            }
            drop(tx);
            for _ in 0..nthreads {
                rx.recv().unwrap();
            }
        }
    }

# Help

## Keyboard Shortcuts

?
  Show this help dialog
S
  Focus the search field
⇤
  Move up in search results
⇥
  Move down in search results
⏎
  Go to active search result
+
  Collapse/expand all sections

## Search Tricks

Prefix searches with a type followed by a colon (e.g. `fn:`) to restrict the search to a given type.

Accepted types are: `fn`, `mod`, `struct`, `enum`, `trait`, `type`, `macro`, and `const`.

Search functions by type signature (e.g. `vec -> usize` or `* -> vec`)