← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/queues.c

Removed dead variable, sorted authors file.

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, uint32_t max_elements, uint32_t offset_to_key,
52
 
               bool max_at_top, int (*compare) (void *, unsigned char *, unsigned char *),
 
51
int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
 
52
               bool max_at_top, int (*compare) (void *, uchar *, uchar *),
53
53
               void *first_cmp_arg)
54
54
{
55
 
  if ((queue->root= (unsigned char **) my_malloc((max_elements+1)*sizeof(void*),
 
55
  DBUG_ENTER("init_queue");
 
56
  if ((queue->root= (uchar **) my_malloc((max_elements+1)*sizeof(void*),
56
57
                                         MYF(MY_WME))) == 0)
57
 
    return(1);
 
58
    DBUG_RETURN(1);
58
59
  queue->elements=0;
59
60
  queue->compare=compare;
60
61
  queue->first_cmp_arg=first_cmp_arg;
61
62
  queue->max_elements=max_elements;
62
63
  queue->offset_to_key=offset_to_key;
63
64
  queue_set_max_at_top(queue, max_at_top);
64
 
  return(0);
 
65
  DBUG_RETURN(0);
65
66
}
66
67
 
67
68
 
90
91
    1   Could not allocate memory
91
92
*/
92
93
 
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)
 
94
int init_queue_ex(QUEUE *queue, uint max_elements, uint offset_to_key,
 
95
               bool max_at_top, int (*compare) (void *, uchar *, uchar *),
 
96
               void *first_cmp_arg, uint auto_extent)
96
97
{
97
98
  int ret;
 
99
  DBUG_ENTER("init_queue_ex");
98
100
 
99
101
  if ((ret= init_queue(queue, max_elements, offset_to_key, max_at_top, compare,
100
102
                       first_cmp_arg)))
101
 
    return(ret);
 
103
    DBUG_RETURN(ret);
102
104
  
103
105
  queue->auto_extent= auto_extent;
104
 
  return(0);
 
106
  DBUG_RETURN(0);
105
107
}
106
108
 
107
109
/*
126
128
    EE_OUTOFMEMORY      Wrong max_elements
127
129
*/
128
130
 
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
int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
 
132
                 bool max_at_top, int (*compare) (void *, uchar *, uchar *),
131
133
                 void *first_cmp_arg)
132
134
{
 
135
  DBUG_ENTER("reinit_queue");
133
136
  queue->elements=0;
134
137
  queue->compare=compare;
135
138
  queue->first_cmp_arg=first_cmp_arg;
136
139
  queue->offset_to_key=offset_to_key;
137
140
  queue_set_max_at_top(queue, max_at_top);
138
141
  resize_queue(queue, max_elements);
139
 
  return(0);
 
142
  DBUG_RETURN(0);
140
143
}
141
144
 
142
145
 
157
160
    1   Error.  In this case the queue is unchanged
158
161
*/
159
162
 
160
 
int resize_queue(QUEUE *queue, uint32_t max_elements)
 
163
int resize_queue(QUEUE *queue, uint max_elements)
161
164
{
162
 
  unsigned char **new_root;
 
165
  uchar **new_root;
 
166
  DBUG_ENTER("resize_queue");
163
167
  if (queue->max_elements == max_elements)
164
 
    return(0);
165
 
  if ((new_root= (unsigned char **) my_realloc((void *)queue->root,
 
168
    DBUG_RETURN(0);
 
169
  if ((new_root= (uchar **) my_realloc((void *)queue->root,
166
170
                                      (max_elements+1)*sizeof(void*),
167
171
                                      MYF(MY_WME))) == 0)
168
 
    return(1);
 
172
    DBUG_RETURN(1);
169
173
  set_if_smaller(queue->elements, max_elements);
170
174
  queue->max_elements= max_elements;
171
175
  queue->root= new_root;
172
 
  return(0);
 
176
  DBUG_RETURN(0);
173
177
}
174
178
 
175
179
 
189
193
 
190
194
void delete_queue(QUEUE *queue)
191
195
{
 
196
  DBUG_ENTER("delete_queue");
192
197
  if (queue->root)
193
198
  {
194
 
    free((unsigned char*) queue->root);
 
199
    my_free((uchar*) queue->root,MYF(0));
195
200
    queue->root=0;
196
201
  }
197
 
  return;
 
202
  DBUG_VOID_RETURN;
198
203
}
199
204
 
200
205
 
201
206
        /* Code for insert, search and delete of elements */
202
207
 
203
 
void queue_insert(register QUEUE *queue, unsigned char *element)
 
208
void queue_insert(register QUEUE *queue, uchar *element)
204
209
{
205
 
  register uint32_t idx, next;
206
 
  assert(queue->elements < queue->max_elements);
 
210
  register uint idx, next;
 
211
  DBUG_ASSERT(queue->elements < queue->max_elements);
207
212
  queue->root[0]= element;
208
213
  idx= ++queue->elements;
209
214
  /* max_at_top swaps the comparison if we want to order by desc */
227
232
  
228
233
*/
229
234
 
230
 
int queue_insert_safe(register QUEUE *queue, unsigned char *element)
 
235
int queue_insert_safe(register QUEUE *queue, uchar *element)
231
236
{
232
237
 
233
238
  if (queue->elements == queue->max_elements)
246
251
        /* Remove item from queue */
247
252
        /* Returns pointer to removed element */
248
253
 
249
 
unsigned char *queue_remove(register QUEUE *queue, uint32_t idx)
 
254
uchar *queue_remove(register QUEUE *queue, uint idx)
250
255
{
251
 
  unsigned char *element;
252
 
  assert(idx < queue->max_elements);
 
256
  uchar *element;
 
257
  DBUG_ASSERT(idx < queue->max_elements);
253
258
  element= queue->root[++idx];  /* Intern index starts from 1 */
254
259
  queue->root[idx]= queue->root[queue->elements--];
255
260
  _downheap(queue, idx);
267
272
 
268
273
#ifndef OLD_VERSION
269
274
 
270
 
void _downheap(register QUEUE *queue, uint32_t idx)
 
275
void _downheap(register QUEUE *queue, uint idx)
271
276
{
272
 
  unsigned char *element;
273
 
  uint32_t elements,half_queue,offset_to_key, next_index;
 
277
  uchar *element;
 
278
  uint elements,half_queue,offset_to_key, next_index;
274
279
  bool first= true;
275
 
  uint32_t start_idx= idx;
 
280
  uint start_idx= idx;
276
281
 
277
282
  offset_to_key=queue->offset_to_key;
278
283
  element=queue->root[idx];
321
326
    suit or new benchmarks anyone wants to run for comparisons.
322
327
  */
323
328
        /* Fix heap when index have changed */
324
 
void _downheap(register QUEUE *queue, uint32_t idx)
 
329
void _downheap(register QUEUE *queue, uint idx)
325
330
{
326
 
  unsigned char *element;
327
 
  uint32_t elements,half_queue,next_index,offset_to_key;
 
331
  uchar *element;
 
332
  uint elements,half_queue,next_index,offset_to_key;
328
333
 
329
334
  offset_to_key=queue->offset_to_key;
330
335
  element=queue->root[idx];
358
363
 
359
364
void queue_fix(QUEUE *queue)
360
365
{
361
 
  uint32_t i;
 
366
  uint i;
362
367
  for (i= queue->elements >> 1; i > 0; i--)
363
368
    _downheap(queue, i);
364
369
}
374
379
   Written by Mikael Ronström, 2005
375
380
 */
376
381
 
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 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;
382
387
static bool max_ind= 0;
383
388
static bool fix_used= 0;
384
389
static uint64_t start_time= 0;
385
390
 
386
 
static bool is_divisible_by(uint32_t num, uint32_t divisor)
 
391
static bool is_divisible_by(uint num, uint divisor)
387
392
{
388
 
  uint32_t quotient= num / divisor;
 
393
  uint quotient= num / divisor;
389
394
  if (quotient * divisor == num)
390
395
    return true;
391
396
  return false;
393
398
 
394
399
void calculate_next()
395
400
{
396
 
  uint32_t part= expected_part, num= expected_num;
397
 
  uint32_t no_parts= tot_no_parts;
 
401
  uint part= expected_part, num= expected_num;
 
402
  uint no_parts= tot_no_parts;
398
403
  if (max_ind)
399
404
  {
400
405
    do
430
435
  }
431
436
}
432
437
 
433
 
void calculate_end_next(uint32_t part)
 
438
void calculate_end_next(uint part)
434
439
{
435
 
  uint32_t no_parts= tot_no_parts, num;
 
440
  uint no_parts= tot_no_parts, num;
436
441
  num_array[part]= 0;
437
442
  if (max_ind)
438
443
  {
472
477
  }
473
478
  return;
474
479
}
475
 
static int test_compare(void *null_arg, unsigned char *a, unsigned char *b)
 
480
static int test_compare(void *null_arg, uchar *a, uchar *b)
476
481
{
477
 
  uint32_t a_num= (*(uint*)a) & 0x3FFFFF;
478
 
  uint32_t b_num= (*(uint*)b) & 0x3FFFFF;
479
 
  uint32_t a_part, b_part;
 
482
  uint a_num= (*(uint*)a) & 0x3FFFFF;
 
483
  uint b_num= (*(uint*)b) & 0x3FFFFF;
 
484
  uint a_part, b_part;
480
485
  if (a_num > b_num)
481
486
    return +1;
482
487
  if (a_num < b_num)
490
495
  return 0;
491
496
}
492
497
 
493
 
bool check_num(uint32_t num_part)
 
498
bool check_num(uint num_part)
494
499
{
495
 
  uint32_t part= num_part >> 22;
496
 
  uint32_t num= num_part & 0x3FFFFF;
 
500
  uint part= num_part >> 22;
 
501
  uint num= num_part & 0x3FFFFF;
497
502
  if (part == expected_part)
498
503
    if (num == expected_num)
499
504
      return false;
505
510
 
506
511
void perform_insert(QUEUE *queue)
507
512
{
508
 
  uint32_t i= 1, no_parts= tot_no_parts;
509
 
  uint32_t backward_start= 0;
 
513
  uint i= 1, no_parts= tot_no_parts;
 
514
  uint backward_start= 0;
510
515
 
511
516
  expected_part= 1;
512
517
  expected_num= 1;
516
521
 
517
522
  do
518
523
  {
519
 
    uint32_t num= (i + backward_start);
 
524
    uint num= (i + backward_start);
520
525
    if (max_ind)
521
526
    {
522
527
      while (!is_divisible_by(num, i))
530
535
    }
531
536
    num_array[i]= num + (i << 22);
532
537
    if (fix_used)
533
 
      queue_element(queue, i-1)= (unsigned char*)&num_array[i];
 
538
      queue_element(queue, i-1)= (uchar*)&num_array[i];
534
539
    else
535
 
      queue_insert(queue, (unsigned char*)&num_array[i]);
 
540
      queue_insert(queue, (uchar*)&num_array[i]);
536
541
  } while (++i <= no_parts);
537
542
  if (fix_used)
538
543
  {
543
548
 
544
549
bool perform_ins_del(QUEUE *queue, bool max_ind)
545
550
{
546
 
  uint32_t i= 0, no_loops= tot_no_loops, j= tot_no_parts;
 
551
  uint i= 0, no_loops= tot_no_loops, j= tot_no_parts;
547
552
  do
548
553
  {
549
 
    uint32_t num_part= *(uint*)queue_top(queue);
550
 
    uint32_t part= num_part >> 22;
 
554
    uint num_part= *(uint*)queue_top(queue);
 
555
    uint part= num_part >> 22;
551
556
    if (check_num(num_part))
552
557
      return true;
553
558
    if (j++ >= no_loops)
562
567
        num_array[part]-= part;
563
568
      else
564
569
        num_array[part]+= part;
565
 
      queue_top(queue)= (unsigned char*)&num_array[part];
 
570
      queue_top(queue)= (uchar*)&num_array[part];
566
571
      queue_replaced(queue);
567
572
    }
568
573
  } while (++i < no_loops);
569
574
  return false;
570
575
}
571
576
 
572
 
bool do_test(uint32_t no_parts, uint32_t l_max_ind, bool l_fix_used)
 
577
bool do_test(uint no_parts, uint l_max_ind, bool l_fix_used)
573
578
{
574
579
  QUEUE queue;
575
580
  bool result;
597
602
static void stop_measurement()
598
603
{
599
604
  uint64_t stop_time= my_getsystime();
600
 
  uint32_t time_in_micros;
 
605
  uint time_in_micros;
601
606
  stop_time-= start_time;
602
607
  stop_time/= 10; /* Convert to microseconds */
603
608
  time_in_micros= (uint)stop_time;
608
613
{
609
614
  QUEUE queue_real;
610
615
  QUEUE *queue= &queue_real;
611
 
  uint32_t i, add;
 
616
  uint i, add;
612
617
  fix_used= true;
613
618
  max_ind= false;
614
619
  tot_no_parts= 1024;
649
654
  perform_insert(queue);
650
655
  for (i= 0; i < 65536; i++)
651
656
  {
652
 
    uint32_t num, part;
 
657
    uint num, part;
653
658
    num= *(uint*)queue_top(queue);
654
659
    num+= 16;
655
660
    part= num >> 22;
656
661
    num_array[part]= num;
657
 
    queue_top(queue)= (unsigned char*)&num_array[part];
 
662
    queue_top(queue)= (uchar*)&num_array[part];
658
663
    queue_replaced(queue);
659
664
  }
660
665
  for (i= 0; i < 16; i++)