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 #pragma once
  21
  22 #include "../irrlichttypes.h"
  23 #include "../exceptions.h"
  24 #include "../threading/mutex_auto_lock.h"
  25 #include "../threading/semaphore.h"
  26 #include <list>
  27 #include <vector>
  28 #include <map>
  29 #include <set>
  30 #include <queue>
  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(const Value& value)
  48         {
  49                 if (m_set.insert(value).second)
  50                 {
  51                         m_queue.push(value);
  52                         return true;
  53                 }
  54                 return false;
  55         }
  56
  57         void pop_front()
  58         {
  59                 m_set.erase(m_queue.front());
  60                 m_queue.pop();
  61         }
  62
  63         const Value& front() const
  64         {
  65                 return m_queue.front();
  66         }
  67
  68         u32 size() const
  69         {
  70                 return m_queue.size();
  71         }
  72
  73 private:
  74         std::set<Value> m_set;
  75         std::queue<Value> m_queue;
  76 };
  77
  78 template<typename Key, typename Value>
  79 class MutexedMap
  80 {
  81 public:
  82         MutexedMap() {}
  83
  84         void set(const Key &name, const Value &value)
  85         {
  86                 MutexAutoLock lock(m_mutex);
  87                 m_values[name] = value;
  88         }
  89
  90         bool get(const Key &name, Value *result) const
  91         {
  92                 MutexAutoLock lock(m_mutex);
  93                 typename std::map<Key, Value>::const_iterator n =
  94                         m_values.find(name);
  95                 if (n == m_values.end())
  96                         return false;
  97                 if (result)
  98                         *result = n->second;
  99                 return true;
 100         }
 101
 102         std::vector<Value> getValues() const
 103         {
 104                 MutexAutoLock lock(m_mutex);
 105                 std::vector<Value> result;
 106                 for (typename std::map<Key, Value>::const_iterator
 107                                 it = m_values.begin();
 108                                 it != m_values.end(); ++it){
 109                         result.push_back(it->second);
 110                 }
 111                 return result;
 112         }
 113
 114         void clear() { m_values.clear(); }
 115
 116 private:
 117         std::map<Key, Value> m_values;
 118         mutable std::mutex m_mutex;
 119 };
 120
 121
 122 // Thread-safe Double-ended queue
 123
 124 template<typename T>
 125 class MutexedQueue
 126 {
 127 public:
 128         template<typename Key, typename U, typename Caller, typename CallerData>
 129         friend class RequestQueue;
 130
 131         MutexedQueue() {}
 132         bool empty() const
 133         {
 134                 MutexAutoLock lock(m_mutex);
 135                 return m_queue.empty();
 136         }
 137
 138         void push_back(T t)
 139         {
 140                 MutexAutoLock lock(m_mutex);
 141                 m_queue.push_back(t);
 142                 m_signal.post();
 143         }
 144
 145         /* this version of pop_front returns a empty element of T on timeout.
 146         * Make sure default constructor of T creates a recognizable "empty" element
 147         */
 148         T pop_frontNoEx(u32 wait_time_max_ms)
 149         {
 150                 if (m_signal.wait(wait_time_max_ms)) {
 151                         MutexAutoLock lock(m_mutex);
 152
 153                         T t = m_queue.front();
 154                         m_queue.pop_front();
 155                         return t;
 156                 } else {
 157                         return T();
 158                 }
 159         }
 160
 161         T pop_front(u32 wait_time_max_ms)
 162         {
 163                 if (m_signal.wait(wait_time_max_ms)) {
 164                         MutexAutoLock lock(m_mutex);
 165
 166                         T t = m_queue.front();
 167                         m_queue.pop_front();
 168                         return t;
 169                 } else {
 170                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 171                 }
 172         }
 173
 174         T pop_frontNoEx()
 175         {
 176                 m_signal.wait();
 177
 178                 MutexAutoLock lock(m_mutex);
 179
 180                 T t = m_queue.front();
 181                 m_queue.pop_front();
 182                 return t;
 183         }
 184
 185         T pop_back(u32 wait_time_max_ms=0)
 186         {
 187                 if (m_signal.wait(wait_time_max_ms)) {
 188                         MutexAutoLock lock(m_mutex);
 189
 190                         T t = m_queue.back();
 191                         m_queue.pop_back();
 192                         return t;
 193                 } else {
 194                         throw ItemNotFoundException("MutexedQueue: queue is empty");
 195                 }
 196         }
 197
 198         /* this version of pop_back returns a empty element of T on timeout.
 199         * Make sure default constructor of T creates a recognizable "empty" element
 200         */
 201         T pop_backNoEx(u32 wait_time_max_ms)
 202         {
 203                 if (m_signal.wait(wait_time_max_ms)) {
 204                         MutexAutoLock lock(m_mutex);
 205
 206                         T t = m_queue.back();
 207                         m_queue.pop_back();
 208                         return t;
 209                 } else {
 210                         return T();
 211                 }
 212         }
 213
 214         T pop_backNoEx()
 215         {
 216                 m_signal.wait();
 217
 218                 MutexAutoLock lock(m_mutex);
 219
 220                 T t = m_queue.back();
 221                 m_queue.pop_back();
 222                 return t;
 223         }
 224
 225 protected:
 226         std::mutex &getMutex() { return m_mutex; }
 227
 228         std::deque<T> &getQueue() { return m_queue; }
 229
 230         std::deque<T> m_queue;
 231         mutable std::mutex m_mutex;
 232         Semaphore m_signal;
 233 };
 234
 235 template<typename K, typename V>
 236 class LRUCache
 237 {
 238 public:
 239         LRUCache(size_t limit, void (*cache_miss)(void *data, const K &key, V *dest),
 240                         void *data)
 241         {
 242                 m_limit = limit;
 243                 m_cache_miss = cache_miss;
 244                 m_cache_miss_data = data;
 245         }
 246
 247         void setLimit(size_t limit)
 248         {
 249                 m_limit = limit;
 250                 invalidate();
 251         }
 252
 253         void invalidate()
 254         {
 255                 m_map.clear();
 256                 m_queue.clear();
 257         }
 258
 259         const V *lookupCache(K key)
 260         {
 261                 typename cache_type::iterator it = m_map.find(key);
 262                 V *ret;
 263                 if (it != m_map.end()) {
 264                         // found!
 265
 266                         cache_entry_t &entry = it->second;
 267
 268                         ret = &entry.second;
 269
 270                         // update the usage information
 271                         m_queue.erase(entry.first);
 272                         m_queue.push_front(key);
 273                         entry.first = m_queue.begin();
 274                 } else {
 275                         // cache miss -- enter into cache
 276                         cache_entry_t &entry =
 277                                 m_map[key];
 278                         ret = &entry.second;
 279                         m_cache_miss(m_cache_miss_data, key, &entry.second);
 280
 281                         // delete old entries
 282                         if (m_queue.size() == m_limit) {
 283                                 const K &id = m_queue.back();
 284                                 m_map.erase(id);
 285                                 m_queue.pop_back();
 286                         }
 287
 288                         m_queue.push_front(key);
 289                         entry.first = m_queue.begin();
 290                 }
 291                 return ret;
 292         }
 293 private:
 294         void (*m_cache_miss)(void *data, const K &key, V *dest);
 295         void *m_cache_miss_data;
 296         size_t m_limit;
 297         typedef typename std::template pair<typename std::template list<K>::iterator, V> cache_entry_t;
 298         typedef std::template map<K, cache_entry_t> cache_type;
 299         cache_type m_map;
 300         // we can't use std::deque here, because its iterators get invalidated
 301         std::list<K> m_queue;
 302 };