folly/AtomicLinkedList.h

   1 /*
   2  * Copyright 2015 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 #ifndef FOLLY_ATOMIC_LINKED_LIST_H_
  18 #define FOLLY_ATOMIC_LINKED_LIST_H_
  19
  20 #include <atomic>
  21 #include <cassert>
  22
  23 namespace folly {
  24
  25 /**
  26  * A very simple atomic single-linked list primitive.
  27  *
  28  * Usage:
  29  *
  30  * class MyClass {
  31  *   AtomicLinkedListHook<MyClass> hook_;
  32  * }
  33  *
  34  * AtomicLinkedList<MyClass, &MyClass::hook_> list;
  35  * list.insert(&a);
  36  * list.sweep([] (MyClass* c) { doSomething(c); }
  37  */
  38 template <class T>
  39 struct AtomicLinkedListHook {
  40   T* next{nullptr};
  41 };
  42
  43 template <class T, AtomicLinkedListHook<T> T::* HookMember>
  44 class AtomicLinkedList {
  45  public:
  46   AtomicLinkedList() {}
  47   AtomicLinkedList(const AtomicLinkedList&) = delete;
  48   AtomicLinkedList& operator=(const AtomicLinkedList&) = delete;
  49   AtomicLinkedList(AtomicLinkedList&& other) noexcept {
  50     auto tmp = other.head_.load();
  51     other.head_ = head_.load();
  52     head_ = tmp;
  53   }
  54   AtomicLinkedList& operator=(AtomicLinkedList&& other) noexcept {
  55     auto tmp = other.head_.load();
  56     other.head_ = head_.load();
  57     head_ = tmp;
  58
  59     return *this;
  60   }
  61
  62   /**
  63    * Note: list must be empty on destruction.
  64    */
  65   ~AtomicLinkedList() {
  66     assert(empty());
  67   }
  68
  69   bool empty() const {
  70     return head_ == nullptr;
  71   }
  72
  73   /**
  74    * Atomically insert t at the head of the list.
  75    * @return True if the inserted element is the only one in the list
  76    *         after the call.
  77    */
  78   bool insertHead(T* t) {
  79     assert(next(t) == nullptr);
  80
  81     auto oldHead = head_.load(std::memory_order_relaxed);
  82     do {
  83       next(t) = oldHead;
  84       /* oldHead is updated by the call below.
  85
  86          NOTE: we don't use next(t) instead of oldHead directly due to
  87          compiler bugs (GCC prior to 4.8.3 (bug 60272), clang (bug 18899),
  88          MSVC (bug 819819); source:
  89          http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange */
  90     } while (!head_.compare_exchange_weak(oldHead, t,
  91                                           std::memory_order_release,
  92                                           std::memory_order_relaxed));
  93
  94     return oldHead == nullptr;
  95   }
  96
  97   /**
  98    * Repeatedly replaces the head with nullptr,
  99    * and calls func() on the removed elements in the order from tail to head.
 100    * Stops when the list is empty.
 101    */
 102   template <typename F>
 103   void sweep(F&& func) {
 104     while (auto head = head_.exchange(nullptr)) {
 105       auto rhead = reverse(head);
 106       while (rhead != nullptr) {
 107         auto t = rhead;
 108         rhead = next(t);
 109         next(t) = nullptr;
 110         func(t);
 111       }
 112     }
 113   }
 114
 115  private:
 116   std::atomic<T*> head_{nullptr};
 117
 118   static T*& next(T* t) {
 119     return (t->*HookMember).next;
 120   }
 121
 122   /* Reverses a linked list, returning the pointer to the new head
 123      (old tail) */
 124   static T* reverse(T* head) {
 125     T* rhead = nullptr;
 126     while (head != nullptr) {
 127       auto t = head;
 128       head = next(t);
 129       next(t) = rhead;
 130       rhead = t;
 131     }
 132     return rhead;
 133   }
 134 };
 135
 136 } // namespace folly
 137
 138 #endif