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