folly/AtomicLinkedList.h

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