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