diff options
Diffstat (limited to 'src/common/multi_level_queue.h')
| -rw-r--r-- | src/common/multi_level_queue.h | 14 |
1 files changed, 10 insertions, 4 deletions
diff --git a/src/common/multi_level_queue.h b/src/common/multi_level_queue.h index 68b35ffaa..2b61b91e0 100644 --- a/src/common/multi_level_queue.h +++ b/src/common/multi_level_queue.h | |||
| @@ -7,12 +7,21 @@ | |||
| 7 | #include <array> | 7 | #include <array> |
| 8 | #include <iterator> | 8 | #include <iterator> |
| 9 | #include <list> | 9 | #include <list> |
| 10 | #include <utility> | ||
| 10 | 11 | ||
| 11 | #include "common/bit_util.h" | 12 | #include "common/bit_util.h" |
| 12 | #include "common/common_types.h" | 13 | #include "common/common_types.h" |
| 13 | 14 | ||
| 14 | namespace Common { | 15 | namespace Common { |
| 15 | 16 | ||
| 17 | /** | ||
| 18 | * A MultiLevelQueue is a type of priority queue which has the following characteristics: | ||
| 19 | * - iteratable through each of its elements. | ||
| 20 | * - back can be obtained. | ||
| 21 | * - O(1) add, lookup (both front and back) | ||
| 22 | * - discrete priorities and a max of 64 priorities (limited domain) | ||
| 23 | * This type of priority queue is normaly used for managing threads within an scheduler | ||
| 24 | */ | ||
| 16 | template <typename T, std::size_t Depth> | 25 | template <typename T, std::size_t Depth> |
| 17 | class MultiLevelQueue { | 26 | class MultiLevelQueue { |
| 18 | public: | 27 | public: |
| @@ -37,9 +46,7 @@ public: | |||
| 37 | friend bool operator==(const iterator_impl& lhs, const iterator_impl& rhs) { | 46 | friend bool operator==(const iterator_impl& lhs, const iterator_impl& rhs) { |
| 38 | if (lhs.IsEnd() && rhs.IsEnd()) | 47 | if (lhs.IsEnd() && rhs.IsEnd()) |
| 39 | return true; | 48 | return true; |
| 40 | if (lhs.current_priority == rhs.current_priority) | 49 | return std::tie(lhs.current_priority, lhs.it) == std::tie(rhs.current_priority, rhs.it); |
| 41 | return lhs.it == rhs.it; | ||
| 42 | return false; | ||
| 43 | } | 50 | } |
| 44 | 51 | ||
| 45 | friend bool operator!=(const iterator_impl& lhs, const iterator_impl& rhs) { | 52 | friend bool operator!=(const iterator_impl& lhs, const iterator_impl& rhs) { |
| @@ -301,7 +308,6 @@ private: | |||
| 301 | using const_list_iterator = typename std::list<T>::const_iterator; | 308 | using const_list_iterator = typename std::list<T>::const_iterator; |
| 302 | 309 | ||
| 303 | static void ListShiftForward(std::list<T>& list, const std::size_t shift = 1) { | 310 | static void ListShiftForward(std::list<T>& list, const std::size_t shift = 1) { |
| 304 | // NOTE: May want to consider making this an assertion or something | ||
| 305 | if (shift >= list.size()) { | 311 | if (shift >= list.size()) { |
| 306 | return; | 312 | return; |
| 307 | } | 313 | } |