1 /* Copyright (C) 2010 Monty Program Ab
2 All Rights reserved
3
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions are met:
6 * Redistributions of source code must retain the above copyright
7 notice, this list of conditions and the following disclaimer.
8 * Redistributions in binary form must reproduce the following disclaimer
9 in the documentation and/or other materials provided with the
10 distribution.
11
12 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
13 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
14 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
15 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
16 <COPYRIGHT HOLDER> BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
17 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
18 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
19 USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
20 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
21 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
22 OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
23 SUCH DAMAGE.
24 */
25
26 /*
27 This code originates from the Unireg project.
28
29 Code for generell handling of priority Queues.
30 Implementation of queues from "Algorithms in C" by Robert Sedgewick.
31
32 The queue can optionally store the position in queue in the element
33 that is in the queue. This allows one to remove any element from the queue
34 in O(1) time.
35
36 Optimisation of _downheap() and queue_fix() is inspired by code done
37 by Mikael Ronström, based on an optimisation of _downheap from
38 Exercise 7.51 in "Data Structures & Algorithms in C++" by Mark Allen
39 Weiss, Second Edition.
40 */
41
42 #include "mysys_priv.h"
43 #include "mysys_err.h"
44 #include <queues.h>
45
46
47 /*
48 Init queue
49
50 SYNOPSIS
51 init_queue()
52 queue Queue to initialise
53 max_elements Max elements that will be put in queue
54 offset_to_key Offset to key in element stored in queue
55 Used when sending pointers to compare function
56 max_at_top Set to 1 if you want biggest element on top.
57 compare Compare function for elements, takes 3 arguments.
58 first_cmp_arg First argument to compare function
59 offset_to_queue_pos If <> 0, then offset+1 in element to store position
60 in queue (for fast delete of element in queue)
61 auto_extent When the queue is full and there is insert operation
62 extend the queue.
63
64 NOTES
65 Will allocate max_element pointers for queue array
66
67 RETURN
68 0 ok
69 1 Could not allocate memory
70 */
71
init_queue(QUEUE * queue,uint max_elements,uint offset_to_key,my_bool max_at_top,int (* compare)(void *,uchar *,uchar *),void * first_cmp_arg,uint offset_to_queue_pos,uint auto_extent)72 int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
73 my_bool max_at_top, int (*compare) (void *, uchar *, uchar *),
74 void *first_cmp_arg, uint offset_to_queue_pos,
75 uint auto_extent)
76 {
77 DBUG_ENTER("init_queue");
78 if ((queue->root= (uchar **) my_malloc(key_memory_QUEUE,
79 (max_elements + 1) * sizeof(void*),
80 MYF(MY_WME))) == 0)
81 DBUG_RETURN(1);
82 queue->elements= 0;
83 queue->compare= compare;
84 queue->first_cmp_arg= first_cmp_arg;
85 queue->max_elements= max_elements;
86 queue->offset_to_key= offset_to_key;
87 queue->offset_to_queue_pos= offset_to_queue_pos;
88 queue->auto_extent= auto_extent;
89 queue_set_max_at_top(queue, max_at_top);
90 DBUG_RETURN(0);
91 }
92
93
94 /*
95 Reinitialize queue for other usage
96
97 SYNOPSIS
98 reinit_queue()
99 queue Queue to initialise
100 For rest of arguments, see init_queue() above
101
102 NOTES
103 This will delete all elements from the queue. If you don't want this,
104 use resize_queue() instead.
105
106 RETURN
107 0 ok
108 1 Wrong max_elements; Queue has old size
109 */
110
reinit_queue(QUEUE * queue,uint max_elements,uint offset_to_key,my_bool max_at_top,int (* compare)(void *,uchar *,uchar *),void * first_cmp_arg,uint offset_to_queue_pos,uint auto_extent)111 int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
112 my_bool max_at_top, int (*compare) (void *, uchar *, uchar *),
113 void *first_cmp_arg, uint offset_to_queue_pos,
114 uint auto_extent)
115 {
116 DBUG_ENTER("reinit_queue");
117 queue->elements= 0;
118 queue->compare= compare;
119 queue->first_cmp_arg= first_cmp_arg;
120 queue->offset_to_key= offset_to_key;
121 queue->offset_to_queue_pos= offset_to_queue_pos;
122 queue->auto_extent= auto_extent;
123 queue_set_max_at_top(queue, max_at_top);
124 DBUG_RETURN(resize_queue(queue, max_elements));
125 }
126
127
128 /*
129 Resize queue
130
131 SYNOPSIS
132 resize_queue()
133 queue Queue
134 max_elements New max size for queue
135
136 NOTES
137 If you resize queue to be less than the elements you have in it,
138 the extra elements will be deleted
139
140 RETURN
141 0 ok
142 1 Error. In this case the queue is unchanged
143 */
144
resize_queue(QUEUE * queue,uint max_elements)145 int resize_queue(QUEUE *queue, uint max_elements)
146 {
147 uchar **new_root;
148 DBUG_ENTER("resize_queue");
149 if (queue->max_elements == max_elements)
150 DBUG_RETURN(0);
151 if ((new_root= (uchar **) my_realloc(key_memory_QUEUE, (void *)queue->root,
152 (max_elements + 1)* sizeof(void*),
153 MYF(MY_WME))) == 0)
154 DBUG_RETURN(1);
155 set_if_smaller(queue->elements, max_elements);
156 queue->max_elements= max_elements;
157 queue->root= new_root;
158 DBUG_RETURN(0);
159 }
160
161
162 /*
163 Delete queue
164
165 SYNOPSIS
166 delete_queue()
167 queue Queue to delete
168
169 IMPLEMENTATION
170 Just free allocated memory.
171
172 NOTES
173 Can be called safely multiple times
174 */
175
delete_queue(QUEUE * queue)176 void delete_queue(QUEUE *queue)
177 {
178 DBUG_ENTER("delete_queue");
179 my_free(queue->root);
180 queue->root=0; /* Allow multiple calls */
181 DBUG_VOID_RETURN;
182 }
183
184
insert_at(QUEUE * queue,uchar * element,uint idx)185 static void insert_at(QUEUE *queue, uchar *element, uint idx)
186 {
187 uint next_index, offset_to_key= queue->offset_to_key;
188 uint offset_to_queue_pos= queue->offset_to_queue_pos;
189 /* max_at_top swaps the comparison if we want to order by desc */
190 while ((next_index= idx >> 1) > 0 &&
191 queue->compare(queue->first_cmp_arg,
192 element + offset_to_key,
193 queue->root[next_index] + offset_to_key) *
194 queue->max_at_top < 0)
195 {
196 queue->root[idx]= queue->root[next_index];
197 if (offset_to_queue_pos)
198 (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
199 idx= next_index;
200 }
201 queue->root[idx]= element;
202 if (offset_to_queue_pos)
203 (*(uint*) (element + offset_to_queue_pos-1))= idx;
204 }
205
206
207 /*
208 Insert element in queue
209
210 SYNOPSIS
211 queue_insert()
212 queue Queue to use
213 element Element to insert
214 */
215
queue_insert(QUEUE * queue,uchar * element)216 void queue_insert(QUEUE *queue, uchar *element)
217 {
218 DBUG_ASSERT(queue->elements < queue->max_elements);
219 insert_at(queue, element, ++queue->elements);
220 }
221
222
223 /*
224 Like queue_insert, but resize queue if queue is full
225
226 SYNOPSIS
227 queue_insert_safe()
228 queue Queue to use
229 element Element to insert
230
231 RETURN
232 0 OK
233 1 Cannot allocate more memory
234 2 auto_extend is 0; No insertion done
235 */
236
queue_insert_safe(QUEUE * queue,uchar * element)237 int queue_insert_safe(QUEUE *queue, uchar *element)
238 {
239
240 if (queue->elements == queue->max_elements)
241 {
242 if (!queue->auto_extent)
243 return 2;
244 if (resize_queue(queue, queue->max_elements + queue->auto_extent))
245 return 1;
246 }
247
248 queue_insert(queue, element);
249 return 0;
250 }
251
252
253 /*
254 Remove item from queue
255
256 SYNOPSIS
257 queue_remove()
258 queue Queue to use
259 element Index of element to remove.
260 First element in queue is 'queue_first_element(queue)'
261
262 RETURN
263 pointer to removed element
264 */
265
queue_remove(QUEUE * queue,uint idx)266 uchar *queue_remove(QUEUE *queue, uint idx)
267 {
268 uchar *element;
269 DBUG_ASSERT(idx >= 1);
270 DBUG_ASSERT(idx <= queue->elements);
271 element= queue->root[idx];
272 queue->root[idx]= queue->root[queue->elements--];
273 queue_replace(queue, idx);
274 return element;
275 }
276
277
278 /*
279 Restores the heap property from idx down the heap
280
281 SYNOPSIS
282 _downheap()
283 queue Queue to use
284 idx Index of element to change
285 */
286
_downheap(QUEUE * queue,uint idx)287 void _downheap(QUEUE *queue, uint idx)
288 {
289 uchar *element= queue->root[idx];
290 uint next_index,
291 elements= queue->elements,
292 half_queue= elements >> 1,
293 offset_to_key= queue->offset_to_key,
294 offset_to_queue_pos= queue->offset_to_queue_pos;
295
296 while (idx <= half_queue)
297 {
298 next_index= idx+idx;
299 if (next_index < elements &&
300 (queue->compare(queue->first_cmp_arg,
301 queue->root[next_index]+offset_to_key,
302 queue->root[next_index+1]+offset_to_key) *
303 queue->max_at_top) > 0)
304 next_index++;
305 if ((queue->compare(queue->first_cmp_arg,
306 queue->root[next_index]+offset_to_key,
307 element+offset_to_key) * queue->max_at_top) >= 0)
308 break;
309 queue->root[idx]= queue->root[next_index];
310 if (offset_to_queue_pos)
311 (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
312 idx= next_index;
313 }
314 queue->root[idx]=element;
315 if (offset_to_queue_pos)
316 (*(uint*) (element + offset_to_queue_pos-1))= idx;
317 }
318
319
320 /*
321 Fix heap when every element was changed.
322
323 SYNOPSIS
324 queue_fix()
325 queue Queue to use
326 */
327
queue_fix(QUEUE * queue)328 void queue_fix(QUEUE *queue)
329 {
330 uint i;
331 for (i= queue->elements >> 1; i > 0; i--)
332 _downheap(queue, i);
333 }
334
335
336 /*
337 Change element at fixed position
338
339 SYNOPSIS
340 queue_replace()
341 queue Queue to use
342 idx Index of element to change
343
344 NOTE
345 optimized for the case when the new position is close to the end of the
346 heap (typical for queue_remove() replacements).
347 */
348
queue_replace(QUEUE * queue,uint idx)349 void queue_replace(QUEUE *queue, uint idx)
350 {
351 uchar *element= queue->root[idx];
352 uint next_index,
353 elements= queue->elements,
354 half_queue= elements>>1,
355 offset_to_key= queue->offset_to_key,
356 offset_to_queue_pos= queue->offset_to_queue_pos;
357 my_bool first= TRUE;
358
359 while (idx <= half_queue)
360 {
361 next_index= idx + idx;
362 if (next_index < elements &&
363 queue->compare(queue->first_cmp_arg,
364 queue->root[next_index]+offset_to_key,
365 queue->root[next_index+1]+offset_to_key) *
366 queue->max_at_top > 0)
367 next_index++;
368 if (first &&
369 queue->compare(queue->first_cmp_arg,
370 queue->root[next_index]+offset_to_key,
371 element+offset_to_key) * queue->max_at_top >= 0)
372 {
373 queue->root[idx]= element;
374 if (offset_to_queue_pos)
375 (*(uint*) (element + offset_to_queue_pos-1))= idx;
376 break;
377 }
378 first= FALSE;
379 queue->root[idx]= queue->root[next_index];
380 if (offset_to_queue_pos)
381 (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
382 idx=next_index;
383 }
384
385 insert_at(queue, element, idx);
386 }
387