Debian Codegraph @

LspCpp/include/LibLsp/JsonRpc/threaded_queue.h

raw
1 #pragma once
2
3 #include <optional>
4 #include <algorithm>
5 #include <atomic>
6 #include <condition_variable>
7 #include <deque>
8 #include <memory>
9 #include <mutex>
10 #include <tuple>
11 #include <utility>
12 #include <vector>
13
14 #include "optionalVersion.h"
15
16 struct MultiQueueWaiter;
17
18 struct BaseThreadQueue
19 {
20 virtual ~BaseThreadQueue() = default;
21
22 virtual bool IsEmpty() = 0;
23
24 std::shared_ptr<MultiQueueWaiter> waiter;
25 };
26
27 // std::lock accepts two or more arguments. We define an overload for one
28 // argument.
29 namespace std
30 {
31 template<typename Lockable>
32 void lock(Lockable& l)
33 {
34 l.lock();
35 }
36 } // namespace std
37
38 template<typename... Queue>
39 struct MultiQueueLock
40 {
41 MultiQueueLock(Queue... lockable) : tuple_ {lockable...}
42 {
43 lock();
44 }
45 ~MultiQueueLock()
46 {
47 unlock();
48 }
49 void lock()
50 {
51 lock_impl(typename std::index_sequence_for<Queue...> {});
52 }
53 void unlock()
54 {
55 unlock_impl(typename std::index_sequence_for<Queue...> {});
56 }
57
58 private:
59 template<size_t... Is>
60 void lock_impl(std::index_sequence<Is...>)
61 {
62 std::lock(std::get<Is>(tuple_)->mutex...);
63 }
64
65 template<size_t... Is>
66 void unlock_impl(std::index_sequence<Is...>)
67 {
68 (void)std::initializer_list<int> {(std::get<Is>(tuple_)->mutex.unlock(), 0)...};
69 }
70
71 std::tuple<Queue...> tuple_;
72 };
73
74 struct MultiQueueWaiter
75 {
76 static bool HasState(std::initializer_list<BaseThreadQueue*> queues);
77
78 bool ValidateWaiter(std::initializer_list<BaseThreadQueue*> queues);
79
80 template<typename... BaseThreadQueue>
81 bool Wait(std::atomic<bool>& quit, BaseThreadQueue... queues)
82 {
83 MultiQueueLock<BaseThreadQueue...> l(queues...);
84 while (!quit.load(std::memory_order_relaxed))
85 {
86 if (HasState({queues...}))
87 {
88 return false;
89 }
90 cv.wait(l);
91 }
92 return true;
93 }
94 template<typename... BaseThreadQueue>
95 void WaitUntil(std::chrono::steady_clock::time_point t, BaseThreadQueue... queues)
96 {
97 MultiQueueLock<BaseThreadQueue...> l(queues...);
98 if (!HasState({queues...}))
99 {
100 cv.wait_until(l, t);
101 }
102 }
103 template<typename... BaseThreadQueue>
104 void Wait(BaseThreadQueue... queues)
105 {
106 assert(ValidateWaiter({queues...}));
107
108 MultiQueueLock<BaseThreadQueue...> l(queues...);
109 while (!HasState({queues...}))
110 {
111 cv.wait(l);
112 }
113 }
114
115 std::condition_variable_any cv;
116 };
117
118 // A threadsafe-queue. http://stackoverflow.com/a/16075550
119 template<class T>
120 struct ThreadedQueue : public BaseThreadQueue
121 {
122 public:
123 ThreadedQueue() : ThreadedQueue(std::make_shared<MultiQueueWaiter>())
124 {
125 }
126
127 explicit ThreadedQueue(std::shared_ptr<MultiQueueWaiter> waiter) : total_count_(0)
128 {
129 this->waiter = waiter;
130 }
131
132 // Returns the number of elements in the queue. This is lock-free.
133 size_t Size() const
134 {
135 return total_count_;
136 }
137
138 // Add an element to the queue.
139 void Enqueue(T&& t, bool priority)
140 {
141 {
142 std::lock_guard<std::mutex> lock(mutex);
143 if (priority)
144 {
145 priority_.push_back(std::move(t));
146 }
147 else
148 {
149 queue_.push_back(std::move(t));
150 }
151 ++total_count_;
152 }
153 waiter->cv.notify_one();
154 }
155
156 // Add a set of elements to the queue.
157 void EnqueueAll(std::vector<T>&& elements, bool priority)
158 {
159 if (elements.empty())
160 {
161 return;
162 }
163
164 {
165 std::lock_guard<std::mutex> lock(mutex);
166 total_count_ += elements.size();
167 for (T& element : elements)
168 {
169 if (priority)
170 {
171 priority_.push_back(std::move(element));
172 }
173 else
174 {
175 queue_.push_back(std::move(element));
176 }
177 }
178 elements.clear();
179 }
180
181 waiter->cv.notify_all();
182 }
183
184 // Returns true if the queue is empty. This is lock-free.
185 bool IsEmpty()
186 {
187 return total_count_ == 0;
188 }
189
190 // Get the first element from the queue. Blocks until one is available.
191 T Dequeue()
192 {
193 std::unique_lock<std::mutex> lock(mutex);
194 waiter->cv.wait(lock, [&]() { return !priority_.empty() || !queue_.empty(); });
195
196 auto execute = [&](std::deque<T>* q)
197 {
198 auto val = std::move(q->front());
199 q->pop_front();
200 --total_count_;
201 return std::move(val);
202 };
203 if (!priority_.empty())
204 {
205 return execute(&priority_);
206 }
207 return execute(&queue_);
208 }
209
210 // Get the first element from the queue without blocking. Returns a null
211 // value if the queue is empty.
212 optional<T> TryDequeue(bool priority)
213 {
214 std::lock_guard<std::mutex> lock(mutex);
215
216 auto pop = [&](std::deque<T>* q)
217 {
218 auto val = std::move(q->front());
219 q->pop_front();
220 --total_count_;
221 return std::move(val);
222 };
223
224 auto get_result = [&](std::deque<T>* first, std::deque<T>* second) -> optional<T>
225 {
226 if (!first->empty())
227 {
228 return pop(first);
229 }
230 if (!second->empty())
231 {
232 return pop(second);
233 }
234 return {};
235 };
236
237 if (priority)
238 {
239 return get_result(&priority_, &queue_);
240 }
241 return get_result(&queue_, &priority_);
242 }
243 // Return all elements in the queue.
244 std::vector<T> DequeueAll()
245 {
246 std::lock_guard<std::mutex> lock(mutex);
247
248 total_count_ = 0;
249
250 std::vector<T> result;
251 result.reserve(priority_.size() + queue_.size());
252 while (!priority_.empty())
253 {
254 result.emplace_back(std::move(priority_.front()));
255 priority_.pop_front();
256 }
257 while (!queue_.empty())
258 {
259 result.emplace_back(std::move(queue_.front()));
260 queue_.pop_front();
261 }
262
263 return result;
264 }
265 std::vector<T> TryDequeueSome(size_t num)
266 {
267 std::lock_guard<std::mutex> lock(mutex);
268
269 std::vector<T> result;
270 num = std::min(num, priority_.size() + queue_.size());
271 total_count_ -= num;
272 result.reserve(num);
273 while (num)
274 {
275 if (!priority_.empty())
276 {
277 result.emplace_back(std::move(priority_.front()));
278 priority_.pop_front();
279 }
280 else
281 {
282 break;
283 }
284 num -= 1;
285 }
286 while (num)
287 {
288 if (!queue_.empty())
289 {
290 result.emplace_back(std::move(queue_.front()));
291 queue_.pop_front();
292 }
293 else
294 {
295 break;
296 }
297 num -= 1;
298 }
299 return result;
300 }
301 template<typename Fn>
302 void Iterate(Fn fn)
303 {
304 std::lock_guard<std::mutex> lock(mutex);
305 for (auto& entry : priority_)
306 {
307 fn(entry);
308 }
309 for (auto& entry : queue_)
310 {
311 fn(entry);
312 }
313 }
314
315 mutable std::mutex mutex;
316
317 private:
318 std::atomic<int> total_count_;
319 std::deque<T> priority_;
320 std::deque<T> queue_;
321 };