1 /* Copyright (c) 2010, 2011, Oracle and/or its affiliates. All rights reserved.
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 Street, Fifth Floor, Boston, MA 02110-1301, USA */
22
23 #ifndef BOUNDED_QUEUE_INCLUDED
24 #define BOUNDED_QUEUE_INCLUDED
25
26 #include <string.h>
27 #include "my_global.h"
28 #include "my_base.h"
29 #include "my_sys.h"
30 #include "queues.h"
31
32 class Sort_param;
33
34 /**
35 A priority queue with a fixed, limited size.
36
37 This is a wrapper on top of QUEUE and the queue_xxx() functions.
38 It keeps the top-N elements which are inserted.
39
40 Elements of type Element_type are pushed into the queue.
41 For each element, we call a user-supplied keymaker_function,
42 to generate a key of type Key_type for the element.
43 Instances of Key_type are compared with the user-supplied compare_function.
44
45 The underlying QUEUE implementation needs one extra element for replacing
46 the lowest/highest element when pushing into a full queue.
47 */
48 template<typename Element_type, typename Key_type>
49 class Bounded_queue
50 {
51 public:
Bounded_queue()52 Bounded_queue()
53 {
54 memset(&m_queue, 0, sizeof(m_queue));
55 }
56
~Bounded_queue()57 ~Bounded_queue()
58 {
59 delete_queue(&m_queue);
60 }
61
62 /**
63 Function for making sort-key from input data.
64 @param param Sort parameters.
65 @param to Where to put the key.
66 @param from The input data.
67 */
68 typedef void (*keymaker_function)(Sort_param *param,
69 Key_type *to,
70 Element_type *from);
71
72 /**
73 Function for comparing two keys.
74 @param n Pointer to number of bytes to compare.
75 @param a First key.
76 @param b Second key.
77 @retval -1, 0, or 1 depending on whether the left argument is
78 less than, equal to, or greater than the right argument.
79 */
80 typedef int (*compare_function)(size_t *n, Key_type **a, Key_type **b);
81
82 /**
83 Initialize the queue.
84
85 @param max_elements The size of the queue.
86 @param max_at_top Set to true if you want biggest element on top.
87 false: We keep the n largest elements.
88 pop() will return the smallest key in the result set.
89 true: We keep the n smallest elements.
90 pop() will return the largest key in the result set.
91 @param compare Compare function for elements, takes 3 arguments.
92 If NULL, we use get_ptr_compare(compare_length).
93 @param compare_length Length of the data (i.e. the keys) used for sorting.
94 @param keymaker Function which generates keys for elements.
95 @param sort_param Sort parameters.
96 @param sort_keys Array of pointers to keys to sort.
97
98 @retval 0 OK, 1 Could not allocate memory.
99
100 We do *not* take ownership of any of the input pointer arguments.
101 */
102 int init(ha_rows max_elements, bool max_at_top,
103 compare_function compare, size_t compare_length,
104 keymaker_function keymaker, Sort_param *sort_param,
105 Key_type **sort_keys);
106
107 /**
108 Pushes an element on the queue.
109 If the queue is already full, we discard one element.
110 Calls keymaker_function to generate a key for the element.
111
112 @param element The element to be pushed.
113 */
114 void push(Element_type *element);
115
116 /**
117 Removes the top element from the queue.
118
119 @retval Pointer to the (key of the) removed element.
120
121 @note This function is for unit testing, where we push elements into to the
122 queue, and test that the appropriate keys are retained.
123 Interleaving of push() and pop() operations has not been tested.
124 */
pop()125 Key_type **pop()
126 {
127 // Don't return the extra element to the client code.
128 if (queue_is_full((&m_queue)))
129 queue_remove(&m_queue, 0);
130 DBUG_ASSERT(m_queue.elements > 0);
131 if (m_queue.elements == 0)
132 return NULL;
133 return reinterpret_cast<Key_type**>(queue_remove(&m_queue, 0));
134 }
135
136 /**
137 The number of elements in the queue.
138 */
num_elements()139 uint num_elements() const { return m_queue.elements; }
140
141 /**
142 Is the queue initialized?
143 */
is_initialized()144 bool is_initialized() const { return m_queue.max_elements > 0; }
145
146 private:
147 Key_type **m_sort_keys;
148 size_t m_compare_length;
149 keymaker_function m_keymaker;
150 Sort_param *m_sort_param;
151 st_queue m_queue;
152 };
153
154
155 template<typename Element_type, typename Key_type>
init(ha_rows max_elements,bool max_at_top,compare_function compare,size_t compare_length,keymaker_function keymaker,Sort_param * sort_param,Key_type ** sort_keys)156 int Bounded_queue<Element_type, Key_type>::init(ha_rows max_elements,
157 bool max_at_top,
158 compare_function compare,
159 size_t compare_length,
160 keymaker_function keymaker,
161 Sort_param *sort_param,
162 Key_type **sort_keys)
163 {
164 DBUG_ASSERT(sort_keys != NULL);
165
166 m_sort_keys= sort_keys;
167 m_compare_length= compare_length;
168 m_keymaker= keymaker;
169 m_sort_param= sort_param;
170 // init_queue() takes an uint, and also does (max_elements + 1)
171 if (max_elements >= (UINT_MAX - 1))
172 return 1;
173 if (compare == NULL)
174 compare=
175 reinterpret_cast<compare_function>(get_ptr_compare(compare_length));
176
177 DBUG_EXECUTE_IF("bounded_queue_init_fail",
178 DBUG_SET("+d,simulate_out_of_memory"););
179
180 // We allocate space for one extra element, for replace when queue is full.
181 return init_queue(&m_queue, (uint) max_elements + 1,
182 0, max_at_top,
183 reinterpret_cast<queue_compare>(compare),
184 &m_compare_length);
185 }
186
187
188 template<typename Element_type, typename Key_type>
push(Element_type * element)189 void Bounded_queue<Element_type, Key_type>::push(Element_type *element)
190 {
191 DBUG_ASSERT(is_initialized());
192 if (queue_is_full((&m_queue)))
193 {
194 // Replace top element with new key, and re-order the queue.
195 Key_type **pq_top= reinterpret_cast<Key_type **>(queue_top(&m_queue));
196 (*m_keymaker)(m_sort_param, *pq_top, element);
197 queue_replaced(&m_queue);
198 } else {
199 // Insert new key into the queue.
200 (*m_keymaker)(m_sort_param, m_sort_keys[m_queue.elements], element);
201 queue_insert(&m_queue,
202 reinterpret_cast<uchar*>(&m_sort_keys[m_queue.elements]));
203 }
204 }
205
206 #endif // BOUNDED_QUEUE_INCLUDED
207