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.
20 #include <glog/logging.h>
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 *this = std::move(other);
52 AtomicIntrusiveLinkedList& operator=(
53 AtomicIntrusiveLinkedList&& other) noexcept {
54 auto tmp = other.head_.load();
55 other.head_ = head_.load();
62 * Note: list must be empty on destruction.
64 ~AtomicIntrusiveLinkedList() { DCHECK(empty()); }
66 bool empty() const { return head_ == nullptr; }
69 * Atomically insert t at the head of the list.
70 * @return True if the inserted element is the only one in the list
73 bool insertHead(T* t) {
74 DCHECK(next(t) == nullptr);
76 auto oldHead = head_.load(std::memory_order_relaxed);
79 /* oldHead is updated by the call below.
81 NOTE: we don't use next(t) instead of oldHead directly due to
82 compiler bugs (GCC prior to 4.8.3 (bug 60272), clang (bug 18899),
83 MSVC (bug 819819); source:
84 http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange */
85 } while (!head_.compare_exchange_weak(
86 oldHead, t, std::memory_order_release, std::memory_order_relaxed));
88 return oldHead == nullptr;
92 * Repeatedly replaces the head with nullptr,
93 * and calls func() on the removed elements in the order from tail to head.
94 * Stops when the list is empty.
97 void sweep(F&& func) {
98 while (auto head = head_.exchange(nullptr)) {
99 auto rhead = reverse(head);
100 while (rhead != nullptr) {
110 std::atomic<T*> head_{nullptr};
112 static T*& next(T* t) { return (t->*HookMember).next; }
114 /* Reverses a linked list, returning the pointer to the new head
116 static T* reverse(T* head) {
118 while (head != nullptr) {