Method dequeue

include/dmlc/concurrentqueue.h:1902–2000

    template<typename U>
    bool dequeue(U &element) {
      auto tail = this->tailIndex.load(std::memory_order_relaxed);
      auto overcommit = this->dequeueOvercommit.load(std::memory_order_relaxed);
      if (details::circular_less_than<index_t>(
        this->dequeueOptimisticCount.load(std::memory_order_relaxed) - overcommit, tail)) {
        // Might be something to dequeue, let's give it a try

        // Note that this if is purely for performance purposes in the common case when the queue is
        // empty and the values are eventually consistent -- we may enter here spuriously.

        // Note that whatever the values of overcommit and tail are, they are not going to change (unless we
        // change them) and must be the same value at this point (inside the if) as when the if condition was
        // evaluated.

        // We insert an acquire fence here to synchronize-with the release upon incrementing dequeueOvercommit below.
        // This ensures that whatever the value we got loaded into overcommit, the load of dequeueOptisticCount in
        // the fetch_add below will result in a value at least as recent as that (and therefore at least as large).
        // Note that I believe a compiler (signal) fence here would be sufficient due to the nature of fetch_add (all
        // read-modify-write operations are guaranteed to work on the latest value in the modification order), but
        // unfortunately that can't be shown to be correct using only the C++11 standard.
        // See http://stackoverflow.com/questions/18223161/what-are-the-c11-memory-ordering-guarantees-in-this-corner-case
        std::atomic_thread_fence(std::memory_order_acquire);

        // Increment optimistic counter, then check if it went over the boundary
        auto myDequeueCount = this->dequeueOptimisticCount.fetch_add(1, std::memory_order_relaxed);

        // Note that since dequeueOvercommit must be <= dequeueOptimisticCount (because dequeueOvercommit is only ever
        // incremented after dequeueOptimisticCount -- this is enforced in the `else` block below), and since we now
        // have a version of dequeueOptimisticCount that is at least as recent as overcommit (due to the release upon
        // incrementing dequeueOvercommit and the acquire above that synchronizes with it), overcommit <= myDequeueCount.
        assert(overcommit <= myDequeueCount);

        // Note that we reload tail here in case it changed; it will be the same value as before or greater, since
        // this load is sequenced after (happens after) the earlier load above. This is supported by read-read
        // coherency (as defined in the standard), explained here: http://en.cppreference.com/w/cpp/atomic/memory_order
        tail = this->tailIndex.load(std::memory_order_acquire);
        if (details::likely(
          details::circular_less_than<index_t>(myDequeueCount - overcommit, tail))) {
          // Guaranteed to be at least one element to dequeue!

          // Get the index. Note that since there's guaranteed to be at least one element, this
          // will never exceed tail. We need to do an acquire-release fence here since it's possible
          // that whatever condition got us to this point was for an earlier enqueued element (that
          // we already see the memory effects for), but that by the time we increment somebody else
          // has incremented it, and we need to see the memory effects for *that* element, which is
          // in such a case is necessarily visible on the thread that incremented it in the first
          // place with the more current condition (they must have acquired a tail that is at least
          // as recent).
          auto index = this->headIndex.fetch_add(1, std::memory_order_acq_rel);


          // Determine which block the element is in

          auto localBlockIndex = blockIndex.load(std::memory_order_acquire);
          auto localBlockIndexHead = localBlockIndex->front.load(std::memory_order_acquire);

          // We need to be careful here about subtracting and dividing because of index wrap-around.
          // When an index wraps, we need to preserve the sign of the offset when dividing it by the