Line data Source code
1 : /*
2 : Minetest
3 : Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
4 :
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.
9 :
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.
14 :
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.
18 : */
19 :
20 : #ifndef UTIL_CONTAINER_HEADER
21 : #define UTIL_CONTAINER_HEADER
22 :
23 : #include "../irrlichttypes.h"
24 : #include "../exceptions.h"
25 : #include "../jthread/jmutex.h"
26 : #include "../jthread/jmutexautolock.h"
27 : #include "../jthread/jsemaphore.h"
28 : #include <list>
29 : #include <vector>
30 : #include <map>
31 : #include <set>
32 : #include <queue>
33 :
34 : /*
35 : Queue with unique values with fast checking of value existence
36 : */
37 :
38 : template<typename Value>
39 2 : class UniqueQueue
40 : {
41 : public:
42 :
43 : /*
44 : Does nothing if value is already queued.
45 : Return value:
46 : true: value added
47 : false: value already exists
48 : */
49 173 : bool push_back(const Value& value)
50 : {
51 173 : if (m_set.insert(value).second)
52 : {
53 22 : m_queue.push(value);
54 22 : return true;
55 : }
56 151 : return false;
57 : }
58 :
59 0 : void pop_front()
60 : {
61 0 : m_set.erase(m_queue.front());
62 0 : m_queue.pop();
63 0 : }
64 :
65 0 : const Value& front() const
66 : {
67 0 : return m_queue.front();
68 : }
69 :
70 0 : u32 size() const
71 : {
72 0 : return m_queue.size();
73 : }
74 :
75 : private:
76 : std::set<Value> m_set;
77 : std::queue<Value> m_queue;
78 : };
79 :
80 : template<typename Key, typename Value>
81 4 : class MutexedMap
82 : {
83 : public:
84 4 : MutexedMap()
85 4 : {
86 4 : }
87 :
88 6927 : void set(const Key &name, const Value &value)
89 : {
90 13854 : JMutexAutoLock lock(m_mutex);
91 :
92 6927 : m_values[name] = value;
93 6927 : }
94 :
95 136349 : bool get(const Key &name, Value *result)
96 : {
97 272698 : JMutexAutoLock lock(m_mutex);
98 :
99 136349 : typename std::map<Key, Value>::iterator n;
100 136349 : n = m_values.find(name);
101 :
102 136349 : if(n == m_values.end())
103 4651 : return false;
104 :
105 131698 : if(result != NULL)
106 131698 : *result = n->second;
107 :
108 131698 : return true;
109 : }
110 :
111 1 : std::vector<Value> getValues()
112 : {
113 1 : std::vector<Value> result;
114 23 : for(typename std::map<Key, Value>::iterator
115 1 : i = m_values.begin();
116 16 : i != m_values.end(); ++i){
117 7 : result.push_back(i->second);
118 : }
119 1 : return result;
120 : }
121 :
122 1 : void clear ()
123 : {
124 1 : m_values.clear();
125 1 : }
126 :
127 : private:
128 : std::map<Key, Value> m_values;
129 : JMutex m_mutex;
130 : };
131 :
132 : /*
133 : Generates ids for comparable values.
134 : Id=0 is reserved for "no value".
135 :
136 : Is fast at:
137 : - Returning value by id (very fast)
138 : - Returning id by value
139 : - Generating a new id for a value
140 :
141 : Is not able to:
142 : - Remove an id/value pair (is possible to implement but slow)
143 : */
144 : template<typename T>
145 : class MutexedIdGenerator
146 : {
147 : public:
148 : MutexedIdGenerator()
149 : {
150 : }
151 :
152 : // Returns true if found
153 : bool getValue(u32 id, T &value)
154 : {
155 : if(id == 0)
156 : return false;
157 : JMutexAutoLock lock(m_mutex);
158 : if(m_id_to_value.size() < id)
159 : return false;
160 : value = m_id_to_value[id-1];
161 : return true;
162 : }
163 :
164 : // If id exists for value, returns the id.
165 : // Otherwise generates an id for the value.
166 : u32 getId(const T &value)
167 : {
168 : JMutexAutoLock lock(m_mutex);
169 : typename std::map<T, u32>::iterator n;
170 : n = m_value_to_id.find(value);
171 : if(n != m_value_to_id.end())
172 : return n->second;
173 : m_id_to_value.push_back(value);
174 : u32 new_id = m_id_to_value.size();
175 : m_value_to_id.insert(value, new_id);
176 : return new_id;
177 : }
178 :
179 : private:
180 : JMutex m_mutex;
181 : // Values are stored here at id-1 position (id 1 = [0])
182 : std::vector<T> m_id_to_value;
183 : std::map<T, u32> m_value_to_id;
184 : };
185 :
186 : /*
187 : Thread-safe FIFO queue (well, actually a FILO also)
188 : */
189 :
190 : template<typename T>
191 8 : class MutexedQueue
192 : {
193 : public:
194 : template<typename Key, typename U, typename Caller, typename CallerData>
195 : friend class RequestQueue;
196 :
197 8 : MutexedQueue()
198 8 : {
199 8 : }
200 5660 : bool empty()
201 : {
202 11320 : JMutexAutoLock lock(m_mutex);
203 11320 : return (m_queue.size() == 0);
204 : }
205 8074 : void push_back(T t)
206 : {
207 16148 : JMutexAutoLock lock(m_mutex);
208 8074 : m_queue.push_back(t);
209 8074 : m_size.Post();
210 8074 : }
211 :
212 : /* this version of pop_front returns a empty element of T on timeout.
213 : * Make sure default constructor of T creates a recognizable "empty" element
214 : */
215 7989 : T pop_frontNoEx(u32 wait_time_max_ms)
216 : {
217 7989 : if (m_size.Wait(wait_time_max_ms)) {
218 9208 : JMutexAutoLock lock(m_mutex);
219 :
220 9208 : T t = m_queue.front();
221 4604 : m_queue.pop_front();
222 4604 : return t;
223 : }
224 : else {
225 3385 : return T();
226 : }
227 : }
228 :
229 2514 : T pop_front(u32 wait_time_max_ms)
230 : {
231 2514 : if (m_size.Wait(wait_time_max_ms)) {
232 2648 : JMutexAutoLock lock(m_mutex);
233 :
234 2648 : T t = m_queue.front();
235 1324 : m_queue.pop_front();
236 2648 : return t;
237 : }
238 : else {
239 1190 : throw ItemNotFoundException("MutexedQueue: queue is empty");
240 : }
241 : }
242 :
243 2141 : T pop_frontNoEx()
244 : {
245 2141 : m_size.Wait();
246 :
247 4282 : JMutexAutoLock lock(m_mutex);
248 :
249 2141 : T t = m_queue.front();
250 2141 : m_queue.pop_front();
251 4282 : return t;
252 : }
253 :
254 : T pop_back(u32 wait_time_max_ms=0)
255 : {
256 : if (m_size.Wait(wait_time_max_ms)) {
257 : JMutexAutoLock lock(m_mutex);
258 :
259 : T t = m_queue.back();
260 : m_queue.pop_back();
261 : return t;
262 : }
263 : else {
264 : throw ItemNotFoundException("MutexedQueue: queue is empty");
265 : }
266 : }
267 :
268 : /* this version of pop_back returns a empty element of T on timeout.
269 : * Make sure default constructor of T creates a recognizable "empty" element
270 : */
271 : T pop_backNoEx(u32 wait_time_max_ms=0)
272 : {
273 : if (m_size.Wait(wait_time_max_ms)) {
274 : JMutexAutoLock lock(m_mutex);
275 :
276 : T t = m_queue.back();
277 : m_queue.pop_back();
278 : return t;
279 : }
280 : else {
281 : return T();
282 : }
283 : }
284 :
285 : T pop_backNoEx()
286 : {
287 : m_size.Wait();
288 :
289 : JMutexAutoLock lock(m_mutex);
290 :
291 : T t = m_queue.back();
292 : m_queue.pop_back();
293 : return t;
294 : }
295 :
296 : protected:
297 2 : JMutex & getMutex()
298 : {
299 2 : return m_mutex;
300 : }
301 :
302 4 : std::deque<T> & getQueue()
303 : {
304 4 : return m_queue;
305 : }
306 :
307 : std::deque<T> m_queue;
308 : JMutex m_mutex;
309 : JSemaphore m_size;
310 : };
311 :
312 : #endif
313 :
|
