Luanti 5.19.0-dev
Loading...
Searching...
No Matches
container.h
Go to the documentation of this file.
1// Luanti
2// SPDX-License-Identifier: LGPL-2.1-or-later
3// Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
4
5#pragma once
6
7#include "irrlichttypes.h"
8#include "debug.h" // sanity_check
9#include "exceptions.h"
11#include "threading/semaphore.h"
12#include <list>
13#include <vector>
14#include <map>
15#include <unordered_set>
16#include <queue>
17#include <cassert>
18#include <limits>
19
20/*
21 Queue with unique values with fast checking of value existence
22*/
23
24template<typename Value>
26{
27public:
28
29 /*
30 Does nothing if value is already queued.
31 Return value:
32 true: value added
33 false: value already exists
34 */
35 bool push_back(const Value &value)
36 {
37 if (m_set.insert(value).second)
38 {
39 m_queue.push(value);
40 return true;
41 }
42 return false;
43 }
44
45 void pop_front()
46 {
47 m_set.erase(m_queue.front());
48 m_queue.pop();
49 }
50
51 const Value &front() const
52 {
53 return m_queue.front();
54 }
55
56 size_t size() const
57 {
58 return m_queue.size();
59 }
60
61 bool empty() const
62 {
63 return m_queue.empty();
64 }
65
66private:
67 std::unordered_set<Value> m_set;
68 std::queue<Value> m_queue;
69};
70
71/*
72 Thread-safe map
73*/
74
75template<typename Key, typename Value>
77{
78public:
79 MutexedMap() = default;
80
81 void set(const Key &name, const Value &value)
82 {
84 m_values[name] = value;
85 }
86
87 bool get(const Key &name, Value *result) const
88 {
90 auto n = m_values.find(name);
91 if (n == m_values.end())
92 return false;
93 if (result)
94 *result = n->second;
95 return true;
96 }
97
98 std::vector<Value> getValues() const
99 {
101 std::vector<Value> result;
102 result.reserve(m_values.size());
103 for (auto it = m_values.begin(); it != m_values.end(); ++it)
104 result.push_back(it->second);
105 return result;
106 }
107
108 void clear()
109 {
111 m_values.clear();
112 }
113
114private:
115 std::map<Key, Value> m_values;
116 mutable std::mutex m_mutex;
117};
118
119
120/*
121 Thread-safe double-ended queue
122*/
123
124template<typename T>
126{
127public:
128 template<typename Key, typename U, typename Caller, typename CallerData>
129 friend class RequestQueue;
130
131 MutexedQueue() = default;
132
133 bool empty() const
134 {
136 return m_queue.empty();
137 }
138
139 void push_back(const T &t)
140 {
141 {
143 m_queue.push_back(t);
144 }
145 m_signal.post();
146 }
147
148 void push_back(T &&t)
149 {
150 {
152 m_queue.push_back(std::move(t));
153 }
154 m_signal.post();
155 }
156
157 /* this version of pop_front returns an empty element of T on timeout.
158 * Make sure default constructor of T creates a recognizable "empty" element
159 */
160 T pop_frontNoEx(u32 wait_time_max_ms)
161 {
162 if (m_signal.wait(wait_time_max_ms)) {
164
165 T t = std::move(m_queue.front());
166 m_queue.pop_front();
167 return t;
168 }
169
170 return T();
171 }
172
173 T pop_front(u32 wait_time_max_ms)
174 {
175 if (m_signal.wait(wait_time_max_ms)) {
177
178 T t = std::move(m_queue.front());
179 m_queue.pop_front();
180 return t;
181 }
182
183 throw ItemNotFoundException("MutexedQueue: queue is empty");
184 }
185
187 {
188 m_signal.wait();
189
191
192 T t = std::move(m_queue.front());
193 m_queue.pop_front();
194 return t;
195 }
196
197 T pop_back(u32 wait_time_max_ms=0)
198 {
199 if (m_signal.wait(wait_time_max_ms)) {
201
202 T t = std::move(m_queue.back());
203 m_queue.pop_back();
204 return t;
205 }
206
207 throw ItemNotFoundException("MutexedQueue: queue is empty");
208 }
209
210 /* this version of pop_back returns an empty element of T on timeout.
211 * Make sure default constructor of T creates a recognizable "empty" element
212 */
213 T pop_backNoEx(u32 wait_time_max_ms)
214 {
215 if (m_signal.wait(wait_time_max_ms)) {
217
218 T t = std::move(m_queue.back());
219 m_queue.pop_back();
220 return t;
221 }
222
223 return T();
224 }
225
227 {
228 m_signal.wait();
229
231
232 T t = std::move(m_queue.back());
233 m_queue.pop_back();
234 return t;
235 }
236
238 {
239 return IterationHelper(this);
240 }
241
242protected:
243 // Helper class that allows direct access to the queue with locking
245 friend class MutexedQueue<T>;
247 bool empty = q->getQueue().empty();
248 q->getMutex().unlock();
249 if (!empty)
250 q->getSignal().post(); // assume modified
251 }
252
253 auto begin() { return q->getQueue().begin(); }
254 auto end() { return q->getQueue().end(); }
255
256 auto erase(typename std::deque<T>::iterator it) {
257 return q->getQueue().erase(it);
258 }
259
260 private:
261 IterationHelper(MutexedQueue<T> *parent) : q(parent) {
262 q->getMutex().lock();
263 }
264
266 };
267
268 std::mutex &getMutex() { return m_mutex; }
270
271 std::deque<T> &getQueue() { return m_queue; }
272
273 std::deque<T> m_queue;
274 mutable std::mutex m_mutex;
276};
277
278/*
279 LRU cache
280*/
281
282template<typename K, typename V>
284{
285public:
286 LRUCache(size_t limit, void (*cache_miss)(void *data, const K &key, V *dest),
287 void *data)
288 {
289 setLimit(limit);
290 m_cache_miss = cache_miss;
291 m_cache_miss_data = data;
292 }
293
294 void setLimit(size_t limit)
295 {
296 m_limit = std::max<size_t>(1, limit);
297 invalidate();
298 }
299
301 {
302 m_map.clear();
303 m_queue.clear();
304 }
305
306 const V *lookupCache(const K &key)
307 {
308 auto it = m_map.find(key);
309 const V *ret;
310 if (it != m_map.end()) {
311 // found!
312 cache_entry &entry = it->second;
313
314 ret = &entry.second;
315
316 // update the usage information
317 if (entry.first != m_queue.begin()) {
318 m_queue.erase(entry.first);
319 m_queue.push_front(key);
320 entry.first = m_queue.begin();
321 }
322 } else {
323 // cache miss -- enter into cache
324 cache_entry &entry = m_map[key];
325 m_cache_miss(m_cache_miss_data, key, &entry.second);
326 ret = &entry.second;
327
328 // delete old entries
329 if (m_queue.size() == m_limit) {
330 const K &id = m_queue.back();
331 m_map.erase(id);
332 m_queue.pop_back();
333 }
334
335 m_queue.push_front(key);
336 entry.first = m_queue.begin();
337 }
338 return ret;
339 }
340
341private:
342 typedef typename std::pair<typename std::list<K>::iterator, V> cache_entry;
343 typedef std::map<K, cache_entry> cache_type;
344
345 void (*m_cache_miss)(void *data, const K &key, V *dest);
347 size_t m_limit;
348
350 // we can't use std::deque here, because its iterators get invalidated
351 std::list<K> m_queue;
352};
353
354/*
355 Map that can be safely modified (insertion, deletion) during iteration
356 Caveats:
357 - you cannot insert null elements
358 - you have to check for null elements during iteration, those are ones already deleted
359 - size() and empty() don't work during iteration
360 - not thread-safe in any way
361
362 How this is implemented:
363 - there are two maps: new and real
364 - if inserting during iteration, the value is inserted into the "new" map
365 - if deleting during iteration, the value is set to null (to be GC'd later)
366 - when iteration finishes the "new" map is merged into the "real" map
367*/
368
369template<typename K, typename V>
371{
372public:
373 // this allows bare pointers but also e.g. std::unique_ptr
374 static_assert(std::is_default_constructible<V>::value,
375 "Value type must be default constructible");
376 static_assert(std::is_constructible<bool, V>::value,
377 "Value type must be convertible to bool");
378 static_assert(std::is_move_assignable<V>::value,
379 "Value type must be move-assignable");
380
381 typedef K key_type;
382 typedef V mapped_type;
383
385 // the null value must convert to false and all others to true, but
386 // we can't statically check the latter.
388 }
390 assert(!m_iterating);
391 }
392
393 // possible to implement but we don't need it
396
397 const V &get(const K &key) const {
398 if (m_iterating) {
399 auto it = m_new.find(key);
400 if (it != m_new.end())
401 return it->second;
402 }
403 auto it = m_values.find(key);
404 // This conditional block was converted from a ternary to ensure no
405 // temporary values are created in evaluating the return expression,
406 // which could cause a dangling reference.
407 if (it != m_values.end())
408 return it->second;
409 else
410 return null_value;
411 }
412
413 void put(const K &key, const V &value) {
414 if (!value) {
415 assert(false);
416 return;
417 }
418 if (m_iterating) {
419 auto it = m_values.find(key);
420 if (it != m_values.end()) {
421 it->second = V();
422 m_garbage++;
423 }
424 m_new[key] = value;
425 } else {
426 m_values[key] = value;
427 }
428 }
429
430 void put(const K &key, V &&value) {
431 if (!value) {
432 assert(false);
433 return;
434 }
435 if (m_iterating) {
436 auto it = m_values.find(key);
437 if (it != m_values.end()) {
438 it->second = V();
439 m_garbage++;
440 }
441 m_new[key] = std::move(value);
442 } else {
443 m_values[key] = std::move(value);
444 }
445 }
446
447 V take(const K &key) {
448 V ret = V();
449 if (m_iterating) {
450 auto it = m_new.find(key);
451 if (it != m_new.end()) {
452 ret = std::move(it->second);
453 m_new.erase(it);
454 }
455 }
456 auto it = m_values.find(key);
457 if (it == m_values.end())
458 return ret;
459 if (!ret)
460 ret = std::move(it->second);
461 if (m_iterating) {
462 it->second = V();
463 m_garbage++;
464 } else {
465 m_values.erase(it);
466 }
467 return ret;
468 }
469
470 bool remove(const K &key) {
471 return !!take(key);
472 }
473
475 size_t size() const {
476 if (m_iterating) {
477 // This is by no means impossible to determine, it's just annoying
478 // to code and we happen to not need this.
479 return unknown;
480 }
481 assert(m_new.empty());
482 if (m_garbage == 0)
483 return m_values.size();
484 size_t n = 0;
485 for (auto &it : m_values)
486 n += !it.second ? 0 : 1;
487 return n;
488 }
489
491 bool empty() const {
492 if (m_iterating)
493 return false; // maybe
494 if (m_garbage == 0)
495 return m_values.empty();
496 for (auto &it : m_values) {
497 if (!!it.second)
498 return false;
499 }
500 return true;
501 }
502
503 auto iter() { return IterationHelper(this); }
504
505 void clear() {
506 if (m_iterating) {
507 for (auto &it : m_values)
508 it.second = V();
509 m_garbage = m_values.size();
510 } else {
511 m_values.clear();
512 m_garbage = 0;
513 }
514 }
515
516 static inline const V null_value = V();
517
518 // returned by size() if called during iteration
519 static constexpr size_t unknown = static_cast<size_t>(-1);
520
521protected:
522 void merge_new() {
523 assert(!m_iterating);
524 if (!m_new.empty()) {
525 m_new.merge(m_values); // entries in m_new take precedence
526 m_values.clear();
527 std::swap(m_values, m_new);
528 }
529 }
530
532 assert(!m_iterating);
533 if (m_values.size() < GC_MIN_SIZE || m_garbage < m_values.size() / 2)
534 return;
535 for (auto it = m_values.begin(); it != m_values.end(); ) {
536 if (!it->second)
537 it = m_values.erase(it);
538 else
539 ++it;
540 }
541 m_garbage = 0;
542 }
543
545 friend class ModifySafeMap<K, V>;
547 assert(m->m_iterating);
548 m->m_iterating--;
549 if (!m->m_iterating) {
550 m->merge_new();
551 m->collect_garbage();
552 }
553 }
554
555 auto begin() { return m->m_values.cbegin(); }
556 auto end() { return m->m_values.cend(); }
557
558 private:
560 assert(m->m_iterating < std::numeric_limits<decltype(m_iterating)>::max());
561 m->m_iterating++;
562 }
563
565 };
566
567private:
568 std::map<K, V> m_values;
569 std::map<K, V> m_new;
570 unsigned int m_iterating = 0;
571 // approximate amount of null-placeholders in m_values, reliable for != 0 tests
572 size_t m_garbage = 0;
573
574 static constexpr size_t GC_MIN_SIZE = 30;
575};
#define DISABLE_CLASS_COPY(C)
Definition basic_macros.h:26
#define ALLOW_CLASS_MOVE(C)
Definition basic_macros.h:32
ItemNotFoundException(const std::string &s)
Definition exceptions.h:68
size_t m_limit
Definition container.h:347
cache_type m_map
Definition container.h:349
LRUCache(size_t limit, void(*cache_miss)(void *data, const K &key, V *dest), void *data)
Definition container.h:286
void setLimit(size_t limit)
Definition container.h:294
const V * lookupCache(const K &key)
Definition container.h:306
void * m_cache_miss_data
Definition container.h:346
std::map< K, cache_entry > cache_type
Definition container.h:343
std::pair< typename std::list< K >::iterator, V > cache_entry
Definition container.h:342
void invalidate()
Definition container.h:300
std::list< K > m_queue
Definition container.h:351
void(*) m_cache_miss(void *data, const K &key, V *dest)
Definition container.h:345
Definition container.h:371
const void *& get(const u16 &key) const
Definition container.h:397
size_t m_garbage
Definition container.h:572
void * mapped_type
Definition container.h:382
~ModifySafeMap()
Definition container.h:389
u16 key_type
Definition container.h:381
void clear()
Definition container.h:505
size_t size() const
Definition container.h:475
auto iter()
Definition container.h:503
void put(const K &key, V &&value)
Definition container.h:430
ModifySafeMap()
Definition container.h:384
V take(const K &key)
Definition container.h:447
static constexpr size_t GC_MIN_SIZE
Definition container.h:574
static constexpr size_t unknown
Definition container.h:519
void put(const K &key, const V &value)
Definition container.h:413
void collect_garbage()
Definition container.h:531
bool empty() const
Definition container.h:491
bool remove(const K &key)
Definition container.h:470
std::map< u16, void * > m_values
Definition container.h:568
unsigned int m_iterating
Definition container.h:570
static const void * null_value
Definition container.h:516
void merge_new()
Definition container.h:522
std::map< u16, void * > m_new
Definition container.h:569
std::vector< Value > getValues() const
Definition container.h:98
bool get(const Key &name, Value *result) const
Definition container.h:87
MutexedMap()=default
std::map< Key, Value > m_values
Definition container.h:115
std::mutex m_mutex
Definition container.h:116
void set(const Key &name, const Value &value)
Definition container.h:81
void clear()
Definition container.h:108
friend class RequestQueue
Definition container.h:129
bool empty() const
Definition container.h:133
void push_back(T &&t)
Definition container.h:148
std::deque< MeshUpdateResult > m_queue
Definition container.h:273
Semaphore m_signal
Definition container.h:275
T pop_front(u32 wait_time_max_ms)
Definition container.h:173
T pop_back(u32 wait_time_max_ms=0)
Definition container.h:197
T pop_frontNoEx()
Definition container.h:186
T pop_backNoEx()
Definition container.h:226
std::deque< T > & getQueue()
Definition container.h:271
std::mutex m_mutex
Definition container.h:274
auto iterLocked()
Definition container.h:237
Semaphore & getSignal()
Definition container.h:269
T pop_backNoEx(u32 wait_time_max_ms)
Definition container.h:213
T pop_frontNoEx(u32 wait_time_max_ms)
Definition container.h:160
void push_back(const T &t)
Definition container.h:139
MutexedQueue()=default
std::mutex & getMutex()
Definition container.h:268
Definition semaphore.h:18
void post(unsigned int num=1)
Definition semaphore.cpp:70
void wait()
Definition semaphore.cpp:85
Definition container.h:26
size_t size() const
Definition container.h:56
void pop_front()
Definition container.h:45
bool push_back(const Value &value)
Definition container.h:35
std::queue< Value > m_queue
Definition container.h:68
const Value & front() const
Definition container.h:51
bool empty() const
Definition container.h:61
std::unordered_set< Value > m_set
Definition container.h:67
#define sanity_check(expr)
Definition debug.h:74
std::lock_guard< std::mutex > MutexAutoLock
Definition mutex_auto_lock.h:31
ModifySafeMap< K, V > * m
Definition container.h:564
IterationHelper(ModifySafeMap< K, V > *parent)
Definition container.h:559
~IterationHelper()
Definition container.h:546
auto end()
Definition container.h:556
auto begin()
Definition container.h:555
auto end()
Definition container.h:254
auto erase(typename std::deque< T >::iterator it)
Definition container.h:256
IterationHelper(MutexedQueue< T > *parent)
Definition container.h:261
~IterationHelper()
Definition container.h:246
auto begin()
Definition container.h:253
MutexedQueue< T > * q
Definition container.h:265