src/util/container.h

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