← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/queues.c

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

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