← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/queues.cc

  • Committer: Monty Taylor
  • Date: 2008-11-16 20:15:33 UTC
  • mto: (584.1.9 devel)
  • mto: This revision was merged to the branch mainline in revision 589.
  • Revision ID: monty@inaugust.com-20081116201533-d0f19s1bk1h95iyw
Removed a big bank of includes from item.h.

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/queues.cc
 
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, uint32_t max_elements, uint32_t offset_to_key,
 
52
               bool max_at_top, int (*compare) (void *, unsigned char *, unsigned char *),
 
53
               void *first_cmp_arg)
 
54
{
 
55
  if ((queue->root= (unsigned char **) 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, uint32_t max_elements, uint32_t offset_to_key,
 
94
               bool max_at_top, int (*compare) (void *, unsigned char *, unsigned char *),
 
95
               void *first_cmp_arg, uint32_t 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, uint32_t max_elements, uint32_t offset_to_key,
 
130
                 bool max_at_top, int (*compare) (void *, unsigned char *, unsigned char *),
 
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, uint32_t max_elements)
 
161
{
 
162
  unsigned char **new_root;
 
163
  if (queue->max_elements == max_elements)
 
164
    return(0);
 
165
  if ((new_root= (unsigned char **) 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
    free((unsigned char*) queue->root);
 
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, unsigned char *element)
 
204
{
 
205
  register uint32_t 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, unsigned char *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
unsigned char *queue_remove(register QUEUE *queue, uint32_t idx)
 
250
{
 
251
  unsigned char *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, uint32_t idx)
 
271
{
 
272
  unsigned char *element;
 
273
  uint32_t elements,half_queue,offset_to_key, next_index;
 
274
  bool first= true;
 
275
  uint32_t 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, uint32_t idx)
 
325
{
 
326
  unsigned char *element;
 
327
  uint32_t 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
  uint32_t 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 uint32_t num_array[1025];
 
378
static uint32_t tot_no_parts= 0;
 
379
static uint32_t tot_no_loops= 0;
 
380
static uint32_t expected_part= 0;
 
381
static uint32_t 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(uint32_t num, uint32_t divisor)
 
387
{
 
388
  uint32_t quotient= num / divisor;
 
389
  if (quotient * divisor == num)
 
390
    return true;
 
391
  return false;
 
392
}
 
393
 
 
394
void calculate_next()
 
395
{
 
396
  uint32_t part= expected_part, num= expected_num;
 
397
  uint32_t 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(uint32_t part)
 
434
{
 
435
  uint32_t 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, unsigned char *a, unsigned char *b)
 
476
{
 
477
  uint32_t a_num= (*(uint*)a) & 0x3FFFFF;
 
478
  uint32_t b_num= (*(uint*)b) & 0x3FFFFF;
 
479
  uint32_t 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(uint32_t num_part)
 
494
{
 
495
  uint32_t part= num_part >> 22;
 
496
  uint32_t 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
  uint32_t i= 1, no_parts= tot_no_parts;
 
509
  uint32_t 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
    uint32_t 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)= (unsigned char*)&num_array[i];
 
534
    else
 
535
      queue_insert(queue, (unsigned char*)&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
  uint32_t i= 0, no_loops= tot_no_loops, j= tot_no_parts;
 
547
  do
 
548
  {
 
549
    uint32_t num_part= *(uint*)queue_top(queue);
 
550
    uint32_t 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)= (unsigned char*)&num_array[part];
 
566
      queue_replaced(queue);
 
567
    }
 
568
  } while (++i < no_loops);
 
569
  return false;
 
570
}
 
571
 
 
572
bool do_test(uint32_t no_parts, uint32_t 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
  uint32_t 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
  uint32_t 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
    uint32_t num, part;
 
653
    num= *(uint*)queue_top(queue);
 
654
    num+= 16;
 
655
    part= num >> 22;
 
656
    num_array[part]= num;
 
657
    queue_top(queue)= (unsigned char*)&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