← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/queues.c

  • Committer: Brian Aker
  • Date: 2008-11-04 15:39:09 UTC
  • mfrom: (575.1.2 devel)
  • Revision ID: brian@tangent.org-20081104153909-c72hn65udxs1ccal
Merge of Monty's work

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/queues.c
48
48
    1   Could not allocate memory
49
49
*/
50
50
 
51
 
int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
52
 
               bool max_at_top, int (*compare) (void *, uchar *, uchar *),
 
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
53
               void *first_cmp_arg)
54
54
{
55
 
  if ((queue->root= (uchar **) my_malloc((max_elements+1)*sizeof(void*),
 
55
  if ((queue->root= (unsigned char **) my_malloc((max_elements+1)*sizeof(void*),
56
56
                                         MYF(MY_WME))) == 0)
57
57
    return(1);
58
58
  queue->elements=0;
90
90
    1   Could not allocate memory
91
91
*/
92
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)
 
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
96
{
97
97
  int ret;
98
98
 
126
126
    EE_OUTOFMEMORY      Wrong max_elements
127
127
*/
128
128
 
129
 
int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
130
 
                 bool max_at_top, int (*compare) (void *, uchar *, uchar *),
 
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
131
                 void *first_cmp_arg)
132
132
{
133
133
  queue->elements=0;
157
157
    1   Error.  In this case the queue is unchanged
158
158
*/
159
159
 
160
 
int resize_queue(QUEUE *queue, uint max_elements)
 
160
int resize_queue(QUEUE *queue, uint32_t max_elements)
161
161
{
162
 
  uchar **new_root;
 
162
  unsigned char **new_root;
163
163
  if (queue->max_elements == max_elements)
164
164
    return(0);
165
 
  if ((new_root= (uchar **) my_realloc((void *)queue->root,
 
165
  if ((new_root= (unsigned char **) my_realloc((void *)queue->root,
166
166
                                      (max_elements+1)*sizeof(void*),
167
167
                                      MYF(MY_WME))) == 0)
168
168
    return(1);
191
191
{
192
192
  if (queue->root)
193
193
  {
194
 
    my_free((uchar*) queue->root,MYF(0));
 
194
    free((unsigned char*) queue->root);
195
195
    queue->root=0;
196
196
  }
197
197
  return;
200
200
 
201
201
        /* Code for insert, search and delete of elements */
202
202
 
203
 
void queue_insert(register QUEUE *queue, uchar *element)
 
203
void queue_insert(register QUEUE *queue, unsigned char *element)
204
204
{
205
 
  register uint idx, next;
 
205
  register uint32_t idx, next;
206
206
  assert(queue->elements < queue->max_elements);
207
207
  queue->root[0]= element;
208
208
  idx= ++queue->elements;
227
227
  
228
228
*/
229
229
 
230
 
int queue_insert_safe(register QUEUE *queue, uchar *element)
 
230
int queue_insert_safe(register QUEUE *queue, unsigned char *element)
231
231
{
232
232
 
233
233
  if (queue->elements == queue->max_elements)
246
246
        /* Remove item from queue */
247
247
        /* Returns pointer to removed element */
248
248
 
249
 
uchar *queue_remove(register QUEUE *queue, uint idx)
 
249
unsigned char *queue_remove(register QUEUE *queue, uint32_t idx)
250
250
{
251
 
  uchar *element;
 
251
  unsigned char *element;
252
252
  assert(idx < queue->max_elements);
253
253
  element= queue->root[++idx];  /* Intern index starts from 1 */
254
254
  queue->root[idx]= queue->root[queue->elements--];
267
267
 
268
268
#ifndef OLD_VERSION
269
269
 
270
 
void _downheap(register QUEUE *queue, uint idx)
 
270
void _downheap(register QUEUE *queue, uint32_t idx)
271
271
{
272
 
  uchar *element;
273
 
  uint elements,half_queue,offset_to_key, next_index;
 
272
  unsigned char *element;
 
273
  uint32_t elements,half_queue,offset_to_key, next_index;
274
274
  bool first= true;
275
 
  uint start_idx= idx;
 
275
  uint32_t start_idx= idx;
276
276
 
277
277
  offset_to_key=queue->offset_to_key;
278
278
  element=queue->root[idx];
321
321
    suit or new benchmarks anyone wants to run for comparisons.
322
322
  */
323
323
        /* Fix heap when index have changed */
324
 
void _downheap(register QUEUE *queue, uint idx)
 
324
void _downheap(register QUEUE *queue, uint32_t idx)
325
325
{
326
 
  uchar *element;
327
 
  uint elements,half_queue,next_index,offset_to_key;
 
326
  unsigned char *element;
 
327
  uint32_t elements,half_queue,next_index,offset_to_key;
328
328
 
329
329
  offset_to_key=queue->offset_to_key;
330
330
  element=queue->root[idx];
358
358
 
359
359
void queue_fix(QUEUE *queue)
360
360
{
361
 
  uint i;
 
361
  uint32_t i;
362
362
  for (i= queue->elements >> 1; i > 0; i--)
363
363
    _downheap(queue, i);
364
364
}
374
374
   Written by Mikael Ronström, 2005
375
375
 */
376
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;
 
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
382
static bool max_ind= 0;
383
383
static bool fix_used= 0;
384
384
static uint64_t start_time= 0;
385
385
 
386
 
static bool is_divisible_by(uint num, uint divisor)
 
386
static bool is_divisible_by(uint32_t num, uint32_t divisor)
387
387
{
388
 
  uint quotient= num / divisor;
 
388
  uint32_t quotient= num / divisor;
389
389
  if (quotient * divisor == num)
390
390
    return true;
391
391
  return false;
393
393
 
394
394
void calculate_next()
395
395
{
396
 
  uint part= expected_part, num= expected_num;
397
 
  uint no_parts= tot_no_parts;
 
396
  uint32_t part= expected_part, num= expected_num;
 
397
  uint32_t no_parts= tot_no_parts;
398
398
  if (max_ind)
399
399
  {
400
400
    do
430
430
  }
431
431
}
432
432
 
433
 
void calculate_end_next(uint part)
 
433
void calculate_end_next(uint32_t part)
434
434
{
435
 
  uint no_parts= tot_no_parts, num;
 
435
  uint32_t no_parts= tot_no_parts, num;
436
436
  num_array[part]= 0;
437
437
  if (max_ind)
438
438
  {
472
472
  }
473
473
  return;
474
474
}
475
 
static int test_compare(void *null_arg, uchar *a, uchar *b)
 
475
static int test_compare(void *null_arg, unsigned char *a, unsigned char *b)
476
476
{
477
 
  uint a_num= (*(uint*)a) & 0x3FFFFF;
478
 
  uint b_num= (*(uint*)b) & 0x3FFFFF;
479
 
  uint a_part, b_part;
 
477
  uint32_t a_num= (*(uint*)a) & 0x3FFFFF;
 
478
  uint32_t b_num= (*(uint*)b) & 0x3FFFFF;
 
479
  uint32_t a_part, b_part;
480
480
  if (a_num > b_num)
481
481
    return +1;
482
482
  if (a_num < b_num)
490
490
  return 0;
491
491
}
492
492
 
493
 
bool check_num(uint num_part)
 
493
bool check_num(uint32_t num_part)
494
494
{
495
 
  uint part= num_part >> 22;
496
 
  uint num= num_part & 0x3FFFFF;
 
495
  uint32_t part= num_part >> 22;
 
496
  uint32_t num= num_part & 0x3FFFFF;
497
497
  if (part == expected_part)
498
498
    if (num == expected_num)
499
499
      return false;
505
505
 
506
506
void perform_insert(QUEUE *queue)
507
507
{
508
 
  uint i= 1, no_parts= tot_no_parts;
509
 
  uint backward_start= 0;
 
508
  uint32_t i= 1, no_parts= tot_no_parts;
 
509
  uint32_t backward_start= 0;
510
510
 
511
511
  expected_part= 1;
512
512
  expected_num= 1;
516
516
 
517
517
  do
518
518
  {
519
 
    uint num= (i + backward_start);
 
519
    uint32_t num= (i + backward_start);
520
520
    if (max_ind)
521
521
    {
522
522
      while (!is_divisible_by(num, i))
530
530
    }
531
531
    num_array[i]= num + (i << 22);
532
532
    if (fix_used)
533
 
      queue_element(queue, i-1)= (uchar*)&num_array[i];
 
533
      queue_element(queue, i-1)= (unsigned char*)&num_array[i];
534
534
    else
535
 
      queue_insert(queue, (uchar*)&num_array[i]);
 
535
      queue_insert(queue, (unsigned char*)&num_array[i]);
536
536
  } while (++i <= no_parts);
537
537
  if (fix_used)
538
538
  {
543
543
 
544
544
bool perform_ins_del(QUEUE *queue, bool max_ind)
545
545
{
546
 
  uint i= 0, no_loops= tot_no_loops, j= tot_no_parts;
 
546
  uint32_t i= 0, no_loops= tot_no_loops, j= tot_no_parts;
547
547
  do
548
548
  {
549
 
    uint num_part= *(uint*)queue_top(queue);
550
 
    uint part= num_part >> 22;
 
549
    uint32_t num_part= *(uint*)queue_top(queue);
 
550
    uint32_t part= num_part >> 22;
551
551
    if (check_num(num_part))
552
552
      return true;
553
553
    if (j++ >= no_loops)
562
562
        num_array[part]-= part;
563
563
      else
564
564
        num_array[part]+= part;
565
 
      queue_top(queue)= (uchar*)&num_array[part];
 
565
      queue_top(queue)= (unsigned char*)&num_array[part];
566
566
      queue_replaced(queue);
567
567
    }
568
568
  } while (++i < no_loops);
569
569
  return false;
570
570
}
571
571
 
572
 
bool do_test(uint no_parts, uint l_max_ind, bool l_fix_used)
 
572
bool do_test(uint32_t no_parts, uint32_t l_max_ind, bool l_fix_used)
573
573
{
574
574
  QUEUE queue;
575
575
  bool result;
597
597
static void stop_measurement()
598
598
{
599
599
  uint64_t stop_time= my_getsystime();
600
 
  uint time_in_micros;
 
600
  uint32_t time_in_micros;
601
601
  stop_time-= start_time;
602
602
  stop_time/= 10; /* Convert to microseconds */
603
603
  time_in_micros= (uint)stop_time;
608
608
{
609
609
  QUEUE queue_real;
610
610
  QUEUE *queue= &queue_real;
611
 
  uint i, add;
 
611
  uint32_t i, add;
612
612
  fix_used= true;
613
613
  max_ind= false;
614
614
  tot_no_parts= 1024;
649
649
  perform_insert(queue);
650
650
  for (i= 0; i < 65536; i++)
651
651
  {
652
 
    uint num, part;
 
652
    uint32_t num, part;
653
653
    num= *(uint*)queue_top(queue);
654
654
    num+= 16;
655
655
    part= num >> 22;
656
656
    num_array[part]= num;
657
 
    queue_top(queue)= (uchar*)&num_array[part];
 
657
    queue_top(queue)= (unsigned char*)&num_array[part];
658
658
    queue_replaced(queue);
659
659
  }
660
660
  for (i= 0; i < 16; i++)