1 | /* |
2 | * Copyright (c) Facebook, Inc. and its affiliates. |
3 | * |
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 |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
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. |
15 | */ |
16 | |
17 | #pragma once |
18 | |
19 | #include <atomic> |
20 | #include <cassert> |
21 | #include <utility> |
22 | |
23 | namespace folly { |
24 | |
25 | /** |
26 | * A very simple atomic single-linked list primitive. |
27 | * |
28 | * Usage: |
29 | * |
30 | * class MyClass { |
31 | * AtomicIntrusiveLinkedListHook<MyClass> hook_; |
32 | * } |
33 | * |
34 | * AtomicIntrusiveLinkedList<MyClass, &MyClass::hook_> list; |
35 | * list.insert(&a); |
36 | * list.sweep([] (MyClass* c) { doSomething(c); } |
37 | */ |
38 | template <class T> |
39 | struct AtomicIntrusiveLinkedListHook { |
40 | T* next{nullptr}; |
41 | }; |
42 | |
43 | template <class T, AtomicIntrusiveLinkedListHook<T> T::*HookMember> |
44 | class AtomicIntrusiveLinkedList { |
45 | public: |
46 | AtomicIntrusiveLinkedList() {} |
47 | AtomicIntrusiveLinkedList(const AtomicIntrusiveLinkedList&) = delete; |
48 | AtomicIntrusiveLinkedList& operator=(const AtomicIntrusiveLinkedList&) = |
49 | delete; |
50 | AtomicIntrusiveLinkedList(AtomicIntrusiveLinkedList&& other) noexcept { |
51 | auto tmp = other.head_.load(); |
52 | other.head_ = head_.load(); |
53 | head_ = tmp; |
54 | } |
55 | AtomicIntrusiveLinkedList& operator=( |
56 | AtomicIntrusiveLinkedList&& other) noexcept { |
57 | auto tmp = other.head_.load(); |
58 | other.head_ = head_.load(); |
59 | head_ = tmp; |
60 | |
61 | return *this; |
62 | } |
63 | |
64 | /** |
65 | * Note: list must be empty on destruction. |
66 | */ |
67 | ~AtomicIntrusiveLinkedList() { |
68 | assert(empty()); |
69 | } |
70 | |
71 | bool empty() const { |
72 | return head_.load() == nullptr; |
73 | } |
74 | |
75 | /** |
76 | * Atomically insert t at the head of the list. |
77 | * @return True if the inserted element is the only one in the list |
78 | * after the call. |
79 | */ |
80 | bool insertHead(T* t) { |
81 | assert(next(t) == nullptr); |
82 | |
83 | auto oldHead = head_.load(std::memory_order_relaxed); |
84 | do { |
85 | next(t) = oldHead; |
86 | /* oldHead is updated by the call below. |
87 | |
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( |
93 | oldHead, t, std::memory_order_release, std::memory_order_relaxed)); |
94 | |
95 | return oldHead == nullptr; |
96 | } |
97 | |
98 | /** |
99 | * Replaces the head with nullptr, |
100 | * and calls func() on the removed elements in the order from tail to head. |
101 | * Returns false if the list was empty. |
102 | */ |
103 | template <typename F> |
104 | bool sweepOnce(F&& func) { |
105 | if (auto head = head_.exchange(nullptr)) { |
106 | auto rhead = reverse(head); |
107 | unlinkAll(rhead, std::forward<F>(func)); |
108 | return true; |
109 | } |
110 | return false; |
111 | } |
112 | |
113 | /** |
114 | * Repeatedly replaces the head with nullptr, |
115 | * and calls func() on the removed elements in the order from tail to head. |
116 | * Stops when the list is empty. |
117 | */ |
118 | template <typename F> |
119 | void sweep(F&& func) { |
120 | while (sweepOnce(func)) { |
121 | } |
122 | } |
123 | |
124 | /** |
125 | * Similar to sweep() but calls func() on elements in LIFO order. |
126 | * |
127 | * func() is called for all elements in the list at the moment |
128 | * reverseSweep() is called. Unlike sweep() it does not loop to ensure the |
129 | * list is empty at some point after the last invocation. This way callers |
130 | * can reason about the ordering: elements inserted since the last call to |
131 | * reverseSweep() will be provided in LIFO order. |
132 | * |
133 | * Example: if elements are inserted in the order 1-2-3, the callback is |
134 | * invoked 3-2-1. If the callback moves elements onto a stack, popping off |
135 | * the stack will produce the original insertion order 1-2-3. |
136 | */ |
137 | template <typename F> |
138 | void reverseSweep(F&& func) { |
139 | // We don't loop like sweep() does because the overall order of callbacks |
140 | // would be strand-wise LIFO which is meaningless to callers. |
141 | auto head = head_.exchange(nullptr); |
142 | unlinkAll(head, std::forward<F>(func)); |
143 | } |
144 | |
145 | private: |
146 | std::atomic<T*> head_{nullptr}; |
147 | |
148 | static T*& next(T* t) { |
149 | return (t->*HookMember).next; |
150 | } |
151 | |
152 | /* Reverses a linked list, returning the pointer to the new head |
153 | (old tail) */ |
154 | static T* reverse(T* head) { |
155 | T* rhead = nullptr; |
156 | while (head != nullptr) { |
157 | auto t = head; |
158 | head = next(t); |
159 | next(t) = rhead; |
160 | rhead = t; |
161 | } |
162 | return rhead; |
163 | } |
164 | |
165 | /* Unlinks all elements in the linked list fragment pointed to by `head', |
166 | * calling func() on every element */ |
167 | template <typename F> |
168 | void unlinkAll(T* head, F&& func) { |
169 | while (head != nullptr) { |
170 | auto t = head; |
171 | head = next(t); |
172 | next(t) = nullptr; |
173 | func(t); |
174 | } |
175 | } |
176 | }; |
177 | |
178 | } // namespace folly |
179 | |