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() = default;
  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() = default;
 132
 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                 }
 158
 159                 return T();
 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                 }
 171
 172                 throw ItemNotFoundException("MutexedQueue: queue is empty");
 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                 }
 195
 196                 throw ItemNotFoundException("MutexedQueue: queue is empty");
 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                 }
 211
 212                 return T();
 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 };