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