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 <jmutex.h>
  25 #include <jmutexautolock.h>
  26 #include "../porting.h" // For sleep_ms
  27 #include <list>
  28 #include <vector>
  29
  30 /*
  31         Queue with unique values with fast checking of value existence
  32 */
  33
  34 template<typename Value>
  35 class UniqueQueue
  36 {
  37 public:
  38
  39         /*
  40                 Does nothing if value is already queued.
  41                 Return value:
  42                         true: value added
  43                         false: value already exists
  44         */
  45         bool push_back(Value value)
  46         {
  47                 // Check if already exists
  48                 if(m_map.find(value) != m_map.end())
  49                         return false;
  50
  51                 // Add
  52                 m_map[value] = 0;
  53                 m_list.push_back(value);
  54
  55                 return true;
  56         }
  57
  58         Value pop_front()
  59         {
  60                 typename std::list<Value>::iterator i = m_list.begin();
  61                 Value value = *i;
  62                 m_map.erase(value);
  63                 m_list.erase(i);
  64                 return value;
  65         }
  66
  67         u32 size()
  68         {
  69                 return m_map.size();
  70         }
  71
  72 private:
  73         std::map<Value, u8> m_map;
  74         std::list<Value> m_list;
  75 };
  76
  77 #if 1
  78 template<typename Key, typename Value>
  79 class MutexedMap
  80 {
  81 public:
  82         MutexedMap()
  83         {
  84                 m_mutex.Init();
  85                 assert(m_mutex.IsInitialized());
  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 private:
 123         std::map<Key, Value> m_values;
 124         JMutex m_mutex;
 125 };
 126 #endif
 127
 128 /*
 129         Generates ids for comparable values.
 130         Id=0 is reserved for "no value".
 131
 132         Is fast at:
 133         - Returning value by id (very fast)
 134         - Returning id by value
 135         - Generating a new id for a value
 136
 137         Is not able to:
 138         - Remove an id/value pair (is possible to implement but slow)
 139 */
 140 template<typename T>
 141 class MutexedIdGenerator
 142 {
 143 public:
 144         MutexedIdGenerator()
 145         {
 146                 m_mutex.Init();
 147                 assert(m_mutex.IsInitialized());
 148         }
 149
 150         // Returns true if found
 151         bool getValue(u32 id, T &value)
 152         {
 153                 if(id == 0)
 154                         return false;
 155                 JMutexAutoLock lock(m_mutex);
 156                 if(m_id_to_value.size() < id)
 157                         return false;
 158                 value = m_id_to_value[id-1];
 159                 return true;
 160         }
 161
 162         // If id exists for value, returns the id.
 163         // Otherwise generates an id for the value.
 164         u32 getId(const T &value)
 165         {
 166                 JMutexAutoLock lock(m_mutex);
 167                 typename std::map<T, u32>::iterator n;
 168                 n = m_value_to_id.find(value);
 169                 if(n != m_value_to_id.end())
 170                         return n->second;
 171                 m_id_to_value.push_back(value);
 172                 u32 new_id = m_id_to_value.size();
 173                 m_value_to_id.insert(value, new_id);
 174                 return new_id;
 175         }
 176
 177 private:
 178         JMutex m_mutex;
 179         // Values are stored here at id-1 position (id 1 = [0])
 180         std::vector<T> m_id_to_value;
 181         std::map<T, u32> m_value_to_id;
 182 };
 183
 184 /*
 185         FIFO queue (well, actually a FILO also)
 186 */
 187 template<typename T>
 188 class Queue
 189 {
 190 public:
 191         Queue():
 192                 m_list_size(0)
 193         {}
 194
 195         void push_back(T t)
 196         {
 197                 m_list.push_back(t);
 198                 ++m_list_size;
 199         }
 200
 201         T pop_front()
 202         {
 203                 if(m_list.empty())
 204                         throw ItemNotFoundException("Queue: queue is empty");
 205
 206                 typename std::list<T>::iterator begin = m_list.begin();
 207                 T t = *begin;
 208                 m_list.erase(begin);
 209                 --m_list_size;
 210                 return t;
 211         }
 212         T pop_back()
 213         {
 214                 if(m_list.empty())
 215                         throw ItemNotFoundException("Queue: queue is empty");
 216
 217                 typename std::list<T>::iterator last = m_list.back();
 218                 T t = *last;
 219                 m_list.erase(last);
 220                 --m_list_size;
 221                 return t;
 222         }
 223
 224         u32 size()
 225         {
 226                 return m_list_size;
 227         }
 228
 229         bool empty()
 230         {
 231                 return m_list.empty();
 232         }
 233
 234 protected:
 235         std::list<T> m_list;
 236         u32 m_list_size;
 237 };
 238
 239 /*
 240         Thread-safe FIFO queue (well, actually a FILO also)
 241 */
 242
 243 template<typename T>
 244 class MutexedQueue
 245 {
 246 public:
 247         MutexedQueue()
 248         {
 249                 m_mutex.Init();
 250         }
 251         bool empty()
 252         {
 253                 JMutexAutoLock lock(m_mutex);
 254                 return m_list.empty();
 255         }
 256         void push_back(T t)
 257         {
 258                 JMutexAutoLock lock(m_mutex);
 259                 m_list.push_back(t);
 260         }
 261         T pop_front(u32 wait_time_max_ms=0)
 262         {
 263                 u32 wait_time_ms = 0;
 264
 265                 for(;;)
 266                 {
 267                         {
 268                                 JMutexAutoLock lock(m_mutex);
 269
 270                                 if(!m_list.empty())
 271                                 {
 272                                         typename std::list<T>::iterator begin = m_list.begin();
 273                                         T t = *begin;
 274                                         m_list.erase(begin);
 275                                         return t;
 276                                 }
 277
 278                                 if(wait_time_ms >= wait_time_max_ms)
 279                                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 280                         }
 281
 282                         // Wait a while before trying again
 283                         sleep_ms(10);
 284                         wait_time_ms += 10;
 285                 }
 286         }
 287         T pop_back(u32 wait_time_max_ms=0)
 288         {
 289                 u32 wait_time_ms = 0;
 290
 291                 for(;;)
 292                 {
 293                         {
 294                                 JMutexAutoLock lock(m_mutex);
 295
 296                                 if(!m_list.empty())
 297                                 {
 298                                         typename std::list<T>::iterator last = m_list.back();
 299                                         T t = *last;
 300                                         m_list.erase(last);
 301                                         return t;
 302                                 }
 303
 304                                 if(wait_time_ms >= wait_time_max_ms)
 305                                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 306                         }
 307
 308                         // Wait a while before trying again
 309                         sleep_ms(10);
 310                         wait_time_ms += 10;
 311                 }
 312         }
 313
 314         JMutex & getMutex()
 315         {
 316                 return m_mutex;
 317         }
 318
 319         std::list<T> & getList()
 320         {
 321                 return m_list;
 322         }
 323
 324 protected:
 325         JMutex m_mutex;
 326         std::list<T> m_list;
 327 };
 328
 329 #endif
 330