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