1 /* Copyright (c) 2000, 2019, 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 Without limiting anything contained in the foregoing, this file,
15 which is part of C Driver for MySQL (Connector/C), is also subject to the
16 Universal FOSS Exception, version 1.0, a copy of which can be found at
17 http://oss.oracle.com/licenses/universal-foss-exception.
18
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU General Public License, version 2.0, for more details.
23
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
27
28 /*
29 Code for generell handling of priority Queues.
30 Implemention of queues from "Algoritms in C" by Robert Sedgewick.
31 An optimisation of _downheap suggested in Exercise 7.51 in "Data
32 Structures & Algorithms in C++" by Mark Allen Weiss, Second Edition
33 was implemented by Mikael Ronstrom 2005. Also the O(N) algorithm
34 of queue_fix was implemented.
35 */
36
37 #include "mysys_priv.h"
38 #include "mysys_err.h"
39 #include <queues.h>
40
41
42 /*
43 Init queue
44
45 SYNOPSIS
46 init_queue()
47 queue Queue to initialise
48 max_elements Max elements that will be put in queue
49 offset_to_key Offset to key in element stored in queue
50 Used when sending pointers to compare function
51 max_at_top Set to 1 if you want biggest element on top.
52 compare Compare function for elements, takes 3 arguments.
53 first_cmp_arg First argument to compare function
54
55 NOTES
56 Will allocate max_element pointers for queue array
57
58 RETURN
59 0 ok
60 1 Could not allocate memory
61 */
62
init_queue(QUEUE * queue,uint max_elements,uint offset_to_key,pbool max_at_top,int (* compare)(void *,uchar *,uchar *),void * first_cmp_arg)63 int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
64 pbool max_at_top, int (*compare) (void *, uchar *, uchar *),
65 void *first_cmp_arg)
66 {
67 DBUG_ENTER("init_queue");
68 if ((queue->root= (uchar **) my_malloc((max_elements+1)*sizeof(void*),
69 MYF(MY_WME))) == 0)
70 DBUG_RETURN(1);
71 queue->elements=0;
72 queue->compare=compare;
73 queue->first_cmp_arg=first_cmp_arg;
74 queue->max_elements=max_elements;
75 queue->offset_to_key=offset_to_key;
76 queue_set_max_at_top(queue, max_at_top);
77 DBUG_RETURN(0);
78 }
79
80
81
82 /*
83 Init queue, uses init_queue internally for init work but also accepts
84 auto_extent as parameter
85
86 SYNOPSIS
87 init_queue_ex()
88 queue Queue to initialise
89 max_elements Max elements that will be put in queue
90 offset_to_key Offset to key in element stored in queue
91 Used when sending pointers to compare function
92 max_at_top Set to 1 if you want biggest element on top.
93 compare Compare function for elements, takes 3 arguments.
94 first_cmp_arg First argument to compare function
95 auto_extent When the queue is full and there is insert operation
96 extend the queue.
97
98 NOTES
99 Will allocate max_element pointers for queue array
100
101 RETURN
102 0 ok
103 1 Could not allocate memory
104 */
105
init_queue_ex(QUEUE * queue,uint max_elements,uint offset_to_key,pbool max_at_top,int (* compare)(void *,uchar *,uchar *),void * first_cmp_arg,uint auto_extent)106 int init_queue_ex(QUEUE *queue, uint max_elements, uint offset_to_key,
107 pbool max_at_top, int (*compare) (void *, uchar *, uchar *),
108 void *first_cmp_arg, uint auto_extent)
109 {
110 int ret;
111 DBUG_ENTER("init_queue_ex");
112
113 if ((ret= init_queue(queue, max_elements, offset_to_key, max_at_top, compare,
114 first_cmp_arg)))
115 DBUG_RETURN(ret);
116
117 queue->auto_extent= auto_extent;
118 DBUG_RETURN(0);
119 }
120
121 /*
122 Reinitialize queue for other usage
123
124 SYNOPSIS
125 reinit_queue()
126 queue Queue to initialise
127 max_elements Max elements that will be put in queue
128 offset_to_key Offset to key in element stored in queue
129 Used when sending pointers to compare function
130 max_at_top Set to 1 if you want biggest element on top.
131 compare Compare function for elements, takes 3 arguments.
132 first_cmp_arg First argument to compare function
133
134 NOTES
135 This will delete all elements from the queue. If you don't want this,
136 use resize_queue() instead.
137
138 RETURN
139 0 ok
140 EE_OUTOFMEMORY Wrong max_elements
141 */
142
reinit_queue(QUEUE * queue,uint max_elements,uint offset_to_key,pbool max_at_top,int (* compare)(void *,uchar *,uchar *),void * first_cmp_arg)143 int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
144 pbool max_at_top, int (*compare) (void *, uchar *, uchar *),
145 void *first_cmp_arg)
146 {
147 DBUG_ENTER("reinit_queue");
148 queue->elements=0;
149 queue->compare=compare;
150 queue->first_cmp_arg=first_cmp_arg;
151 queue->offset_to_key=offset_to_key;
152 queue_set_max_at_top(queue, max_at_top);
153 resize_queue(queue, max_elements);
154 DBUG_RETURN(0);
155 }
156
157
158 /*
159 Resize queue
160
161 SYNOPSIS
162 resize_queue()
163 queue Queue
164 max_elements New max size for queue
165
166 NOTES
167 If you resize queue to be less than the elements you have in it,
168 the extra elements will be deleted
169
170 RETURN
171 0 ok
172 1 Error. In this case the queue is unchanged
173 */
174
resize_queue(QUEUE * queue,uint max_elements)175 int resize_queue(QUEUE *queue, uint max_elements)
176 {
177 uchar **new_root;
178 DBUG_ENTER("resize_queue");
179 if (queue->max_elements == max_elements)
180 DBUG_RETURN(0);
181 if ((new_root= (uchar **) my_realloc((void *)queue->root,
182 (max_elements+1)*sizeof(void*),
183 MYF(MY_WME))) == 0)
184 DBUG_RETURN(1);
185 set_if_smaller(queue->elements, max_elements);
186 queue->max_elements= max_elements;
187 queue->root= new_root;
188 DBUG_RETURN(0);
189 }
190
191
192 /*
193 Delete queue
194
195 SYNOPSIS
196 delete_queue()
197 queue Queue to delete
198
199 IMPLEMENTATION
200 Just free allocated memory.
201
202 NOTES
203 Can be called safely multiple times
204 */
205
delete_queue(QUEUE * queue)206 void delete_queue(QUEUE *queue)
207 {
208 DBUG_ENTER("delete_queue");
209 my_free(queue->root);
210 queue->root= NULL;
211 DBUG_VOID_RETURN;
212 }
213
214
215 /* Code for insert, search and delete of elements */
216
queue_insert(QUEUE * queue,uchar * element)217 void queue_insert(QUEUE *queue, uchar *element)
218 {
219 uint idx, next;
220 DBUG_ASSERT(queue->elements < queue->max_elements);
221 queue->root[0]= element;
222 idx= ++queue->elements;
223 /* max_at_top swaps the comparison if we want to order by desc */
224 while ((queue->compare(queue->first_cmp_arg,
225 element + queue->offset_to_key,
226 queue->root[(next= idx >> 1)] +
227 queue->offset_to_key) * queue->max_at_top) < 0)
228 {
229 queue->root[idx]= queue->root[next];
230 idx= next;
231 }
232 queue->root[idx]= element;
233 }
234
235 /*
236 Does safe insert. If no more space left on the queue resize it.
237 Return codes:
238 0 - OK
239 1 - Cannot allocate more memory
240 2 - auto_extend is 0, the operation would
241
242 */
243
queue_insert_safe(QUEUE * queue,uchar * element)244 int queue_insert_safe(QUEUE *queue, uchar *element)
245 {
246
247 if (queue->elements == queue->max_elements)
248 {
249 if (!queue->auto_extent)
250 return 2;
251 else if (resize_queue(queue, queue->max_elements + queue->auto_extent))
252 return 1;
253 }
254
255 queue_insert(queue, element);
256 return 0;
257 }
258
259
260 /* Remove item from queue */
261 /* Returns pointer to removed element */
262
queue_remove(QUEUE * queue,uint idx)263 uchar *queue_remove(QUEUE *queue, uint idx)
264 {
265 uchar *element;
266 my_bool use_downheap;
267
268 DBUG_ASSERT(idx < queue->max_elements);
269 /*
270 If we remove the top element in the queue, we use _downheap else queue_fix
271 to maintain the heap property.
272 */
273 use_downheap = (idx == 0);
274 element= queue->root[++idx]; /* Intern index starts from 1 */
275 queue->root[idx]= queue->root[queue->elements--];
276 if (use_downheap)
277 _downheap(queue, idx);
278 else
279 queue_fix(queue);
280 return element;
281 }
282
283 /* Fix when element on top has been replaced */
284
285 #ifndef queue_replaced
queue_replaced(QUEUE * queue)286 void queue_replaced(QUEUE *queue)
287 {
288 _downheap(queue,1);
289 }
290 #endif
291
292 #ifndef OLD_VERSION
293
_downheap(QUEUE * queue,uint idx)294 void _downheap(QUEUE *queue, uint idx)
295 {
296 uchar *element;
297 uint elements,half_queue,offset_to_key, next_index;
298 my_bool first= TRUE;
299 uint start_idx= idx;
300
301 offset_to_key=queue->offset_to_key;
302 element=queue->root[idx];
303 half_queue=(elements=queue->elements) >> 1;
304
305 while (idx <= half_queue)
306 {
307 next_index=idx+idx;
308 if (next_index < elements &&
309 (queue->compare(queue->first_cmp_arg,
310 queue->root[next_index]+offset_to_key,
311 queue->root[next_index+1]+offset_to_key) *
312 queue->max_at_top) > 0)
313 next_index++;
314 if (first &&
315 (((queue->compare(queue->first_cmp_arg,
316 queue->root[next_index]+offset_to_key,
317 element+offset_to_key) * queue->max_at_top) >= 0)))
318 {
319 queue->root[idx]= element;
320 return;
321 }
322 queue->root[idx]=queue->root[next_index];
323 idx=next_index;
324 first= FALSE;
325 }
326
327 next_index= idx >> 1;
328 while (next_index > start_idx)
329 {
330 if ((queue->compare(queue->first_cmp_arg,
331 queue->root[next_index]+offset_to_key,
332 element+offset_to_key) *
333 queue->max_at_top) < 0)
334 break;
335 queue->root[idx]=queue->root[next_index];
336 idx=next_index;
337 next_index= idx >> 1;
338 }
339 queue->root[idx]=element;
340 }
341
342 #else
343 /*
344 The old _downheap version is kept for comparisons with the benchmark
345 suit or new benchmarks anyone wants to run for comparisons.
346 */
347 /* Fix heap when index have changed */
_downheap(QUEUE * queue,uint idx)348 void _downheap(QUEUE *queue, uint idx)
349 {
350 uchar *element;
351 uint elements,half_queue,next_index,offset_to_key;
352
353 offset_to_key=queue->offset_to_key;
354 element=queue->root[idx];
355 half_queue=(elements=queue->elements) >> 1;
356
357 while (idx <= half_queue)
358 {
359 next_index=idx+idx;
360 if (next_index < elements &&
361 (queue->compare(queue->first_cmp_arg,
362 queue->root[next_index]+offset_to_key,
363 queue->root[next_index+1]+offset_to_key) *
364 queue->max_at_top) > 0)
365 next_index++;
366 if ((queue->compare(queue->first_cmp_arg,
367 queue->root[next_index]+offset_to_key,
368 element+offset_to_key) * queue->max_at_top) >= 0)
369 break;
370 queue->root[idx]=queue->root[next_index];
371 idx=next_index;
372 }
373 queue->root[idx]=element;
374 }
375
376
377 #endif
378
379 /*
380 Fix heap when every element was changed.
381 */
382
queue_fix(QUEUE * queue)383 void queue_fix(QUEUE *queue)
384 {
385 uint i;
386 for (i= queue->elements >> 1; i > 0; i--)
387 _downheap(queue, i);
388 }
389
390 #ifdef MAIN
391 /*
392 A test program for the priority queue implementation.
393 It can also be used to benchmark changes of the implementation
394 Build by doing the following in the directory mysys
395 make queues
396 ./queues
397
398 Written by Mikael Ronström, 2005
399 */
400
401 static uint num_array[1025];
402 static uint tot_no_parts= 0;
403 static uint tot_no_loops= 0;
404 static uint expected_part= 0;
405 static uint expected_num= 0;
406 static my_bool max_ind= 0;
407 static my_bool fix_used= 0;
408 static ulonglong start_time= 0;
409
is_divisible_by(uint num,uint divisor)410 static my_bool is_divisible_by(uint num, uint divisor)
411 {
412 uint quotient= num / divisor;
413 if (quotient * divisor == num)
414 return TRUE;
415 return FALSE;
416 }
417
calculate_next()418 void calculate_next()
419 {
420 uint part= expected_part, num= expected_num;
421 uint no_parts= tot_no_parts;
422 if (max_ind)
423 {
424 do
425 {
426 while (++part <= no_parts)
427 {
428 if (is_divisible_by(num, part) &&
429 (num <= ((1 << 21) + part)))
430 {
431 expected_part= part;
432 expected_num= num;
433 return;
434 }
435 }
436 part= 0;
437 } while (--num);
438 }
439 else
440 {
441 do
442 {
443 while (--part > 0)
444 {
445 if (is_divisible_by(num, part))
446 {
447 expected_part= part;
448 expected_num= num;
449 return;
450 }
451 }
452 part= no_parts + 1;
453 } while (++num);
454 }
455 }
456
calculate_end_next(uint part)457 void calculate_end_next(uint part)
458 {
459 uint no_parts= tot_no_parts, num;
460 num_array[part]= 0;
461 if (max_ind)
462 {
463 expected_num= 0;
464 for (part= no_parts; part > 0 ; part--)
465 {
466 if (num_array[part])
467 {
468 num= num_array[part] & 0x3FFFFF;
469 if (num >= expected_num)
470 {
471 expected_num= num;
472 expected_part= part;
473 }
474 }
475 }
476 if (expected_num == 0)
477 expected_part= 0;
478 }
479 else
480 {
481 expected_num= 0xFFFFFFFF;
482 for (part= 1; part <= no_parts; part++)
483 {
484 if (num_array[part])
485 {
486 num= num_array[part] & 0x3FFFFF;
487 if (num <= expected_num)
488 {
489 expected_num= num;
490 expected_part= part;
491 }
492 }
493 }
494 if (expected_num == 0xFFFFFFFF)
495 expected_part= 0;
496 }
497 return;
498 }
test_compare(void * null_arg,uchar * a,uchar * b)499 static int test_compare(void *null_arg, uchar *a, uchar *b)
500 {
501 uint a_num= (*(uint*)a) & 0x3FFFFF;
502 uint b_num= (*(uint*)b) & 0x3FFFFF;
503 uint a_part, b_part;
504 (void) null_arg;
505 if (a_num > b_num)
506 return +1;
507 if (a_num < b_num)
508 return -1;
509 a_part= (*(uint*)a) >> 22;
510 b_part= (*(uint*)b) >> 22;
511 if (a_part < b_part)
512 return +1;
513 if (a_part > b_part)
514 return -1;
515 return 0;
516 }
517
check_num(uint num_part)518 my_bool check_num(uint num_part)
519 {
520 uint part= num_part >> 22;
521 uint num= num_part & 0x3FFFFF;
522 if (part == expected_part)
523 if (num == expected_num)
524 return FALSE;
525 printf("Expect part %u Expect num 0x%x got part %u num 0x%x max_ind %u fix_used %u \n",
526 expected_part, expected_num, part, num, max_ind, fix_used);
527 return TRUE;
528 }
529
530
perform_insert(QUEUE * queue)531 void perform_insert(QUEUE *queue)
532 {
533 uint i= 1, no_parts= tot_no_parts;
534 uint backward_start= 0;
535
536 expected_part= 1;
537 expected_num= 1;
538
539 if (max_ind)
540 backward_start= 1 << 21;
541
542 do
543 {
544 uint num= (i + backward_start);
545 if (max_ind)
546 {
547 while (!is_divisible_by(num, i))
548 num--;
549 if (max_ind && (num > expected_num ||
550 (num == expected_num && i < expected_part)))
551 {
552 expected_num= num;
553 expected_part= i;
554 }
555 }
556 num_array[i]= num + (i << 22);
557 if (fix_used)
558 queue_element(queue, i-1)= (uchar*)&num_array[i];
559 else
560 queue_insert(queue, (uchar*)&num_array[i]);
561 } while (++i <= no_parts);
562 if (fix_used)
563 {
564 queue->elements= no_parts;
565 queue_fix(queue);
566 }
567 }
568
perform_ins_del(QUEUE * queue,my_bool max_ind)569 my_bool perform_ins_del(QUEUE *queue, my_bool max_ind)
570 {
571 uint i= 0, no_loops= tot_no_loops, j= tot_no_parts;
572 do
573 {
574 uint num_part= *(uint*)queue_top(queue);
575 uint part= num_part >> 22;
576 if (check_num(num_part))
577 return TRUE;
578 if (j++ >= no_loops)
579 {
580 calculate_end_next(part);
581 queue_remove(queue, (uint) 0);
582 }
583 else
584 {
585 calculate_next();
586 if (max_ind)
587 num_array[part]-= part;
588 else
589 num_array[part]+= part;
590 queue_top(queue)= (uchar*)&num_array[part];
591 queue_replaced(queue);
592 }
593 } while (++i < no_loops);
594 return FALSE;
595 }
596
do_test(uint no_parts,uint l_max_ind,my_bool l_fix_used)597 my_bool do_test(uint no_parts, uint l_max_ind, my_bool l_fix_used)
598 {
599 QUEUE queue;
600 my_bool result;
601 max_ind= l_max_ind;
602 fix_used= l_fix_used;
603 init_queue(&queue, no_parts, 0, max_ind, test_compare, NULL);
604 tot_no_parts= no_parts;
605 tot_no_loops= 1024;
606 perform_insert(&queue);
607 result= perform_ins_del(&queue, max_ind);
608 if (result)
609 {
610 printf("Error\n");
611 delete_queue(&queue);
612 return TRUE;
613 }
614 delete_queue(&queue);
615 return FALSE;
616 }
617
start_measurement()618 static void start_measurement()
619 {
620 start_time= my_getsystime();
621 }
622
stop_measurement()623 static void stop_measurement()
624 {
625 ulonglong stop_time= my_getsystime();
626 uint time_in_micros;
627 stop_time-= start_time;
628 stop_time/= 10; /* Convert to microseconds */
629 time_in_micros= (uint)stop_time;
630 printf("Time expired is %u microseconds \n", time_in_micros);
631 }
632
benchmark_test()633 static void benchmark_test()
634 {
635 QUEUE queue_real;
636 QUEUE *queue= &queue_real;
637 uint i, add;
638 fix_used= TRUE;
639 max_ind= FALSE;
640 tot_no_parts= 1024;
641 init_queue(queue, tot_no_parts, 0, max_ind, test_compare, NULL);
642 /*
643 First benchmark whether queue_fix is faster than using queue_insert
644 for sizes of 16 partitions.
645 */
646 for (tot_no_parts= 2, add=2; tot_no_parts < 128;
647 tot_no_parts+= add, add++)
648 {
649 printf("Start benchmark queue_fix, tot_no_parts= %u \n", tot_no_parts);
650 start_measurement();
651 for (i= 0; i < 128; i++)
652 {
653 perform_insert(queue);
654 queue_remove_all(queue);
655 }
656 stop_measurement();
657
658 fix_used= FALSE;
659 printf("Start benchmark queue_insert\n");
660 start_measurement();
661 for (i= 0; i < 128; i++)
662 {
663 perform_insert(queue);
664 queue_remove_all(queue);
665 }
666 stop_measurement();
667 }
668 /*
669 Now benchmark insertion and deletion of 16400 elements.
670 Used in consecutive runs this shows whether the optimised _downheap
671 is faster than the standard implementation.
672 */
673 printf("Start benchmarking _downheap \n");
674 start_measurement();
675 perform_insert(queue);
676 for (i= 0; i < 65536; i++)
677 {
678 uint num, part;
679 num= *(uint*)queue_top(queue);
680 num+= 16;
681 part= num >> 22;
682 num_array[part]= num;
683 queue_top(queue)= (uchar*)&num_array[part];
684 queue_replaced(queue);
685 }
686 for (i= 0; i < 16; i++)
687 queue_remove(queue, (uint) 0);
688 queue_remove_all(queue);
689 stop_measurement();
690 delete_queue(queue);
691 }
692
693 /**
694 Bug#30301356 - SOME EVENTS ARE DELAYED AFTER DROPPING EVENT
695
696 Test that ensures heap property is not violated if we remove an
697 element from an interior node. In the below test, we remove the
698 element 90 at index 6 in the array. After 90 is removed, the
699 parent node's of the deleted node violates the heap property
700 with the queue_remove function. We need to ensure the heap
701 property is satisfied by call queue_fix after removal from an
702 interior node in the queue_remove() function.
703 */
704
705 // Element comparator for comparison of elements in heap.
element_comparator(void * null_arg MY_ATTRIBUTE ((unused)),uchar * lhs,uchar * rhs)706 static int element_comparator(void *null_arg MY_ATTRIBUTE((unused)), uchar *lhs, uchar *rhs)
707 {
708 int lkey = *(int *)lhs;
709 int rkey = *(int *)rhs;
710
711 return (lkey < rkey ? -1 : (lkey > rkey ? 1 : 0));
712 }
713
is_tree_heap(uint index,QUEUE * queue)714 static my_bool is_tree_heap(uint index, QUEUE *queue)
715 {
716 uint left, right;
717
718 if (index > queue->elements) return TRUE;
719 left = 2 * index;
720 right = 2 * index + 1;
721
722 if (left <= queue->elements &&
723 element_comparator(NULL, queue->root[index], queue->root[left]) == 1)
724 return FALSE;
725
726 if (left <= queue->elements &&
727 element_comparator(NULL, queue->root[index], queue->root[right]) == 1)
728 return FALSE;
729
730 return is_tree_heap(left, queue) && is_tree_heap(right, queue);
731 }
732
733 // Check if queue is a valid heap
is_queue_valid(QUEUE * queue)734 static my_bool is_queue_valid(QUEUE *queue)
735 {
736 unsigned i;
737
738 for(i = 0; i <= queue->elements; i++)
739 if (queue->root[i] == NULL) return FALSE;
740
741 return is_tree_heap(1, queue);
742 }
743
remove_queue_element_test()744 static void remove_queue_element_test()
745 {
746 QUEUE queue;
747 int keys[11] = {60, 65, 84, 75, 80, 85, 90, 95, 100, 105, 82};
748 int i;
749 init_queue(&queue, 11, 0, 0, element_comparator, NULL);
750 for (i = 0; i < 11; i++)
751 queue_insert(&queue, (uchar*)&keys[i]);
752 assert(is_queue_valid(&queue));
753 queue_remove(&queue, 6);
754 assert(is_queue_valid(&queue));
755 delete_queue(&queue);
756 }
757
main()758 int main()
759 {
760 int i, add= 1;
761 for (i= 1; i < 1024; i+=add, add++)
762 {
763 printf("Start test for priority queue of size %u\n", i);
764 if (do_test(i, 0, 1))
765 return -1;
766 if (do_test(i, 1, 1))
767 return -1;
768 if (do_test(i, 0, 0))
769 return -1;
770 if (do_test(i, 1, 0))
771 return -1;
772 }
773 benchmark_test();
774 remove_queue_element_test();
775 printf("OK\n");
776 return 0;
777 }
778 #endif
779