folly/AtomicIntrusiveLinkedList.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <atomic>
  20 #include <cassert>
  21 #include <utility>
  22
  23 namespace folly {
  24
  25 /**
  26  * A very simple atomic single-linked list primitive.
  27  *
  28  * Usage:
  29  *
  30  * class MyClass {
  31  *   AtomicIntrusiveLinkedListHook<MyClass> hook_;
  32  * }
  33  *
  34  * AtomicIntrusiveLinkedList<MyClass, &MyClass::hook_> list;
  35  * list.insert(&a);
  36  * list.sweep([] (MyClass* c) { doSomething(c); }
  37  */
  38 template <class T>
  39 struct AtomicIntrusiveLinkedListHook {
  40   T* next{nullptr};
  41 };
  42
  43 template <class T, AtomicIntrusiveLinkedListHook<T> T::*HookMember>
  44 class AtomicIntrusiveLinkedList {
  45  public:
  46   AtomicIntrusiveLinkedList() {}
  47   AtomicIntrusiveLinkedList(const AtomicIntrusiveLinkedList&) = delete;
  48   AtomicIntrusiveLinkedList& operator=(const AtomicIntrusiveLinkedList&) =
  49       delete;
  50   AtomicIntrusiveLinkedList(AtomicIntrusiveLinkedList&& other) noexcept {
  51     auto tmp = other.head_.load();
  52     other.head_ = head_.load();
  53     head_ = tmp;
  54   }
  55   AtomicIntrusiveLinkedList& operator=(
  56       AtomicIntrusiveLinkedList&& other) noexcept {
  57     auto tmp = other.head_.load();
  58     other.head_ = head_.load();
  59     head_ = tmp;
  60
  61     return *this;
  62   }
  63
  64   /**
  65    * Note: list must be empty on destruction.
  66    */
  67   ~AtomicIntrusiveLinkedList() {
  68     assert(empty());
  69   }
  70
  71   bool empty() const {
  72     return head_.load() == nullptr;
  73   }
  74
  75   /**
  76    * Atomically insert t at the head of the list.
  77    * @return True if the inserted element is the only one in the list
  78    *         after the call.
  79    */
  80   bool insertHead(T* t) {
  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(oldHead, t,
  93                                           std::memory_order_release,
  94                                           std::memory_order_relaxed));
  95
  96     return oldHead == nullptr;
  97   }
  98
  99   /**
 100    * Repeatedly replaces the head with nullptr,
 101    * and calls func() on the removed elements in the order from tail to head.
 102    * Stops when the list is empty.
 103    */
 104   template <typename F>
 105   void sweep(F&& func) {
 106     while (auto head = head_.exchange(nullptr)) {
 107       auto rhead = reverse(head);
 108       unlinkAll(rhead, std::forward<F>(func));
 109     }
 110   }
 111
 112   /**
 113    * Similar to sweep() but calls func() on elements in LIFO order.
 114    *
 115    * func() is called for all elements in the list at the moment
 116    * reverseSweep() is called.  Unlike sweep() it does not loop to ensure the
 117    * list is empty at some point after the last invocation.  This way callers
 118    * can reason about the ordering: elements inserted since the last call to
 119    * reverseSweep() will be provided in LIFO order.
 120    *
 121    * Example: if elements are inserted in the order 1-2-3, the callback is
 122    * invoked 3-2-1.  If the callback moves elements onto a stack, popping off
 123    * the stack will produce the original insertion order 1-2-3.
 124    */
 125   template <typename F>
 126   void reverseSweep(F&& func) {
 127     // We don't loop like sweep() does because the overall order of callbacks
 128     // would be strand-wise LIFO which is meaningless to callers.
 129     auto head = head_.exchange(nullptr);
 130     unlinkAll(head, std::forward<F>(func));
 131   }
 132
 133  private:
 134   std::atomic<T*> head_{nullptr};
 135
 136   static T*& next(T* t) {
 137     return (t->*HookMember).next;
 138   }
 139
 140   /* Reverses a linked list, returning the pointer to the new head
 141      (old tail) */
 142   static T* reverse(T* head) {
 143     T* rhead = nullptr;
 144     while (head != nullptr) {
 145       auto t = head;
 146       head = next(t);
 147       next(t) = rhead;
 148       rhead = t;
 149     }
 150     return rhead;
 151   }
 152
 153   /* Unlinks all elements in the linked list fragment pointed to by `head',
 154    * calling func() on every element */
 155   template <typename F>
 156   void unlinkAll(T* head, F&& func) {
 157     while (head != nullptr) {
 158       auto t = head;
 159       head = next(t);
 160       next(t) = nullptr;
 161       func(t);
 162     }
 163   }
 164 };
 165
 166 } // namespace folly