2 * Copyright 2015 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.
17 #ifndef FOLLY_ATOMIC_LINKED_LIST_H_
18 #define FOLLY_ATOMIC_LINKED_LIST_H_
26 * A very simple atomic single-linked list primitive.
31 * AtomicLinkedListHook<MyClass> hook_;
34 * AtomicLinkedList<MyClass, &MyClass::hook_> list;
36 * list.sweep([] (MyClass* c) { doSomething(c); }
39 struct AtomicLinkedListHook {
43 template <class T, AtomicLinkedListHook<T> T::* HookMember>
44 class AtomicLinkedList {
47 AtomicLinkedList(const AtomicLinkedList&) = delete;
48 AtomicLinkedList& operator=(const AtomicLinkedList&) = delete;
49 AtomicLinkedList(AtomicLinkedList&& other) noexcept {
50 auto tmp = other.head_.load();
51 other.head_ = head_.load();
54 AtomicLinkedList& operator=(AtomicLinkedList&& other) noexcept {
55 auto tmp = other.head_.load();
56 other.head_ = head_.load();
63 * Note: list must be empty on destruction.
70 return head_ == nullptr;
74 * Atomically insert t at the head of the list.
75 * @return True if the inserted element is the only one in the list
78 bool insertHead(T* t) {
79 assert(next(t) == nullptr);
81 auto oldHead = head_.load(std::memory_order_relaxed);
84 /* oldHead is updated by the call below.
86 NOTE: we don't use next(t) instead of oldHead directly due to
87 compiler bugs (GCC prior to 4.8.3 (bug 60272), clang (bug 18899),
88 MSVC (bug 819819); source:
89 http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange */
90 } while (!head_.compare_exchange_weak(oldHead, t,
91 std::memory_order_release,
92 std::memory_order_relaxed));
94 return oldHead == nullptr;
98 * Repeatedly replaces the head with nullptr,
99 * and calls func() on the removed elements in the order from tail to head.
100 * Stops when the list is empty.
102 template <typename F>
103 void sweep(F&& func) {
104 while (auto head = head_.exchange(nullptr)) {
105 auto rhead = reverse(head);
106 while (rhead != nullptr) {
116 std::atomic<T*> head_{nullptr};
118 static T*& next(T* t) {
119 return (t->*HookMember).next;
122 /* Reverses a linked list, returning the pointer to the new head
124 static T* reverse(T* head) {
126 while (head != nullptr) {