/Users/deen/code/yugabyte-db/src/yb/util/priority_queue.h
Line | Count | Source |
1 | | // Copyright (c) YugaByte, Inc. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
4 | | // in compliance with the License. You may obtain a copy of the License at |
5 | | // |
6 | | // http://www.apache.org/licenses/LICENSE-2.0 |
7 | | // |
8 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
9 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
10 | | // or implied. See the License for the specific language governing permissions and limitations |
11 | | // under the License. |
12 | | // |
13 | | |
14 | | #ifndef YB_UTIL_PRIORITY_QUEUE_H |
15 | | #define YB_UTIL_PRIORITY_QUEUE_H |
16 | | |
17 | | namespace yb { |
18 | | |
19 | | // Priority queue that supports pop with returning result. |
20 | | // Useful for non copyable but moveable types. |
21 | | // It is max priority queue like std::priority_queue. |
22 | | template <class T, |
23 | | class Container = std::vector<T>, |
24 | | class Compare = std::less<typename Container::value_type>> |
25 | | class PriorityQueue { |
26 | | public: |
27 | | typedef typename Container::const_iterator const_iterator; |
28 | | |
29 | 513 | T Pop() { |
30 | 513 | auto result = std::move(queue_.front()); |
31 | 513 | std::pop_heap(queue_.begin(), queue_.end(), compare_); |
32 | 513 | queue_.pop_back(); |
33 | 513 | return result; |
34 | 513 | } |
35 | | |
36 | 525 | void Push(const T& task) { |
37 | 525 | queue_.push_back(task); |
38 | 525 | std::push_heap(queue_.begin(), queue_.end(), compare_); |
39 | 525 | } |
40 | | |
41 | 8 | void Push(T&& task) { |
42 | 8 | queue_.push_back(std::move(task)); |
43 | 8 | std::push_heap(queue_.begin(), queue_.end(), compare_); |
44 | 8 | } |
45 | | |
46 | | template <class Predicate> |
47 | 3 | void RemoveIf(const Predicate& predicate) { |
48 | 3 | auto end = queue_.end(); |
49 | 3 | auto it = queue_.begin(); |
50 | 23 | while (it < end) { |
51 | 20 | if (predicate(&*it)) { |
52 | 10 | --end; |
53 | 10 | *it = std::move(*end); |
54 | 10 | } else { |
55 | 10 | ++it; |
56 | 10 | } |
57 | 20 | } |
58 | 3 | if (end == queue_.end()) { |
59 | 1 | return; |
60 | 1 | } |
61 | 2 | queue_.erase(end, queue_.end()); |
62 | 2 | std::make_heap(queue_.begin(), queue_.end(), compare_); |
63 | 2 | } priority_queue-test.cc:_ZN2yb13PriorityQueueIiNSt3__16vectorIiNS1_9allocatorIiEEEENS1_4lessIiEEE8RemoveIfIZNS_31PriorityQueueTest_RemoveIf_Test8TestBodyEvE3$_0EEvRKT_ Line | Count | Source | 47 | 1 | void RemoveIf(const Predicate& predicate) { | 48 | 1 | auto end = queue_.end(); | 49 | 1 | auto it = queue_.begin(); | 50 | 11 | while (it < end) { | 51 | 10 | if (predicate(&*it)) { | 52 | 5 | --end; | 53 | 5 | *it = std::move(*end); | 54 | 5 | } else { | 55 | 5 | ++it; | 56 | 5 | } | 57 | 10 | } | 58 | 1 | if (end == queue_.end()) { | 59 | 0 | return; | 60 | 0 | } | 61 | 1 | queue_.erase(end, queue_.end()); | 62 | 1 | std::make_heap(queue_.begin(), queue_.end(), compare_); | 63 | 1 | } |
priority_queue-test.cc:_ZN2yb13PriorityQueueIiNSt3__16vectorIiNS1_9allocatorIiEEEENS1_4lessIiEEE8RemoveIfIZNS_33PriorityQueueTest_RemoveNone_Test8TestBodyEvE3$_1EEvRKT_ Line | Count | Source | 47 | 1 | void RemoveIf(const Predicate& predicate) { | 48 | 1 | auto end = queue_.end(); | 49 | 1 | auto it = queue_.begin(); | 50 | 6 | while (it < end) { | 51 | 5 | if (predicate(&*it)) { | 52 | 0 | --end; | 53 | 0 | *it = std::move(*end); | 54 | 5 | } else { | 55 | 5 | ++it; | 56 | 5 | } | 57 | 5 | } | 58 | 1 | if (end == queue_.end()) { | 59 | 1 | return; | 60 | 1 | } | 61 | 0 | queue_.erase(end, queue_.end()); | 62 | 0 | std::make_heap(queue_.begin(), queue_.end(), compare_); | 63 | 0 | } |
priority_queue-test.cc:_ZN2yb13PriorityQueueIiNSt3__16vectorIiNS1_9allocatorIiEEEENS1_4lessIiEEE8RemoveIfIZNS_32PriorityQueueTest_RemoveAll_Test8TestBodyEvE3$_2EEvRKT_ Line | Count | Source | 47 | 1 | void RemoveIf(const Predicate& predicate) { | 48 | 1 | auto end = queue_.end(); | 49 | 1 | auto it = queue_.begin(); | 50 | 6 | while (it < end) { | 51 | 5 | if (predicate(&*it)) { | 52 | 5 | --end; | 53 | 5 | *it = std::move(*end); | 54 | 0 | } else { | 55 | 0 | ++it; | 56 | 0 | } | 57 | 5 | } | 58 | 1 | if (end == queue_.end()) { | 59 | 0 | return; | 60 | 0 | } | 61 | 1 | queue_.erase(end, queue_.end()); | 62 | 1 | std::make_heap(queue_.begin(), queue_.end(), compare_); | 63 | 1 | } |
|
64 | | |
65 | 1 | void Swap(Container* out) { |
66 | 1 | out->swap(queue_); |
67 | 1 | std::make_heap(queue_.begin(), queue_.end(), compare_); |
68 | 1 | } |
69 | | |
70 | 2.00k | bool empty() const { |
71 | 2.00k | return queue_.empty(); |
72 | 2.00k | } |
73 | | |
74 | | size_t size() const { |
75 | | return queue_.size(); |
76 | | } |
77 | | |
78 | | const T& top() const { |
79 | | DCHECK(!queue_.empty()); |
80 | | return queue_.front(); |
81 | | } |
82 | | |
83 | | const_iterator begin() const { |
84 | | return queue_.begin(); |
85 | | } |
86 | | |
87 | | const_iterator end() const { |
88 | | return queue_.end(); |
89 | | } |
90 | | |
91 | | private: |
92 | | Container queue_; |
93 | | Compare compare_; |
94 | | }; |
95 | | |
96 | | } // namespace yb |
97 | | |
98 | | #endif // YB_UTIL_PRIORITY_QUEUE_H |