3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as published by
7 the Free Software Foundation; either version 2.1 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public License along
16 with this program; if not, write to the Free Software Foundation, Inc.,
17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 #include "irrlichttypes.h"
23 #include "exceptions.h"
24 #include "threading/mutex_auto_lock.h"
25 #include "threading/semaphore.h"
33 Queue with unique values with fast checking of value existence
36 template<typename Value
>
42 Does nothing if value is already queued.
45 false: value already exists
47 bool push_back(const Value
& value
)
49 if (m_set
.insert(value
).second
)
59 m_set
.erase(m_queue
.front());
63 const Value
& front() const
65 return m_queue
.front();
70 return m_queue
.size();
74 std::set
<Value
> m_set
;
75 std::queue
<Value
> m_queue
;
78 template<typename Key
, typename Value
>
82 MutexedMap() = default;
84 void set(const Key
&name
, const Value
&value
)
86 MutexAutoLock
lock(m_mutex
);
87 m_values
[name
] = value
;
90 bool get(const Key
&name
, Value
*result
) const
92 MutexAutoLock
lock(m_mutex
);
93 typename
std::map
<Key
, Value
>::const_iterator n
=
95 if (n
== m_values
.end())
102 std::vector
<Value
> getValues() const
104 MutexAutoLock
lock(m_mutex
);
105 std::vector
<Value
> result
;
106 for (typename
std::map
<Key
, Value
>::const_iterator
107 it
= m_values
.begin();
108 it
!= m_values
.end(); ++it
){
109 result
.push_back(it
->second
);
114 void clear() { m_values
.clear(); }
117 std::map
<Key
, Value
> m_values
;
118 mutable std::mutex m_mutex
;
122 // Thread-safe Double-ended queue
128 template<typename Key
, typename U
, typename Caller
, typename CallerData
>
129 friend class RequestQueue
;
131 MutexedQueue() = default;
135 MutexAutoLock
lock(m_mutex
);
136 return m_queue
.empty();
141 MutexAutoLock
lock(m_mutex
);
142 m_queue
.push_back(t
);
146 /* this version of pop_front returns a empty element of T on timeout.
147 * Make sure default constructor of T creates a recognizable "empty" element
149 T
pop_frontNoEx(u32 wait_time_max_ms
)
151 if (m_signal
.wait(wait_time_max_ms
)) {
152 MutexAutoLock
lock(m_mutex
);
154 T t
= m_queue
.front();
162 T
pop_front(u32 wait_time_max_ms
)
164 if (m_signal
.wait(wait_time_max_ms
)) {
165 MutexAutoLock
lock(m_mutex
);
167 T t
= m_queue
.front();
172 throw ItemNotFoundException("MutexedQueue: queue is empty");
179 MutexAutoLock
lock(m_mutex
);
181 T t
= m_queue
.front();
186 T
pop_back(u32 wait_time_max_ms
=0)
188 if (m_signal
.wait(wait_time_max_ms
)) {
189 MutexAutoLock
lock(m_mutex
);
191 T t
= m_queue
.back();
196 throw ItemNotFoundException("MutexedQueue: queue is empty");
199 /* this version of pop_back returns a empty element of T on timeout.
200 * Make sure default constructor of T creates a recognizable "empty" element
202 T
pop_backNoEx(u32 wait_time_max_ms
)
204 if (m_signal
.wait(wait_time_max_ms
)) {
205 MutexAutoLock
lock(m_mutex
);
207 T t
= m_queue
.back();
219 MutexAutoLock
lock(m_mutex
);
221 T t
= m_queue
.back();
227 std::mutex
&getMutex() { return m_mutex
; }
229 std::deque
<T
> &getQueue() { return m_queue
; }
231 std::deque
<T
> m_queue
;
232 mutable std::mutex m_mutex
;
236 template<typename K
, typename V
>
240 LRUCache(size_t limit
, void (*cache_miss
)(void *data
, const K
&key
, V
*dest
),
244 m_cache_miss
= cache_miss
;
245 m_cache_miss_data
= data
;
248 void setLimit(size_t limit
)
260 const V
*lookupCache(K key
)
262 typename
cache_type::iterator it
= m_map
.find(key
);
264 if (it
!= m_map
.end()) {
267 cache_entry_t
&entry
= it
->second
;
271 // update the usage information
272 m_queue
.erase(entry
.first
);
273 m_queue
.push_front(key
);
274 entry
.first
= m_queue
.begin();
276 // cache miss -- enter into cache
277 cache_entry_t
&entry
=
280 m_cache_miss(m_cache_miss_data
, key
, &entry
.second
);
282 // delete old entries
283 if (m_queue
.size() == m_limit
) {
284 const K
&id
= m_queue
.back();
289 m_queue
.push_front(key
);
290 entry
.first
= m_queue
.begin();
295 void (*m_cache_miss
)(void *data
, const K
&key
, V
*dest
);
296 void *m_cache_miss_data
;
298 typedef typename
std::template pair
<typename
std::template list
<K
>::iterator
, V
> cache_entry_t
;
299 typedef std::template map
<K
, cache_entry_t
> cache_type
;
301 // we can't use std::deque here, because its iterators get invalidated
302 std::list
<K
> m_queue
;