MySQL 8.4.3
Source Code Documentation
bounded_queue.h
Go to the documentation of this file.
1/* Copyright (c) 2010, 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 BOUNDED_QUEUE_INCLUDED
25#define BOUNDED_QUEUE_INCLUDED
26
27#include "my_base.h"
28#include "my_sys.h"
29#include "mysys_err.h"
30#include "priority_queue.h"
32
33/**
34 A priority queue with a fixed, limited size.
35
36 This is a wrapper on top of Priority_queue.
37 It keeps the top-N elements which are inserted.
38
39 Elements of type Element_type are pushed into the queue.
40 For each element, we call a user-supplied Key_generator::make_sortkey(),
41 to generate a key of type Key_type for the element.
42 Instances of Key_type are compared with the user-supplied Key_compare.
43
44 Pointers to the top-N elements are stored in the sort_keys array given
45 to the init() function below. To access elements in sorted order,
46 sort the array and access it sequentially.
47 */
48template <typename Element_type, typename Key_type, typename Key_generator,
49 typename Key_compare = std::less<Key_type>>
51 public:
52 typedef Priority_queue<
53 Key_type, std::vector<Key_type, Malloc_allocator<Key_type>>, Key_compare>
55
57
59 size_t element_size = sizeof(Element_type),
61 : m_queue(Key_compare(), alloc),
64 m_element_size(element_size) {}
65
66 /**
67 Initialize the queue.
68
69 @param max_elements The size of the queue.
70 @param sort_param Sort parameters. We call sort_param->make_sortkey()
71 to generate keys for elements.
72 @param[in,out] sort_keys Array of keys to sort.
73 Must be initialized by caller.
74 Will be filled with pointers to the top-N elements.
75
76 @retval false OK, true Could not allocate memory.
77
78 We do *not* take ownership of any of the input pointer arguments.
79 */
80 bool init(ha_rows max_elements, Key_generator *sort_param,
81 Key_type *sort_keys) {
82 m_sort_keys = sort_keys;
83 m_sort_param = sort_param;
84 DBUG_EXECUTE_IF("bounded_queue_init_fail",
86 return true;);
87
88 // We allocate space for one extra element, for replace when queue is full.
89 if (m_queue.reserve(max_elements + 1)) return true;
90 // We cannot have packed keys in the queue.
91 m_queue.m_compare_length = sort_param->max_compare_length();
92 // We can have variable length keys though.
93 if (sort_param->using_varlen_keys()) m_queue.m_param = sort_param;
94 return false;
95 }
96
97 /**
98 Pushes an element on the queue.
99 If the queue is already full, we discard one element.
100 Calls m_sort_param::make_sortkey() to generate a key for the element.
101
102 @param opaque Parameter to send on to make_sortkey().
103
104 @retval false OK, true error.
105 */
106 template <class Opaque>
107 [[nodiscard]] bool push(const Opaque &opaque) {
108 /*
109 Add one extra byte to each key, so that sort-key generating functions
110 won't be returning out-of-space. Since we know there's always room
111 given a "m_element_size"-sized buffer even in the worst case (by
112 definition), we could in principle make a special mode flag in
113 Sort_param::make_sortkey() instead for the case of fixed-length records,
114 but this is much simpler.
115 */
116 assert(m_element_size < 0xFFFFFFFF);
117 const uint element_size = m_element_size + 1;
118
119 if (m_queue.size() == m_queue.capacity()) {
120 const Key_type &pq_top = m_queue.top();
121 const uint rec_sz =
122 m_sort_param->make_sortkey(pq_top, element_size, opaque);
123 // UINT_MAX means error, but we do not want to add a dependency
124 // on class THD here, as in current_thd->is_error().
125 if (rec_sz == UINT_MAX) return true;
126 assert(rec_sz <= m_element_size);
128 return false;
129 } else {
130 const uint rec_sz = m_sort_param->make_sortkey(
131 m_sort_keys[m_queue.size()], element_size, opaque);
132 // UINT_MAX means error, but we do not want to add a dependency
133 // on class THD here, as in current_thd->is_error().
134 if (rec_sz == UINT_MAX) return true;
135 assert(rec_sz <= m_element_size);
137 }
138 }
139
140 /**
141 The number of elements in the queue.
142 */
143 size_t num_elements() const { return m_queue.size(); }
144
145 private:
147 Key_type *m_sort_keys;
148 Key_generator *m_sort_param;
150};
151
152#endif // BOUNDED_QUEUE_INCLUDED
Kerberos Client Authentication nullptr
Definition: auth_kerberos_client_plugin.cc:251
A priority queue with a fixed, limited size.
Definition: bounded_queue.h:50
Key_generator * m_sort_param
Definition: bounded_queue.h:148
Queue_type m_queue
Definition: bounded_queue.h:146
Queue_type::allocator_type allocator_type
Definition: bounded_queue.h:56
size_t num_elements() const
The number of elements in the queue.
Definition: bounded_queue.h:143
Priority_queue< Key_type, std::vector< Key_type, Malloc_allocator< Key_type > >, Key_compare > Queue_type
Definition: bounded_queue.h:54
Key_type * m_sort_keys
Definition: bounded_queue.h:147
bool push(const Opaque &opaque)
Pushes an element on the queue.
Definition: bounded_queue.h:107
size_t m_element_size
Definition: bounded_queue.h:149
Bounded_queue(size_t element_size=sizeof(Element_type), const allocator_type &alloc=allocator_type(PSI_NOT_INSTRUMENTED))
Definition: bounded_queue.h:58
bool init(ha_rows max_elements, Key_generator *sort_param, Key_type *sort_keys)
Initialize the queue.
Definition: bounded_queue.h:80
Implements a priority queue using a vector-based max-heap.
Definition: priority_queue.h:104
size_type capacity() const
Returns the capacity of the internal container.
Definition: priority_queue.h:409
container_type::allocator_type allocator_type
Definition: priority_queue.h:112
value_type const & top() const
Returns a const reference to the top element of the priority queue.
Definition: priority_queue.h:223
bool reserve(size_type n)
Reserves space for array elements.
Definition: priority_queue.h:417
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
bool push(value_type const &x)
Inserts an element in the priority queue.
Definition: priority_queue.h:240
void my_error(int nr, myf MyFlags,...)
Fill in and print a previously registered error message.
Definition: my_error.cc:216
#define ME_FATALERROR
Definition: my_sys.h:157
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1141
#define DBUG_EXECUTE_IF(keyword, a1)
Definition: my_dbug.h:171
#define MYF(v)
Definition: my_inttypes.h:97
Common header for many mysys elements.
#define EE_OUTOFMEMORY
Definition: mysys_err.h:50
#define PSI_NOT_INSTRUMENTED
Definition: validate_password_imp.cc:42