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 "../jthread/jmutex.h"
26 #include "../jthread/jmutexautolock.h"
27 #include "../jthread/jsemaphore.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;
81 template<typename Key, typename Value>
89 void set(const Key &name, const Value &value)
91 JMutexAutoLock lock(m_mutex);
93 m_values[name] = value;
96 bool get(const Key &name, Value *result)
98 JMutexAutoLock lock(m_mutex);
100 typename std::map<Key, Value>::iterator n;
101 n = m_values.find(name);
103 if(n == m_values.end())
112 std::list<Value> getValues()
114 std::list<Value> result;
115 for(typename std::map<Key, Value>::iterator
116 i = m_values.begin();
117 i != m_values.end(); ++i){
118 result.push_back(i->second);
129 std::map<Key, Value> m_values;
135 Generates ids for comparable values.
136 Id=0 is reserved for "no value".
139 - Returning value by id (very fast)
140 - Returning id by value
141 - Generating a new id for a value
144 - Remove an id/value pair (is possible to implement but slow)
147 class MutexedIdGenerator
154 // Returns true if found
155 bool getValue(u32 id, T &value)
159 JMutexAutoLock lock(m_mutex);
160 if(m_id_to_value.size() < id)
162 value = m_id_to_value[id-1];
166 // If id exists for value, returns the id.
167 // Otherwise generates an id for the value.
168 u32 getId(const T &value)
170 JMutexAutoLock lock(m_mutex);
171 typename std::map<T, u32>::iterator n;
172 n = m_value_to_id.find(value);
173 if(n != m_value_to_id.end())
175 m_id_to_value.push_back(value);
176 u32 new_id = m_id_to_value.size();
177 m_value_to_id.insert(value, new_id);
183 // Values are stored here at id-1 position (id 1 = [0])
184 std::vector<T> m_id_to_value;
185 std::map<T, u32> m_value_to_id;
189 FIFO queue (well, actually a FILO also)
207 m_list.push_front(t);
214 throw ItemNotFoundException("Queue: queue is empty");
216 typename std::list<T>::iterator begin = m_list.begin();
225 throw ItemNotFoundException("Queue: queue is empty");
227 typename std::list<T>::iterator last = m_list.back();
241 return m_list.empty();
250 Thread-safe FIFO queue (well, actually a FILO also)
257 template<typename Key, typename U, typename Caller, typename CallerData>
258 friend class RequestQueue;
265 JMutexAutoLock lock(m_mutex);
266 return (m_size.GetValue() == 0);
270 JMutexAutoLock lock(m_mutex);
275 /* this version of pop_front returns a empty element of T on timeout.
276 * Make sure default constructor of T creates a recognizable "empty" element
278 T pop_frontNoEx(u32 wait_time_max_ms)
280 if (m_size.Wait(wait_time_max_ms))
282 JMutexAutoLock lock(m_mutex);
284 typename std::list<T>::iterator begin = m_list.begin();
295 T pop_front(u32 wait_time_max_ms)
297 if (m_size.Wait(wait_time_max_ms))
299 JMutexAutoLock lock(m_mutex);
301 typename std::list<T>::iterator begin = m_list.begin();
308 throw ItemNotFoundException("MutexedQueue: queue is empty");
316 JMutexAutoLock lock(m_mutex);
318 typename std::list<T>::iterator begin = m_list.begin();
324 T pop_back(u32 wait_time_max_ms=0)
326 if (m_size.Wait(wait_time_max_ms))
328 JMutexAutoLock lock(m_mutex);
330 typename std::list<T>::iterator last = m_list.end();
338 throw ItemNotFoundException("MutexedQueue: queue is empty");
342 /* this version of pop_back returns a empty element of T on timeout.
343 * Make sure default constructor of T creates a recognizable "empty" element
345 T pop_backNoEx(u32 wait_time_max_ms=0)
347 if (m_size.Wait(wait_time_max_ms))
349 JMutexAutoLock lock(m_mutex);
351 typename std::list<T>::iterator last = m_list.end();
367 JMutexAutoLock lock(m_mutex);
369 typename std::list<T>::iterator last = m_list.end();
382 // NEVER EVER modify the >>list<< you got by using this function!
383 // You may only modify it's content
384 std::list<T> & getList()