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 <list>
#include <vector>
#include <map>
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<Key, Value>::iterator n;
- n = m_values.find(name);
-
- if(n == m_values.end())
+ MutexAutoLock lock(m_mutex);
+ auto n = m_values.find(name);
+ if (n == m_values.end())
return false;
-
- if(result != NULL)
+ if (result)
*result = n->second;
-
return true;
}
- std::vector<Value> getValues()
+ std::vector<Value> getValues() const
{
+ MutexAutoLock lock(m_mutex);
std::vector<Value> result;
- for(typename std::map<Key, Value>::iterator
- i = m_values.begin();
- i != m_values.end(); ++i){
- result.push_back(i->second);
- }
+ result.reserve(m_values.size());
+ for (auto 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<Key, Value> 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<typename T>
-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<T, u32>::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<T> m_id_to_value;
- std::map<T, u32> m_value_to_id;
-};
-
-/*
-FIFO queue (well, actually a FILO also)
-*/
-template<typename T>
-class Queue
-{
-public:
- Queue():
- m_list_size(0)
- {}
-
- void push_back(T t)
- {
- m_list.push_back(t);
- ++m_list_size;
- }
-
- void push_front(T t)
- {
- m_list.push_front(t);
- ++m_list_size;
- }
-
- T pop_front()
- {
- if(m_list.empty())
- throw ItemNotFoundException("Queue: queue is empty");
-
- typename std::list<T>::iterator begin = m_list.begin();
- T t = *begin;
- m_list.erase(begin);
- --m_list_size;
- return t;
- }
- T pop_back()
- {
- if(m_list.empty())
- throw ItemNotFoundException("Queue: queue is empty");
-
- typename std::list<T>::iterator last = m_list.back();
- T t = *last;
- m_list.erase(last);
- --m_list_size;
- return t;
- }
- u32 size()
- {
- return m_list_size;
- }
-
- bool empty()
- {
- return m_list.empty();
- }
-
-protected:
- std::list<T> m_list;
- u32 m_list_size;
-};
-
-/*
-Thread-safe FIFO queue (well, actually a FILO also)
-*/
+// Thread-safe Double-ended queue
template<typename T>
class MutexedQueue
template<typename Key, typename U, typename Caller, typename CallerData>
friend class RequestQueue;
- MutexedQueue()
+ MutexedQueue() = default;
+
+ bool empty() const
{
+ MutexAutoLock lock(m_mutex);
+ return m_queue.empty();
}
- bool empty()
+
+ void push_back(const T &t)
{
- JMutexAutoLock lock(m_mutex);
- return (m_size.GetValue() == 0);
+ MutexAutoLock lock(m_mutex);
+ m_queue.push_back(t);
+ m_signal.post();
}
- void push_back(T t)
+
+ void push_back(T &&t)
{
- JMutexAutoLock lock(m_mutex);
- m_list.push_back(t);
- m_size.Post();
+ MutexAutoLock lock(m_mutex);
+ m_queue.push_back(std::move(t));
+ m_signal.post();
}
/* this version of pop_front returns a empty element of T on timeout.
*/
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);
- typename std::list<T>::iterator begin = m_list.begin();
- T t = *begin;
- m_list.erase(begin);
+ T t = std::move(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);
- typename std::list<T>::iterator begin = m_list.begin();
- T t = *begin;
- m_list.erase(begin);
+ T t = std::move(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);
- typename std::list<T>::iterator begin = m_list.begin();
- T t = *begin;
- m_list.erase(begin);
+ T t = std::move(m_queue.front());
+ m_queue.pop_front();
return t;
}
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);
- typename std::list<T>::iterator last = m_list.end();
- last--;
- T t = *last;
- m_list.erase(last);
+ T t = std::move(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);
- typename std::list<T>::iterator last = m_list.end();
- last--;
- T t = *last;
- m_list.erase(last);
+ T t = std::move(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);
- typename std::list<T>::iterator last = m_list.end();
- last--;
- T t = *last;
- m_list.erase(last);
+ T t = std::move(m_queue.back());
+ m_queue.pop_back();
return t;
}
protected:
- JMutex & getMutex()
+ std::mutex &getMutex() { return m_mutex; }
+
+ std::deque<T> &getQueue() { return m_queue; }
+
+ std::deque<T> m_queue;
+ mutable std::mutex m_mutex;
+ Semaphore m_signal;
+};
+
+template<typename K, typename V>
+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;
}
- // NEVER EVER modify the >>list<< you got by using this function!
- // You may only modify it's content
- std::list<T> & getList()
+ void setLimit(size_t limit)
{
- return m_list;
+ m_limit = limit;
+ invalidate();
}
- JMutex m_mutex;
- std::list<T> m_list;
- 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<typename std::template list<K>::iterator, V> cache_entry_t;
+ typedef std::template map<K, cache_entry_t> cache_type;
+ cache_type m_map;
+ // we can't use std::deque here, because its iterators get invalidated
+ std::list<K> m_queue;
+};
projects / dragonfireclient.git / blobdiff