A fast, scalable, relaxed concurrent priority queue.

Synopsis

Declared in <folly/concurrency/container/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> typename Atom = atomic>
class RelaxedConcurrentPriorityQueue;

Description

The queue is built on the Mound data structure and trades strict priority ordering for throughput under contention. It supports arbitrary priorities, unbounded size, and optional blocking on pop.

Member Functions

Name

Description

RelaxedConcurrentPriorityQueue [constructor]

Constructor

~RelaxedConcurrentPriorityQueue [destructor]

Destroys the queue and reclaims all remaining nodes and levels.

empty

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

pop

Removes a highest‐priority value from the queue.

push

Inserts a value into the queue.

size

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

Template Parameters

Name

Description

T

The element type; larger values have higher priority.

MayBlock

Whether pop can block waiting for elements.

SupportsSize

Whether size() is tracked and reported.

PopBatch

Number of nodes kept in the shared buffer for fast pops; 0 pops one node at a time and keeps strict highest‐priority order.

ListTargetSize

The preferred length for each per‐element list.

Mutex

The mutex type guarding each tree element.

Atom

The atomic template used for internal state.

Created with MrDocs