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