« back to all changes in this revision
Viewing changes to storage/myisam/queues.cc
- browse files at revision 960.2.7
- compare with another revision
- download diff
- download tarball
- view history from revision 960.2.7
- Committer: Padraig O'Sullivan
- Date: 2009-03-21 23:23:07 UTC
- mto: (960.5.2 mordred)
- mto: This revision was merged to the branch mainline in revision 961.
- Revision ID: osullivan.padraig@gmail.com-20090321232307-ier1xqflczgp7r1v
Removed all traces of QUEUE from the codebase. We are using
std::priority_queue in MyISAM now.
std::priority_queue in MyISAM now.
- files removed:
- storage/myisam/queues.cc
- files modified:
- storage/myisam/Makefile.am
added
removed
storage/myisam/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/mysys_priv.h>
26
#include <mysys/mysys_err.h>
27
#include "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
Loggerhead is a web-based interface for Breezy
Version: 2.0.1