Single consumer only.
| 86 | |
| 87 | // Single consumer only. |
| 88 | T* dequeue() |
| 89 | { |
| 90 | auto currentTail = tail; |
| 91 | |
| 92 | // Check and see if there is an actual element linked from `tail` |
| 93 | // since we use `tail` as a "stub" rather than the actual element. |
| 94 | auto nextTail = currentTail->next.load(std::memory_order_acquire); |
| 95 | |
| 96 | // There are three possible cases here: |
| 97 | // |
| 98 | // (1) The queue is empty. |
| 99 | // (2) The queue appears empty but a producer is still enqueuing |
| 100 | // so let's wait for it and then dequeue. |
| 101 | // (3) We have something to dequeue. |
| 102 | // |
| 103 | // Start by checking if the queue is or appears empty. |
| 104 | if (nextTail == nullptr) { |
| 105 | // Now check if the queue is actually empty or just appears |
| 106 | // empty. If it's actually empty then return `nullptr` to denote |
| 107 | // emptiness. |
| 108 | if (head.load(std::memory_order_relaxed) == tail) { |
| 109 | return nullptr; |
| 110 | } |
| 111 | |
| 112 | // Another thread already inserted a new node, but did not |
| 113 | // connect it to the tail, yet, so we spin-wait. At this point |
| 114 | // we are not wait-free anymore. |
| 115 | do { |
| 116 | nextTail = currentTail->next.load(std::memory_order_acquire); |
| 117 | } while (nextTail == nullptr); |
| 118 | } |
| 119 | |
| 120 | CHECK_NOTNULL(nextTail); |
| 121 | |
| 122 | // Set next pointer of current tail to null to disconnect it |
| 123 | // from the queue. |
| 124 | currentTail->next.store(nullptr, std::memory_order_release); |
| 125 | |
| 126 | auto element = nextTail->element; |
| 127 | nextTail->element = nullptr; |
| 128 | |
| 129 | tail = nextTail; |
| 130 | delete currentTail; |
| 131 | |
| 132 | return element; |
| 133 | } |
| 134 | |
| 135 | // Single consumer only. |
| 136 | // |