2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
26 * A very simple atomic single-linked list primitive.
31 * AtomicIntrusiveLinkedListHook<MyClass> hook_;
34 * AtomicIntrusiveLinkedList<MyClass, &MyClass::hook_> list;
36 * list.sweep([] (MyClass* c) { doSomething(c); }
39 struct AtomicIntrusiveLinkedListHook {
43 template <class T, AtomicIntrusiveLinkedListHook<T> T::*HookMember>
44 class AtomicIntrusiveLinkedList {
46 AtomicIntrusiveLinkedList() {}
47 AtomicIntrusiveLinkedList(const AtomicIntrusiveLinkedList&) = delete;
48 AtomicIntrusiveLinkedList& operator=(const AtomicIntrusiveLinkedList&) =
50 AtomicIntrusiveLinkedList(AtomicIntrusiveLinkedList&& other) noexcept {
51 auto tmp = other.head_.load();
52 other.head_ = head_.load();
55 AtomicIntrusiveLinkedList& operator=(
56 AtomicIntrusiveLinkedList&& other) noexcept {
57 auto tmp = other.head_.load();
58 other.head_ = head_.load();
65 * Note: list must be empty on destruction.
67 ~AtomicIntrusiveLinkedList() {
72 return head_.load() == nullptr;
76 * Atomically insert t at the head of the list.
77 * @return True if the inserted element is the only one in the list
80 bool insertHead(T* t) {
81 assert(next(t) == nullptr);
83 auto oldHead = head_.load(std::memory_order_relaxed);
86 /* oldHead is updated by the call below.
88 NOTE: we don't use next(t) instead of oldHead directly due to
89 compiler bugs (GCC prior to 4.8.3 (bug 60272), clang (bug 18899),
90 MSVC (bug 819819); source:
91 http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange */
92 } while (!head_.compare_exchange_weak(oldHead, t,
93 std::memory_order_release,
94 std::memory_order_relaxed));
96 return oldHead == nullptr;
100 * Repeatedly replaces the head with nullptr,
101 * and calls func() on the removed elements in the order from tail to head.
102 * Stops when the list is empty.
104 template <typename F>
105 void sweep(F&& func) {
106 while (auto head = head_.exchange(nullptr)) {
107 auto rhead = reverse(head);
108 unlinkAll(rhead, std::forward<F>(func));
113 * Similar to sweep() but calls func() on elements in LIFO order.
115 * func() is called for all elements in the list at the moment
116 * reverseSweep() is called. Unlike sweep() it does not loop to ensure the
117 * list is empty at some point after the last invocation. This way callers
118 * can reason about the ordering: elements inserted since the last call to
119 * reverseSweep() will be provided in LIFO order.
121 * Example: if elements are inserted in the order 1-2-3, the callback is
122 * invoked 3-2-1. If the callback moves elements onto a stack, popping off
123 * the stack will produce the original insertion order 1-2-3.
125 template <typename F>
126 void reverseSweep(F&& func) {
127 // We don't loop like sweep() does because the overall order of callbacks
128 // would be strand-wise LIFO which is meaningless to callers.
129 auto head = head_.exchange(nullptr);
130 unlinkAll(head, std::forward<F>(func));
134 std::atomic<T*> head_{nullptr};
136 static T*& next(T* t) {
137 return (t->*HookMember).next;
140 /* Reverses a linked list, returning the pointer to the new head
142 static T* reverse(T* head) {
144 while (head != nullptr) {
153 /* Unlinks all elements in the linked list fragment pointed to by `head',
154 * calling func() on every element */
155 template <typename F>
156 void unlinkAll(T* head, F&& func) {
157 while (head != nullptr) {