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.
20 #ifndef UTIL_CONTAINER_HEADER
21 #define UTIL_CONTAINER_HEADER
23 #include "../irrlichttypes.h"
24 #include "../exceptions.h"
25 #include "../threading/mutex_auto_lock.h"
26 #include "../threading/semaphore.h"
34 Queue with unique values with fast checking of value existence
37 template<typename Value>
43 Does nothing if value is already queued.
46 false: value already exists
48 bool push_back(const Value& value)
50 if (m_set.insert(value).second)
60 m_set.erase(m_queue.front());
64 const Value& front() const
66 return m_queue.front();
71 return m_queue.size();
75 std::set<Value> m_set;
76 std::queue<Value> m_queue;
79 template<typename Key, typename Value>
85 void set(const Key &name, const Value &value)
87 MutexAutoLock lock(m_mutex);
88 m_values[name] = value;
91 bool get(const Key &name, Value *result) const
93 MutexAutoLock lock(m_mutex);
94 typename std::map<Key, Value>::const_iterator n =
96 if (n == m_values.end())
103 std::vector<Value> getValues() const
105 MutexAutoLock lock(m_mutex);
106 std::vector<Value> result;
107 for (typename std::map<Key, Value>::const_iterator
108 it = m_values.begin();
109 it != m_values.end(); ++it){
110 result.push_back(it->second);
115 void clear() { m_values.clear(); }
118 std::map<Key, Value> m_values;
119 mutable std::mutex m_mutex;
123 // Thread-safe Double-ended queue
129 template<typename Key, typename U, typename Caller, typename CallerData>
130 friend class RequestQueue;
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();
171 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();
195 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;