| 283 | // moves front to result using operator=, then returns true. |
| 284 | template<typename U> |
| 285 | bool try_dequeue(U& result) AE_NO_TSAN |
| 286 | { |
| 287 | #ifndef NDEBUG |
| 288 | ReentrantGuard guard(this->dequeuing); |
| 289 | #endif |
| 290 | |
| 291 | // High-level pseudocode: |
| 292 | // Remember where the tail block is |
| 293 | // If the front block has an element in it, dequeue it |
| 294 | // Else |
| 295 | // If front block was the tail block when we entered the function, return false |
| 296 | // Else advance to next block and dequeue the item there |
| 297 | |
| 298 | // Note that we have to use the value of the tail block from before we check if the front |
| 299 | // block is full or not, in case the front block is empty and then, before we check if the |
| 300 | // tail block is at the front block or not, the producer fills up the front block *and |
| 301 | // moves on*, which would make us skip a filled block. Seems unlikely, but was consistently |
| 302 | // reproducible in practice. |
| 303 | // In order to avoid overhead in the common case, though, we do a double-checked pattern |
| 304 | // where we have the fast path if the front block is not empty, then read the tail block, |
| 305 | // then re-read the front block and check if it's not empty again, then check if the tail |
| 306 | // block has advanced. |
| 307 | |
| 308 | Block* frontBlock_ = frontBlock.load(); |
| 309 | size_t blockTail = frontBlock_->localTail; |
| 310 | size_t blockFront = frontBlock_->front.load(); |
| 311 | |
| 312 | if (blockFront != blockTail || blockFront != (frontBlock_->localTail = frontBlock_->tail.load())) { |
| 313 | fence(memory_order_acquire); |
| 314 | |
| 315 | non_empty_front_block: |
| 316 | // Front block not empty, dequeue from here |
| 317 | auto element = reinterpret_cast<T*>(frontBlock_->data + blockFront * sizeof(T)); |
| 318 | result = std::move(*element); |
| 319 | element->~T(); |
| 320 | |
| 321 | blockFront = (blockFront + 1) & frontBlock_->sizeMask; |
| 322 | |
| 323 | fence(memory_order_release); |
| 324 | frontBlock_->front = blockFront; |
| 325 | } |
| 326 | else if (frontBlock_ != tailBlock.load()) { |
| 327 | fence(memory_order_acquire); |
| 328 | |
| 329 | frontBlock_ = frontBlock.load(); |
| 330 | blockTail = frontBlock_->localTail = frontBlock_->tail.load(); |
| 331 | blockFront = frontBlock_->front.load(); |
| 332 | fence(memory_order_acquire); |
| 333 | |
| 334 | if (blockFront != blockTail) { |
| 335 | // Oh look, the front block isn't empty after all |
| 336 | goto non_empty_front_block; |
| 337 | } |
| 338 | |
| 339 | // Front block is empty but there's another block ahead, advance to it |
| 340 | Block* nextBlock = frontBlock_->next; |
| 341 | // Don't need an acquire fence here since next can only ever be set on the tailBlock, |
| 342 | // and we're not the tailBlock, and we did an acquire earlier after reading tailBlock which |