Change UniqueQueue to use a queue and a set.

2 files changed, 58 insertions, 53 deletions

diff --git a/src/map.cpp b/src/map.cpp
index ec2a5f74c..48585a170 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -1663,7 +1663,8 @@ void Map::transformLiquids(std::map<v3s16, MapBlock*> & modified_blocks)
 		/*
 			Get a queued transforming liquid node
 		*/
-		v3s16 p0 = m_transforming_liquid.pop_front();
+		v3s16 p0 = m_transforming_liquid.front();
+		m_transforming_liquid.pop_front();
 
 		MapNode n0 = getNodeNoEx(p0);
 
@@ -1909,7 +1910,10 @@ void Map::transformLiquids(std::map<v3s16, MapBlock*> & modified_blocks)
 	}
 	//infostream<<"Map::transformLiquids(): loopcount="<<loopcount<<std::endl;
 	while (must_reflow.size() > 0)
-		m_transforming_liquid.push_back(must_reflow.pop_front());
+	{
+		m_transforming_liquid.push_back(must_reflow.front());
+		must_reflow.pop_front();
+	}
 	updateLighting(lighting_modified_blocks, modified_blocks);
 
 
@@ -2380,8 +2384,8 @@ void ServerMap::finishBlockMake(BlockMakeData *data,
 	*/
 	while(data->transforming_liquid.size() > 0)
 	{
-		v3s16 p = data->transforming_liquid.pop_front();
-		m_transforming_liquid.push_back(p);
+		m_transforming_liquid.push_back(data->transforming_liquid.front());
+		data->transforming_liquid.pop_front();
 	}
 
 	/*
diff --git a/src/util/container.h b/src/util/container.h
index 6d836a4d5..5e9f13d88 100644
--- a/src/util/container.h
+++ b/src/util/container.h
@@ -28,52 +28,53 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #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) != m_map.end())
-			return false;
+		if (m_set.insert(value).second)
+		{
+			m_queue.push(value);
+			return true;
+		}
+		return false;
+	}
 
-		// Add
-		m_map[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 std::list<Value>::iterator i = m_list.begin();
-		Value value = *i;
-		m_map.erase(value);
-		m_list.erase(i);
-		return value;
+		return m_queue.front();
 	}
 
-	u32 size()
+	u32 size() const
 	{
-		return m_map.size();
+		return m_queue.size();
 	}
 
 private:
-	std::map<Value, u8> m_map;
-	std::list<Value> m_list;
+	std::set<Value> m_set;
+	std::queue<Value> m_queue;
 };
 
 #if 1
@@ -84,14 +85,14 @@ public:
 	MutexedMap()
 	{
 	}
-	
+
 	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);
@@ -101,10 +102,10 @@ public:
 
 		if(n == m_values.end())
 			return false;
-		
+
 		if(result != NULL)
 			*result = n->second;
-			
+
 		return true;
 	}
 
@@ -112,13 +113,13 @@ public:
 	{
 		std::list<Value> result;
 		for(typename std::map<Key, Value>::iterator
-				i = m_values.begin();
-				i != m_values.end(); ++i){
+			i = m_values.begin();
+			i != m_values.end(); ++i){
 			result.push_back(i->second);
 		}
 		return result;
 	}
-	
+
 	void clear ()
 	{
 		m_values.clear();
@@ -131,16 +132,16 @@ private:
 #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
@@ -149,7 +150,7 @@ public:
 	MutexedIdGenerator()
 	{
 	}
-	
+
 	// Returns true if found
 	bool getValue(u32 id, T &value)
 	{
@@ -161,7 +162,7 @@ public:
 		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)
@@ -185,7 +186,7 @@ private:
 };
 
 /*
-	FIFO queue (well, actually a FILO also)
+FIFO queue (well, actually a FILO also)
 */
 template<typename T>
 class Queue
@@ -200,7 +201,7 @@ public:
 		m_list.push_back(t);
 		++m_list_size;
 	}
-	
+
 	void push_front(T t)
 	{
 		m_list.push_front(t);
@@ -246,7 +247,7 @@ protected:
 };
 
 /*
-	Thread-safe FIFO queue (well, actually a FILO also)
+Thread-safe FIFO queue (well, actually a FILO also)
 */
 
 template<typename T>
@@ -272,8 +273,8 @@ public:
 	}
 
 	/* this version of pop_front returns a empty element of T on timeout.
-	 * Make sure default constructor of T creates a recognizable "empty" element
-	 */
+	* Make sure default constructor of T creates a recognizable "empty" element
+	*/
 	T pop_frontNoEx(u32 wait_time_max_ms)
 	{
 		if (m_size.Wait(wait_time_max_ms))
@@ -339,8 +340,8 @@ public:
 	}
 
 	/* this version of pop_back returns a empty element of T on timeout.
-	 * Make sure default constructor of T creates a recognizable "empty" element
-	 */
+	* 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))