#define UTIL_CONTAINER_HEADER
#include "../irrlichttypes.h"
-#include <jmutex.h>
-#include <jmutexautolock.h>
-#include "../porting.h" // For sleep_ms
+#include "../exceptions.h"
+#include "../jthread/jmutex.h"
+#include "../jthread/jmutexautolock.h"
+#include "../jthread/jsemaphore.h"
+#include <list>
+#include <vector>
+#include <map>
+#include <set>
+#include <queue>
/*
- Queue with unique values with fast checking of value existence
+Queue with unique values with fast checking of value existence
*/
template<typename Value>
class UniqueQueue
{
public:
-
+
/*
- Does nothing if value is already queued.
- Return value:
- true: value added
- false: value already exists
+ Does nothing if value is already queued.
+ Return value:
+ true: value added
+ false: value already exists
*/
- bool push_back(Value value)
+ bool push_back(const Value& value)
{
- // Check if already exists
- if(m_map.find(value) != NULL)
- return false;
+ if (m_set.insert(value).second)
+ {
+ m_queue.push(value);
+ return true;
+ }
+ return false;
+ }
- // Add
- m_map.insert(value, 0);
- m_list.push_back(value);
-
- return true;
+ void pop_front()
+ {
+ m_set.erase(m_queue.front());
+ m_queue.pop();
}
- Value pop_front()
+ const Value& front() const
{
- typename core::list<Value>::Iterator i = m_list.begin();
- Value value = *i;
- m_map.remove(value);
- m_list.erase(i);
- return value;
+ return m_queue.front();
}
- u32 size()
+ u32 size() const
{
- assert(m_list.size() == m_map.size());
- return m_list.size();
+ return m_queue.size();
}
private:
- core::map<Value, u8> m_map;
- core::list<Value> m_list;
+ std::set<Value> m_set;
+ std::queue<Value> m_queue;
};
-#if 1
template<typename Key, typename Value>
class MutexedMap
{
public:
MutexedMap()
{
- m_mutex.Init();
- assert(m_mutex.IsInitialized());
}
-
+
void set(const Key &name, const Value &value)
{
JMutexAutoLock lock(m_mutex);
m_values[name] = value;
}
-
+
bool get(const Key &name, Value *result)
{
JMutexAutoLock lock(m_mutex);
- typename core::map<Key, Value>::Node *n;
+ typename std::map<Key, Value>::iterator n;
n = m_values.find(name);
- if(n == NULL)
+ if(n == m_values.end())
return false;
-
+
if(result != NULL)
- *result = n->getValue();
-
+ *result = n->second;
+
return true;
}
- core::list<Value> getValues()
+ std::vector<Value> getValues()
{
- core::list<Value> result;
- for(typename core::map<Key, Value>::Iterator
- i = m_values.getIterator();
- i.atEnd() == false; i++){
- result.push_back(i.getNode()->getValue());
+ 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);
}
return result;
}
+ void clear ()
+ {
+ m_values.clear();
+ }
+
private:
- core::map<Key, Value> m_values;
+ std::map<Key, Value> m_values;
JMutex m_mutex;
};
-#endif
/*
- Generates ids for comparable values.
- Id=0 is reserved for "no value".
+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 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)
+Is not able to:
+- Remove an id/value pair (is possible to implement but slow)
*/
template<typename T>
class MutexedIdGenerator
public:
MutexedIdGenerator()
{
- m_mutex.Init();
- assert(m_mutex.IsInitialized());
}
-
+
// Returns true if found
bool getValue(u32 id, T &value)
{
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 core::map<T, u32>::Node *n;
+ typename std::map<T, u32>::iterator n;
n = m_value_to_id.find(value);
- if(n != NULL)
- return n->getValue();
+ 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);
private:
JMutex m_mutex;
// Values are stored here at id-1 position (id 1 = [0])
- core::array<T> m_id_to_value;
- core::map<T, u32> m_value_to_id;
+ std::vector<T> m_id_to_value;
+ std::map<T, u32> m_value_to_id;
};
/*
- FIFO queue (well, actually a FILO also)
+Thread-safe FIFO queue (well, actually a FILO also)
*/
+
template<typename T>
-class Queue
+class MutexedQueue
{
public:
- void push_back(T t)
+ template<typename Key, typename U, typename Caller, typename CallerData>
+ friend class RequestQueue;
+
+ MutexedQueue()
{
- m_list.push_back(t);
}
-
- T pop_front()
+ bool empty()
{
- if(m_list.size() == 0)
- throw ItemNotFoundException("Queue: queue is empty");
-
- typename core::list<T>::Iterator begin = m_list.begin();
- T t = *begin;
- m_list.erase(begin);
- return t;
+ JMutexAutoLock lock(m_mutex);
+ return (m_queue.size() == 0);
}
- T pop_back()
+ void push_back(T t)
{
- if(m_list.size() == 0)
- throw ItemNotFoundException("Queue: queue is empty");
-
- typename core::list<T>::Iterator last = m_list.getLast();
- T t = *last;
- m_list.erase(last);
- return t;
+ JMutexAutoLock lock(m_mutex);
+ m_queue.push_back(t);
+ m_size.Post();
}
- u32 size()
+ /* this version of pop_front returns a empty element of T on timeout.
+ * Make sure default constructor of T creates a recognizable "empty" element
+ */
+ T pop_frontNoEx(u32 wait_time_max_ms)
{
- return m_list.size();
- }
-
-protected:
- core::list<T> m_list;
-};
+ if (m_size.Wait(wait_time_max_ms)) {
+ JMutexAutoLock lock(m_mutex);
-/*
- Thread-safe FIFO queue (well, actually a FILO also)
-*/
+ T t = m_queue.front();
+ m_queue.pop_front();
+ return t;
+ }
+ else {
+ return T();
+ }
+ }
-template<typename T>
-class MutexedQueue
-{
-public:
- MutexedQueue()
+ T pop_front(u32 wait_time_max_ms)
{
- m_mutex.Init();
+ if (m_size.Wait(wait_time_max_ms)) {
+ JMutexAutoLock lock(m_mutex);
+
+ T t = m_queue.front();
+ m_queue.pop_front();
+ return t;
+ }
+ else {
+ throw ItemNotFoundException("MutexedQueue: queue is empty");
+ }
}
- u32 size()
+
+ T pop_frontNoEx()
{
+ m_size.Wait();
+
JMutexAutoLock lock(m_mutex);
- return m_list.size();
+
+ T t = m_queue.front();
+ m_queue.pop_front();
+ return t;
}
- void push_back(T t)
+
+ T pop_back(u32 wait_time_max_ms=0)
{
- JMutexAutoLock lock(m_mutex);
- m_list.push_back(t);
+ if (m_size.Wait(wait_time_max_ms)) {
+ JMutexAutoLock lock(m_mutex);
+
+ T t = m_queue.back();
+ m_queue.pop_back();
+ return t;
+ }
+ else {
+ throw ItemNotFoundException("MutexedQueue: queue is empty");
+ }
}
- T pop_front(u32 wait_time_max_ms=0)
- {
- u32 wait_time_ms = 0;
- for(;;)
- {
- {
- JMutexAutoLock lock(m_mutex);
-
- if(m_list.size() > 0)
- {
- typename core::list<T>::Iterator begin = m_list.begin();
- T t = *begin;
- m_list.erase(begin);
- return t;
- }
-
- if(wait_time_ms >= wait_time_max_ms)
- 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)
+ {
+ if (m_size.Wait(wait_time_max_ms)) {
+ JMutexAutoLock lock(m_mutex);
- // Wait a while before trying again
- sleep_ms(10);
- wait_time_ms += 10;
+ T t = m_queue.back();
+ m_queue.pop_back();
+ return t;
+ }
+ else {
+ return T();
}
}
- T pop_back(u32 wait_time_max_ms=0)
+
+ T pop_backNoEx()
{
- u32 wait_time_ms = 0;
+ m_size.Wait();
- for(;;)
- {
- {
- JMutexAutoLock lock(m_mutex);
-
- if(m_list.size() > 0)
- {
- typename core::list<T>::Iterator last = m_list.getLast();
- T t = *last;
- m_list.erase(last);
- return t;
- }
-
- if(wait_time_ms >= wait_time_max_ms)
- throw ItemNotFoundException("MutexedQueue: queue is empty");
- }
+ JMutexAutoLock lock(m_mutex);
- // Wait a while before trying again
- sleep_ms(10);
- wait_time_ms += 10;
- }
+ T t = m_queue.back();
+ m_queue.pop_back();
+ return t;
}
+protected:
JMutex & getMutex()
{
return m_mutex;
}
- core::list<T> & getList()
+ std::deque<T> & getQueue()
{
- return m_list;
+ return m_queue;
}
-protected:
+ std::deque<T> m_queue;
JMutex m_mutex;
- core::list<T> m_list;
+ JSemaphore m_size;
+};
+
+template<typename K, typename V>
+class LRUCache
+{
+public:
+ LRUCache(size_t limit, void (*cache_miss)(void *data, const K &key, V *dest),
+ void *data)
+ {
+ m_limit = limit;
+ m_cache_miss = cache_miss;
+ m_cache_miss_data = data;
+ }
+
+ void setLimit(size_t limit)
+ {
+ m_limit = limit;
+ invalidate();
+ }
+
+ 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;
};
#endif
projects / dragonfireclient.git / blobdiff