From f97d1e15699d281911274911f83acbdc07e1f27e Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Fri, 26 Jul 2013 21:06:05 +0200 Subject: Queue optimizations --- mmss/queue.hpp | 33 +++++++++++++++++++-------------- 1 file changed, 19 insertions(+), 14 deletions(-) (limited to 'mmss/queue.hpp') 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 +#include #include -#include namespace MMSS { @@ -40,30 +39,36 @@ template class timeout_queue_t { std::shared_ptr data; uint64_t timeout; - element_t(std::shared_ptr 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 &data0, uint64_t timeout0) : data(data0), timeout(timeout0) {} }; context_t *mmss; - std::priority_queue> queue; + std::list queue; public: timeout_queue_t(context_t *mmss0) : mmss(mmss0) {} - void put(std::shared_ptr data, uint64_t timeout) { - queue.push(element_t(data, timeout)); + void put(const std::shared_ptr &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 get() { - if (queue.empty() || queue.top().timeout > now(mmss)) + if (queue.empty()) + return std::shared_ptr(); + + element_t &el = queue.front(); + + if (el.timeout > now(mmss)) return std::shared_ptr(); - std::shared_ptr ret = queue.top().data; - queue.pop(); + std::shared_ptr 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; -- cgit v1.2.3