MySQL 8.0.30
Source Code Documentation
bounded_queue.h
Go to the documentation of this file.
1/* Copyright (c) 2010, 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 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 template <class Opaque>
104 void push(const Opaque &opaque) {
105 /*
106 Add one extra byte to each key, so that sort-key generating functions
107 won't be returning out-of-space. Since we know there's always room
108 given a "m_element_size"-sized buffer even in the worst case (by
109 definition), we could in principle make a special mode flag in
110 Sort_param::make_sortkey() instead for the case of fixed-length records,
111 but this is much simpler.
112 */
113 assert(m_element_size < 0xFFFFFFFF);
114 const uint element_size = m_element_size + 1;
115
116 if (m_queue.size() == m_queue.capacity()) {
117 const Key_type &pq_top = m_queue.top();
118 [[maybe_unused]] const uint rec_sz =
119 m_sort_param->make_sortkey(pq_top, element_size, opaque);
120 // UINT_MAX means error, but we do not want to add a dependency
121 // on class THD here, as in current_thd->is_error().
122 assert(rec_sz <= m_element_size || rec_sz == UINT_MAX);
124 } else {
125 [[maybe_unused]] const uint rec_sz = m_sort_param->make_sortkey(
126 m_sort_keys[m_queue.size()], element_size, opaque);
127 // UINT_MAX means error, but we do not want to add a dependency
128 // on class THD here, as in current_thd->is_error().
129 assert(rec_sz <= m_element_size || rec_sz == UINT_MAX);
131 }
132 }
133
134 /**
135 The number of elements in the queue.
136 */
137 size_t num_elements() const { return m_queue.size(); }
138
139 private:
141 Key_type *m_sort_keys;
142 Key_generator *m_sort_param;
144};
145
146#endif // BOUNDED_QUEUE_INCLUDED
A priority queue with a fixed, limited size.
Definition: bounded_queue.h:49
Key_generator * m_sort_param
Definition: bounded_queue.h:142
Queue_type m_queue
Definition: bounded_queue.h:140
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:137
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:141
void push(const Opaque &opaque)
Pushes an element on the queue.
Definition: bounded_queue.h:104
size_t m_element_size
Definition: bounded_queue.h:143
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
Fido Client Authentication nullptr
Definition: fido_client_plugin.cc:221
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:151
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1139
#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
unsigned int uint
Definition: uca-dump.cc:29
#define PSI_NOT_INSTRUMENTED
Definition: validate_password_imp.cc:39