/*
- * Copyright 2016 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.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+
#pragma once
#include <atomic>
-
-#include <glog/logging.h>
+#include <cassert>
+#include <utility>
namespace folly {
AtomicIntrusiveLinkedList& operator=(const AtomicIntrusiveLinkedList&) =
delete;
AtomicIntrusiveLinkedList(AtomicIntrusiveLinkedList&& other) noexcept {
- *this = std::move(other);
+ auto tmp = other.head_.load();
+ other.head_ = head_.load();
+ head_ = tmp;
}
AtomicIntrusiveLinkedList& operator=(
AtomicIntrusiveLinkedList&& other) noexcept {
/**
* Note: list must be empty on destruction.
*/
- ~AtomicIntrusiveLinkedList() { DCHECK(empty()); }
+ ~AtomicIntrusiveLinkedList() {
+ assert(empty());
+ }
- bool empty() const { return head_ == nullptr; }
+ bool empty() const {
+ return head_.load() == nullptr;
+ }
/**
* Atomically insert t at the head of the list.
* after the call.
*/
bool insertHead(T* t) {
- DCHECK(next(t) == nullptr);
+ assert(next(t) == nullptr);
auto oldHead = head_.load(std::memory_order_relaxed);
do {
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));
+ } while (!head_.compare_exchange_weak(oldHead, t,
+ std::memory_order_release,
+ std::memory_order_relaxed));
return oldHead == nullptr;
}
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);
- }
+ unlinkAll(rhead, std::forward<F>(func));
}
}
+ /**
+ * 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) {
+ // We don't loop like sweep() does because the overall order of callbacks
+ // would be strand-wise LIFO which is meaningless to callers.
+ auto head = head_.exchange(nullptr);
+ unlinkAll(head, std::forward<F>(func));
+ }
+
private:
std::atomic<T*> head_{nullptr};
- static T*& next(T* t) { return (t->*HookMember).next; }
+ static T*& next(T* t) {
+ return (t->*HookMember).next;
+ }
/* Reverses a linked list, returning the pointer to the new head
(old tail) */
}
return rhead;
}
+
+ /* Unlinks all elements in the linked list fragment pointed to by `head',
+ * calling func() on every element */
+ template <typename F>
+ void unlinkAll(T* head, F&& func) {
+ while (head != nullptr) {
+ auto t = head;
+ head = next(t);
+ next(t) = nullptr;
+ func(t);
+ }
+ }
};
} // namespace folly