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 "../porting.h" // For sleep_ms
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(Value value)
49 // Check if already exists
50 if(m_map.find(value) != m_map.end())
55 m_list.push_back(value);
62 typename std::list<Value>::iterator i = m_list.begin();
75 std::map<Value, u8> m_map;
76 std::list<Value> m_list;
80 template<typename Key, typename Value>
87 assert(m_mutex.IsInitialized());
90 void set(const Key &name, const Value &value)
92 JMutexAutoLock lock(m_mutex);
94 m_values[name] = value;
97 bool get(const Key &name, Value *result)
99 JMutexAutoLock lock(m_mutex);
101 typename std::map<Key, Value>::iterator n;
102 n = m_values.find(name);
104 if(n == m_values.end())
113 std::list<Value> getValues()
115 std::list<Value> result;
116 for(typename std::map<Key, Value>::iterator
117 i = m_values.begin();
118 i != m_values.end(); ++i){
119 result.push_back(i->second);
130 std::map<Key, Value> m_values;
136 Generates ids for comparable values.
137 Id=0 is reserved for "no value".
140 - Returning value by id (very fast)
141 - Returning id by value
142 - Generating a new id for a value
145 - Remove an id/value pair (is possible to implement but slow)
148 class MutexedIdGenerator
154 assert(m_mutex.IsInitialized());
157 // Returns true if found
158 bool getValue(u32 id, T &value)
162 JMutexAutoLock lock(m_mutex);
163 if(m_id_to_value.size() < id)
165 value = m_id_to_value[id-1];
169 // If id exists for value, returns the id.
170 // Otherwise generates an id for the value.
171 u32 getId(const T &value)
173 JMutexAutoLock lock(m_mutex);
174 typename std::map<T, u32>::iterator n;
175 n = m_value_to_id.find(value);
176 if(n != m_value_to_id.end())
178 m_id_to_value.push_back(value);
179 u32 new_id = m_id_to_value.size();
180 m_value_to_id.insert(value, new_id);
186 // Values are stored here at id-1 position (id 1 = [0])
187 std::vector<T> m_id_to_value;
188 std::map<T, u32> m_value_to_id;
192 FIFO queue (well, actually a FILO also)
211 throw ItemNotFoundException("Queue: queue is empty");
213 typename std::list<T>::iterator begin = m_list.begin();
222 throw ItemNotFoundException("Queue: queue is empty");
224 typename std::list<T>::iterator last = m_list.back();
238 return m_list.empty();
247 Thread-safe FIFO queue (well, actually a FILO also)
260 JMutexAutoLock lock(m_mutex);
261 return m_list.empty();
265 JMutexAutoLock lock(m_mutex);
268 T pop_front(u32 wait_time_max_ms=0)
270 u32 wait_time_ms = 0;
275 JMutexAutoLock lock(m_mutex);
279 typename std::list<T>::iterator begin = m_list.begin();
285 if(wait_time_ms >= wait_time_max_ms)
286 throw ItemNotFoundException("MutexedQueue: queue is empty");
289 // Wait a while before trying again
294 T pop_back(u32 wait_time_max_ms=0)
296 u32 wait_time_ms = 0;
301 JMutexAutoLock lock(m_mutex);
305 typename std::list<T>::iterator last = m_list.back();
311 if(wait_time_ms >= wait_time_max_ms)
312 throw ItemNotFoundException("MutexedQueue: queue is empty");
315 // Wait a while before trying again
326 std::list<T> & getList()