X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Futil%2Fcontainer.h;h=267d54c16632cce645aee9df2db856b831d3cc0e;hb=abe6c072d66777b171399f42548bad75f618f1a3;hp=775372649bdc4ee14d2067255976dbe032a862d4;hpb=22e186b4aa88b585e71500c4e9a03bf69b0b6191;p=dragonfireclient.git

diff --git a/src/util/container.h b/src/util/container.h
index 775372649..267d54c16 100644
--- a/src/util/container.h
+++ b/src/util/container.h
@@ -21,120 +21,125 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #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
@@ -142,10 +147,8 @@ class MutexedIdGenerator
 public:
 	MutexedIdGenerator()
 	{
-		m_mutex.Init();
-		assert(m_mutex.IsInitialized());
 	}
-	
+
 	// Returns true if found
 	bool getValue(u32 id, T &value)
 	{
@@ -157,16 +160,16 @@ class MutexedIdGenerator
 		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);
@@ -176,140 +179,203 @@ class MutexedIdGenerator
 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