summaryrefslogtreecommitdiff
path: root/src/util/container.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/container.h')
-rw-r--r--src/util/container.h99
1 files changed, 50 insertions, 49 deletions
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))