2 * Copyright 2016 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.
25 * A very simple atomic single-linked list primitive.
30 * AtomicIntrusiveLinkedListHook<MyClass> hook_;
33 * AtomicIntrusiveLinkedList<MyClass, &MyClass::hook_> list;
35 * list.sweep([] (MyClass* c) { doSomething(c); }
38 struct AtomicIntrusiveLinkedListHook {
42 template <class T, AtomicIntrusiveLinkedListHook<T> T::*HookMember>
43 class AtomicIntrusiveLinkedList {
45 AtomicIntrusiveLinkedList() {}
46 AtomicIntrusiveLinkedList(const AtomicIntrusiveLinkedList&) = delete;
47 AtomicIntrusiveLinkedList& operator=(const AtomicIntrusiveLinkedList&) =
49 AtomicIntrusiveLinkedList(AtomicIntrusiveLinkedList&& other) noexcept {
50 auto tmp = other.head_.load();
51 other.head_ = head_.load();
54 AtomicIntrusiveLinkedList& operator=(
55 AtomicIntrusiveLinkedList&& other) noexcept {
56 auto tmp = other.head_.load();
57 other.head_ = head_.load();
64 * Note: list must be empty on destruction.
66 ~AtomicIntrusiveLinkedList() {
71 return head_.load() == nullptr;
75 * Atomically insert t at the head of the list.
76 * @return True if the inserted element is the only one in the list
79 bool insertHead(T* t) {
80 assert(next(t) == nullptr);
82 auto oldHead = head_.load(std::memory_order_relaxed);
85 /* oldHead is updated by the call below.
87 NOTE: we don't use next(t) instead of oldHead directly due to
88 compiler bugs (GCC prior to 4.8.3 (bug 60272), clang (bug 18899),
89 MSVC (bug 819819); source:
90 http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange */
91 } while (!head_.compare_exchange_weak(oldHead, t,
92 std::memory_order_release,
93 std::memory_order_relaxed));
95 return oldHead == nullptr;
99 * Repeatedly replaces the head with nullptr,
100 * and calls func() on the removed elements in the order from tail to head.
101 * Stops when the list is empty.
103 template <typename F>
104 void sweep(F&& func) {
105 while (auto head = head_.exchange(nullptr)) {
106 auto rhead = reverse(head);
107 while (rhead != nullptr) {
117 std::atomic<T*> head_{nullptr};
119 static T*& next(T* t) {
120 return (t->*HookMember).next;
123 /* Reverses a linked list, returning the pointer to the new head
125 static T* reverse(T* head) {
127 while (head != nullptr) {