← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/queues.cc

  • Committer: Brian Aker
  • Date: 2009-03-05 07:55:26 UTC
  • mfrom: (910.1.5 drizzle)
  • Revision ID: brian@tangent.org-20090305075526-ua34bjproq6oxujx
Merge of Brian (test extensions, dead code killing)

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