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.h"
26 #include "../threading/mutex_auto_lock.h"
27 #include "../threading/semaphore.h"
35 Queue with unique values with fast checking of value existence
38 template<typename Value>
44 Does nothing if value is already queued.
47 false: value already exists
49 bool push_back(const Value& value)
51 if (m_set.insert(value).second)
61 m_set.erase(m_queue.front());
65 const Value& front() const
67 return m_queue.front();
72 return m_queue.size();
76 std::set<Value> m_set;
77 std::queue<Value> m_queue;
80 template<typename Key, typename Value>
86 void set(const Key &name, const Value &value)
88 MutexAutoLock lock(m_mutex);
89 m_values[name] = value;
92 bool get(const Key &name, Value *result) const
94 MutexAutoLock lock(m_mutex);
95 typename std::map<Key, Value>::const_iterator n =
97 if (n == m_values.end())
104 std::vector<Value> getValues() const
106 MutexAutoLock lock(m_mutex);
107 std::vector<Value> result;
108 for (typename std::map<Key, Value>::const_iterator
109 it = m_values.begin();
110 it != m_values.end(); ++it){
111 result.push_back(it->second);
116 void clear() { m_values.clear(); }
119 std::map<Key, Value> m_values;
120 mutable Mutex m_mutex;
124 // Thread-safe Double-ended queue
130 template<typename Key, typename U, typename Caller, typename CallerData>
131 friend class RequestQueue;
136 MutexAutoLock lock(m_mutex);
137 return m_queue.empty();
142 MutexAutoLock lock(m_mutex);
143 m_queue.push_back(t);
147 /* this version of pop_front returns a empty element of T on timeout.
148 * Make sure default constructor of T creates a recognizable "empty" element
150 T pop_frontNoEx(u32 wait_time_max_ms)
152 if (m_signal.wait(wait_time_max_ms)) {
153 MutexAutoLock lock(m_mutex);
155 T t = m_queue.front();
163 T pop_front(u32 wait_time_max_ms)
165 if (m_signal.wait(wait_time_max_ms)) {
166 MutexAutoLock lock(m_mutex);
168 T t = m_queue.front();
172 throw ItemNotFoundException("MutexedQueue: queue is empty");
180 MutexAutoLock lock(m_mutex);
182 T t = m_queue.front();
187 T pop_back(u32 wait_time_max_ms=0)
189 if (m_signal.wait(wait_time_max_ms)) {
190 MutexAutoLock lock(m_mutex);
192 T t = m_queue.back();
196 throw ItemNotFoundException("MutexedQueue: queue is empty");
200 /* this version of pop_back returns a empty element of T on timeout.
201 * Make sure default constructor of T creates a recognizable "empty" element
203 T pop_backNoEx(u32 wait_time_max_ms)
205 if (m_signal.wait(wait_time_max_ms)) {
206 MutexAutoLock lock(m_mutex);
208 T t = m_queue.back();
220 MutexAutoLock lock(m_mutex);
222 T t = m_queue.back();
228 Mutex &getMutex() { return m_mutex; }
230 std::deque<T> &getQueue() { return m_queue; }
232 std::deque<T> m_queue;
233 mutable Mutex m_mutex;
237 template<typename K, typename V>
241 LRUCache(size_t limit, void (*cache_miss)(void *data, const K &key, V *dest),
245 m_cache_miss = cache_miss;
246 m_cache_miss_data = data;
249 void setLimit(size_t limit)
261 const V *lookupCache(K key)
263 typename cache_type::iterator it = m_map.find(key);
265 if (it != m_map.end()) {
268 cache_entry_t &entry = it->second;
272 // update the usage information
273 m_queue.erase(entry.first);
274 m_queue.push_front(key);
275 entry.first = m_queue.begin();
277 // cache miss -- enter into cache
278 cache_entry_t &entry =
281 m_cache_miss(m_cache_miss_data, key, &entry.second);
283 // delete old entries
284 if (m_queue.size() == m_limit) {
285 const K &id = m_queue.back();
290 m_queue.push_front(key);
291 entry.first = m_queue.begin();
296 void (*m_cache_miss)(void *data, const K &key, V *dest);
297 void *m_cache_miss_data;
299 typedef typename std::template pair<typename std::template list<K>::iterator, V> cache_entry_t;
300 typedef std::template map<K, cache_entry_t> cache_type;
302 // we can't use std::deque here, because its iterators get invalidated
303 std::list<K> m_queue;