/*
- * 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.
* 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 {
*
* 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();
}
/**
* @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