proxygen
Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
folly::AtomicIntrusiveLinkedList< T, HookMember > Class Template Reference

#include <AtomicIntrusiveLinkedList.h>

Public Member Functions

 AtomicIntrusiveLinkedList ()
 
 AtomicIntrusiveLinkedList (const AtomicIntrusiveLinkedList &)=delete
 
AtomicIntrusiveLinkedList & operator= (const AtomicIntrusiveLinkedList &)=delete
 
 AtomicIntrusiveLinkedList (AtomicIntrusiveLinkedList &&other) noexcept
 
AtomicIntrusiveLinkedList & operator= (AtomicIntrusiveLinkedList &&other) noexcept
 
 ~AtomicIntrusiveLinkedList ()
 
bool empty () const
 
bool insertHead (T *t)
 
template<typename F >
bool sweepOnce (F &&func)
 
template<typename F >
void sweep (F &&func)
 
template<typename F >
void reverseSweep (F &&func)
 

Private Member Functions

template<typename F >
void unlinkAll (T *head, F &&func)
 

Static Private Member Functions

static T *& next (T *t)
 
static T * reverse (T *head)
 

Private Attributes

std::atomic< T * > head_ {nullptr}
 

Detailed Description

template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
class folly::AtomicIntrusiveLinkedList< T, HookMember >

Definition at line 44 of file AtomicIntrusiveLinkedList.h.

Constructor & Destructor Documentation

template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
folly::AtomicIntrusiveLinkedList< T, HookMember >::AtomicIntrusiveLinkedList ( )
inline

Definition at line 46 of file AtomicIntrusiveLinkedList.h.

46 {}
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
folly::AtomicIntrusiveLinkedList< T, HookMember >::AtomicIntrusiveLinkedList ( const AtomicIntrusiveLinkedList< T, HookMember > &  )
delete
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
folly::AtomicIntrusiveLinkedList< T, HookMember >::AtomicIntrusiveLinkedList ( AtomicIntrusiveLinkedList< T, HookMember > &&  other)
inlinenoexcept

Definition at line 50 of file AtomicIntrusiveLinkedList.h.

50  {
51  auto tmp = other.head_.load();
52  other.head_ = head_.load();
53  head_ = tmp;
54  }
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
folly::AtomicIntrusiveLinkedList< T, HookMember >::~AtomicIntrusiveLinkedList ( )
inline

Note: list must be empty on destruction.

Definition at line 67 of file AtomicIntrusiveLinkedList.h.

67  {
68  assert(empty());
69  }

Member Function Documentation

template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
bool folly::AtomicIntrusiveLinkedList< T, HookMember >::empty ( ) const
inline

Definition at line 71 of file AtomicIntrusiveLinkedList.h.

Referenced by TEST().

71  {
72  return head_.load() == nullptr;
73  }
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
bool folly::AtomicIntrusiveLinkedList< T, HookMember >::insertHead ( T *  t)
inline

Atomically insert t at the head of the list.

Returns
True if the inserted element is the only one in the list after the call.

Definition at line 80 of file AtomicIntrusiveLinkedList.h.

Referenced by TEST().

80  {
81  assert(next(t) == nullptr);
82 
83  auto oldHead = head_.load(std::memory_order_relaxed);
84  do {
85  next(t) = oldHead;
86  /* oldHead is updated by the call below.
87 
88  NOTE: we don't use next(t) instead of oldHead directly due to
89  compiler bugs (GCC prior to 4.8.3 (bug 60272), clang (bug 18899),
90  MSVC (bug 819819); source:
91  http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange */
92  } while (!head_.compare_exchange_weak(
93  oldHead, t, std::memory_order_release, std::memory_order_relaxed));
94 
95  return oldHead == nullptr;
96  }
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
static T*& folly::AtomicIntrusiveLinkedList< T, HookMember >::next ( T *  t)
inlinestaticprivate

Definition at line 148 of file AtomicIntrusiveLinkedList.h.

148  {
149  return (t->*HookMember).next;
150  }
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
AtomicIntrusiveLinkedList& folly::AtomicIntrusiveLinkedList< T, HookMember >::operator= ( const AtomicIntrusiveLinkedList< T, HookMember > &  )
delete
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
AtomicIntrusiveLinkedList& folly::AtomicIntrusiveLinkedList< T, HookMember >::operator= ( AtomicIntrusiveLinkedList< T, HookMember > &&  other)
inlinenoexcept

Definition at line 55 of file AtomicIntrusiveLinkedList.h.

56  {
57  auto tmp = other.head_.load();
58  other.head_ = head_.load();
59  head_ = tmp;
60 
61  return *this;
62  }
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
static T* folly::AtomicIntrusiveLinkedList< T, HookMember >::reverse ( T *  head)
inlinestaticprivate

Definition at line 154 of file AtomicIntrusiveLinkedList.h.

154  {
155  T* rhead = nullptr;
156  while (head != nullptr) {
157  auto t = head;
158  head = next(t);
159  next(t) = rhead;
160  rhead = t;
161  }
162  return rhead;
163  }
folly::T
folly::std T
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
template<typename F >
void folly::AtomicIntrusiveLinkedList< T, HookMember >::reverseSweep ( F &&  func)
inline

Similar to sweep() but calls func() on elements in LIFO order.

func() is called for all elements in the list at the moment reverseSweep() is called. Unlike sweep() it does not loop to ensure the list is empty at some point after the last invocation. This way callers can reason about the ordering: elements inserted since the last call to reverseSweep() will be provided in LIFO order.

Example: if elements are inserted in the order 1-2-3, the callback is invoked 3-2-1. If the callback moves elements onto a stack, popping off the stack will produce the original insertion order 1-2-3.

Definition at line 138 of file AtomicIntrusiveLinkedList.h.

Referenced by TEST().

138  {
139  // We don't loop like sweep() does because the overall order of callbacks
140  // would be strand-wise LIFO which is meaningless to callers.
141  auto head = head_.exchange(nullptr);
142  unlinkAll(head, std::forward<F>(func));
143  }
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
template<typename F >
void folly::AtomicIntrusiveLinkedList< T, HookMember >::sweep ( F &&  func)
inline

Repeatedly replaces the head with nullptr, and calls func() on the removed elements in the order from tail to head. Stops when the list is empty.

Definition at line 119 of file AtomicIntrusiveLinkedList.h.

Referenced by TEST().

119  {
120  while (sweepOnce(func)) {
121  }
122  }
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
template<typename F >
bool folly::AtomicIntrusiveLinkedList< T, HookMember >::sweepOnce ( F &&  func)
inline

Replaces the head with nullptr, and calls func() on the removed elements in the order from tail to head. Returns false if the list was empty.

Definition at line 104 of file AtomicIntrusiveLinkedList.h.

104  {
105  if (auto head = head_.exchange(nullptr)) {
106  auto rhead = reverse(head);
107  unlinkAll(rhead, std::forward<F>(func));
108  return true;
109  }
110  return false;
111  }
template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
template<typename F >
void folly::AtomicIntrusiveLinkedList< T, HookMember >::unlinkAll ( T *  head,
F &&  func 
)
inlineprivate

Definition at line 168 of file AtomicIntrusiveLinkedList.h.

168  {
169  while (head != nullptr) {
170  auto t = head;
171  head = next(t);
172  next(t) = nullptr;
173  func(t);
174  }
175  }

Member Data Documentation

template<class T, AtomicIntrusiveLinkedListHook< T > T::* HookMember>
std::atomic<T*> folly::AtomicIntrusiveLinkedList< T, HookMember >::head_ {nullptr}
private

Definition at line 146 of file AtomicIntrusiveLinkedList.h.

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