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