X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;ds=sidebyside;f=src%2Futil%2Fcontainer.h;h=2ad2bbfc740362da4447b9ae6293c82d416e0c6d;hb=9bb381ebd387cd783da8d582949bf284a29d9b3a;hp=936c46d6111b8f69ef7ebffa6ad9f16ee7548371;hpb=2f0107f4a7e82019a68ae3c0572886622d9d49bf;p=dragonfireclient.git diff --git a/src/util/container.h b/src/util/container.h index 936c46d61..2ad2bbfc7 100644 --- a/src/util/container.h +++ b/src/util/container.h @@ -17,14 +17,12 @@ with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ -#ifndef UTIL_CONTAINER_HEADER -#define UTIL_CONTAINER_HEADER - -#include "../irrlichttypes.h" -#include "../exceptions.h" -#include "../jthread/jmutex.h" -#include "../jthread/jmutexautolock.h" -#include "../jthread/jsemaphore.h" +#pragma once + +#include "irrlichttypes.h" +#include "exceptions.h" +#include "threading/mutex_auto_lock.h" +#include "threading/semaphore.h" #include #include #include @@ -81,111 +79,47 @@ template class MutexedMap { public: - MutexedMap() - { - } + MutexedMap() = default; void set(const Key &name, const Value &value) { - JMutexAutoLock lock(m_mutex); - + MutexAutoLock lock(m_mutex); m_values[name] = value; } - bool get(const Key &name, Value *result) + bool get(const Key &name, Value *result) const { - JMutexAutoLock lock(m_mutex); - - typename std::map::iterator n; - n = m_values.find(name); - - if(n == m_values.end()) + MutexAutoLock lock(m_mutex); + typename std::map::const_iterator n = + m_values.find(name); + if (n == m_values.end()) return false; - - if(result != NULL) + if (result) *result = n->second; - return true; } - std::vector getValues() + std::vector getValues() const { + MutexAutoLock lock(m_mutex); std::vector result; - for(typename std::map::iterator - i = m_values.begin(); - i != m_values.end(); ++i){ - result.push_back(i->second); + for (typename std::map::const_iterator + it = m_values.begin(); + it != m_values.end(); ++it){ + result.push_back(it->second); } return result; } - void clear () - { - m_values.clear(); - } + void clear() { m_values.clear(); } private: std::map m_values; - JMutex m_mutex; + mutable std::mutex m_mutex; }; -/* -Generates ids for comparable values. -Id=0 is reserved for "no value". - -Is fast at: -- Returning value by id (very fast) -- Returning id by value -- Generating a new id for a value - -Is not able to: -- Remove an id/value pair (is possible to implement but slow) -*/ -template -class MutexedIdGenerator -{ -public: - MutexedIdGenerator() - { - } - - // Returns true if found - bool getValue(u32 id, T &value) - { - if(id == 0) - return false; - JMutexAutoLock lock(m_mutex); - if(m_id_to_value.size() < id) - return false; - value = m_id_to_value[id-1]; - return true; - } - - // If id exists for value, returns the id. - // Otherwise generates an id for the value. - u32 getId(const T &value) - { - JMutexAutoLock lock(m_mutex); - typename std::map::iterator n; - n = m_value_to_id.find(value); - if(n != m_value_to_id.end()) - return n->second; - m_id_to_value.push_back(value); - u32 new_id = m_id_to_value.size(); - m_value_to_id.insert(value, new_id); - return new_id; - } - -private: - JMutex m_mutex; - // Values are stored here at id-1 position (id 1 = [0]) - std::vector m_id_to_value; - std::map m_value_to_id; -}; -/* -Thread-safe FIFO queue (well, actually a FILO also) -*/ +// Thread-safe Double-ended queue template class MutexedQueue @@ -194,19 +128,19 @@ class MutexedQueue template friend class RequestQueue; - MutexedQueue() - { - } - bool empty() + MutexedQueue() = default; + + bool empty() const { - JMutexAutoLock lock(m_mutex); - return (m_queue.size() == 0); + MutexAutoLock lock(m_mutex); + return m_queue.empty(); } + void push_back(T t) { - JMutexAutoLock lock(m_mutex); + MutexAutoLock lock(m_mutex); m_queue.push_back(t); - m_size.Post(); + m_signal.post(); } /* this version of pop_front returns a empty element of T on timeout. @@ -214,37 +148,35 @@ class MutexedQueue */ T pop_frontNoEx(u32 wait_time_max_ms) { - if (m_size.Wait(wait_time_max_ms)) { - JMutexAutoLock lock(m_mutex); + if (m_signal.wait(wait_time_max_ms)) { + MutexAutoLock lock(m_mutex); T t = m_queue.front(); m_queue.pop_front(); return t; } - else { - return T(); - } + + return T(); } T pop_front(u32 wait_time_max_ms) { - if (m_size.Wait(wait_time_max_ms)) { - JMutexAutoLock lock(m_mutex); + if (m_signal.wait(wait_time_max_ms)) { + MutexAutoLock lock(m_mutex); T t = m_queue.front(); m_queue.pop_front(); return t; } - else { - throw ItemNotFoundException("MutexedQueue: queue is empty"); - } + + throw ItemNotFoundException("MutexedQueue: queue is empty"); } T pop_frontNoEx() { - m_size.Wait(); + m_signal.wait(); - JMutexAutoLock lock(m_mutex); + MutexAutoLock lock(m_mutex); T t = m_queue.front(); m_queue.pop_front(); @@ -253,40 +185,38 @@ class MutexedQueue T pop_back(u32 wait_time_max_ms=0) { - if (m_size.Wait(wait_time_max_ms)) { - JMutexAutoLock lock(m_mutex); + if (m_signal.wait(wait_time_max_ms)) { + MutexAutoLock lock(m_mutex); T t = m_queue.back(); m_queue.pop_back(); return t; } - else { - throw ItemNotFoundException("MutexedQueue: queue is empty"); - } + + throw ItemNotFoundException("MutexedQueue: queue is empty"); } /* this version of pop_back returns a empty element of T on timeout. * Make sure default constructor of T creates a recognizable "empty" element */ - T pop_backNoEx(u32 wait_time_max_ms=0) + T pop_backNoEx(u32 wait_time_max_ms) { - if (m_size.Wait(wait_time_max_ms)) { - JMutexAutoLock lock(m_mutex); + if (m_signal.wait(wait_time_max_ms)) { + MutexAutoLock lock(m_mutex); T t = m_queue.back(); m_queue.pop_back(); return t; } - else { - return T(); - } + + return T(); } T pop_backNoEx() { - m_size.Wait(); + m_signal.wait(); - JMutexAutoLock lock(m_mutex); + MutexAutoLock lock(m_mutex); T t = m_queue.back(); m_queue.pop_back(); @@ -294,20 +224,80 @@ class MutexedQueue } protected: - JMutex & getMutex() + std::mutex &getMutex() { return m_mutex; } + + std::deque &getQueue() { return m_queue; } + + std::deque m_queue; + mutable std::mutex m_mutex; + Semaphore m_signal; +}; + +template +class LRUCache +{ +public: + LRUCache(size_t limit, void (*cache_miss)(void *data, const K &key, V *dest), + void *data) { - return m_mutex; + m_limit = limit; + m_cache_miss = cache_miss; + m_cache_miss_data = data; } - std::deque & getQueue() + void setLimit(size_t limit) { - return m_queue; + m_limit = limit; + invalidate(); } - std::deque m_queue; - JMutex m_mutex; - JSemaphore m_size; -}; - -#endif + void invalidate() + { + m_map.clear(); + m_queue.clear(); + } + const V *lookupCache(K key) + { + typename cache_type::iterator it = m_map.find(key); + V *ret; + if (it != m_map.end()) { + // found! + + cache_entry_t &entry = it->second; + + ret = &entry.second; + + // update the usage information + m_queue.erase(entry.first); + m_queue.push_front(key); + entry.first = m_queue.begin(); + } else { + // cache miss -- enter into cache + cache_entry_t &entry = + m_map[key]; + ret = &entry.second; + m_cache_miss(m_cache_miss_data, key, &entry.second); + + // delete old entries + if (m_queue.size() == m_limit) { + const K &id = m_queue.back(); + m_map.erase(id); + m_queue.pop_back(); + } + + m_queue.push_front(key); + entry.first = m_queue.begin(); + } + return ret; + } +private: + void (*m_cache_miss)(void *data, const K &key, V *dest); + void *m_cache_miss_data; + size_t m_limit; + typedef typename std::template pair::iterator, V> cache_entry_t; + typedef std::template map cache_type; + cache_type m_map; + // we can't use std::deque here, because its iterators get invalidated + std::list m_queue; +};