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