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         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                 m_mutex.Init();
 152                 assert(m_mutex.IsInitialized());
 153         }
 154
 155         // Returns true if found
 156         bool getValue(u32 id, T &value)
 157         {
 158                 if(id == 0)
 159                         return false;
 160                 JMutexAutoLock lock(m_mutex);
 161                 if(m_id_to_value.size() < id)
 162                         return false;
 163                 value = m_id_to_value[id-1];
 164                 return true;
 165         }
 166
 167         // If id exists for value, returns the id.
 168         // Otherwise generates an id for the value.
 169         u32 getId(const T &value)
 170         {
 171                 JMutexAutoLock lock(m_mutex);
 172                 typename std::map<T, u32>::iterator n;
 173                 n = m_value_to_id.find(value);
 174                 if(n != m_value_to_id.end())
 175                         return n->second;
 176                 m_id_to_value.push_back(value);
 177                 u32 new_id = m_id_to_value.size();
 178                 m_value_to_id.insert(value, new_id);
 179                 return new_id;
 180         }
 181
 182 private:
 183         JMutex m_mutex;
 184         // Values are stored here at id-1 position (id 1 = [0])
 185         std::vector<T> m_id_to_value;
 186         std::map<T, u32> m_value_to_id;
 187 };
 188
 189 /*
 190         FIFO queue (well, actually a FILO also)
 191 */
 192 template<typename T>
 193 class Queue
 194 {
 195 public:
 196         Queue():
 197                 m_list_size(0)
 198         {}
 199
 200         void push_back(T t)
 201         {
 202                 m_list.push_back(t);
 203                 ++m_list_size;
 204         }
 205
 206         T pop_front()
 207         {
 208                 if(m_list.empty())
 209                         throw ItemNotFoundException("Queue: queue is empty");
 210
 211                 typename std::list<T>::iterator begin = m_list.begin();
 212                 T t = *begin;
 213                 m_list.erase(begin);
 214                 --m_list_size;
 215                 return t;
 216         }
 217         T pop_back()
 218         {
 219                 if(m_list.empty())
 220                         throw ItemNotFoundException("Queue: queue is empty");
 221
 222                 typename std::list<T>::iterator last = m_list.back();
 223                 T t = *last;
 224                 m_list.erase(last);
 225                 --m_list_size;
 226                 return t;
 227         }
 228
 229         u32 size()
 230         {
 231                 return m_list_size;
 232         }
 233
 234         bool empty()
 235         {
 236                 return m_list.empty();
 237         }
 238
 239 protected:
 240         std::list<T> m_list;
 241         u32 m_list_size;
 242 };
 243
 244 /*
 245         Thread-safe FIFO queue (well, actually a FILO also)
 246 */
 247
 248 template<typename T>
 249 class MutexedQueue
 250 {
 251 public:
 252         MutexedQueue()
 253         {
 254                 m_mutex.Init();
 255         }
 256         bool empty()
 257         {
 258                 JMutexAutoLock lock(m_mutex);
 259                 return m_list.empty();
 260         }
 261         void push_back(T t)
 262         {
 263                 JMutexAutoLock lock(m_mutex);
 264                 m_list.push_back(t);
 265         }
 266         T pop_front(u32 wait_time_max_ms=0)
 267         {
 268                 u32 wait_time_ms = 0;
 269
 270                 for(;;)
 271                 {
 272                         {
 273                                 JMutexAutoLock lock(m_mutex);
 274
 275                                 if(!m_list.empty())
 276                                 {
 277                                         typename std::list<T>::iterator begin = m_list.begin();
 278                                         T t = *begin;
 279                                         m_list.erase(begin);
 280                                         return t;
 281                                 }
 282
 283                                 if(wait_time_ms >= wait_time_max_ms)
 284                                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 285                         }
 286
 287                         // Wait a while before trying again
 288                         sleep_ms(10);
 289                         wait_time_ms += 10;
 290                 }
 291         }
 292         T pop_back(u32 wait_time_max_ms=0)
 293         {
 294                 u32 wait_time_ms = 0;
 295
 296                 for(;;)
 297                 {
 298                         {
 299                                 JMutexAutoLock lock(m_mutex);
 300
 301                                 if(!m_list.empty())
 302                                 {
 303                                         typename std::list<T>::iterator last = m_list.back();
 304                                         T t = *last;
 305                                         m_list.erase(last);
 306                                         return t;
 307                                 }
 308
 309                                 if(wait_time_ms >= wait_time_max_ms)
 310                                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 311                         }
 312
 313                         // Wait a while before trying again
 314                         sleep_ms(10);
 315                         wait_time_ms += 10;
 316                 }
 317         }
 318
 319         JMutex & getMutex()
 320         {
 321                 return m_mutex;
 322         }
 323
 324         std::list<T> & getList()
 325         {
 326                 return m_list;
 327         }
 328
 329 protected:
 330         JMutex m_mutex;
 331         std::list<T> m_list;
 332 };
 333
 334 #endif
 335