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 template<typename Key, typename Value>
  81 class MutexedMap
  82 {
  83 public:
  84         MutexedMap()
  85         {
  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::vector<Value> getValues()
 112         {
 113                 std::vector<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
 132 /*
 133 Generates ids for comparable values.
 134 Id=0 is reserved for "no value".
 135
 136 Is fast at:
 137 - Returning value by id (very fast)
 138 - Returning id by value
 139 - Generating a new id for a value
 140
 141 Is not able to:
 142 - Remove an id/value pair (is possible to implement but slow)
 143 */
 144 template<typename T>
 145 class MutexedIdGenerator
 146 {
 147 public:
 148         MutexedIdGenerator()
 149         {
 150         }
 151
 152         // Returns true if found
 153         bool getValue(u32 id, T &value)
 154         {
 155                 if(id == 0)
 156                         return false;
 157                 JMutexAutoLock lock(m_mutex);
 158                 if(m_id_to_value.size() < id)
 159                         return false;
 160                 value = m_id_to_value[id-1];
 161                 return true;
 162         }
 163
 164         // If id exists for value, returns the id.
 165         // Otherwise generates an id for the value.
 166         u32 getId(const T &value)
 167         {
 168                 JMutexAutoLock lock(m_mutex);
 169                 typename std::map<T, u32>::iterator n;
 170                 n = m_value_to_id.find(value);
 171                 if(n != m_value_to_id.end())
 172                         return n->second;
 173                 m_id_to_value.push_back(value);
 174                 u32 new_id = m_id_to_value.size();
 175                 m_value_to_id.insert(value, new_id);
 176                 return new_id;
 177         }
 178
 179 private:
 180         JMutex m_mutex;
 181         // Values are stored here at id-1 position (id 1 = [0])
 182         std::vector<T> m_id_to_value;
 183         std::map<T, u32> m_value_to_id;
 184 };
 185
 186 /*
 187 Thread-safe FIFO queue (well, actually a FILO also)
 188 */
 189
 190 template<typename T>
 191 class MutexedQueue
 192 {
 193 public:
 194         template<typename Key, typename U, typename Caller, typename CallerData>
 195         friend class RequestQueue;
 196
 197         MutexedQueue()
 198         {
 199         }
 200         bool empty()
 201         {
 202                 JMutexAutoLock lock(m_mutex);
 203                 return (m_queue.size() == 0);
 204         }
 205         void push_back(T t)
 206         {
 207                 JMutexAutoLock lock(m_mutex);
 208                 m_queue.push_back(t);
 209                 m_size.Post();
 210         }
 211
 212         /* this version of pop_front returns a empty element of T on timeout.
 213         * Make sure default constructor of T creates a recognizable "empty" element
 214         */
 215         T pop_frontNoEx(u32 wait_time_max_ms)
 216         {
 217                 if (m_size.Wait(wait_time_max_ms)) {
 218                         JMutexAutoLock lock(m_mutex);
 219
 220                         T t = m_queue.front();
 221                         m_queue.pop_front();
 222                         return t;
 223                 }
 224                 else {
 225                         return T();
 226                 }
 227         }
 228
 229         T pop_front(u32 wait_time_max_ms)
 230         {
 231                 if (m_size.Wait(wait_time_max_ms)) {
 232                         JMutexAutoLock lock(m_mutex);
 233
 234                         T t = m_queue.front();
 235                         m_queue.pop_front();
 236                         return t;
 237                 }
 238                 else {
 239                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 240                 }
 241         }
 242
 243         T pop_frontNoEx()
 244         {
 245                 m_size.Wait();
 246
 247                 JMutexAutoLock lock(m_mutex);
 248
 249                 T t = m_queue.front();
 250                 m_queue.pop_front();
 251                 return t;
 252         }
 253
 254         T pop_back(u32 wait_time_max_ms=0)
 255         {
 256                 if (m_size.Wait(wait_time_max_ms)) {
 257                         JMutexAutoLock lock(m_mutex);
 258
 259                         T t = m_queue.back();
 260                         m_queue.pop_back();
 261                         return t;
 262                 }
 263                 else {
 264                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 265                 }
 266         }
 267
 268         /* this version of pop_back returns a empty element of T on timeout.
 269         * Make sure default constructor of T creates a recognizable "empty" element
 270         */
 271         T pop_backNoEx(u32 wait_time_max_ms=0)
 272         {
 273                 if (m_size.Wait(wait_time_max_ms)) {
 274                         JMutexAutoLock lock(m_mutex);
 275
 276                         T t = m_queue.back();
 277                         m_queue.pop_back();
 278                         return t;
 279                 }
 280                 else {
 281                         return T();
 282                 }
 283         }
 284
 285         T pop_backNoEx()
 286         {
 287                 m_size.Wait();
 288
 289                 JMutexAutoLock lock(m_mutex);
 290
 291                 T t = m_queue.back();
 292                 m_queue.pop_back();
 293                 return t;
 294         }
 295
 296 protected:
 297         JMutex & getMutex()
 298         {
 299                 return m_mutex;
 300         }
 301
 302         std::deque<T> & getQueue()
 303         {
 304                 return m_queue;
 305         }
 306
 307         std::deque<T> m_queue;
 308         JMutex m_mutex;
 309         JSemaphore m_size;
 310 };
 311
 312 template<typename K, typename V>
 313 class LRUCache
 314 {
 315 public:
 316         LRUCache(size_t limit, void (*cache_miss)(void *data, const K &key, V *dest),
 317                         void *data)
 318         {
 319                 m_limit = limit;
 320                 m_cache_miss = cache_miss;
 321                 m_cache_miss_data = data;
 322         }
 323
 324         void setLimit(size_t limit)
 325         {
 326                 m_limit = limit;
 327                 invalidate();
 328         }
 329
 330         void invalidate()
 331         {
 332                 m_map.clear();
 333                 m_queue.clear();
 334         }
 335
 336         const V *lookupCache(K key)
 337         {
 338                 typename cache_type::iterator it = m_map.find(key);
 339                 V *ret;
 340                 if (it != m_map.end()) {
 341                         // found!
 342
 343                         cache_entry_t &entry = it->second;
 344
 345                         ret = &entry.second;
 346
 347                         // update the usage information
 348                         m_queue.erase(entry.first);
 349                         m_queue.push_front(key);
 350                         entry.first = m_queue.begin();
 351                 } else {
 352                         // cache miss -- enter into cache
 353                         cache_entry_t &entry =
 354                                 m_map[key];
 355                         ret = &entry.second;
 356                         m_cache_miss(m_cache_miss_data, key, &entry.second);
 357
 358                         // delete old entries
 359                         if (m_queue.size() == m_limit) {
 360                                 const K &id = m_queue.back();
 361                                 m_map.erase(id);
 362                                 m_queue.pop_back();
 363                         }
 364
 365                         m_queue.push_front(key);
 366                         entry.first = m_queue.begin();
 367                 }
 368                 return ret;
 369         }
 370 private:
 371         void (*m_cache_miss)(void *data, const K &key, V *dest);
 372         void *m_cache_miss_data;
 373         size_t m_limit;
 374         typedef typename std::template pair<typename std::template list<K>::iterator, V> cache_entry_t;
 375         typedef std::template map<K, cache_entry_t> cache_type;
 376         cache_type m_map;
 377         // we can't use std::deque here, because its iterators get invalidated
 378         std::list<K> m_queue;
 379 };
 380
 381 #endif
 382