src/util/container.h

   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
  32 /*
  33         Queue with unique values with fast checking of value existence
  34 */
  35
  36 template<typename Value>
  37 class UniqueQueue
  38 {
  39 public:
  40
  41         /*
  42                 Does nothing if value is already queued.
  43                 Return value:
  44                         true: value added
  45                         false: value already exists
  46         */
  47         bool push_back(Value value)
  48         {
  49                 // Check if already exists
  50                 if(m_map.find(value) != m_map.end())
  51                         return false;
  52
  53                 // Add
  54                 m_map[value] = 0;
  55                 m_list.push_back(value);
  56
  57                 return true;
  58         }
  59
  60         Value pop_front()
  61         {
  62                 typename std::list<Value>::iterator i = m_list.begin();
  63                 Value value = *i;
  64                 m_map.erase(value);
  65                 m_list.erase(i);
  66                 return value;
  67         }
  68
  69         u32 size()
  70         {
  71                 return m_map.size();
  72         }
  73
  74 private:
  75         std::map<Value, u8> m_map;
  76         std::list<Value> m_list;
  77 };
  78
  79 #if 1
  80 template<typename Key, typename Value>
  81 class MutexedMap
  82 {
  83 public:
  84         MutexedMap()
  85         {
  86         }
  87
  88         void set(const Key &name, const Value &value)
  89         {
  90                 JMutexAutoLock lock(m_mutex);
  91
  92                 m_values[name] = value;
  93         }
  94
  95         bool get(const Key &name, Value *result)
  96         {
  97                 JMutexAutoLock lock(m_mutex);
  98
  99                 typename std::map<Key, Value>::iterator n;
 100                 n = m_values.find(name);
 101
 102                 if(n == m_values.end())
 103                         return false;
 104
 105                 if(result != NULL)
 106                         *result = n->second;
 107
 108                 return true;
 109         }
 110
 111         std::list<Value> getValues()
 112         {
 113                 std::list<Value> result;
 114                 for(typename std::map<Key, Value>::iterator
 115                                 i = m_values.begin();
 116                                 i != m_values.end(); ++i){
 117                         result.push_back(i->second);
 118                 }
 119                 return result;
 120         }
 121
 122         void clear ()
 123         {
 124                 m_values.clear();
 125         }
 126
 127 private:
 128         std::map<Key, Value> m_values;
 129         JMutex m_mutex;
 130 };
 131 #endif
 132
 133 /*
 134         Generates ids for comparable values.
 135         Id=0 is reserved for "no value".
 136
 137         Is fast at:
 138         - Returning value by id (very fast)
 139         - Returning id by value
 140         - Generating a new id for a value
 141
 142         Is not able to:
 143         - Remove an id/value pair (is possible to implement but slow)
 144 */
 145 template<typename T>
 146 class MutexedIdGenerator
 147 {
 148 public:
 149         MutexedIdGenerator()
 150         {
 151         }
 152
 153         // Returns true if found
 154         bool getValue(u32 id, T &value)
 155         {
 156                 if(id == 0)
 157                         return false;
 158                 JMutexAutoLock lock(m_mutex);
 159                 if(m_id_to_value.size() < id)
 160                         return false;
 161                 value = m_id_to_value[id-1];
 162                 return true;
 163         }
 164
 165         // If id exists for value, returns the id.
 166         // Otherwise generates an id for the value.
 167         u32 getId(const T &value)
 168         {
 169                 JMutexAutoLock lock(m_mutex);
 170                 typename std::map<T, u32>::iterator n;
 171                 n = m_value_to_id.find(value);
 172                 if(n != m_value_to_id.end())
 173                         return n->second;
 174                 m_id_to_value.push_back(value);
 175                 u32 new_id = m_id_to_value.size();
 176                 m_value_to_id.insert(value, new_id);
 177                 return new_id;
 178         }
 179
 180 private:
 181         JMutex m_mutex;
 182         // Values are stored here at id-1 position (id 1 = [0])
 183         std::vector<T> m_id_to_value;
 184         std::map<T, u32> m_value_to_id;
 185 };
 186
 187 /*
 188         FIFO queue (well, actually a FILO also)
 189 */
 190 template<typename T>
 191 class Queue
 192 {
 193 public:
 194         Queue():
 195                 m_list_size(0)
 196         {}
 197
 198         void push_back(T t)
 199         {
 200                 m_list.push_back(t);
 201                 ++m_list_size;
 202         }
 203
 204         void push_front(T t)
 205         {
 206                 m_list.push_front(t);
 207                 ++m_list_size;
 208         }
 209
 210         T pop_front()
 211         {
 212                 if(m_list.empty())
 213                         throw ItemNotFoundException("Queue: queue is empty");
 214
 215                 typename std::list<T>::iterator begin = m_list.begin();
 216                 T t = *begin;
 217                 m_list.erase(begin);
 218                 --m_list_size;
 219                 return t;
 220         }
 221         T pop_back()
 222         {
 223                 if(m_list.empty())
 224                         throw ItemNotFoundException("Queue: queue is empty");
 225
 226                 typename std::list<T>::iterator last = m_list.back();
 227                 T t = *last;
 228                 m_list.erase(last);
 229                 --m_list_size;
 230                 return t;
 231         }
 232
 233         u32 size()
 234         {
 235                 return m_list_size;
 236         }
 237
 238         bool empty()
 239         {
 240                 return m_list.empty();
 241         }
 242
 243 protected:
 244         std::list<T> m_list;
 245         u32 m_list_size;
 246 };
 247
 248 /*
 249         Thread-safe FIFO queue (well, actually a FILO also)
 250 */
 251
 252 template<typename T>
 253 class MutexedQueue
 254 {
 255 public:
 256         template<typename Key, typename U, typename Caller, typename CallerData>
 257         friend class RequestQueue;
 258
 259         MutexedQueue()
 260         {
 261         }
 262         bool empty()
 263         {
 264                 JMutexAutoLock lock(m_mutex);
 265                 return (m_size.GetValue() == 0);
 266         }
 267         void push_back(T t)
 268         {
 269                 JMutexAutoLock lock(m_mutex);
 270                 m_list.push_back(t);
 271                 m_size.Post();
 272         }
 273
 274         /* this version of pop_front returns a empty element of T on timeout.
 275          * Make sure default constructor of T creates a recognizable "empty" element
 276          */
 277         T pop_frontNoEx(u32 wait_time_max_ms)
 278         {
 279                 if (m_size.Wait(wait_time_max_ms))
 280                 {
 281                         JMutexAutoLock lock(m_mutex);
 282
 283                         typename std::list<T>::iterator begin = m_list.begin();
 284                         T t = *begin;
 285                         m_list.erase(begin);
 286                         return t;
 287                 }
 288                 else
 289                 {
 290                         return T();
 291                 }
 292         }
 293
 294         T pop_front(u32 wait_time_max_ms)
 295         {
 296                 if (m_size.Wait(wait_time_max_ms))
 297                 {
 298                         JMutexAutoLock lock(m_mutex);
 299
 300                         typename std::list<T>::iterator begin = m_list.begin();
 301                         T t = *begin;
 302                         m_list.erase(begin);
 303                         return t;
 304                 }
 305                 else
 306                 {
 307                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 308                 }
 309         }
 310
 311         T pop_frontNoEx()
 312         {
 313                 m_size.Wait();
 314
 315                 JMutexAutoLock lock(m_mutex);
 316
 317                 typename std::list<T>::iterator begin = m_list.begin();
 318                 T t = *begin;
 319                 m_list.erase(begin);
 320                 return t;
 321         }
 322
 323         T pop_back(u32 wait_time_max_ms=0)
 324         {
 325                 if (m_size.Wait(wait_time_max_ms))
 326                 {
 327                         JMutexAutoLock lock(m_mutex);
 328
 329                         typename std::list<T>::iterator last = m_list.end();
 330                         last--;
 331                         T t = *last;
 332                         m_list.erase(last);
 333                         return t;
 334                 }
 335                 else
 336                 {
 337                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 338                 }
 339         }
 340
 341         /* this version of pop_back returns a empty element of T on timeout.
 342          * Make sure default constructor of T creates a recognizable "empty" element
 343          */
 344         T pop_backNoEx(u32 wait_time_max_ms=0)
 345         {
 346                 if (m_size.Wait(wait_time_max_ms))
 347                 {
 348                         JMutexAutoLock lock(m_mutex);
 349
 350                         typename std::list<T>::iterator last = m_list.end();
 351                         last--;
 352                         T t = *last;
 353                         m_list.erase(last);
 354                         return t;
 355                 }
 356                 else
 357                 {
 358                         return T();
 359                 }
 360         }
 361
 362         T pop_backNoEx()
 363         {
 364                 m_size.Wait();
 365
 366                 JMutexAutoLock lock(m_mutex);
 367
 368                 typename std::list<T>::iterator last = m_list.end();
 369                 last--;
 370                 T t = *last;
 371                 m_list.erase(last);
 372                 return t;
 373         }
 374
 375 protected:
 376         JMutex & getMutex()
 377         {
 378                 return m_mutex;
 379         }
 380
 381         // NEVER EVER modify the >>list<< you got by using this function!
 382         // You may only modify it's content
 383         std::list<T> & getList()
 384         {
 385                 return m_list;
 386         }
 387
 388         JMutex m_mutex;
 389         std::list<T> m_list;
 390         JSemaphore m_size;
 391 };
 392
 393 #endif
 394