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 <jmutex.h>
  26 #include <jmutexautolock.h>
  27 #include "../porting.h" // For sleep_ms
  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                 m_mutex.Init();
  87                 assert(m_mutex.IsInitialized());
  88         }
  89
  90         void set(const Key &name, const Value &value)
  91         {
  92                 JMutexAutoLock lock(m_mutex);
  93
  94                 m_values[name] = value;
  95         }
  96
  97         bool get(const Key &name, Value *result)
  98         {
  99                 JMutexAutoLock lock(m_mutex);
 100
 101                 typename std::map<Key, Value>::iterator n;
 102                 n = m_values.find(name);
 103
 104                 if(n == m_values.end())
 105                         return false;
 106
 107                 if(result != NULL)
 108                         *result = n->second;
 109
 110                 return true;
 111         }
 112
 113         std::list<Value> getValues()
 114         {
 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);
 120                 }
 121                 return result;
 122         }
 123
 124         void clear ()
 125         {
 126                 m_values.clear();
 127         }
 128
 129 private:
 130         std::map<Key, Value> m_values;
 131         JMutex m_mutex;
 132 };
 133 #endif
 134
 135 /*
 136         Generates ids for comparable values.
 137         Id=0 is reserved for "no value".
 138
 139         Is fast at:
 140         - Returning value by id (very fast)
 141         - Returning id by value
 142         - Generating a new id for a value
 143
 144         Is not able to:
 145         - Remove an id/value pair (is possible to implement but slow)
 146 */
 147 template<typename T>
 148 class MutexedIdGenerator
 149 {
 150 public:
 151         MutexedIdGenerator()
 152         {
 153                 m_mutex.Init();
 154                 assert(m_mutex.IsInitialized());
 155         }
 156
 157         // Returns true if found
 158         bool getValue(u32 id, T &value)
 159         {
 160                 if(id == 0)
 161                         return false;
 162                 JMutexAutoLock lock(m_mutex);
 163                 if(m_id_to_value.size() < id)
 164                         return false;
 165                 value = m_id_to_value[id-1];
 166                 return true;
 167         }
 168
 169         // If id exists for value, returns the id.
 170         // Otherwise generates an id for the value.
 171         u32 getId(const T &value)
 172         {
 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())
 177                         return n->second;
 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);
 181                 return new_id;
 182         }
 183
 184 private:
 185         JMutex m_mutex;
 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;
 189 };
 190
 191 /*
 192         FIFO queue (well, actually a FILO also)
 193 */
 194 template<typename T>
 195 class Queue
 196 {
 197 public:
 198         Queue():
 199                 m_list_size(0)
 200         {}
 201
 202         void push_back(T t)
 203         {
 204                 m_list.push_back(t);
 205                 ++m_list_size;
 206         }
 207
 208         T pop_front()
 209         {
 210                 if(m_list.empty())
 211                         throw ItemNotFoundException("Queue: queue is empty");
 212
 213                 typename std::list<T>::iterator begin = m_list.begin();
 214                 T t = *begin;
 215                 m_list.erase(begin);
 216                 --m_list_size;
 217                 return t;
 218         }
 219         T pop_back()
 220         {
 221                 if(m_list.empty())
 222                         throw ItemNotFoundException("Queue: queue is empty");
 223
 224                 typename std::list<T>::iterator last = m_list.back();
 225                 T t = *last;
 226                 m_list.erase(last);
 227                 --m_list_size;
 228                 return t;
 229         }
 230
 231         u32 size()
 232         {
 233                 return m_list_size;
 234         }
 235
 236         bool empty()
 237         {
 238                 return m_list.empty();
 239         }
 240
 241 protected:
 242         std::list<T> m_list;
 243         u32 m_list_size;
 244 };
 245
 246 /*
 247         Thread-safe FIFO queue (well, actually a FILO also)
 248 */
 249
 250 template<typename T>
 251 class MutexedQueue
 252 {
 253 public:
 254         MutexedQueue()
 255         {
 256                 m_mutex.Init();
 257         }
 258         bool empty()
 259         {
 260                 JMutexAutoLock lock(m_mutex);
 261                 return m_list.empty();
 262         }
 263         void push_back(T t)
 264         {
 265                 JMutexAutoLock lock(m_mutex);
 266                 m_list.push_back(t);
 267         }
 268         T pop_front(u32 wait_time_max_ms=0)
 269         {
 270                 u32 wait_time_ms = 0;
 271
 272                 for(;;)
 273                 {
 274                         {
 275                                 JMutexAutoLock lock(m_mutex);
 276
 277                                 if(!m_list.empty())
 278                                 {
 279                                         typename std::list<T>::iterator begin = m_list.begin();
 280                                         T t = *begin;
 281                                         m_list.erase(begin);
 282                                         return t;
 283                                 }
 284
 285                                 if(wait_time_ms >= wait_time_max_ms)
 286                                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 287                         }
 288
 289                         // Wait a while before trying again
 290                         sleep_ms(10);
 291                         wait_time_ms += 10;
 292                 }
 293         }
 294         T pop_back(u32 wait_time_max_ms=0)
 295         {
 296                 u32 wait_time_ms = 0;
 297
 298                 for(;;)
 299                 {
 300                         {
 301                                 JMutexAutoLock lock(m_mutex);
 302
 303                                 if(!m_list.empty())
 304                                 {
 305                                         typename std::list<T>::iterator last = m_list.back();
 306                                         T t = *last;
 307                                         m_list.erase(last);
 308                                         return t;
 309                                 }
 310
 311                                 if(wait_time_ms >= wait_time_max_ms)
 312                                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 313                         }
 314
 315                         // Wait a while before trying again
 316                         sleep_ms(10);
 317                         wait_time_ms += 10;
 318                 }
 319         }
 320
 321         JMutex & getMutex()
 322         {
 323                 return m_mutex;
 324         }
 325
 326         std::list<T> & getList()
 327         {
 328                 return m_list;
 329         }
 330
 331 protected:
 332         JMutex m_mutex;
 333         std::list<T> m_list;
 334 };
 335
 336 #endif
 337