MySQL  8.0.27
Source Code Documentation
bounded_queue.h
Go to the documentation of this file.
1 /* Copyright (c) 2010, 2021, 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"
30 #include "sql/malloc_allocator.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  */
47 template <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:91
bool push(value_type const &x)
Inserts an element in the priority queue.
Definition: priority_queue.h:220
size_type size() const
Returns the number of elements of the priority queue.
Definition: priority_queue.h:316
void update_top()
Assumes that the top element's value has changed and rebuilds the priority queue.
Definition: priority_queue.h:310
size_type capacity() const
Returns the capacity of the internal container.
Definition: priority_queue.h:385
container_type::allocator_type allocator_type
Definition: priority_queue.h:99
value_type const & top() const
Returns a const reference to the top element of the priority queue.
Definition: priority_queue.h:203
bool reserve(size_type n)
Reserves space for array elements.
Definition: priority_queue.h:393
Dialog Client Authentication nullptr
Definition: dialog.cc:352
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:1138
#define DBUG_EXECUTE_IF(keyword, a1)
Definition: my_dbug.h:158
#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