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 <folly/AtomicIntrusiveLinkedList.h> |
20 | #include <folly/Memory.h> |
21 | |
22 | namespace folly { |
23 | |
24 | /** |
25 | * A very simple atomic single-linked list primitive. |
26 | * |
27 | * Usage: |
28 | * |
29 | * AtomicLinkedList<MyClass> list; |
30 | * list.insert(a); |
31 | * list.sweep([] (MyClass& c) { doSomething(c); } |
32 | */ |
33 | |
34 | template <class T> |
35 | class AtomicLinkedList { |
36 | public: |
37 | AtomicLinkedList() {} |
38 | AtomicLinkedList(const AtomicLinkedList&) = delete; |
39 | AtomicLinkedList& operator=(const AtomicLinkedList&) = delete; |
40 | AtomicLinkedList(AtomicLinkedList&& other) noexcept = default; |
41 | AtomicLinkedList& operator=(AtomicLinkedList&& other) = default; |
42 | |
43 | ~AtomicLinkedList() { |
44 | sweep([](T&&) {}); |
45 | } |
46 | |
47 | bool empty() const { |
48 | return list_.empty(); |
49 | } |
50 | |
51 | /** |
52 | * Atomically insert t at the head of the list. |
53 | * @return True if the inserted element is the only one in the list |
54 | * after the call. |
55 | */ |
56 | bool insertHead(T t) { |
57 | auto wrapper = std::make_unique<Wrapper>(std::move(t)); |
58 | |
59 | return list_.insertHead(wrapper.release()); |
60 | } |
61 | |
62 | /** |
63 | * Repeatedly pops element from head, |
64 | * and calls func() on the removed elements in the order from tail to head. |
65 | * Stops when the list is empty. |
66 | */ |
67 | template <typename F> |
68 | void sweep(F&& func) { |
69 | list_.sweep([&](Wrapper* wrapperPtr) mutable { |
70 | std::unique_ptr<Wrapper> wrapper(wrapperPtr); |
71 | |
72 | func(std::move(wrapper->data)); |
73 | }); |
74 | } |
75 | |
76 | /** |
77 | * Similar to sweep() but calls func() on elements in LIFO order. |
78 | * |
79 | * func() is called for all elements in the list at the moment |
80 | * reverseSweep() is called. Unlike sweep() it does not loop to ensure the |
81 | * list is empty at some point after the last invocation. This way callers |
82 | * can reason about the ordering: elements inserted since the last call to |
83 | * reverseSweep() will be provided in LIFO order. |
84 | * |
85 | * Example: if elements are inserted in the order 1-2-3, the callback is |
86 | * invoked 3-2-1. If the callback moves elements onto a stack, popping off |
87 | * the stack will produce the original insertion order 1-2-3. |
88 | */ |
89 | template <typename F> |
90 | void reverseSweep(F&& func) { |
91 | list_.reverseSweep([&](Wrapper* wrapperPtr) mutable { |
92 | std::unique_ptr<Wrapper> wrapper(wrapperPtr); |
93 | |
94 | func(std::move(wrapper->data)); |
95 | }); |
96 | } |
97 | |
98 | private: |
99 | struct Wrapper { |
100 | explicit Wrapper(T&& t) : data(std::move(t)) {} |
101 | |
102 | AtomicIntrusiveLinkedListHook<Wrapper> hook; |
103 | T data; |
104 | }; |
105 | AtomicIntrusiveLinkedList<Wrapper, &Wrapper::hook> list_; |
106 | }; |
107 | |
108 | } // namespace folly |
109 | |