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 */ push_back(const Value & value)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 pop_front()57 void pop_front() 58 { 59 m_set.erase(m_queue.front()); 60 m_queue.pop(); 61 } 62 front()63 const Value& front() const 64 { 65 return m_queue.front(); 66 } 67 size()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 set(const Key & name,const Value & value)84 void set(const Key &name, const Value &value) 85 { 86 MutexAutoLock lock(m_mutex); 87 m_values[name] = value; 88 } 89 get(const Key & name,Value * result)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 getValues()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 clear()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 empty()133 bool empty() const 134 { 135 MutexAutoLock lock(m_mutex); 136 return m_queue.empty(); 137 } 138 push_back(T t)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 */ pop_frontNoEx(u32 wait_time_max_ms)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 pop_front(u32 wait_time_max_ms)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 pop_frontNoEx()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 */ pop_backNoEx(u32 wait_time_max_ms)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 pop_backNoEx()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: getMutex()227 std::mutex &getMutex() { return m_mutex; } 228 getQueue()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: LRUCache(size_t limit,void (* cache_miss)(void * data,const K & key,V * dest),void * data)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 setLimit(size_t limit)248 void setLimit(size_t limit) 249 { 250 m_limit = limit; 251 invalidate(); 252 } 253 invalidate()254 void invalidate() 255 { 256 m_map.clear(); 257 m_queue.clear(); 258 } 259 lookupCache(K key)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