YugabyteDB (2.13.0.0-b42, bfc6a6643e7399ac8a0e81d06a3ee6d6571b33ab)

Coverage Report

Created: 2022-03-09 17:30

/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