folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom > Class Template Reference

#include <UnboundedQueue.h>

Classes
struct	Consumer
class	Entry
struct	Producer
class	Segment

Public Member Functions
	UnboundedQueue ()
	~UnboundedQueue ()
FOLLY_ALWAYS_INLINE void	enqueue (const T &arg)
FOLLY_ALWAYS_INLINE void	enqueue (T &&arg)
FOLLY_ALWAYS_INLINE void	dequeue (T &item) noexcept
FOLLY_ALWAYS_INLINE bool	try_dequeue (T &item) noexcept
FOLLY_ALWAYS_INLINE folly::Optional< T >	try_dequeue () noexcept
template<typename Clock , typename Duration >
FOLLY_ALWAYS_INLINE bool	try_dequeue_until (T &item, const std::chrono::time_point< Clock, Duration > &deadline) noexcept
template<typename Clock , typename Duration >
FOLLY_ALWAYS_INLINE folly::Optional< T >	try_dequeue_until (const std::chrono::time_point< Clock, Duration > &deadline) noexcept
template<typename Rep , typename Period >
FOLLY_ALWAYS_INLINE bool	try_dequeue_for (T &item, const std::chrono::duration< Rep, Period > &duration) noexcept
template<typename Rep , typename Period >
FOLLY_ALWAYS_INLINE folly::Optional< T >	try_dequeue_for (const std::chrono::duration< Rep, Period > &duration) noexcept
FOLLY_ALWAYS_INLINE const T *	try_peek () noexcept
size_t	size () const noexcept
bool	empty () const noexcept

Private Types
using	Ticket = uint64_t

Private Member Functions
template<typename Arg >
FOLLY_ALWAYS_INLINE void	enqueueImpl (Arg &&arg)
template<typename Arg >
FOLLY_ALWAYS_INLINE void	enqueueCommon (Segment *s, Arg &&arg)
FOLLY_ALWAYS_INLINE void	dequeueImpl (T &item) noexcept
FOLLY_ALWAYS_INLINE void	dequeueCommon (Segment *s, T &item) noexcept
template<typename Clock , typename Duration >
FOLLY_ALWAYS_INLINE folly::Optional< T >	tryDequeueUntil (const std::chrono::time_point< Clock, Duration > &deadline) noexcept
template<typename Clock , typename Duration >
FOLLY_ALWAYS_INLINE folly::Optional< T >	tryDequeueUntilSC (Segment *s, const std::chrono::time_point< Clock, Duration > &deadline) noexcept
template<typename Clock , typename Duration >
FOLLY_ALWAYS_INLINE folly::Optional< T >	tryDequeueUntilMC (Segment *s, const std::chrono::time_point< Clock, Duration > &deadline) noexcept
template<typename Clock , typename Duration >
FOLLY_ALWAYS_INLINE bool	tryDequeueWaitElem (Entry &e, Ticket t, const std::chrono::time_point< Clock, Duration > &deadline) noexcept
template<typename Clock , typename Duration >
FOLLY_ALWAYS_INLINE const T *	tryPeekUntil (const std::chrono::time_point< Clock, Duration > &deadline) noexcept
FOLLY_ALWAYS_INLINE Segment *	findSegment (Segment *s, const Ticket t) noexcept
Segment *	getAllocNextSegment (Segment *s, Ticket t) noexcept
Segment *	allocNextSegment (Segment *s)
void	advanceTail (Segment *s) noexcept
void	advanceTailToTicket (Ticket t) noexcept
void	advanceHead (Segment *s) noexcept
void	advanceHeadToTicket (Ticket t) noexcept
void	reclaimSegment (Segment *s) noexcept
void	cleanUpRemainingItems ()
void	reclaimRemainingSegments ()
FOLLY_ALWAYS_INLINE size_t	index (Ticket t) const noexcept
FOLLY_ALWAYS_INLINE bool	responsibleForAlloc (Ticket t) const noexcept
FOLLY_ALWAYS_INLINE bool	responsibleForAdvance (Ticket t) const noexcept
FOLLY_ALWAYS_INLINE Segment *	head () const noexcept
FOLLY_ALWAYS_INLINE Segment *	tail () const noexcept
FOLLY_ALWAYS_INLINE Ticket	producerTicket () const noexcept
FOLLY_ALWAYS_INLINE Ticket	consumerTicket () const noexcept
void	setHead (Segment *s) noexcept
void	setTail (Segment *s) noexcept
bool	casHead (Segment *&s, Segment *next) noexcept
void	casTail (Segment *&s, Segment *next) noexcept
FOLLY_ALWAYS_INLINE void	setProducerTicket (Ticket t) noexcept
FOLLY_ALWAYS_INLINE void	setConsumerTicket (Ticket t) noexcept
FOLLY_ALWAYS_INLINE Ticket	fetchIncrementConsumerTicket () noexcept
FOLLY_ALWAYS_INLINE Ticket	fetchIncrementProducerTicket () noexcept

Private Attributes
Consumer	c_
Producer	p_

Static Private Attributes
static constexpr bool	SPSC = SingleProducer && SingleConsumer
static constexpr size_t	Stride = SPSC || (LgSegmentSize <= 1) ? 1 : 27
static constexpr size_t	SegmentSize = 1u << LgSegmentSize
static constexpr size_t	Align = 1u << LgAlign

Detailed Description

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>
class folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >

UnboundedQueue supports a variety of options for unbounded dynamically expanding an shrinking queues, including variations of:

• Single vs. multiple producers
• Single vs. multiple consumers
• Blocking vs. spin-waiting
• Non-waiting, timed, and waiting consumer operations. Producer operations never wait or fail (unless out-of-memory).

Template parameters:

• T: element type
• SingleProducer: true if there can be only one producer at a time.
• SingleConsumer: true if there can be only one consumer at a time.
• MayBlock: true if consumers may block, false if they only spin. A performance tuning parameter.
• LgSegmentSize (default 8): Log base 2 of number of elements per segment. A performance tuning parameter. See below.
• LgAlign (default 7): Log base 2 of alignment directive; can be used to balance scalability (avoidance of false sharing) with memory efficiency.

When to use UnboundedQueue:

• If a small bound may lead to deadlock or performance degradation under bursty patterns.
• If there is no risk of the queue growing too much.

When not to use UnboundedQueue:

• If there is risk of the queue growing too much and a large bound is acceptable, then use DynamicBoundedQueue.
• If the queue must not allocate on enqueue or it must have a small bound, then use fixed-size MPMCQueue or (if non-blocking SPSC) ProducerConsumerQueue.

Template Aliases: USPSCQueue<T, MayBlock, LgSegmentSize, LgAlign> UMPSCQueue<T, MayBlock, LgSegmentSize, LgAlign> USPMCQueue<T, MayBlock, LgSegmentSize, LgAlign> UMPMCQueue<T, MayBlock, LgSegmentSize, LgAlign>

Functions: Producer operations never wait or fail (unless OOM) void enqueue(const T&); void enqueue(T&&); Adds an element to the end of the queue.

Consumer operations: void dequeue(T&); Extracts an element from the front of the queue. Waits until an element is available if needed. bool try_dequeue(T&); folly::Optional<T> try_dequeue(); Tries to extract an element from the front of the queue if available. bool try_dequeue_until(T&, time_point& deadline); folly::Optional<T> try_dequeue_until(time_point& deadline); Tries to extract an element from the front of the queue if available until the specified deadline. bool try_dequeue_for(T&, duration&); folly::Optional<T> try_dequeue_for(duration&); Tries to extract an element from the front of the queue if available until the expiration of the specified duration. const T* try_peek(); Returns pointer to the element at the front of the queue if available, or nullptr if the queue is empty. Only for SPSC and MPSC.

Secondary functions: size_t size(); Returns an estimate of the size of the queue. bool empty(); Returns true only if the queue was empty during the call. Note: size() and empty() are guaranteed to be accurate only if the queue is not changed concurrently.

Usage examples:

/* UMPSC, doesn't block, 1024 int elements per segment */
UMPSCQueue<int, false, 10> q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
ASSERT_FALSE(q.empty());
ASSERT_EQ(q.size(), 3);
int v;
q.dequeue(v);
ASSERT_EQ(v, 1);
ASSERT_TRUE(try_dequeue(v));
ASSERT_EQ(v, 2);
ASSERT_TRUE(try_dequeue_until(v, now() + seconds(1)));
ASSERT_EQ(v, 3);
ASSERT_TRUE(q.empty());
ASSERT_EQ(q.size(), 0);
ASSERT_FALSE(try_dequeue(v));
ASSERT_FALSE(try_dequeue_for(v, microseconds(100)));

Design:

• The queue is composed of one or more segments. Each segment has a fixed size of 2^LgSegmentSize entries. Each segment is used exactly once.
• Each entry is composed of a futex and a single element.
• The queue contains two 64-bit ticket variables. The producer ticket counts the number of producer tickets issued so far, and the same for the consumer ticket. Each ticket number corresponds to a specific entry in a specific segment.
• The queue maintains two pointers, head and tail. Head points to the segment that corresponds to the current consumer ticket. Similarly, tail pointer points to the segment that corresponds to the producer ticket.
• Segments are organized as a singly linked list.
• The producer with the first ticket in the current producer segment has primary responsibility for allocating and linking the next segment. Other producers and connsumers may help do so when needed if that thread is delayed.
• The producer with the last ticket in the current producer segment is primarily responsible for advancing the tail pointer to the next segment. Other producers and consumers may help do so when needed if that thread is delayed.
• Similarly, the consumer with the last ticket in the current consumer segment is primarily responsible for advancing the head pointer to the next segment. Other consumers may help do so when needed if that thread is delayed.
• The tail pointer must not lag behind the head pointer. Otherwise, the algorithm cannot be certain about the removal of segment and would have to incur higher costs to ensure safe reclamation. Consumers must ensure that head never overtakes tail.

Memory Usage:

• An empty queue contains one segment. A nonempty queue contains one or two more segment than fits its contents.
• Removed segments are not reclaimed until there are no threads, producers or consumers, with references to them or their predecessors. That is, a lagging thread may delay the reclamation of a chain of removed segments.
• The template parameter LgAlign can be used to reduce memory usage at the cost of increased chance of false sharing.

Performance considerations:

• All operations take constant time, excluding the costs of allocation, reclamation, interference from other threads, and waiting for actions by other threads.
• In general, using the single producer and or single consumer variants yield better performance than the MP and MC alternatives.
• SPSC without blocking is the fastest configuration. It doesn't include any read-modify-write atomic operations, full fences, or system calls in the critical path.
• MP adds a fetch_add to the critical path of each producer operation.
• MC adds a fetch_add or compare_exchange to the critical path of each consumer operation.
• The possibility of consumers blocking, even if they never do, adds a compare_exchange to the critical path of each producer operation.
• MPMC, SPMC, MPSC require the use of a deferred reclamation mechanism to guarantee that segments removed from the linked list, i.e., unreachable from the head pointer, are reclaimed only after they are no longer needed by any lagging producers or consumers.
• The overheads of segment allocation and reclamation are intended to be mostly out of the critical path of the queue's throughput.
• If the template parameter LgSegmentSize is changed, it should be set adequately high to keep the amortized cost of allocation and reclamation low.
• It is recommended to measure performance with different variants when applicable, e.g., UMPMC vs UMPSC. Depending on the use case, sometimes the variant with the higher sequential overhead may yield better results due to, for example, more favorable producer-consumer balance or favorable timing for avoiding costly blocking.

Definition at line 216 of file UnboundedQueue.h.

Member Typedef Documentation

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

using folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Ticket = uint64_t

private

Definition at line 217 of file UnboundedQueue.h.

Constructor & Destructor Documentation

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::UnboundedQueue ( )

inline

constructor

Definition at line 249 of file UnboundedQueue.h.

      : c_(new Segment(0)), p_(c_.head.load(std::memory_order_relaxed)) {}

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::~UnboundedQueue ( )

inline

destructor

Definition at line 253 of file UnboundedQueue.h.

                    {
    cleanUpRemainingItems();
    reclaimRemainingSegments();
  }

Member Function Documentation

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::advanceHead ( Segment *  s )

inlineprivatenoexcept

advanceHead

Definition at line 586 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::dequeueCommon(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilMC(), and folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilSC().

                                        {
    if (SPSC) {
      while (tail() == s) {
        /* Wait for producer to advance tail. */
        asm_volatile_pause();
      }
      Segment* next = s->nextSegment();
      DCHECK(next);
      setHead(next);
      reclaimSegment(s);
    } else {
      Ticket t = s->minTicket() + SegmentSize;
      advanceHeadToTicket(t);
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::advanceHeadToTicket ( Ticket  t )

inlineprivatenoexcept

advanceHeadToTicket

Definition at line 603 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceHead().

                                              {
    /* Tail must not lag behind head. Otherwise, the algorithm cannot
       be certain about removal of segments. */
    advanceTailToTicket(t);
    Segment* s = head();
    if (SingleConsumer) {
      DCHECK_EQ(s->minTicket() + SegmentSize, t);
      Segment* next = s->nextSegment();
      DCHECK(next);
      setHead(next);
      reclaimSegment(s);
    } else {
      while (s->minTicket() < t) {
        Segment* next = s->nextSegment();
        DCHECK(next);
        if (casHead(s, next)) {
          reclaimSegment(s);
          s = next;
        }
      }
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::advanceTail ( Segment *  s )

inlineprivatenoexcept

advanceTail

Definition at line 560 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::enqueueCommon().

                                        {
    if (SPSC) {
      Segment* next = s->nextSegment();
      DCHECK(next);
      setTail(next);
    } else {
      Ticket t = s->minTicket() + SegmentSize;
      advanceTailToTicket(t);
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::advanceTailToTicket ( Ticket  t )

inlineprivatenoexcept

advanceTailToTicket

Definition at line 572 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceHeadToTicket(), and folly::UnboundedQueue< T, false, 6 >::advanceTail().

                                              {
    Segment* s = tail();
    while (s->minTicket() < t) {
      Segment* next = s->nextSegment();
      if (!next) {
        next = allocNextSegment(s);
      }
      DCHECK(next);
      casTail(s, next);
      s = tail();
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

Segment* folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::allocNextSegment ( Segment *  s )

inlineprivate

allocNextSegment

Definition at line 547 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceTailToTicket(), folly::UnboundedQueue< T, false, 6 >::enqueueCommon(), and folly::UnboundedQueue< T, false, 6 >::getAllocNextSegment().

                                        {
    auto t = s->minTicket() + SegmentSize;
    Segment* next = new Segment(t);
    next->acquire_ref_safe(); // defined in hazptr_obj_base_linked
    if (!s->casNextSegment(next)) {
      delete next;
      next = s->nextSegment();
    }
    DCHECK(next);
    return next;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

bool folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::casHead ( Segment *&  s, Segment *  next  )

inlineprivatenoexcept

Definition at line 701 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceHeadToTicket().

                                                    {
    DCHECK(!SingleConsumer);
    return c_.head.compare_exchange_strong(
        s, next, std::memory_order_release, std::memory_order_acquire);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::casTail ( Segment *&  s, Segment *  next  )

inlineprivatenoexcept

Definition at line 707 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceTailToTicket().

                                                    {
    DCHECK(!SPSC);
    p_.tail.compare_exchange_strong(
        s, next, std::memory_order_release, std::memory_order_relaxed);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::cleanUpRemainingItems ( )

inlineprivate

cleanUpRemainingItems

Definition at line 636 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::~UnboundedQueue().

                               {
    auto end = producerTicket();
    auto s = head();
    for (auto t = consumerTicket(); t < end; ++t) {
      if (t >= s->minTicket() + SegmentSize) {
        s = s->nextSegment();
      }
      DCHECK_LT(t, (s->minTicket() + SegmentSize));
      auto idx = index(t);
      auto& e = s->entry(idx);
      e.destroyItem();
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Ticket folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::consumerTicket ( ) const

inlineprivatenoexcept

Definition at line 687 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::cleanUpRemainingItems(), folly::UnboundedQueue< T, false, 6 >::empty(), folly::UnboundedQueue< T, false, 6 >::fetchIncrementConsumerTicket(), folly::UnboundedQueue< T, false, 6 >::size(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilMC(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilSC(), and folly::UnboundedQueue< T, false, 6 >::tryPeekUntil().

                                                             {
    return c_.ticket.load(std::memory_order_acquire);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::dequeue ( T &  item )

inlinenoexcept

dequeue

Definition at line 268 of file UnboundedQueue.h.

Referenced by enq_deq_test().

                                                     {
    dequeueImpl(item);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::dequeueCommon ( Segment *  s, T &  item  )

inlineprivatenoexcept

dequeueCommon

Definition at line 405 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::dequeueImpl().

                                                                       {
    Ticket t = fetchIncrementConsumerTicket();
    if (!SingleConsumer) {
      s = findSegment(s, t);
    }
    size_t idx = index(t);
    Entry& e = s->entry(idx);
    e.takeItem(item);
    if (responsibleForAdvance(t)) {
      advanceHead(s);
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::dequeueImpl ( T &  item )

inlineprivatenoexcept

dequeueImpl

Definition at line 390 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::dequeue().

                                                         {
    if (SPSC) {
      Segment* s = head();
      dequeueCommon(s, item);
    } else {
      // Using hazptr_holder instead of hazptr_local because it is
      // possible to call the T dtor and it may happen to use hazard
      // pointers.
      hazptr_holder<Atom> hptr;
      Segment* s = hptr.get_protected(c_.head);
      dequeueCommon(s, item);
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

bool folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::empty ( ) const

inlinenoexcept

empty

Definition at line 347 of file UnboundedQueue.h.

                              {
    auto c = consumerTicket();
    auto p = producerTicket();
    return p <= c;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::enqueue ( const T &  arg )

inline

enqueue

Definition at line 259 of file UnboundedQueue.h.

Referenced by enq_deq_test(), and TEST().

                                                 {
    enqueueImpl(arg);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::enqueue ( T &&  arg )

inline

Definition at line 263 of file UnboundedQueue.h.

                                            {
    enqueueImpl(std::move(arg));
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Arg >

FOLLY_ALWAYS_INLINE void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::enqueueCommon ( Segment *  s, Arg &&  arg  )

inlineprivate

enqueueCommon

Definition at line 371 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::enqueueImpl().

                                                                {
    Ticket t = fetchIncrementProducerTicket();
    if (!SingleProducer) {
      s = findSegment(s, t);
    }
    DCHECK_GE(t, s->minTicket());
    DCHECK_LT(t, s->minTicket() + SegmentSize);
    size_t idx = index(t);
    Entry& e = s->entry(idx);
    e.putItem(std::forward<Arg>(arg));
    if (responsibleForAlloc(t)) {
      allocNextSegment(s);
    }
    if (responsibleForAdvance(t)) {
      advanceTail(s);
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Arg >

FOLLY_ALWAYS_INLINE void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::enqueueImpl ( Arg &&  arg )

inlineprivate

enqueueImpl

Definition at line 356 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::enqueue().

                                                  {
    if (SPSC) {
      Segment* s = tail();
      enqueueCommon(s, std::forward<Arg>(arg));
    } else {
      // Using hazptr_holder instead of hazptr_local because it is
      // possible that the T ctor happens to use hazard pointers.
      hazptr_holder<Atom> hptr;
      Segment* s = hptr.get_protected(p_.tail);
      enqueueCommon(s, std::forward<Arg>(arg));
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Ticket folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::fetchIncrementConsumerTicket ( )

inlineprivatenoexcept

Definition at line 721 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::dequeueCommon().

                                                                     {
    if (SingleConsumer) {
      Ticket oldval = consumerTicket();
      setConsumerTicket(oldval + 1);
      return oldval;
    } else { // MC
      return c_.ticket.fetch_add(1, std::memory_order_acq_rel);
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Ticket folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::fetchIncrementProducerTicket ( )

inlineprivatenoexcept

Definition at line 731 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::enqueueCommon().

                                                                     {
    if (SingleProducer) {
      Ticket oldval = producerTicket();
      setProducerTicket(oldval + 1);
      return oldval;
    } else { // MP
      return p_.ticket.fetch_add(1, std::memory_order_acq_rel);
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Segment* folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::findSegment ( Segment *  s, const Ticket  t  )

inlineprivatenoexcept

findSegment

Definition at line 514 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::dequeueCommon(), and folly::UnboundedQueue< T, false, 6 >::enqueueCommon().

                                                            {
    while (UNLIKELY(t >= (s->minTicket() + SegmentSize))) {
      s = getAllocNextSegment(s, t);
      DCHECK(s);
    }
    return s;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

Segment* folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::getAllocNextSegment ( Segment *  s, Ticket  t  )

inlineprivatenoexcept

getAllocNextSegment

Definition at line 523 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::findSegment(), and folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilMC().

                                                              {
    Segment* next = s->nextSegment();
    if (!next) {
      DCHECK_GE(t, s->minTicket() + SegmentSize);
      auto diff = t - (s->minTicket() + SegmentSize);
      if (diff > 0) {
        auto dur = std::chrono::microseconds(diff);
        auto deadline = std::chrono::steady_clock::now() + dur;
        WaitOptions opt;
        opt.spin_max(dur);
        detail::spin_pause_until(
            deadline, opt, [s] { return s->nextSegment(); });
        next = s->nextSegment();
        if (next) {
          return next;
        }
      }
      next = allocNextSegment(s);
    }
    DCHECK(next);
    return next;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Segment* folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::head ( ) const

inlineprivatenoexcept

Definition at line 675 of file UnboundedQueue.h.

                                                     {
    return c_.head.load(std::memory_order_acquire);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE size_t folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::index ( Ticket  t ) const

inlineprivatenoexcept

Definition at line 663 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::cleanUpRemainingItems(), folly::UnboundedQueue< T, false, 6 >::dequeueCommon(), folly::UnboundedQueue< T, false, 6 >::enqueueCommon(), folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Segment::entry(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilMC(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilSC(), and folly::UnboundedQueue< T, false, 6 >::tryPeekUntil().

                                                            {
    return (t * Stride) & (SegmentSize - 1);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Ticket folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::producerTicket ( ) const

inlineprivatenoexcept

Definition at line 683 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::cleanUpRemainingItems(), folly::UnboundedQueue< T, false, 6 >::empty(), folly::UnboundedQueue< T, false, 6 >::fetchIncrementProducerTicket(), folly::UnboundedQueue< T, false, 6 >::size(), and folly::UnboundedQueue< T, false, 6 >::tryDequeueWaitElem().

                                                             {
    return p_.ticket.load(std::memory_order_acquire);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::reclaimRemainingSegments ( )

inlineprivate

reclaimRemainingSegments

Definition at line 651 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::~UnboundedQueue().

                                  {
    auto h = head();
    auto s = h->nextSegment();
    h->setNextSegment(nullptr);
    reclaimSegment(h);
    while (s) {
      auto next = s->nextSegment();
      delete s;
      s = next;
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::reclaimSegment ( Segment *  s )

inlineprivatenoexcept

reclaimSegment

Definition at line 627 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceHead(), folly::UnboundedQueue< T, false, 6 >::advanceHeadToTicket(), and folly::UnboundedQueue< T, false, 6 >::reclaimRemainingSegments().

                                           {
    if (SPSC) {
      delete s;
    } else {
      s->retire(); // defined in hazptr_obj_base_linked
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::responsibleForAdvance ( Ticket  t ) const

inlineprivatenoexcept

Definition at line 671 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::dequeueCommon(), folly::UnboundedQueue< T, false, 6 >::enqueueCommon(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilMC(), and folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilSC().

                                                                          {
    return (t & (SegmentSize - 1)) == (SegmentSize - 1);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::responsibleForAlloc ( Ticket  t ) const

inlineprivatenoexcept

Definition at line 667 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::enqueueCommon().

                                                                        {
    return (t & (SegmentSize - 1)) == 0;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::setConsumerTicket ( Ticket  t )

inlineprivatenoexcept

Definition at line 717 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::fetchIncrementConsumerTicket(), and folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilSC().

                                                                {
    c_.ticket.store(t, std::memory_order_release);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::setHead ( Segment *  s )

inlineprivatenoexcept

Definition at line 691 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceHead(), and folly::UnboundedQueue< T, false, 6 >::advanceHeadToTicket().

                                    {
    DCHECK(SingleConsumer);
    c_.head.store(s, std::memory_order_relaxed);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::setProducerTicket ( Ticket  t )

inlineprivatenoexcept

Definition at line 713 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::fetchIncrementProducerTicket().

                                                                {
    p_.ticket.store(t, std::memory_order_release);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

void folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::setTail ( Segment *  s )

inlineprivatenoexcept

Definition at line 696 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceTail().

                                    {
    DCHECK(SPSC);
    p_.tail.store(s, std::memory_order_release);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

size_t folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::size ( ) const

inlinenoexcept

size

Definition at line 340 of file UnboundedQueue.h.

                               {
    auto p = producerTicket();
    auto c = consumerTicket();
    return p > c ? p - c : 0;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE Segment* folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::tail ( ) const

inlineprivatenoexcept

Definition at line 679 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceHead(), folly::UnboundedQueue< T, false, 6 >::advanceTailToTicket(), and folly::UnboundedQueue< T, false, 6 >::enqueueImpl().

                                                     {
    return p_.tail.load(std::memory_order_acquire);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::try_dequeue ( T &  item )

inlinenoexcept

try_dequeue

Definition at line 273 of file UnboundedQueue.h.

Referenced by enq_deq_test().

                                                         {
    auto o = try_dequeue();
    if (LIKELY(o.has_value())) {
      item = std::move(*o);
      return true;
    }
    return false;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE folly::Optional<T> folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::try_dequeue ( )

inlinenoexcept

Definition at line 282 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::try_dequeue(), and folly::UnboundedQueue< T, false, 6 >::try_dequeue_for().

                                                              {
    return tryDequeueUntil(std::chrono::steady_clock::time_point::min());
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Rep , typename Period >

FOLLY_ALWAYS_INLINE bool folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::try_dequeue_for ( T &  item, const std::chrono::duration< Rep, Period > &  duration  )

inlinenoexcept

try_dequeue_for

Definition at line 309 of file UnboundedQueue.h.

Referenced by enq_deq_test(), and folly::UnboundedQueue< T, false, 6 >::try_dequeue_for().

                                                               {
    folly::Optional<T> o = try_dequeue_for(duration);

    if (LIKELY(o.has_value())) {
      item = std::move(*o);
      return true;
    }

    return false;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Rep , typename Period >

FOLLY_ALWAYS_INLINE folly::Optional<T> folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::try_dequeue_for ( const std::chrono::duration< Rep, Period > &  duration )

inlinenoexcept

Definition at line 323 of file UnboundedQueue.h.

                                                               {
    folly::Optional<T> o = try_dequeue();
    if (LIKELY(o.has_value())) {
      return o;
    }
    return tryDequeueUntil(std::chrono::steady_clock::now() + duration);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_ALWAYS_INLINE bool folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::try_dequeue_until ( T &  item, const std::chrono::time_point< Clock, Duration > &  deadline  )

inlinenoexcept

try_dequeue_until

Definition at line 288 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::try_dequeue_until().

                                                                     {
    folly::Optional<T> o = try_dequeue_until(deadline);

    if (LIKELY(o.has_value())) {
      item = std::move(*o);
      return true;
    }

    return false;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_ALWAYS_INLINE folly::Optional<T> folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::try_dequeue_until ( const std::chrono::time_point< Clock, Duration > &  deadline )

inlinenoexcept

Definition at line 302 of file UnboundedQueue.h.

                                                                     {
    return tryDequeueUntil(deadline);
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE const T* folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::try_peek ( )

inlinenoexcept

try_peek

Definition at line 333 of file UnboundedQueue.h.

Referenced by enq_deq_test().

                                                   {
    /* This function is supported only for USPSC and UMPSC queues. */
    DCHECK(SingleConsumer);
    return tryPeekUntil(std::chrono::steady_clock::time_point::min());
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_ALWAYS_INLINE folly::Optional<T> folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::tryDequeueUntil ( const std::chrono::time_point< Clock, Duration > &  deadline )

inlineprivatenoexcept

tryDequeueUntil

Definition at line 420 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::try_dequeue(), folly::UnboundedQueue< T, false, 6 >::try_dequeue_for(), and folly::UnboundedQueue< T, false, 6 >::try_dequeue_until().

                                                                     {
    if (SingleConsumer) {
      Segment* s = head();
      return tryDequeueUntilSC(s, deadline);
    } else {
      // Using hazptr_holder instead of hazptr_local because it is
      //  possible to call ~T() and it may happen to use hazard pointers.
      hazptr_holder<Atom> hptr;
      Segment* s = hptr.get_protected(c_.head);
      return tryDequeueUntilMC(s, deadline);
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_ALWAYS_INLINE folly::Optional<T> folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::tryDequeueUntilMC ( Segment *  s, const std::chrono::time_point< Clock, Duration > &  deadline  )

inlineprivatenoexcept

tryDequeueUntilMC

Definition at line 457 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::tryDequeueUntil().

                                                                     {
    while (true) {
      Ticket t = consumerTicket();
      if (UNLIKELY(t >= (s->minTicket() + SegmentSize))) {
        s = getAllocNextSegment(s, t);
        DCHECK(s);
        continue;
      }
      size_t idx = index(t);
      Entry& e = s->entry(idx);
      if (UNLIKELY(!tryDequeueWaitElem(e, t, deadline))) {
        return folly::Optional<T>();
      }
      if (!c_.ticket.compare_exchange_weak(
              t, t + 1, std::memory_order_acq_rel, std::memory_order_acquire)) {
        continue;
      }
      auto ret = e.takeItem();
      if (responsibleForAdvance(t)) {
        advanceHead(s);
      }
      return ret;
    }
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_ALWAYS_INLINE folly::Optional<T> folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::tryDequeueUntilSC ( Segment *  s, const std::chrono::time_point< Clock, Duration > &  deadline  )

inlineprivatenoexcept

tryDequeueUntilSC

Definition at line 436 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::tryDequeueUntil().

                                                                     {
    Ticket t = consumerTicket();
    DCHECK_GE(t, s->minTicket());
    DCHECK_LT(t, (s->minTicket() + SegmentSize));
    size_t idx = index(t);
    Entry& e = s->entry(idx);
    if (UNLIKELY(!tryDequeueWaitElem(e, t, deadline))) {
      return folly::Optional<T>();
    }
    setConsumerTicket(t + 1);
    auto ret = e.takeItem();
    if (responsibleForAdvance(t)) {
      advanceHead(s);
    }
    return ret;
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_ALWAYS_INLINE bool folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::tryDequeueWaitElem ( Entry &  e, Ticket  t, const std::chrono::time_point< Clock, Duration > &  deadline  )

inlineprivatenoexcept

tryDequeueWaitElem

Definition at line 486 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilMC(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilSC(), and folly::UnboundedQueue< T, false, 6 >::tryPeekUntil().

                                                                     {
    if (LIKELY(e.tryWaitUntil(deadline))) {
      return true;
    }
    return t < producerTicket();
  }

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_ALWAYS_INLINE const T* folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::tryPeekUntil ( const std::chrono::time_point< Clock, Duration > &  deadline )

inlineprivatenoexcept

tryPeekUntil

Definition at line 498 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::try_peek().

                                                                     {
    Segment* s = head();
    Ticket t = consumerTicket();
    DCHECK_GE(t, s->minTicket());
    DCHECK_LT(t, (s->minTicket() + SegmentSize));
    size_t idx = index(t);
    Entry& e = s->entry(idx);
    if (UNLIKELY(!tryDequeueWaitElem(e, t, deadline))) {
      return nullptr;
    }
    return e.peekItem();
  }

Member Data Documentation

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

constexpr size_t folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Align = 1u << LgAlign

staticprivate

Definition at line 224 of file UnboundedQueue.h.

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

Consumer folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::c_

private

Definition at line 244 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::casHead(), folly::UnboundedQueue< T, false, 6 >::consumerTicket(), folly::UnboundedQueue< T, false, 6 >::dequeueImpl(), folly::UnboundedQueue< T, false, 6 >::fetchIncrementConsumerTicket(), folly::UnboundedQueue< T, false, 6 >::head(), folly::UnboundedQueue< T, false, 6 >::setConsumerTicket(), folly::UnboundedQueue< T, false, 6 >::setHead(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntil(), and folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilMC().

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

Producer folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::p_

private

Definition at line 245 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::casTail(), folly::UnboundedQueue< T, false, 6 >::enqueueImpl(), folly::UnboundedQueue< T, false, 6 >::fetchIncrementProducerTicket(), folly::UnboundedQueue< T, false, 6 >::producerTicket(), folly::UnboundedQueue< T, false, 6 >::setProducerTicket(), folly::UnboundedQueue< T, false, 6 >::setTail(), and folly::UnboundedQueue< T, false, 6 >::tail().

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

constexpr size_t folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::SegmentSize = 1u << LgSegmentSize

staticprivate

Definition at line 223 of file UnboundedQueue.h.

Referenced by folly::UnboundedQueue< T, false, 6 >::advanceHead(), folly::UnboundedQueue< T, false, 6 >::advanceHeadToTicket(), folly::UnboundedQueue< T, false, 6 >::advanceTail(), folly::UnboundedQueue< T, false, 6 >::allocNextSegment(), folly::UnboundedQueue< T, false, 6 >::cleanUpRemainingItems(), folly::UnboundedQueue< T, false, 6 >::enqueueCommon(), folly::UnboundedQueue< T, false, 6 >::findSegment(), folly::UnboundedQueue< T, false, 6 >::getAllocNextSegment(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilMC(), folly::UnboundedQueue< T, false, 6 >::tryDequeueUntilSC(), and folly::UnboundedQueue< T, false, 6 >::tryPeekUntil().

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

constexpr bool folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::SPSC = SingleProducer && SingleConsumer

staticprivate

Definition at line 221 of file UnboundedQueue.h.

template<typename T, bool SingleProducer, bool SingleConsumer, bool MayBlock, size_t LgSegmentSize = 8, size_t LgAlign = constexpr_log2(hardware_destructive_interference_size), template< typename > class Atom = std::atomic>

constexpr size_t folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Stride = SPSC || (LgSegmentSize <= 1) ? 1 : 27

staticprivate

Definition at line 222 of file UnboundedQueue.h.

---

The documentation for this class was generated from the following file:

• proxygen/folly/folly/concurrency/UnboundedQueue.h