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"
25 #include <jmutexautolock.h>
26 #include "../porting.h" // For sleep_ms
29 Queue with unique values with fast checking of value existence
32 template<typename Value>
38 Does nothing if value is already queued.
41 false: value already exists
43 bool push_back(Value value)
45 // Check if already exists
46 if(m_map.find(value) != NULL)
50 m_map.insert(value, 0);
51 m_list.push_back(value);
58 typename core::list<Value>::Iterator i = m_list.begin();
67 assert(m_list.size() == m_map.size());
72 core::map<Value, u8> m_map;
73 core::list<Value> m_list;
77 template<typename Key, typename Value>
84 assert(m_mutex.IsInitialized());
87 void set(const Key &name, const Value &value)
89 JMutexAutoLock lock(m_mutex);
91 m_values[name] = value;
94 bool get(const Key &name, Value *result)
96 JMutexAutoLock lock(m_mutex);
98 typename core::map<Key, Value>::Node *n;
99 n = m_values.find(name);
105 *result = n->getValue();
110 core::list<Value> getValues()
112 core::list<Value> result;
113 for(typename core::map<Key, Value>::Iterator
114 i = m_values.getIterator();
115 i.atEnd() == false; i++){
116 result.push_back(i.getNode()->getValue());
122 core::map<Key, Value> m_values;
128 Generates ids for comparable values.
129 Id=0 is reserved for "no value".
132 - Returning value by id (very fast)
133 - Returning id by value
134 - Generating a new id for a value
137 - Remove an id/value pair (is possible to implement but slow)
140 class MutexedIdGenerator
146 assert(m_mutex.IsInitialized());
149 // Returns true if found
150 bool getValue(u32 id, T &value)
154 JMutexAutoLock lock(m_mutex);
155 if(m_id_to_value.size() < id)
157 value = m_id_to_value[id-1];
161 // If id exists for value, returns the id.
162 // Otherwise generates an id for the value.
163 u32 getId(const T &value)
165 JMutexAutoLock lock(m_mutex);
166 typename core::map<T, u32>::Node *n;
167 n = m_value_to_id.find(value);
169 return n->getValue();
170 m_id_to_value.push_back(value);
171 u32 new_id = m_id_to_value.size();
172 m_value_to_id.insert(value, new_id);
178 // Values are stored here at id-1 position (id 1 = [0])
179 core::array<T> m_id_to_value;
180 core::map<T, u32> m_value_to_id;
184 FIFO queue (well, actually a FILO also)
197 if(m_list.size() == 0)
198 throw ItemNotFoundException("Queue: queue is empty");
200 typename core::list<T>::Iterator begin = m_list.begin();
207 if(m_list.size() == 0)
208 throw ItemNotFoundException("Queue: queue is empty");
210 typename core::list<T>::Iterator last = m_list.getLast();
218 return m_list.size();
222 core::list<T> m_list;
226 Thread-safe FIFO queue (well, actually a FILO also)
239 JMutexAutoLock lock(m_mutex);
240 return m_list.size();
244 JMutexAutoLock lock(m_mutex);
247 T pop_front(u32 wait_time_max_ms=0)
249 u32 wait_time_ms = 0;
254 JMutexAutoLock lock(m_mutex);
256 if(m_list.size() > 0)
258 typename core::list<T>::Iterator begin = m_list.begin();
264 if(wait_time_ms >= wait_time_max_ms)
265 throw ItemNotFoundException("MutexedQueue: queue is empty");
268 // Wait a while before trying again
273 T pop_back(u32 wait_time_max_ms=0)
275 u32 wait_time_ms = 0;
280 JMutexAutoLock lock(m_mutex);
282 if(m_list.size() > 0)
284 typename core::list<T>::Iterator last = m_list.getLast();
290 if(wait_time_ms >= wait_time_max_ms)
291 throw ItemNotFoundException("MutexedQueue: queue is empty");
294 // Wait a while before trying again
305 core::list<T> & getList()
312 core::list<T> m_list;