MySQL 8.0.30
Source Code Documentation
priority_queue.h
Go to the documentation of this file.
1/* Copyright (c) 2014, 2022, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23#ifndef PRIORITY_QUEUE_INCLUDED
24#define PRIORITY_QUEUE_INCLUDED
25
26/**
27 @file include/priority_queue.h
28*/
29
30#include <assert.h>
31#include <functional>
32#include <new>
33#include <utility>
34#include <vector>
35
36#include "template_utils.h"
37
38#if defined(EXTRA_CODE_FOR_UNIT_TESTING)
39#include <iostream>
40#include <sstream>
41#endif
42
44class PriorityQueueTest;
45} // namespace priority_queue_unittest
46
47template <typename T>
49 public:
50 void operator()(size_t, T *) const {}
51};
52
53/**
54 Implements a priority queue using a vector-based max-heap.
55
56 A priority queue is a container specifically designed such that its first
57 element is always the greatest of the elements it contains, according to
58 some strict weak ordering criterion.
59
60 For object locality, the implementation is vector-based, rather than
61 node-based.
62
63 The priority queue is mutable, which means that the priority of an element
64 can be changed. See increase/decrease/update member functions.
65 The typical use case is to change the value/priority of the root node.
66
67 We provide iterators, which can be used to visit all elements.
68 Iterators do not visit queue elements in priority order.
69 Iterators should not be used to change the priority of elements.
70
71 The underlying container must be
72 constructible from an iterator range, should provide const and
73 non-const random access iterators to access its elements, as well as
74 the following operations:
75 - size()
76 - empty()
77 - push_back()
78 - pop_back()
79 - swap()
80 - clear()
81 - capacity()
82 - reserve()
83 - max_size()
84
85 @tparam T Type of the elements of the priority queue.
86 @tparam Container Type of the underlying container object where elements
87 are stored. Its value_type shall be T.
88 @tparam Less A binary predicate that takes two elements (of type T)
89 and returns a bool. The expression less(a,b), where
90 less is an object of this type and a and b are elements
91 in the container, shall return true if a is considered
92 to go before b in the strict weak ordering the
93 function defines.
94 @tparam Marker A functor, with signature void operator()(size_t, T *),
95 that gets called whenever an element gets a new position
96 in the queue (including initial insert, but excluding
97 removals). The marker can then store the element's
98 position somewhere, for later calls to update() as needed.
99 */
100template <typename T, typename Container = std::vector<T>,
101 typename Less = std::less<typename Container::value_type>,
102 typename Marker = NoopMarker<T>>
103class Priority_queue : public Less {
104 public:
105 typedef Container container_type;
106 typedef Less less_type;
108 typedef typename container_type::size_type size_type;
109 typedef typename container_type::iterator iterator;
110 typedef typename container_type::const_iterator const_iterator;
111 typedef typename container_type::allocator_type allocator_type;
112
114
115 private:
116 // Deriving from Less allows empty base-class optimization in some cases.
117 typedef Less Base;
118
119 // Returns the index of the parent node of node i.
121 assert(i != 0);
122 return (--i) >> 1; // (i - 1) / 2
123 }
124
125 // Returns the index of the left child of node i.
127 return (i << 1) | 1; // 2 * i + 1
128 }
129
130 // Returns the index of the right child of node i.
132 return (++i) << 1; // 2 * i + 2
133 }
134
136 assert(i < size());
137 size_type largest = i;
138
139 do {
140 i = largest;
141 size_type l = left(i);
142 size_type r = right(i);
143
144 if (l < last && Base::operator()(m_container[i], m_container[l])) {
145 largest = l;
146 }
147
148 if (r < last && Base::operator()(m_container[largest], m_container[r])) {
149 largest = r;
150 }
151
152 if (largest != i) {
153 std::swap(m_container[i], m_container[largest]);
154 m_marker(i, &m_container[i]);
155 m_marker(largest, &m_container[largest]);
156 }
157 } while (largest != i);
158 }
159
160 void heapify(size_type i) { heapify(i, m_container.size()); }
161
163 assert(i < size());
164 while (i > 0 && !Base::operator()(m_container[i], m_container[parent(i)])) {
165 size_t parent_idx = parent(i);
166 std::swap(m_container[parent_idx], m_container[i]);
167 m_marker(parent_idx, &m_container[parent_idx]);
168 m_marker(i, &m_container[i]);
169 i = parent(i);
170 }
171 }
172
173 // Sets the value of element i, and rebuilds the priority queue.
175 m_container[i] = x;
176 heapify(i);
177 }
178
179 // Sets the value of element i, and rebuilds the priority queue.
181 m_container[i] = x;
183 }
184
185 public:
186 /// Constructs an empty priority queue.
187 Priority_queue(Less const &less = Less(),
188 const allocator_type &alloc = allocator_type(),
189 const Marker &marker = Marker())
190 : Base(less), m_container(alloc), m_marker(marker) {}
191
192 /// Constructs a heap of the objects between first and beyond.
193 template <typename Input_iterator>
194 Priority_queue(Input_iterator first, Input_iterator beyond,
195 Less const &less = Less(),
196 const allocator_type &alloc = allocator_type(),
197 const Marker &marker = Marker())
198 : Base(less), m_container(first, beyond, alloc), m_marker(marker) {
199 build_heap();
200 }
201
202 /// Constructs a heap based on input argument.
205 build_heap();
206 }
207
208 /**
209 Constructs a heap based on container contents.
210 Can also be used when many elements have changed.
211 */
212 void build_heap() {
213 if (m_container.size() > 1) {
214 for (size_type i = parent(m_container.size() - 1); i > 0; --i) {
215 heapify(i);
216 }
217 heapify(0);
218 }
219 }
220
221 /// Returns a const reference to the top element of the priority queue.
222 value_type const &top() const {
223 assert(!empty());
224 return m_container[0];
225 }
226
227 /// Returns a reference to the top element of the priority queue.
229 assert(!empty());
230 return m_container[0];
231 }
232
233 /**
234 Inserts an element in the priority queue.
235
236 @param x value to be pushed.
237 @retval true if out-of-memory, false otherwise.
238 */
239 bool push(value_type const &x) {
240 try {
241 m_container.push_back(x);
242 } catch (std::bad_alloc const &) {
243 return true;
244 }
245
246 m_marker(m_container.size() - 1, &m_container.back());
247 reverse_heapify(m_container.size() - 1);
248 return false;
249 }
250
251 /// Pops the top-most element in the priority queue.
252 void pop() { remove(0); }
253
254 /// Removes the element at position i from the priority queue.
256 assert(i < size());
257
258 if (i == m_container.size() - 1) {
259 m_container.pop_back();
260 return;
261 }
262
263 m_container[i] = m_container[m_container.size() - 1];
264 m_marker(i, &m_container[i]);
265 m_container.pop_back();
266 update(i);
267 }
268
269 /**
270 Decreases the priority of the element at position i, where the
271 new priority is x.
272 */
273 void decrease(size_type i, value_type const &x) {
274 assert(i < size());
275 assert(!Base::operator()(m_container[i], x));
276 decrease_key(i, x);
277 }
278
279 /**
280 Increases the priority of the element at position i, where the
281 new priority is x.
282 */
283 void increase(size_type i, value_type const &x) {
284 assert(i < size());
285 assert(!Base::operator()(x, m_container[i]));
286 increase_key(i, x);
287 }
288
289 /**
290 Changes the priority of the element at position i, where the
291 new priority is x.
292 */
293 void update(size_type i, value_type const &x) {
294 assert(i < size());
295 if (Base::operator()(x, m_container[i])) {
296 decrease_key(i, x);
297 } else {
298 increase_key(i, x);
299 }
300 }
301
302 /**
303 Assumes that the i-th element's value has increased
304 and rebuilds the priority queue.
305 */
307
308 /**
309 Assumes that the i-th element's value has decreased
310 and rebuilds the priority queue.
311 */
312 void decrease(size_type i) { heapify(i); }
313
314 /**
315 Assumes that the i-th element's value has changed
316 and rebuilds the priority queue.
317 */
319 assert(i < size());
320 if (i == 0 || Base::operator()(m_container[i], m_container[parent(i)])) {
321 heapify(i);
322 } else {
324 }
325 }
326
327 /**
328 Assumes that the top element's value has changed
329 and rebuilds the priority queue.
330 */
331 void update_top() {
332 assert(!empty());
333 heapify(0);
334 }
335
336 /// Returns the number of elements of the priority queue
337 size_type size() const { return m_container.size(); }
338
339 /// Returns true if the priority queue is empty
340 bool empty() const { return m_container.empty(); }
341
342 /// Returns a const reference to the i-th element in the underlying container.
344 assert(i < size());
345 return m_container[i];
346 }
347
348 /// Returns a reference to the i-th element in the underlying container.
350 assert(i < size());
351 return m_container[i];
352 }
353
354 /// Returns a const iterator to the first element of the underlying container.
355 const_iterator begin() const { return m_container.begin(); }
356
357 /// Returns a const iterator to the end element of the underlying container.
358 const_iterator end() const { return m_container.end(); }
359
360 /// Returns an iterator to the first element of the underlying container.
361 iterator begin() { return m_container.begin(); }
362
363 /// Returns an iterator to the end element of the underlying container.
364 iterator end() { return m_container.end(); }
365
366 /// Swaps the contents of two priority queues.
367 void swap(Priority_queue &other) {
368 std::swap(static_cast<Base &>(*this), static_cast<Base &>(other));
369 m_container.swap(other.m_container);
370 }
371
372 /// Returns true if the priority queue has the heap property.
373 bool is_valid() const {
374 for (size_type i = 1; i < m_container.size(); ++i) {
375 if (Base::operator()(m_container[parent(i)], m_container[i])) {
376 return false;
377 }
378 }
379 return true;
380 }
381
382 /**
383 Sorts the elements of the priority queue according to the strict
384 partial ordering defined by the object of type Less passed to
385 the priority queue.
386
387 The heap property of the priority queue is invalidated by this
388 operation.
389 */
390 void sort() {
391 if (!m_container.empty()) {
392 for (size_type i = m_container.size() - 1; i > 0; --i) {
394 m_marker(i, &m_container[i]);
395 m_marker(0, &m_container[0]);
396 heapify(0, i);
397 }
398 }
399 }
400
401 /// Clears the priority queue.
402 void clear() { m_container.clear(); }
403
404 /// Clears the priority queue, but deletes all elements first.
406
407 /// Returns the capacity of the internal container.
408 size_type capacity() const { return m_container.capacity(); }
409
410 /**
411 Reserves space for array elements.
412
413 @param n number of elements.
414 @retval true if out-of-memory, false otherwise.
415 */
416 [[nodiscard]] bool reserve(size_type n) {
417 assert(n <= m_container.max_size());
418 try {
419 m_container.reserve(n);
420 } catch (std::bad_alloc const &) {
421 return true;
422 }
423 return false;
424 }
425
426 private:
428 Marker m_marker;
429};
430
431#if defined(EXTRA_CODE_FOR_UNIT_TESTING)
432template <class T, class Container, class Less, class Marker>
433inline std::ostream &operator<<(
434 std::ostream &os, Priority_queue<T, Container, Less, Marker> const &pq) {
435 typedef
437
438 for (size_type i = 0; i < pq.size(); i++) {
439 os << pq[i] << " " << std::flush;
440 }
441
442 return os;
443}
444
445template <class T, class Container, class Less, class Marker>
446inline std::stringstream &operator<<(
447 std::stringstream &ss,
449 typedef
451
452 for (size_type i = 0; i < pq.size(); i++) {
453 ss << pq[i] << " ";
454 }
455
456 return ss;
457}
458#endif // EXTRA_CODE_FOR_UNIT_TESTING
459
460#endif // PRIORITY_QUEUE_INCLUDED
Definition: priority_queue.h:48
void operator()(size_t, T *) const
Definition: priority_queue.h:50
Implements a priority queue using a vector-based max-heap.
Definition: priority_queue.h:103
value_type & operator[](size_type i)
Returns a reference to the i-th element in the underlying container.
Definition: priority_queue.h:349
static size_type parent(size_type i)
Definition: priority_queue.h:120
Priority_queue(Input_iterator first, Input_iterator beyond, Less const &less=Less(), const allocator_type &alloc=allocator_type(), const Marker &marker=Marker())
Constructs a heap of the objects between first and beyond.
Definition: priority_queue.h:194
void increase_key(size_type i, value_type const &x)
Definition: priority_queue.h:180
value_type & top()
Returns a reference to the top element of the priority queue.
Definition: priority_queue.h:228
size_type capacity() const
Returns the capacity of the internal container.
Definition: priority_queue.h:408
void swap(Priority_queue &other)
Swaps the contents of two priority queues.
Definition: priority_queue.h:367
void clear()
Clears the priority queue.
Definition: priority_queue.h:402
void sort()
Sorts the elements of the priority queue according to the strict partial ordering defined by the obje...
Definition: priority_queue.h:390
container_type::allocator_type allocator_type
Definition: priority_queue.h:111
Marker m_marker
Definition: priority_queue.h:428
void decrease(size_type i, value_type const &x)
Decreases the priority of the element at position i, where the new priority is x.
Definition: priority_queue.h:273
void update(size_type i, value_type const &x)
Changes the priority of the element at position i, where the new priority is x.
Definition: priority_queue.h:293
static size_type right(size_type i)
Definition: priority_queue.h:131
container_type::iterator iterator
Definition: priority_queue.h:109
void heapify(size_type i)
Definition: priority_queue.h:160
friend class priority_queue_unittest::PriorityQueueTest
Definition: priority_queue.h:113
void update(size_type i)
Assumes that the i-th element's value has changed and rebuilds the priority queue.
Definition: priority_queue.h:318
void delete_elements()
Clears the priority queue, but deletes all elements first.
Definition: priority_queue.h:405
container_type::const_iterator const_iterator
Definition: priority_queue.h:110
void reverse_heapify(size_type i)
Definition: priority_queue.h:162
bool is_valid() const
Returns true if the priority queue has the heap property.
Definition: priority_queue.h:373
container_type::value_type value_type
Definition: priority_queue.h:107
static size_type left(size_type i)
Definition: priority_queue.h:126
Less less_type
Definition: priority_queue.h:106
void increase(size_type i, value_type const &x)
Increases the priority of the element at position i, where the new priority is x.
Definition: priority_queue.h:283
container_type::size_type size_type
Definition: priority_queue.h:108
iterator begin()
Returns an iterator to the first element of the underlying container.
Definition: priority_queue.h:361
Priority_queue(Less const &less=Less(), const allocator_type &alloc=allocator_type(), const Marker &marker=Marker())
Constructs an empty priority queue.
Definition: priority_queue.h:187
value_type const & top() const
Returns a const reference to the top element of the priority queue.
Definition: priority_queue.h:222
iterator end()
Returns an iterator to the end element of the underlying container.
Definition: priority_queue.h:364
value_type const & operator[](size_type i) const
Returns a const reference to the i-th element in the underlying container.
Definition: priority_queue.h:343
void decrease(size_type i)
Assumes that the i-th element's value has decreased and rebuilds the priority queue.
Definition: priority_queue.h:312
container_type m_container
Definition: priority_queue.h:427
void increase(size_type i)
Assumes that the i-th element's value has increased and rebuilds the priority queue.
Definition: priority_queue.h:306
Container container_type
Definition: priority_queue.h:105
const_iterator end() const
Returns a const iterator to the end element of the underlying container.
Definition: priority_queue.h:358
void decrease_key(size_type i, value_type const &x)
Definition: priority_queue.h:174
void remove(size_type i)
Removes the element at position i from the priority queue.
Definition: priority_queue.h:255
bool reserve(size_type n)
Reserves space for array elements.
Definition: priority_queue.h:416
bool empty() const
Returns true if the priority queue is empty.
Definition: priority_queue.h:340
void pop()
Pops the top-most element in the priority queue.
Definition: priority_queue.h:252
size_type size() const
Returns the number of elements of the priority queue.
Definition: priority_queue.h:337
void update_top()
Assumes that the top element's value has changed and rebuilds the priority queue.
Definition: priority_queue.h:331
void assign(const container_type &container)
Constructs a heap based on input argument.
Definition: priority_queue.h:203
void heapify(size_type i, size_type last)
Definition: priority_queue.h:135
bool push(value_type const &x)
Inserts an element in the priority queue.
Definition: priority_queue.h:239
void build_heap()
Constructs a heap based on container contents.
Definition: priority_queue.h:212
Less Base
Definition: priority_queue.h:117
const_iterator begin() const
Returns a const iterator to the first element of the underlying container.
Definition: priority_queue.h:355
ostream & operator<<(ostream &os, const Datetime &)
Definition: logger.cc:34
uint16_t value_type
Definition: vt100.h:182
Definition: atomics_array.h:38
Definition: priority_queue.h:43
static mysql_service_status_t flush(reference_caching_cache cache) noexcept
Definition: component.cc:121
const mysql_service_registry_t * r
Definition: pfs_example_plugin_employee.cc:85
static void swap(String &a, String &b) noexcept
Definition: sql_string.h:611
void delete_container_pointers(Container_type &container)
Clears a container, but deletes all objects that the elements point to first.
Definition: template_utils.h:43
int n
Definition: xcom_base.cc:505