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
72int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
73 pbool max_at_top, int (*compare) (void *, uchar *, uchar *),
74 void *first_cmp_arg, uint offset_to_queue_pos,
75 uint auto_extent)
76
77{
78 DBUG_ENTER("init_queue");
79 if ((queue->root= (uchar **) my_malloc((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
111int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
112 pbool 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
145int 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((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
176void 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
185/*
186 Insert element in queue
187
188 SYNOPSIS
189 queue_insert()
190 queue Queue to use
191 element Element to insert
192*/
193
194void queue_insert(register QUEUE *queue, uchar *element)
195{
196 reg2 uint idx, next;
197 uint offset_to_queue_pos= queue->offset_to_queue_pos;
198 DBUG_ASSERT(queue->elements < queue->max_elements);
199
200 idx= ++queue->elements;
201 /* max_at_top swaps the comparison if we want to order by desc */
202 while (idx > 1 &&
203 (queue->compare(queue->first_cmp_arg,
204 element + queue->offset_to_key,
205 queue->root[(next= idx >> 1)] +
206 queue->offset_to_key) * queue->max_at_top) < 0)
207 {
208 queue->root[idx]= queue->root[next];
209 if (offset_to_queue_pos)
210 (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
211 idx= next;
212 }
213 queue->root[idx]= element;
214 if (offset_to_queue_pos)
215 (*(uint*) (element+ offset_to_queue_pos-1))= idx;
216}
217
218
219/*
220 Like queue_insert, but resize queue if queue is full
221
222 SYNOPSIS
223 queue_insert_safe()
224 queue Queue to use
225 element Element to insert
226
227 RETURN
228 0 OK
229 1 Cannot allocate more memory
230 2 auto_extend is 0; No insertion done
231*/
232
233int queue_insert_safe(register QUEUE *queue, uchar *element)
234{
235
236 if (queue->elements == queue->max_elements)
237 {
238 if (!queue->auto_extent)
239 return 2;
240 if (resize_queue(queue, queue->max_elements + queue->auto_extent))
241 return 1;
242 }
243
244 queue_insert(queue, element);
245 return 0;
246}
247
248
249/*
250 Remove item from queue
251
252 SYNOPSIS
253 queue_remove()
254 queue Queue to use
255 element Index of element to remove.
256 First element in queue is 'queue_first_element(queue)'
257
258 RETURN
259 pointer to removed element
260*/
261
262uchar *queue_remove(register QUEUE *queue, uint idx)
263{
264 uchar *element;
265 DBUG_ASSERT(idx >= 1 && idx <= queue->elements);
266 element= queue->root[idx];
267 _downheap(queue, idx, queue->root[queue->elements--]);
268 return element;
269}
270
271
272/*
273 Add element to fixed position and update heap
274
275 SYNOPSIS
276 _downheap()
277 queue Queue to use
278 idx Index of element to change
279 element Element to store at 'idx'
280
281 NOTE
282 This only works if element is >= all elements <= start_idx
283*/
284
285void _downheap(register QUEUE *queue, uint start_idx, uchar *element)
286{
287 uint elements,half_queue,offset_to_key, next_index, offset_to_queue_pos;
288 register uint idx= start_idx;
289 my_bool first= TRUE;
290
291 offset_to_key=queue->offset_to_key;
292 offset_to_queue_pos= queue->offset_to_queue_pos;
293 half_queue= (elements= queue->elements) >> 1;
294
295 while (idx <= half_queue)
296 {
297 next_index=idx+idx;
298 if (next_index < elements &&
299 (queue->compare(queue->first_cmp_arg,
300 queue->root[next_index]+offset_to_key,
301 queue->root[next_index+1]+offset_to_key) *
302 queue->max_at_top) > 0)
303 next_index++;
304 if (first &&
305 (((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 {
309 queue->root[idx]= element;
310 if (offset_to_queue_pos)
311 (*(uint*) (element + offset_to_queue_pos-1))= idx;
312 return;
313 }
314 first= FALSE;
315 queue->root[idx]= queue->root[next_index];
316 if (offset_to_queue_pos)
317 (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
318 idx=next_index;
319 }
320
321 /*
322 Insert the element into the right position. This is the same code
323 as we have in queue_insert()
324 */
325 while ((next_index= (idx >> 1)) > start_idx &&
326 queue->compare(queue->first_cmp_arg,
327 element+offset_to_key,
328 queue->root[next_index]+offset_to_key)*
329 queue->max_at_top < 0)
330 {
331 queue->root[idx]= queue->root[next_index];
332 if (offset_to_queue_pos)
333 (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
334 idx= next_index;
335 }
336 queue->root[idx]= element;
337 if (offset_to_queue_pos)
338 (*(uint*) (element + offset_to_queue_pos-1))= idx;
339}
340
341
342/*
343 Fix heap when every element was changed.
344
345 SYNOPSIS
346 queue_fix()
347 queue Queue to use
348*/
349
350void queue_fix(QUEUE *queue)
351{
352 uint i;
353 for (i= queue->elements >> 1; i > 0; i--)
354 _downheap(queue, i, queue_element(queue, i));
355}
356
357
358/*
359 Change element at fixed position
360
361 SYNOPSIS
362 queue_replace()
363 queue Queue to use
364 idx Index of element to change
365 element Element to store at 'idx'
366*/
367
368void queue_replace(QUEUE *queue, uint idx)
369{
370 uchar *element= queue->root[idx];
371 DBUG_ASSERT(idx >= 1 && idx <= queue->elements);
372 queue_remove(queue, idx);
373 queue_insert(queue, element);
374}
375