X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Futil%2Fcontainer.h;h=b55777ff7a59edff4b1414fb3ac987b90dc9fb89;hb=d1b80b462eaa74a8640cf132c21f74e4f924052a;hp=8c1ae02fbf1c5ddfb224b4006b0de3bf3665f48a;hpb=bee170570de7a796ac7b5ba6c0b39b253380b5e3;p=minetest.git

diff --git a/src/util/container.h b/src/util/container.h
index 8c1ae02fb..b55777ff7 100644
--- a/src/util/container.h
+++ b/src/util/container.h
@@ -1,6 +1,6 @@
 /*
-Minetest-c55
-Copyright (C) 2010-2012 celeron55, Perttu Ahola <celeron55@gmail.com>
+Minetest
+Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
 
 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU Lesser General Public License as published by
@@ -17,300 +17,291 @@ 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
+#pragma once
 
-#include "../irrlichttypes.h"
-#include <jmutex.h>
-#include <jmutexautolock.h>
-#include "../porting.h" // For sleep_ms
+#include "irrlichttypes.h"
+#include "exceptions.h"
+#include "threading/mutex_auto_lock.h"
+#include "threading/semaphore.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());
-	}
-	
+	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)
-	{
-		JMutexAutoLock lock(m_mutex);
-
-		typename core::map<Key, Value>::Node *n;
-		n = m_values.find(name);
 
-		if(n == NULL)
+	bool get(const Key &name, Value *result) const
+	{
+		MutexAutoLock lock(m_mutex);
+		auto n = m_values.find(name);
+		if (n == m_values.end())
 			return false;
-		
-		if(result != NULL)
-			*result = n->getValue();
-			
+		if (result)
+			*result = n->second;
 		return true;
 	}
 
-	core::list<Value> getValues()
+	std::vector<Value> getValues() const
 	{
-		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());
-		}
+		MutexAutoLock lock(m_mutex);
+		std::vector<Value> result;
+		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(); }
+
 private:
-	core::map<Key, Value> m_values;
-	JMutex m_mutex;
+	std::map<Key, Value> m_values;
+	mutable std::mutex m_mutex;
 };
-#endif
 
-/*
-	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
+// Thread-safe Double-ended queue
 
-	Is not able to:
-	- Remove an id/value pair (is possible to implement but slow)
-*/
 template<typename T>
-class MutexedIdGenerator
+class MutexedQueue
 {
 public:
-	MutexedIdGenerator()
+	template<typename Key, typename U, typename Caller, typename CallerData>
+	friend class RequestQueue;
+
+	MutexedQueue() = default;
+
+	bool empty() const
 	{
-		m_mutex.Init();
-		assert(m_mutex.IsInitialized());
+		MutexAutoLock lock(m_mutex);
+		return m_queue.empty();
 	}
-	
-	// Returns true if found
-	bool getValue(u32 id, T &value)
+
+	void push_back(const T &t)
 	{
-		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;
+		MutexAutoLock lock(m_mutex);
+		m_queue.push_back(t);
+		m_signal.post();
 	}
-	
-	// If id exists for value, returns the id.
-	// Otherwise generates an id for the value.
-	u32 getId(const T &value)
+
+	void push_back(T &&t)
 	{
-		JMutexAutoLock lock(m_mutex);
-		typename core::map<T, u32>::Node *n;
-		n = m_value_to_id.find(value);
-		if(n != NULL)
-			return n->getValue();
-		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;
+		MutexAutoLock lock(m_mutex);
+		m_queue.push_back(std::move(t));
+		m_signal.post();
 	}
 
-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;
-};
+	/* this version of pop_front returns an 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)
+	{
+		if (m_signal.wait(wait_time_max_ms)) {
+			MutexAutoLock lock(m_mutex);
 
-/*
-	FIFO queue (well, actually a FILO also)
-*/
-template<typename T>
-class Queue
-{
-public:
-	void push_back(T t)
+			T t = std::move(m_queue.front());
+			m_queue.pop_front();
+			return t;
+		}
+
+		return T();
+	}
+
+	T pop_front(u32 wait_time_max_ms)
 	{
-		m_list.push_back(t);
+		if (m_signal.wait(wait_time_max_ms)) {
+			MutexAutoLock lock(m_mutex);
+
+			T t = std::move(m_queue.front());
+			m_queue.pop_front();
+			return t;
+		}
+
+		throw ItemNotFoundException("MutexedQueue: queue is empty");
 	}
-	
-	T pop_front()
+
+	T pop_frontNoEx()
 	{
-		if(m_list.size() == 0)
-			throw ItemNotFoundException("Queue: queue is empty");
+		m_signal.wait();
+
+		MutexAutoLock lock(m_mutex);
 
-		typename core::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()
+
+	T pop_back(u32 wait_time_max_ms=0)
 	{
-		if(m_list.size() == 0)
-			throw ItemNotFoundException("Queue: queue is empty");
+		if (m_signal.wait(wait_time_max_ms)) {
+			MutexAutoLock lock(m_mutex);
 
-		typename core::list<T>::Iterator last = m_list.getLast();
-		T t = *last;
-		m_list.erase(last);
-		return t;
+			T t = std::move(m_queue.back());
+			m_queue.pop_back();
+			return t;
+		}
+
+		throw ItemNotFoundException("MutexedQueue: queue is empty");
+	}
+
+	/* this version of pop_back returns an 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)
+	{
+		if (m_signal.wait(wait_time_max_ms)) {
+			MutexAutoLock lock(m_mutex);
+
+			T t = std::move(m_queue.back());
+			m_queue.pop_back();
+			return t;
+		}
+
+		return T();
 	}
 
-	u32 size()
+	T pop_backNoEx()
 	{
-		return m_list.size();
+		m_signal.wait();
+
+		MutexAutoLock lock(m_mutex);
+
+		T t = std::move(m_queue.back());
+		m_queue.pop_back();
+		return t;
 	}
 
 protected:
-	core::list<T> m_list;
-};
+	std::mutex &getMutex() { return m_mutex; }
 
-/*
-	Thread-safe FIFO queue (well, actually a FILO also)
-*/
+	std::deque<T> &getQueue() { return m_queue; }
 
-template<typename T>
-class MutexedQueue
+	std::deque<T> m_queue;
+	mutable std::mutex m_mutex;
+	Semaphore m_signal;
+};
+
+template<typename K, typename V>
+class LRUCache
 {
 public:
-	MutexedQueue()
+	LRUCache(size_t limit, void (*cache_miss)(void *data, const K &key, V *dest),
+			void *data)
 	{
-		m_mutex.Init();
+		m_limit = limit;
+		m_cache_miss = cache_miss;
+		m_cache_miss_data = data;
 	}
-	u32 size()
+
+	void setLimit(size_t limit)
 	{
-		JMutexAutoLock lock(m_mutex);
-		return m_list.size();
+		m_limit = limit;
+		invalidate();
 	}
-	void push_back(T t)
+
+	void invalidate()
 	{
-		JMutexAutoLock lock(m_mutex);
-		m_list.push_back(t);
+		m_map.clear();
+		m_queue.clear();
 	}
-	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");
-			}
 
-			// Wait a while before trying again
-			sleep_ms(10);
-			wait_time_ms += 10;
-		}
-	}
-	T pop_back(u32 wait_time_max_ms=0)
+	const V *lookupCache(K key)
 	{
-		u32 wait_time_ms = 0;
-
-		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");
+		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();
 			}
 
-			// Wait a while before trying again
-			sleep_ms(10);
-			wait_time_ms += 10;
+			m_queue.push_front(key);
+			entry.first = m_queue.begin();
 		}
+		return ret;
 	}
-
-	JMutex & getMutex()
-	{
-		return m_mutex;
-	}
-
-	core::list<T> & getList()
-	{
-		return m_list;
-	}
-
-protected:
-	JMutex m_mutex;
-	core::list<T> m_list;
+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
-