Non-intrusive AtomicLinkedList

[folly.git] / folly / AtomicLinkedList.h

diff --git a/folly/AtomicLinkedList.h b/folly/AtomicLinkedList.h
index 459036ef6a91f5d0cf1b9e0aa6025f5f6c36e443..71f56bfc5d318b2af2fbbfe867f4954e63798672 100644 (file)
--- a/folly/AtomicLinkedList.h
+++ b/folly/AtomicLinkedList.h
@@ -16,8 +16,8 @@
 
 #pragma once
 
-#include <atomic>
-#include <cassert>
+#include <folly/AtomicIntrusiveLinkedList.h>
+#include <folly/Memory.h>
 
 namespace folly {
 
@@ -26,47 +26,26 @@ namespace folly {
  *
  * Usage:
  *
- * class MyClass {
- *   AtomicLinkedListHook<MyClass> hook_;
- * }
- *
- * AtomicLinkedList<MyClass, &MyClass::hook_> list;
- * list.insert(&a);
- * list.sweep([] (MyClass* c) { doSomething(c); }
+ * AtomicLinkedList<MyClass> list;
+ * list.insert(a);
+ * list.sweep([] (MyClass& c) { doSomething(c); }
  */
-template <class T>
-struct AtomicLinkedListHook {
-  T* next{nullptr};
-};
 
-template <class T, AtomicLinkedListHook<T> T::* HookMember>
+template <class T>
 class AtomicLinkedList {
  public:
   AtomicLinkedList() {}
   AtomicLinkedList(const AtomicLinkedList&) = delete;
   AtomicLinkedList& operator=(const AtomicLinkedList&) = delete;
-  AtomicLinkedList(AtomicLinkedList&& other) noexcept {
-    auto tmp = other.head_.load();
-    other.head_ = head_.load();
-    head_ = tmp;
-  }
-  AtomicLinkedList& operator=(AtomicLinkedList&& other) noexcept {
-    auto tmp = other.head_.load();
-    other.head_ = head_.load();
-    head_ = tmp;
-
-    return *this;
-  }
+  AtomicLinkedList(AtomicLinkedList&& other) noexcept = default;
+  AtomicLinkedList& operator=(AtomicLinkedList&& other) = default;
 
-  /**
-   * Note: list must be empty on destruction.
-   */
   ~AtomicLinkedList() {
-    assert(empty());
+    sweep([](T&&) {});
   }
 
   bool empty() const {
-    return head_ == nullptr;
+    return list_.empty();
   }
 
   /**
@@ -74,62 +53,34 @@ class AtomicLinkedList {
    * @return True if the inserted element is the only one in the list
    *         after the call.
    */
-  bool insertHead(T* t) {
-    assert(next(t) == nullptr);
-
-    auto oldHead = head_.load(std::memory_order_relaxed);
-    do {
-      next(t) = oldHead;
-      /* oldHead is updated by the call below.
+  bool insertHead(T t) {
+    auto wrapper = folly::make_unique<Wrapper>(std::move(t));
 
-         NOTE: we don't use next(t) instead of oldHead directly due to
-         compiler bugs (GCC prior to 4.8.3 (bug 60272), clang (bug 18899),
-         MSVC (bug 819819); source:
-         http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange */
-    } while (!head_.compare_exchange_weak(oldHead, t,
-                                          std::memory_order_release,
-                                          std::memory_order_relaxed));
-
-    return oldHead == nullptr;
+    return list_.insertHead(wrapper.release());
   }
 
   /**
-   * Repeatedly replaces the head with nullptr,
+   * Repeatedly pops element from head,
    * and calls func() on the removed elements in the order from tail to head.
    * Stops when the list is empty.
    */
   template <typename F>
   void sweep(F&& func) {
-    while (auto head = head_.exchange(nullptr)) {
-      auto rhead = reverse(head);
-      while (rhead != nullptr) {
-        auto t = rhead;
-        rhead = next(t);
-        next(t) = nullptr;
-        func(t);
-      }
-    }
+    list_.sweep([&](Wrapper* wrapperPtr) mutable {
+      std::unique_ptr<Wrapper> wrapper(wrapperPtr);
+
+      func(std::move(wrapper->data));
+    });
   }
 
  private:
-  std::atomic<T*> head_{nullptr};
+  struct Wrapper {
+    explicit Wrapper(T&& t) : data(std::move(t)) {}
 
-  static T*& next(T* t) {
-    return (t->*HookMember).next;
-  }
-
-  /* Reverses a linked list, returning the pointer to the new head
-     (old tail) */
-  static T* reverse(T* head) {
-    T* rhead = nullptr;
-    while (head != nullptr) {
-      auto t = head;
-      head = next(t);
-      next(t) = rhead;
-      rhead = t;
-    }
-    return rhead;
-  }
+    AtomicIntrusiveLinkedListHook<Wrapper> hook;
+    T data;
+  };
+  AtomicIntrusiveLinkedList<Wrapper, &Wrapper::hook> list_;
 };
 
 } // namespace folly