proxygen: folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::RelaxedConcurrentPriorityQueue ( )

inline

Constructor.

Definition at line 207 of file RelaxedConcurrentPriorityQueue.h.

References i, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MAX_LEVELS, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::top_loc_, and uint32_t.

       : cticket_(1), pticket_(1), counter_p_(0), counter_c_(0) {
     if (MayBlock) {
       futex_array_.reset(new folly::detail::Futex<Atom>[NumFutex]);
     }
 
     if (PopBatch > 0) {
       top_loc_ = -1;
       shared_buffer_.reset(new BufferNode[PopBatch]);
       for (size_t i = 0; i < PopBatch; i++) {
         shared_buffer_[i].pnode = nullptr;
       }
     }
     bottom_.store(0, std::memory_order_relaxed);
     guard_.store(0, std::memory_order_relaxed);
     // allocate the root MoundElement and initialize Mound
     levels_[0] = new MoundElement[1]; // default MM for MoundElement
     for (uint32_t i = 1; i < MAX_LEVELS; i++) {
       levels_[i] = nullptr;
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::~RelaxedConcurrentPriorityQueue ( )

inline

Definition at line 229 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deleteAllNodes(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deleteSharedBuffer(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getBottomLevel(), i, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level.

                                     {
     if (PopBatch > 0) {
       deleteSharedBuffer();
     }
     if (MayBlock) {
       futex_array_.reset();
     }
     Position pos;
     pos.level = pos.index = 0;
     deleteAllNodes(pos);
     // default MM for MoundElement
     for (int i = getBottomLevel(); i >= 0; i--) {
       delete[] levels_[i];
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::binarySearchPosition	(	Position &	cur,
		const T &	val,
		folly::hazptr_holder< Atom > &	hptr
	)

inlineprivate

Definition at line 807 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::optimisticReadValue(), parent, and folly::T.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPush().

                                       {
     Position parent, mid;
     if (cur.level == 0) {
       return;
     }
     // start from the root
     parent.level = parent.index = 0;
 
     while (true) { // binary search
       mid.level = (cur.level + parent.level) / 2;
       mid.index = cur.index >> (cur.level - mid.level);
 
       T mv = optimisticReadValue(mid, hptr);
       if (val < mv) {
         parent = mid;
       } else {
         cur = mid;
       }
 
       if (mid.level == 0 || // the root
           ((parent.level + 1 == cur.level) && parent.level != 0)) {
         return;
       }
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::blockingPopImpl ( )

inlineprivate

Definition at line 1122 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::cticket_, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::futexIsReady(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryBlockingPop().

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPop().

                          {
     auto ct = cticket_.fetch_add(1, std::memory_order_acq_rel);
     // fast path check
     if (futexIsReady(ct)) {
       return;
     }
     // Blocking
     tryBlockingPop(ct);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::blockingPushImpl ( )

inlineprivate

Definition at line 1028 of file RelaxedConcurrentPriorityQueue.h.

References folly::detail::futexWake(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getFutexArrayLoc(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::pticket_, uint32_t, and UNLIKELY.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPush().

                           {
     auto p = pticket_.fetch_add(1, std::memory_order_acq_rel);
     auto loc = getFutexArrayLoc(p);
     uint32_t curfutex = futex_array_[loc].load(std::memory_order_acquire);
 
     while (true) {
       uint32_t ready = p << 1; // get the lower 31 bits
       // avoid the situation that push has larger ticket already set the value
       if (UNLIKELY(
               ready + 1 < curfutex ||
               ((curfutex > ready) && (curfutex - ready > 0x40000000)))) {
         return;
       }
 
       if (futex_array_[loc].compare_exchange_strong(curfutex, ready)) {
         if (curfutex &
             1) { // One or more consumers may be blocked on this futex
           detail::futexWake(&futex_array_[loc]);
         }
         return;
       } else {
         curfutex = futex_array_[loc].load(std::memory_order_acquire);
       }
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deferSettingRootSize ( Position & pos )

inlineprivate

Definition at line 944 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPopMany().

                                            {
     if (isLeaf(pos)) {
       setElementSize(pos, 0);
       unlockNode(pos);
       return true;
     }
 
     // acquire locks for L and R and compare
     Position lchild = leftOf(pos);
     Position rchild = rightOf(pos);
     lockNode(lchild);
     lockNode(rchild);
     if (getElementSize(lchild) == 0 && getElementSize(rchild) == 0) {
       setElementSize(pos, 0);
       unlockNode(pos);
       unlockNode(lchild);
       unlockNode(rchild);
       return true;
     } else {
       // read values
       T lv = readValue(lchild);
       T rv = readValue(rchild);
       if (lv >= rv) {
         swapList(lchild, pos);
         setElementSize(lchild, 0);
         unlockNode(pos);
         unlockNode(rchild);
         pos = lchild;
       } else {
         swapList(rchild, pos);
         setElementSize(rchild, 0);
         unlockNode(pos);
         unlockNode(lchild);
         pos = rchild;
       }
       return false;
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deleteAllNodes ( const Position & pos )

inlineprivate

This function is only called by the destructor.

Definition at line 293 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getElementSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getList(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isLeaf(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::leftOf(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Node::next, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::rightOf(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::setTreeNode().

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::~RelaxedConcurrentPriorityQueue().

                                            {
     if (getElementSize(pos) == 0) {
       // current list is empty, do not need to check
       // its children again.
       return;
     }
 
     Node* curList = getList(pos);
     setTreeNode(pos, nullptr);
     while (curList != nullptr) { // reclaim nodes
       Node* n = curList;
       curList = curList->next;
       delete n;
     }
 
     if (!isLeaf(pos)) {
       deleteAllNodes(leftOf(pos));
       deleteAllNodes(rightOf(pos));
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deleteSharedBuffer ( )

inlineprivate

This function is only called by the destructor.

Definition at line 280 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::top_loc_.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::~RelaxedConcurrentPriorityQueue().

                             {
     DCHECK(PopBatch > 0);
     // delete nodes in the buffer
     int loc = top_loc_.load(std::memory_order_relaxed);
     while (loc >= 0) {
       Node* n = shared_buffer_[loc--].pnode.load(std::memory_order_relaxed);
       delete n;
     }
     // delete buffer
     shared_buffer_.reset();
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::empty ( )

inline

Returns true only if the queue was empty during the call.

Definition at line 270 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isEmpty().

                {
     return isEmpty();
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::forceInsert	(	const Position &	pos,
		const T &	val,
		Node *	newNode
	)

inlineprivate

Definition at line 771 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPush().

                                                                      {
     if (isRoot(pos)) {
       return forceInsertToRoot(newNode);
     }
 
     while (true) {
       std::unique_lock<Mutex> lck(
           levels_[pos.level][pos.index].lock, std::try_to_lock);
       if (!lck.owns_lock()) {
         if (getElementSize(pos) < ListTargetSize && readValue(pos) >= val) {
           continue;
         } else {
           return false;
         }
       }
       T nv = readValue(pos);
       uint32_t sz = getElementSize(pos);
       // do not allow the new node to be the first one
       // do not allow the list size tooooo big
       if (UNLIKELY(nv < val || sz >= ListTargetSize)) {
         return false;
       }
 
       Node* p = getList(pos);
       // find a place to insert the node
       while (p->next != nullptr && p->next->val > val) {
         p = p->next;
       }
       newNode->next = p->next;
       p->next = newNode;
       // do not forget to change the metadata
       setElementSize(pos, sz + 1);
       return true;
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::forceInsertToRoot ( Node * newNode )

inlineprivate

Definition at line 733 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::forceInsert().

                                         {
     Position pos;
     pos.level = pos.index = 0;
     std::unique_lock<Mutex> lck(
         levels_[pos.level][pos.index].lock, std::try_to_lock);
     if (!lck.owns_lock()) {
       return false;
     }
     uint32_t sz = getElementSize(pos);
     if (sz >= ListTargetSize) {
       return false;
     }
 
     Node* curList = getList(pos);
     if (curList == nullptr) {
       newNode->next = nullptr;
       setTreeNode(pos, newNode);
     } else {
       Node* p = curList;
       if (p->val <= newNode->val) {
         newNode->next = curList;
         setTreeNode(pos, newNode);
       } else {
         while (p->next != nullptr && p->next->val >= newNode->val) {
           p = p->next;
         }
         newNode->next = p->next;
         p->next = newNode;
       }
     }
     setElementSize(pos, sz + 1);
     return true;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::futexIsReady ( const size_t & curticket )

inlineprivate

Definition at line 1073 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getFutexArrayLoc(), and uint32_t.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::blockingPopImpl(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryBlockingPop(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::trySpinBeforeBlock().

                                                                  {
     auto loc = getFutexArrayLoc(curticket);
     auto curfutex = futex_array_[loc].load(std::memory_order_acquire);
     uint32_t short_cticket = curticket & 0x7FFFFFFF;
     uint32_t futex_ready = curfutex >> 1;
     // handle unsigned 31 bits overflow
     return futex_ready >= short_cticket ||
         short_cticket - futex_ready > 0x40000000;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

uint32_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getBottomLevel ( )

inlineprivate

Definition at line 275 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::grow(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isLeaf(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::pruningLeaf(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::selectPosition(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::~RelaxedConcurrentPriorityQueue().

                             {
     return bottom_.load(std::memory_order_acquire);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE size_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getElementSize ( const Position & pos )

inlineprivate

get the list size in current MoundElement

Definition at line 361 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MoundElement::size.

                                                                  {
     return levels_[pos.level][pos.index].size.load(std::memory_order_relaxed);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

size_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getFutexArrayLoc ( size_t s )

inlineprivate

Definition at line 1193 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::blockingPushImpl(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::futexIsReady(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryBlockingPop().

                                     {
     return ((s - 1) * Stride) & (NumFutex - 1);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Node* folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getList ( const Position & pos )

inlineprivate

Definition at line 485 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MoundElement::head, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level.

                                                          {
     return levels_[pos.level][pos.index].head.load(std::memory_order_relaxed);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::grow ( uint32_t btm )

inlineprivate

Extend the tree level.

Definition at line 373 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getBottomLevel(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::size(), uint32_t, and folly::fibers::yield().

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::selectPosition(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning().

                           {
     while (true) {
       if (guard_.fetch_add(1, std::memory_order_acq_rel) == 0) {
         break;
       }
       // someone already expanded the tree
       if (btm != getBottomLevel()) {
         return;
       }
       std::this_thread::yield();
     }
     // double check the bottom has not changed yet
     if (btm != getBottomLevel()) {
       guard_.store(0, std::memory_order_release);
       return;
     }
     // create and initialize the new level
     uint32_t tmp_btm = getBottomLevel();
     uint32_t size = 1 << (tmp_btm + 1);
     MoundElement* new_level = new MoundElement[size]; // MM
     levels_[tmp_btm + 1] = new_level;
     bottom_.store(tmp_btm + 1, std::memory_order_release);
     guard_.store(0, std::memory_order_release);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isEmpty ( )

inlineprivate

Definition at line 1066 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isMoundEmpty(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isSharedBufferEmpty().

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::empty(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryWait().

                                      {
     if (PopBatch > 0) {
       return isMoundEmpty() && isSharedBufferEmpty();
     }
     return isMoundEmpty();
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isHeap ( const Position & pos )

inlineprivate

Check the first node in TreeElement keeps the heap structure.

Definition at line 315 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isLeaf(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::leftOf(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::readValue(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::rightOf().

                                    {
     if (isLeaf(pos)) {
       return true;
     }
     Position lchild = leftOf(pos);
     Position rchild = rightOf(pos);
     return isHeap(lchild) && isHeap(rchild) &&
         readValue(pos) >= readValue(lchild) &&
         readValue(pos) >= readValue(rchild);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isLeaf ( const Position & pos )

inlineprivate

Current position is leaf?

Definition at line 327 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getBottomLevel(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deferSettingRootSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deleteAllNodes(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isHeap(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeDown(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning().

                                                        {
     return pos.level == getBottomLevel();
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isMoundEmpty ( )

inlineprivate

Definition at line 1055 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getElementSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isEmpty(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryPopFromMound().

                                           {
     Position pos;
     pos.level = pos.index = 0;
     return getElementSize(pos) == 0;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isRoot ( const Position & pos )

inlineprivate

Current element is the root?

Definition at line 332 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::forceInsert(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::regularInsert().

                                                        {
     return pos.level == 0;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isSharedBufferEmpty ( )

inlineprivate

Definition at line 1062 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::top_loc_.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isEmpty(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryPopFromSharedBuffer().

                                                  {
     return top_loc_.load(std::memory_order_acquire) < 0;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Position folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::leftOf ( const Position & pos )

inlineprivate

Locate the left child.

Definition at line 345 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deferSettingRootSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deleteAllNodes(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isHeap(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeDown(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning().

                                                            {
     Position res;
     res.level = pos.level + 1;
     res.index = pos.index * 2;
     return res;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::lockNode ( const Position & pos )

inlineprivate

Definition at line 461 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MoundElement::lock.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deferSettingRootSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeDown(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::regularInsert(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning().

                                                          {
     levels_[pos.level][pos.index].lock.lock();
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeDown ( const Position & pos )

inlineprivate

Definition at line 889 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPopMany().

                                       {
     if (isLeaf(pos)) {
       unlockNode(pos);
       return;
     }
 
     // acquire locks for L and R and compare
     Position lchild = leftOf(pos);
     Position rchild = rightOf(pos);
     lockNode(lchild);
     lockNode(rchild);
     // read values
     T nv = readValue(pos);
     T lv = readValue(lchild);
     T rv = readValue(rchild);
     if (nv >= lv && nv >= rv) {
       unlockNode(pos);
       unlockNode(lchild);
       unlockNode(rchild);
       return;
     }
 
     // If two children contains nodes less than the
     // threshold, we merge two children to the parent
     // and do merge down on both of them.
     size_t sum =
         getElementSize(rchild) + getElementSize(lchild) + getElementSize(pos);
     if (sum <= MergingSize) {
       Node* l1 = mergeList(getList(rchild), getList(lchild));
       setTreeNode(pos, mergeList(l1, getList(pos)));
       setElementSize(pos, sum);
       setTreeNode(lchild, nullptr);
       setElementSize(lchild, 0);
       setTreeNode(rchild, nullptr);
       setElementSize(rchild, 0);
       unlockNode(pos);
       mergeDown(lchild);
       mergeDown(rchild);
       return;
     }
     // pull from right
     if (rv >= lv && rv > nv) {
       swapList(rchild, pos);
       unlockNode(pos);
       unlockNode(lchild);
       mergeDown(rchild);
     } else if (lv >= rv && lv > nv) {
       // pull from left
       swapList(lchild, pos);
       unlockNode(pos);
       unlockNode(rchild);
       mergeDown(lchild);
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

Node* folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeList	(	Node *	base,
		Node *	source
	)

inlineprivate

Definition at line 494 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Node::next, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Node::val.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeDown(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeListTo().

                                             {
     if (base == nullptr) {
       return source;
     } else if (source == nullptr) {
       return base;
     }
 
     Node *res, *p;
     // choose the head node
     if (base->val >= source->val) {
       res = base;
       base = base->next;
       p = res;
     } else {
       res = source;
       source = source->next;
       p = res;
     }
 
     while (base != nullptr && source != nullptr) {
       if (base->val >= source->val) {
         p->next = base;
         base = base->next;
       } else {
         p->next = source;
         source = source->next;
       }
       p = p->next;
     }
     if (base == nullptr) {
       p->next = source;
     } else {
       p->next = base;
     }
     return res;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeListTo	(	const Position &	pos,
		Node *	t,
		const size_t &	list_length
	)

inlineprivate

Merge list t to the Element Position.

Definition at line 532 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getElementSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getList(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeList(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::setElementSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::setTreeNode(), and uint32_t.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning().

                                                                             {
     Node* head = getList(pos);
     setTreeNode(pos, mergeList(head, t));
     uint32_t ns = getElementSize(pos) + list_length;
     setElementSize(pos, ns);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPop ( T & val )

inlineprivate

Definition at line 1197 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::blockingPopImpl(), LIKELY, max, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryPopFromMound(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryPopFromSharedBuffer(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryWait().

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::pop().

                         {
     if (MayBlock) {
       blockingPopImpl();
     }
 
     if (PopBatch > 0) {
       if (tryPopFromSharedBuffer(val)) {
         return;
       }
     }
 
     while (true) {
       if (LIKELY(tryPopFromMound(val))) {
         return;
       }
       tryWait(std::chrono::time_point<std::chrono::steady_clock>::max());
       if (PopBatch > 0 && tryPopFromSharedBuffer(val)) {
         return;
       }
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPopMany ( T & val )

inlineprivate

Definition at line 983 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryPopFromMound().

                             {
     // pop from the root
     Position pos;
     pos.level = pos.index = 0;
     // the root is nullptr, return false
     Node* head = getList(pos);
     if (head == nullptr) {
       unlockNode(pos);
       return false;
     }
 
     // shared buffer already filled by other threads
     if (PopBatch > 0 && top_loc_.load(std::memory_order_acquire) >= 0) {
       unlockNode(pos);
       return false;
     }
 
     uint32_t sz = getElementSize(pos);
     // get the one node first
     val = head->val;
     Node* p = head;
     head = head->next;
     sz--;
 
     if (PopBatch > 0) {
       sz = popToSharedBuffer(sz, head);
     } else {
       setTreeNode(pos, head);
     }
 
     bool done = false;
     if (LIKELY(sz == 0)) {
       done = deferSettingRootSize(pos);
     } else {
       setElementSize(pos, sz);
     }
 
     if (LIKELY(!done)) {
       mergeDown(pos);
     }
 
     p->retire();
     return true;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPush ( const T & val )

inlineprivate

Definition at line 837 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::binarySearchPosition(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::blockingPushImpl(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::forceInsert(), LIKELY, folly::Random::rand32(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::regularInsert(), seed, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::selectPosition(), uint32_t, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Node::val.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::push().

                                {
     Position cur;
     folly::hazptr_holder<Atom> hptr;
     Node* newNode = new Node;
     newNode->val = val;
     uint32_t seed = folly::Random::rand32() % (1 << 21);
 
     while (true) {
       // shell we go the fast path?
       bool go_fast_path = false;
       // chooice the right node to start
       cur = selectPosition(val, go_fast_path, seed, hptr);
       if (go_fast_path) {
         if (LIKELY(forceInsert(cur, val, newNode))) {
           if (MayBlock) {
             blockingPushImpl();
           }
           return;
         } else {
           continue;
         }
       }
 
       binarySearchPosition(cur, val, hptr);
       if (LIKELY(regularInsert(cur, val, newNode))) {
         if (MayBlock) {
           blockingPushImpl();
         }
         return;
       }
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE T folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::optimisticReadValue	(	const Position &	pos,
		folly::hazptr_holder< Atom > &	hptr
	)

inlineprivate

Definition at line 474 of file RelaxedConcurrentPriorityQueue.h.

References folly::hazptr_holder< Atom >::get_protected(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MoundElement::head, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Node::val.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::binarySearchPosition(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::selectPosition().

                                                                            {
     Node* tmp = hptr.get_protected(levels_[pos.level][pos.index].head);
     return (tmp == nullptr) ? MIN_VALUE : tmp->val;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Position folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::parentOf ( const Position & pos )

inlineprivate

Locate the parent node.

Definition at line 337 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::regularInsert().

                                                              {
     Position res;
     res.level = pos.level - 1;
     res.index = pos.index / 2;
     return res;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::pop ( T & val )

inline

Definition at line 252 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::counter_c_, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPop().

                    {
     moundPop(val);
     if (SupportsSize) {
       counter_c_.fetch_add(1, std::memory_order_relaxed);
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

int folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::popToSharedBuffer	(	const uint32_t	rsize,
		Node *	head
	)

inlineprivate

Definition at line 870 of file RelaxedConcurrentPriorityQueue.h.

References i, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, min, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Node::next, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::setTreeNode(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::top_loc_, and uint32_t.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPopMany().

                                                           {
     Position pos;
     pos.level = pos.index = 0;
 
     int num = std::min(rsize, (uint32_t)PopBatch);
     for (int i = num - 1; i >= 0; i--) {
       // wait until this block is empty
       while (shared_buffer_[i].pnode.load(std::memory_order_relaxed) != nullptr)
         ;
       shared_buffer_[i].pnode.store(head, std::memory_order_relaxed);
       head = head->next;
     }
     if (num > 0) {
       top_loc_.store(num - 1, std::memory_order_release);
     }
     setTreeNode(pos, head);
     return rsize - num;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::pruningLeaf ( const Position & pos )

inlineprivate

Definition at line 539 of file RelaxedConcurrentPriorityQueue.h.

References b, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getBottomLevel(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getElementSize(), i, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::unlockNode().

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning().

                                         {
     if (getElementSize(pos) <= PruningSize) {
       unlockNode(pos);
       return true;
     }
 
     int b = getBottomLevel();
     int leaves = 1 << b;
     int cnodes = 0;
     for (int i = 0; i < leaves; i++) {
       Position tmp;
       tmp.level = b;
       tmp.index = i;
       if (getElementSize(tmp) != 0) {
         cnodes++;
       }
       if (cnodes > leaves * 2 / 3) {
         break;
       }
     }
 
     if (cnodes <= leaves * 2 / 3) {
       unlockNode(pos);
       return true;
     }
     return false;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::push ( const T & val )

inline

Definition at line 245 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::counter_p_, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPush().

                           {
     moundPush(val);
     if (SupportsSize) {
       counter_p_.fetch_add(1, std::memory_order_relaxed);
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE T folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::readValue ( const Position & pos )

inlineprivate

Definition at line 480 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getList(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Node::val.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deferSettingRootSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::forceInsert(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isHeap(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeDown(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::regularInsert().

                                                        {
     Node* tmp = getList(pos);
     return (tmp == nullptr) ? MIN_VALUE : tmp->val;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::regularInsert	(	const Position &	pos,
		const T &	val,
		Node *	newNode
	)

inlineprivate

Definition at line 643 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPush().

                                                                        {
     // insert to the root node
     if (isRoot(pos)) {
       lockNode(pos);
       T nv = readValue(pos);
       if (LIKELY(nv <= val)) {
         newNode->next = getList(pos);
         setTreeNode(pos, newNode);
         uint32_t sz = getElementSize(pos);
         setElementSize(pos, sz + 1);
         if (UNLIKELY(sz > PruningSize)) {
           startPruning(pos);
         } else {
           unlockNode(pos);
         }
         return true;
       }
       unlockNode(pos);
       return false;
     }
 
     // insert to an inner node
     Position parent = parentOf(pos);
     if (!trylockNode(parent)) {
       return false;
     }
     if (!trylockNode(pos)) {
       unlockNode(parent);
       return false;
     }
     T pv = readValue(parent);
     T nv = readValue(pos);
     if (LIKELY(pv > val && nv <= val)) {
       // improve the accuracy by getting the node(R) with less priority than the
       // new value from parent level, insert the new node to the parent list
       // and insert R to the current list.
       // It only happens at >= LevelForTraverseParent for reducing contention
       uint32_t sz = getElementSize(pos);
       if (pos.level >= LevelForTraverseParent) {
         Node* start = getList(parent);
         while (start->next != nullptr && start->next->val >= val) {
           start = start->next;
         }
         if (start->next != nullptr) {
           newNode->next = start->next;
           start->next = newNode;
           while (start->next->next != nullptr) {
             start = start->next;
           }
           newNode = start->next;
           start->next = nullptr;
         }
         unlockNode(parent);
 
         Node* curList = getList(pos);
         if (curList == nullptr) {
           newNode->next = nullptr;
           setTreeNode(pos, newNode);
         } else {
           Node* p = curList;
           if (p->val <= newNode->val) {
             newNode->next = curList;
             setTreeNode(pos, newNode);
           } else {
             while (p->next != nullptr && p->next->val >= newNode->val) {
               p = p->next;
             }
             newNode->next = p->next;
             p->next = newNode;
           }
         }
         setElementSize(pos, sz + 1);
       } else {
         unlockNode(parent);
         newNode->next = getList(pos);
         setTreeNode(pos, newNode);
         setElementSize(pos, sz + 1);
       }
       if (UNLIKELY(sz > PruningSize)) {
         startPruning(pos);
       } else {
         unlockNode(pos);
       }
       return true;
     }
     unlockNode(parent);
     unlockNode(pos);
     return false;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Position folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::rightOf ( const Position & pos )

inlineprivate

Locate the right child.

Definition at line 353 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deferSettingRootSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deleteAllNodes(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isHeap(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeDown(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning().

                                                             {
     Position res;
     res.level = pos.level + 1;
     res.index = pos.index * 2 + 1;
     return res;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

Position folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::selectPosition	(	const T &	val,
		bool &	path,
		uint32_t &	seed,
		folly::hazptr_holder< Atom > &	hptr
	)

inlineprivate

TODO: optimization.

Definition at line 406 of file RelaxedConcurrentPriorityQueue.h.

References b, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getBottomLevel(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getElementSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::grow(), i, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::optimisticReadValue(), seed, shell_builder::steps, uint32_t, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Node::val.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPush().

                                       {
     while (true) {
       uint32_t b = getBottomLevel();
       int bound = 1 << b; // number of elements in this level
       int steps = 1 + b * b; // probe the length
       ++seed;
       uint32_t index = seed % bound;
 
       for (int i = 0; i < steps; i++) {
         int loc = (index + i) % bound;
         Position pos;
         pos.level = b;
         pos.index = loc;
         // the first round, we do the quick check
         if (optimisticReadValue(pos, hptr) <= val) {
           path = false;
           seed = ++loc;
           return pos;
         } else if (
             b > LevelForForceInsert && getElementSize(pos) < ListTargetSize) {
           // [fast path] conservative implementation
           // it makes sure every tree element should
           // have more than the given number of nodes.
           seed = ++loc;
           path = true;
           return pos;
         }
         if (b != getBottomLevel()) {
           break;
         }
       }
       // failed too many times grow
       if (b == getBottomLevel()) {
         grow(b);
       }
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::setElementSize	(	const Position &	pos,
		const uint32_t &	v
	)

inlineprivate

Set the size of current MoundElement.

Definition at line 366 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MoundElement::size.

                          {
     levels_[pos.level][pos.index].size.store(v, std::memory_order_relaxed);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::setTreeNode	(	const Position &	pos,
		Node *	t
	)

inlineprivate

Definition at line 489 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MoundElement::head, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level.

                                                                      {
     levels_[pos.level][pos.index].head.store(t, std::memory_order_relaxed);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

size_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::size ( )

inline

Note: size() and empty() are guaranteed to be accurate only if the queue is not changed concurrently. Returns an estimate of the size of the queue

Definition at line 262 of file RelaxedConcurrentPriorityQueue.h.

References c, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::counter_c_, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::counter_p_.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::grow().

                 {
     DCHECK(SupportsSize);
     size_t p = counter_p_.load(std::memory_order_acquire);
     size_t c = counter_c_.load(std::memory_order_acquire);
     return (p > c) ? p - c : 0;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning ( const Position & pos )

inlineprivate

Split the current list into two lists, then split the tail list and merge to two children.

Definition at line 569 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::regularInsert().

                                          {
     if (isLeaf(pos) && pruningLeaf(pos)) {
       return;
     }
 
     // split the list, record the tail
     Node* pruning_head = getList(pos);
     int steps = ListTargetSize; // keep in the original list
     for (int i = 0; i < steps - 1; i++) {
       pruning_head = pruning_head->next;
     }
     Node* t = pruning_head;
     pruning_head = pruning_head->next;
     t->next = nullptr;
     int tail_length = getElementSize(pos) - steps;
     setElementSize(pos, steps);
 
     // split the tail list into two lists
     // evenly merge to two children
     if (pos.level != getBottomLevel()) {
       // split the rest into two lists
       int left_length = (tail_length + 1) / 2;
       int right_length = tail_length - left_length;
       Node *to_right, *to_left = pruning_head;
       for (int i = 0; i < left_length - 1; i++) {
         pruning_head = pruning_head->next;
       }
       to_right = pruning_head->next;
       pruning_head->next = nullptr;
 
       Position lchild = leftOf(pos);
       Position rchild = rightOf(pos);
       if (left_length != 0) {
         lockNode(lchild);
         mergeListTo(lchild, to_left, left_length);
       }
       if (right_length != 0) {
         lockNode(rchild);
         mergeListTo(rchild, to_right, right_length);
       }
       unlockNode(pos);
       if (left_length != 0 && getElementSize(lchild) > PruningSize) {
         startPruning(lchild);
       } else if (left_length != 0) {
         unlockNode(lchild);
       }
       if (right_length != 0 && getElementSize(rchild) > PruningSize) {
         startPruning(rchild);
       } else if (right_length != 0) {
         unlockNode(rchild);
       }
     } else { // time to grow the Mound
       grow(pos.level);
       // randomly choose a child to insert
       if (steps % 2 == 1) {
         Position rchild = rightOf(pos);
         lockNode(rchild);
         mergeListTo(rchild, pruning_head, tail_length);
         unlockNode(pos);
         unlockNode(rchild);
       } else {
         Position lchild = leftOf(pos);
         lockNode(lchild);
         mergeListTo(lchild, pruning_head, tail_length);
         unlockNode(pos);
         unlockNode(lchild);
       }
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::swapList	(	const Position &	a,
		const Position &	b
	)

inlineprivate

Swap two Tree Elements (head, size)

Definition at line 449 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getElementSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getList(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::setElementSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::setTreeNode(), and uint32_t.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deferSettingRootSize(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeDown().

                                                       {
     Node* tmp = getList(a);
     setTreeNode(a, getList(b));
     setTreeNode(b, tmp);
 
     // need to swap the tree node meta-data
     uint32_t sa = getElementSize(a);
     uint32_t sb = getElementSize(b);
     setElementSize(a, sb);
     setElementSize(b, sa);
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryBlockingPop ( const size_t & curticket )

inlineprivate

The last round consumers are still waiting, go to sleep

Spin until the push ticket is ready

The last round consumers are still waiting, go to sleep

Definition at line 1093 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::futexIsReady(), folly::detail::futexWait(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::getFutexArrayLoc(), max, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::trySpinBeforeBlock(), and uint32_t.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::blockingPopImpl().

                                                {
     auto loc = getFutexArrayLoc(curticket);
     auto curfutex = futex_array_[loc].load(std::memory_order_acquire);
     if (curfutex &
         1) { 
       detail::futexWait(&futex_array_[loc], curfutex);
     }
     if (trySpinBeforeBlock(
             curticket,
             std::chrono::time_point<std::chrono::steady_clock>::max())) {
       return; 
     }
     while (true) {
       curfutex = futex_array_[loc].load(std::memory_order_acquire);
       if (curfutex &
           1) { 
         detail::futexWait(&futex_array_[loc], curfutex);
       } else if (!futexIsReady(curticket)) { // current ticket < pop ticket
         uint32_t blocking_futex = curfutex + 1;
         if (futex_array_[loc].compare_exchange_strong(
                 curfutex, blocking_futex)) {
           detail::futexWait(&futex_array_[loc], blocking_futex);
         }
       } else {
         return;
       }
     }
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::trylockNode ( const Position & pos )

inlineprivate

Definition at line 469 of file RelaxedConcurrentPriorityQueue.h.

References FOLLY_ALWAYS_INLINE, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MoundElement::lock, and folly::T.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::regularInsert(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryPopFromMound().

                                                             {
     return levels_[pos.level][pos.index].lock.try_lock();
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryPopFromMound ( T & val )

inlineprivate

Definition at line 1132 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isMoundEmpty(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPopMany(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::trylockNode().

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPop().

                                {
     if (isMoundEmpty()) {
       return false;
     }
     Position pos;
     pos.level = pos.index = 0;
 
     // lock the root
     if (trylockNode(pos)) {
       return moundPopMany(val);
     }
     return false;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryPopFromSharedBuffer ( T & val )

inlineprivate

Definition at line 1178 of file RelaxedConcurrentPriorityQueue.h.

References c, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isSharedBufferEmpty(), folly::hazptr_obj_base< T, Atom, D >::retire(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::top_loc_, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Node::val.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPop().

                                       {
     int get_or = -1;
     if (!isSharedBufferEmpty()) {
       get_or = top_loc_.fetch_sub(1, std::memory_order_acq_rel);
       if (get_or >= 0) {
         Node* c = shared_buffer_[get_or].pnode.load(std::memory_order_relaxed);
         shared_buffer_[get_or].pnode.store(nullptr, std::memory_order_release);
         val = c->val;
         c->retire();
         return true;
       }
     }
     return false;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_NOINLINE bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::trySpinBeforeBlock	(	const size_t &	curticket,
		const std::chrono::time_point< Clock, Duration > &	deadline,
		const folly::WaitOptions &	opt = `wait_options()`
	)

inlineprivate

Definition at line 1084 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::futexIsReady(), folly::detail::spin_pause_until(), and folly::detail::success.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryBlockingPop().

                                                     {
     return folly::detail::spin_pause_until(deadline, opt, [=] {
              return futexIsReady(curticket);
            }) == folly::detail::spin_result::success;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_NOINLINE bool folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryWait	(	const std::chrono::time_point< Clock, Duration > &	deadline,
		const folly::WaitOptions &	opt = `wait_options()`
	)

inlineprivate

Definition at line 1151 of file RelaxedConcurrentPriorityQueue.h.

References folly::detail::advance, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isEmpty(), folly::detail::spin_pause_until(), folly::detail::spin_yield_until(), folly::detail::success, and folly::detail::timeout.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPop().

                                                     {
     // Fast path, by quick check the status
     switch (folly::detail::spin_pause_until(
         deadline, opt, [=] { return !isEmpty(); })) {
       case folly::detail::spin_result::success:
         return true;
       case folly::detail::spin_result::timeout:
         return false;
       case folly::detail::spin_result::advance:
         break;
     }
 
     // Spinning strategy
     while (true) {
       auto res =
           folly::detail::spin_yield_until(deadline, [=] { return !isEmpty(); });
       if (res == folly::detail::spin_result::success) {
         return true;
       } else if (res == folly::detail::spin_result::timeout) {
         return false;
       }
     }
     return true;
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::unlockNode ( const Position & pos )

inlineprivate

Definition at line 465 of file RelaxedConcurrentPriorityQueue.h.

References folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::index, folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Position::level, and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MoundElement::lock.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deferSettingRootSize(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::mergeDown(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPopMany(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::pruningLeaf(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::regularInsert(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::startPruning().

                                                            {
     levels_[pos.level][pos.index].lock.unlock();
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

static FOLLY_ALWAYS_INLINE folly::WaitOptions folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::wait_options ( )

inlinestaticprivate

Definition at line 1146 of file RelaxedConcurrentPriorityQueue.h.

                                                              {
     return {};
   }

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

constexpr size_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Align = 1u << 7

staticprivate

Definition at line 132 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

Atom<uint32_t> folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::bottom_

private

Definition at line 183 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

Atom<size_t> folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::counter_c_

private

Definition at line 203 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::pop(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::size().

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

Atom<size_t> folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::counter_p_

private

Definition at line 202 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::push(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::size().

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

Atom<uint32_t> folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::cticket_

private

Definition at line 198 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::blockingPopImpl().

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

std::unique_ptr<folly::detail::Futex<Atom>[]> folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::futex_array_

private

Definition at line 197 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

Atom<uint32_t> folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::guard_

private

Definition at line 185 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

constexpr int folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::LevelForForceInsert = 3

staticprivate

Definition at line 133 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

constexpr int folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::LevelForTraverseParent = 7

staticprivate

Definition at line 134 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

MoundElement* folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::levels_[MAX_LEVELS]

private

Data members.

Definition at line 181 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

constexpr uint32_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MAX_LEVELS = 32

staticprivate

Definition at line 127 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::RelaxedConcurrentPriorityQueue().

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

constexpr size_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MergingSize = ListTargetSize

staticprivate

Definition at line 147 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

constexpr T folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::MIN_VALUE = std::numeric_limits<T>::min()

staticprivate

Definition at line 129 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

constexpr size_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::NumFutex = 128

staticprivate

Blocking algorithm.

Definition at line 194 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

constexpr size_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::PruningSize = ListTargetSize * 2

staticprivate

Definition at line 142 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

Atom<uint32_t> folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::pticket_

private

Definition at line 199 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::blockingPushImpl().

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

std::unique_ptr<BufferNode[]> folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::shared_buffer_

private

Definition at line 189 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

constexpr size_t folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::Stride = 33

staticprivate

Definition at line 196 of file RelaxedConcurrentPriorityQueue.h.

template<typename T , bool MayBlock = false, bool SupportsSize = false, size_t PopBatch = 16, size_t ListTargetSize = 25, typename Mutex = folly::SpinLock, template< typename > class Atom = std::atomic>

Atom<int> folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::top_loc_

private

Definition at line 190 of file RelaxedConcurrentPriorityQueue.h.

Referenced by folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::deleteSharedBuffer(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::isSharedBufferEmpty(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::moundPopMany(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::popToSharedBuffer(), folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::RelaxedConcurrentPriorityQueue(), and folly::RelaxedConcurrentPriorityQueue< T, MayBlock, SupportsSize, PopBatch, ListTargetSize, Mutex, Atom >::tryPopFromSharedBuffer().

Public Member Functions
	RelaxedConcurrentPriorityQueue ()
	Constructor. More...

	~RelaxedConcurrentPriorityQueue ()

void	push (const T &val)

void	pop (T &val)

size_t	size ()

bool	empty ()
	Returns true only if the queue was empty during the call. More...

Private Member Functions
uint32_t	getBottomLevel ()

void	deleteSharedBuffer ()
	This function is only called by the destructor. More...

void	deleteAllNodes (const Position &pos)
	This function is only called by the destructor. More...

bool	isHeap (const Position &pos)
	Check the first node in TreeElement keeps the heap structure. More...

FOLLY_ALWAYS_INLINE bool	isLeaf (const Position &pos)
	Current position is leaf? More...

FOLLY_ALWAYS_INLINE bool	isRoot (const Position &pos)
	Current element is the root? More...

FOLLY_ALWAYS_INLINE Position	parentOf (const Position &pos)
	Locate the parent node. More...

FOLLY_ALWAYS_INLINE Position	leftOf (const Position &pos)
	Locate the left child. More...

FOLLY_ALWAYS_INLINE Position	rightOf (const Position &pos)
	Locate the right child. More...

FOLLY_ALWAYS_INLINE size_t	getElementSize (const Position &pos)
	get the list size in current MoundElement More...

FOLLY_ALWAYS_INLINE void	setElementSize (const Position &pos, const uint32_t &v)
	Set the size of current MoundElement. More...

void	grow (uint32_t btm)
	Extend the tree level. More...

Position	selectPosition (const T &val, bool &path, uint32_t &seed, folly::hazptr_holder< Atom > &hptr)
	TODO: optimization. More...

void	swapList (const Position &a, const Position &b)
	Swap two Tree Elements (head, size) More...

FOLLY_ALWAYS_INLINE void	lockNode (const Position &pos)

FOLLY_ALWAYS_INLINE void	unlockNode (const Position &pos)

FOLLY_ALWAYS_INLINE bool	trylockNode (const Position &pos)

FOLLY_ALWAYS_INLINE T	optimisticReadValue (const Position &pos, folly::hazptr_holder< Atom > &hptr)

FOLLY_ALWAYS_INLINE T	readValue (const Position &pos)

FOLLY_ALWAYS_INLINE Node *	getList (const Position &pos)

FOLLY_ALWAYS_INLINE void	setTreeNode (const Position &pos, Node *t)

Node *	mergeList (Node base, Node source)

void	mergeListTo (const Position &pos, Node *t, const size_t &list_length)
	Merge list t to the Element Position. More...

bool	pruningLeaf (const Position &pos)

void	startPruning (const Position &pos)

bool	regularInsert (const Position &pos, const T &val, Node *newNode)

bool	forceInsertToRoot (Node *newNode)

bool	forceInsert (const Position &pos, const T &val, Node *newNode)

void	binarySearchPosition (Position &cur, const T &val, folly::hazptr_holder< Atom > &hptr)

void	moundPush (const T &val)

int	popToSharedBuffer (const uint32_t rsize, Node *head)

void	mergeDown (const Position &pos)

bool	deferSettingRootSize (Position &pos)

bool	moundPopMany (T &val)

void	blockingPushImpl ()

FOLLY_ALWAYS_INLINE bool	isMoundEmpty ()

FOLLY_ALWAYS_INLINE bool	isSharedBufferEmpty ()

FOLLY_ALWAYS_INLINE bool	isEmpty ()

FOLLY_ALWAYS_INLINE bool	futexIsReady (const size_t &curticket)

template<typename Clock , typename Duration >
FOLLY_NOINLINE bool	trySpinBeforeBlock (const size_t &curticket, const std::chrono::time_point< Clock, Duration > &deadline, const folly::WaitOptions &opt=wait_options())

void	tryBlockingPop (const size_t &curticket)

void	blockingPopImpl ()

bool	tryPopFromMound (T &val)

template<typename Clock , typename Duration >
FOLLY_NOINLINE bool	tryWait (const std::chrono::time_point< Clock, Duration > &deadline, const folly::WaitOptions &opt=wait_options())

bool	tryPopFromSharedBuffer (T &val)

size_t	getFutexArrayLoc (size_t s)

void	moundPop (T &val)

Private Attributes
MoundElement *	levels_ [MAX_LEVELS]
	Data members. More...

Atom< uint32_t >	bottom_

Atom< uint32_t >	guard_

std::unique_ptr< BufferNode[]>	shared_buffer_

Atom< int >	top_loc_

std::unique_ptr< folly::detail::Futex< Atom >[]>	futex_array_

Atom< uint32_t >	cticket_

Atom< uint32_t >	pticket_

Atom< size_t >	counter_p_

Atom< size_t >	counter_c_

Static Private Attributes
static constexpr uint32_t	MAX_LEVELS = 32

static constexpr T	MIN_VALUE = std::numeric_limits<T>::min()

static constexpr size_t	Align = 1u << 7

static constexpr int	LevelForForceInsert = 3

static constexpr int	LevelForTraverseParent = 7

static constexpr size_t	PruningSize = ListTargetSize * 2

static constexpr size_t	MergingSize = ListTargetSize

static constexpr size_t	NumFutex = 128
	Blocking algorithm. More...

static constexpr size_t	Stride = 33

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Classes
struct	BufferNode
	Node for shared buffer should be aligned. More...

struct	MoundElement
	Mound Element (Tree node), head points to a linked list. More...

struct	Node
	List Node structure. More...

struct	Position
	The pos strcture simplify the implementation. More...

Static Private Member Functions
static FOLLY_ALWAYS_INLINE folly::WaitOptions	wait_options ()