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