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
  48   /**
  49    * Note: list must be empty on destruction.
  50    */
  51   ~AtomicLinkedList() {
  52     assert(head_ == nullptr);
  53   }
  54
  55   bool empty() const {
  56     return head_ == nullptr;
  57   }
  58
  59   /**
  60    * Atomically insert t at the head of the list.
  61    * @return True if the inserted element is the only one in the list
  62    *         after the call.
  63    */
  64   bool insertHead(T* t) {
  65     assert(next(t) == nullptr);
  66
  67     auto oldHead = head_.load(std::memory_order_relaxed);
  68     do {
  69       next(t) = oldHead;
  70       /* oldHead is updated by the call below.
  71
  72          NOTE: we don't use next(t) instead of oldHead directly due to
  73          compiler bugs (GCC prior to 4.8.3 (bug 60272), clang (bug 18899),
  74          MSVC (bug 819819); source:
  75          http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange */
  76     } while (!head_.compare_exchange_weak(oldHead, t,
  77                                           std::memory_order_release,
  78                                           std::memory_order_relaxed));
  79
  80     return oldHead == nullptr;
  81   }
  82
  83   /**
  84    * Repeatedly replaces the head with nullptr,
  85    * and calls func() on the removed elements in the order from tail to head.
  86    * Stops when the list is empty.
  87    */
  88   template <typename F>
  89   void sweep(F&& func) {
  90     while (auto head = head_.exchange(nullptr)) {
  91       auto rhead = reverse(head);
  92       while (rhead != nullptr) {
  93         auto t = rhead;
  94         rhead = next(t);
  95         next(t) = nullptr;
  96         func(t);
  97       }
  98     }
  99   }
 100
 101  private:
 102   std::atomic<T*> head_{nullptr};
 103
 104   static T*& next(T* t) {
 105     return (t->*HookMember).next;
 106   }
 107
 108   /* Reverses a linked list, returning the pointer to the new head
 109      (old tail) */
 110   static T* reverse(T* head) {
 111     T* rhead = nullptr;
 112     while (head != nullptr) {
 113       auto t = head;
 114       head = next(t);
 115       next(t) = rhead;
 116       rhead = t;
 117     }
 118     return rhead;
 119   }
 120 };
 121
 122 } // namespace folly
 123
 124 #endif