← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/queues.c

pandora-build v0.100 - Fixes several bugs found by cb1kenobi. Add several thoughts from folks at LCA.

Show diffs side-by-side

added added

removed removed

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