diff options
author | Matthias Schiffer <mschiffer@universe-factory.net> | 2013-07-26 21:06:05 +0200 |
---|---|---|
committer | Matthias Schiffer <mschiffer@universe-factory.net> | 2013-07-26 21:06:05 +0200 |
commit | f97d1e15699d281911274911f83acbdc07e1f27e (patch) | |
tree | 2ee8d7b8db0c2efa9651fbe0993361b3ef474162 /mmss | |
parent | cc1a4b9493e0e6996e4138f65630b66199ee088a (diff) | |
download | gmrf-f97d1e15699d281911274911f83acbdc07e1f27e.tar gmrf-f97d1e15699d281911274911f83acbdc07e1f27e.zip |
Queue optimizations
Diffstat (limited to 'mmss')
-rw-r--r-- | mmss/queue.hpp | 33 |
1 files changed, 19 insertions, 14 deletions
diff --git a/mmss/queue.hpp b/mmss/queue.hpp index 2cdb2a1..1b1d2af 100644 --- a/mmss/queue.hpp +++ b/mmss/queue.hpp @@ -29,9 +29,8 @@ #include "types.hpp" -#include <deque> +#include <list> #include <memory> -#include <queue> namespace MMSS { @@ -40,30 +39,36 @@ template<typename T> class timeout_queue_t { std::shared_ptr<T> data; uint64_t timeout; - element_t(std::shared_ptr<T> data0, uint64_t timeout0) : data(data0), timeout(timeout0) {} - - bool operator<(const element_t &e) const { - return timeout > e.timeout; - } + element_t(const std::shared_ptr<T> &data0, uint64_t timeout0) : data(data0), timeout(timeout0) {} }; context_t *mmss; - std::priority_queue<element_t, std::deque<element_t>> queue; + std::list<element_t> queue; public: timeout_queue_t(context_t *mmss0) : mmss(mmss0) {} - void put(std::shared_ptr<T> data, uint64_t timeout) { - queue.push(element_t(data, timeout)); + void put(const std::shared_ptr<T> &data, uint64_t timeout) { + auto it = queue.begin(), end = queue.end(); + + while (it != end && it->timeout < timeout) + ++it; + + queue.insert(it, element_t(data, timeout)); } std::shared_ptr<T> get() { - if (queue.empty() || queue.top().timeout > now(mmss)) + if (queue.empty()) + return std::shared_ptr<T>(); + + element_t &el = queue.front(); + + if (el.timeout > now(mmss)) return std::shared_ptr<T>(); - std::shared_ptr<T> ret = queue.top().data; - queue.pop(); + std::shared_ptr<T> ret(std::move(el.data)); + queue.pop_front(); return ret; } @@ -71,7 +76,7 @@ public: if (queue.empty()) return -1; - int diff = queue.top().timeout - now(mmss); + int diff = queue.front().timeout - now(mmss); if (diff < 0) return 0; |