1/*
2 * Copyright 2014-present Facebook, Inc.
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
23namespace 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 */
38template <class T>
39struct AtomicIntrusiveLinkedListHook {
40 T* next{nullptr};
41};
42
43template <class T, AtomicIntrusiveLinkedListHook<T> T::*HookMember>
44class 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