Move folly/BitIterator.h to folly/container/

[folly.git] / folly / AtomicLinkedList.h

diff --git a/folly/AtomicLinkedList.h b/folly/AtomicLinkedList.h
index eca8de16d9b32450cdab81876ae1c3834c6c9efe..4d1d8503452ad6683be6a8fc479a4f343bf16d9f 100644 (file)
--- a/folly/AtomicLinkedList.h
+++ b/folly/AtomicLinkedList.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2015 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -14,11 +14,10 @@
  * limitations under the License.
  */
 
-#ifndef FOLLY_ATOMIC_LINKED_LIST_H_
-#define FOLLY_ATOMIC_LINKED_LIST_H_
+#pragma once
 
-#include <atomic>
-#include <cassert>
+#include <folly/AtomicIntrusiveLinkedList.h>
+#include <folly/Memory.h>
 
 namespace folly {
 
@@ -27,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;
+  AtomicLinkedList(AtomicLinkedList&& other) noexcept = default;
+  AtomicLinkedList& operator=(AtomicLinkedList&& other) = default;
 
-    return *this;
-  }
-
-  /**
-   * Note: list must be empty on destruction.
-   */
   ~AtomicLinkedList() {
-    assert(head_ == nullptr);
+    sweep([](T&&) {});
   }
 
   bool empty() const {
-    return head_ == nullptr;
+    return list_.empty();
   }
 
   /**
@@ -75,64 +53,56 @@ 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.
-
-         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;
+  bool insertHead(T t) {
+    auto wrapper = std::make_unique<Wrapper>(std::move(t));
+
+    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};
+  /**
+   * Similar to sweep() but calls func() on elements in LIFO order.
+   *
+   * func() is called for all elements in the list at the moment
+   * reverseSweep() is called.  Unlike sweep() it does not loop to ensure the
+   * list is empty at some point after the last invocation.  This way callers
+   * can reason about the ordering: elements inserted since the last call to
+   * reverseSweep() will be provided in LIFO order.
+   *
+   * Example: if elements are inserted in the order 1-2-3, the callback is
+   * invoked 3-2-1.  If the callback moves elements onto a stack, popping off
+   * the stack will produce the original insertion order 1-2-3.
+   */
+  template <typename F>
+  void reverseSweep(F&& func) {
+    list_.reverseSweep([&](Wrapper* wrapperPtr) mutable {
+      std::unique_ptr<Wrapper> wrapper(wrapperPtr);
 
-  static T*& next(T* t) {
-    return (t->*HookMember).next;
+      func(std::move(wrapper->data));
+    });
   }
 
-  /* 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;
-  }
+ private:
+  struct Wrapper {
+    explicit Wrapper(T&& t) : data(std::move(t)) {}
+
+    AtomicIntrusiveLinkedListHook<Wrapper> hook;
+    T data;
+  };
+  AtomicIntrusiveLinkedList<Wrapper, &Wrapper::hook> list_;
 };
 
 } // namespace folly
-
-#endif