fast 0.4.0

A helper library
Documentation 
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

use core::pin::pin;
use core::sync::atomic::Ordering::*;
use core::{
    cell::UnsafeCell,
    marker::PhantomData,
    mem,
    ops::{Deref, DerefMut},
    pin::Pin,
    ptr,
    sync::atomic::{AtomicBool, AtomicPtr, AtomicUsize},
    task::{Poll, Waker},
};

use alloc::boxed::Box;

pub type AtomicNode<T> = AtomicPtr<Node<T>>;

pub struct Queue<T> {
    head: AtomicNode<T>,
    tail: AtomicNode<T>,

    len: AtomicUsize,
}

pub struct Node<T> {
    val: T,
    next: AtomicNode<T>,
}

impl<T: Send> Queue<T> {
    pub fn len(&self) -> usize {
        self.len.load(Acquire)
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
    pub const fn new() -> Self {
        Self {
            head: AtomicPtr::new(ptr::null_mut()),
            tail: AtomicPtr::new(ptr::null_mut()),
            len: AtomicUsize::new(0),
        }
    }

    pub unsafe fn enqueue(&self, value: T) {
        let node = Box::into_raw(Box::new(Node {
            val: value,
            next: AtomicPtr::new(ptr::null_mut()),
        }));

        loop {
            let tail = self.tail.load(Acquire);

            // If empty queue
            if tail.is_null() {
                if let Ok(_) =
                    self.head
                        .compare_exchange_weak(ptr::null_mut(), node, Release, Acquire)
                {
                    self.tail.store(node, Release);
                    self.len.fetch_add(1, AcqRel);
                    return;
                }
                continue;
            }

            // Non-empty queue - try to link to current tail
            if let Ok(_) =
                (*tail)
                    .next
                    .compare_exchange_weak(ptr::null_mut(), node, Release, Acquire)
            {
                self.tail.store(node, Release);
                self.len.fetch_add(1, AcqRel);
                return;
            }
        }
    }

    pub unsafe fn dequeue(&self) -> Option<T> {
        loop {
            let head = self.head.load(Acquire);
            if head.is_null() {
                return None;
            }

            let next = (*head).next.load(Acquire);

            if let Ok(_) = self
                .head
                .compare_exchange_weak(head, next, Release, Acquire)
            {
                if next.is_null() {
                    self.tail.store(ptr::null_mut(), Release);
                }

                let node = Box::from_raw(head);
                self.len.fetch_sub(1, AcqRel);
                return Some(node.val);
            }
        }
    }
}