~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/queues.cc

Merged from Toru - removal of my_time_t.

Show diffs side-by-side

added added

removed removed

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