« back to all changes in this revision
Viewing changes to mysys/my_tree.cc
- browse files at revision 1130.3.20
- compare with another revision
- compare with revision 1130.2.15
- download diff
- download tarball
- view history from revision 1130.3.20
- Committer: Monty Taylor
- Date: 2009-10-06 19:14:39 UTC
- mfrom: (1130.2.18 plugin-base-class)
- mto: This revision was merged to the branch mainline in revision 1184.
- Revision ID: mordred@inaugust.com-20091006191439-fd1vvlp22654l3k3
Merged latest plugin-base-class.
- files added:
- plugin/multi_thread/multi_thread.h
- plugin/sleep
- tests/suite/sleep
- tests/suite/sleep/r
- tests/suite/sleep/t
- files renamed:
- mysys/tree.cc => mysys/my_tree.cc
- files modified:
- Makefile.am
added
removed
mysys/my_tree.cc
75
75
76
76
77
77
void init_tree(TREE *tree, uint32_t default_alloc_size, uint32_t memory_limit,
78
int size, qsort_cmp2 compare, bool with_delete,
78
uint32_t size, qsort_cmp2 compare, bool with_delete,
79
79
tree_element_free free_element, void *custom_arg)
80
80
{
81
81
if (default_alloc_size < DEFAULT_ALLOC_SIZE)
83
83
default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
84
84
memset(&tree->null_element, 0, sizeof(tree->null_element));
85
85
tree->root= &tree->null_element;
86
tree->compare=compare;
87
tree->size_of_element=size > 0 ? (uint32_t) size : 0;
88
tree->memory_limit=memory_limit;
89
tree->free=free_element;
90
tree->allocated=0;
91
tree->elements_in_tree=0;
86
tree->compare= compare;
87
tree->size_of_element= size > 0 ? (uint32_t) size : 0;
88
tree->memory_limit= memory_limit;
89
tree->free= free_element;
90
tree->allocated= 0;
91
tree->elements_in_tree= 0;
92
92
tree->custom_arg = custom_arg;
93
tree->null_element.colour=BLACK;
94
tree->null_element.left=tree->null_element.right=0;
93
tree->null_element.colour= BLACK;
94
tree->null_element.left=tree->null_element.right= 0;
95
95
tree->flag= 0;
96
if (!free_element && size >= 0 &&
97
((uint32_t) size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
96
if (!free_element &&
97
(size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
98
98
{
99
99
/*
100
100
We know that the data doesn't have to be aligned (like if the key
101
101
contains a double), so we can store the data combined with the
102
102
TREE_ELEMENT.
103
103
*/
104
tree->offset_to_key=sizeof(TREE_ELEMENT); /* Put key after element */
104
tree->offset_to_key= sizeof(TREE_ELEMENT); /* Put key after element */
105
105
/* Fix allocation size so that we don't lose any memory */
106
default_alloc_size/=(sizeof(TREE_ELEMENT)+size);
106
default_alloc_size/= (sizeof(TREE_ELEMENT)+size);
107
107
if (!default_alloc_size)
108
default_alloc_size=1;
109
default_alloc_size*=(sizeof(TREE_ELEMENT)+size);
108
default_alloc_size= 1;
109
default_alloc_size*= (sizeof(TREE_ELEMENT)+size);
110
110
}
111
111
else
112
112
{
113
tree->offset_to_key=0; /* use key through pointer */
114
tree->size_of_element+=sizeof(void*);
113
tree->offset_to_key= 0; /* use key through pointer */
114
tree->size_of_element+= sizeof(void*);
115
115
}
116
if (!(tree->with_delete=with_delete))
116
if (! (tree->with_delete= with_delete))
117
117
{
118
118
init_alloc_root(&tree->mem_root, (uint32_t) default_alloc_size, 0);
119
tree->mem_root.min_malloc=(sizeof(TREE_ELEMENT)+tree->size_of_element);
119
tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
120
120
}
121
return;
122
121
}
123
122
124
123
static void free_tree(TREE *tree, myf free_flags)
141
140
}
142
141
}
143
142
tree->root= &tree->null_element;
144
tree->elements_in_tree=0;
145
tree->allocated=0;
146
147
return;
143
tree->elements_in_tree= 0;
144
tree->allocated= 0;
148
145
}
149
146
150
147
void delete_tree(TREE* tree)
206
203
}
207
204
if (element == &tree->null_element)
208
205
{
209
uint32_t alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
210
tree->allocated+=alloc_size;
206
size_t alloc_size= sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
207
tree->allocated+= alloc_size;
211
208
212
209
if (tree->memory_limit && tree->elements_in_tree
213
210
&& tree->allocated > tree->memory_limit)
216
213
return tree_insert(tree, key, key_size, custom_arg);
217
214
}
218
215
219
key_size+=tree->size_of_element;
216
key_size+= tree->size_of_element;
220
217
if (tree->with_delete)
221
element=(TREE_ELEMENT *) malloc(alloc_size);
218
element= (TREE_ELEMENT *) malloc(alloc_size);
222
219
else
223
element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
220
element= (TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
224
221
if (!element)
225
222
return(NULL);
226
**parent=element;
227
element->left=element->right= &tree->null_element;
223
**parent= element;
224
element->left= element->right= &tree->null_element;
228
225
if (!tree->offset_to_key)
229
226
{
230
227
if (key_size == sizeof(void*)) /* no length, save pointer */
231
*((void**) (element+1))=key;
228
*((void**) (element+1))= key;
232
229
else
233
230
{
234
231
*((void**) (element+1))= (void*) ((void **) (element+1)+1);
237
234
}
238
235
else
239
236
memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
240
element->count=1; /* May give warning in purify */
237
element->count= 1; /* May give warning in purify */
241
238
tree->elements_in_tree++;
242
239
rb_insert(tree,parent,element); /* rebalance tree */
243
240
}
250
247
if (! element->count)
251
248
element->count--;
252
249
}
250
253
251
return element;
254
252
}
255
253
256
254
int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
257
255
{
258
int cmp,remove_colour;
256
int remove_colour;
259
257
TREE_ELEMENT *element,***parent, ***org_parent, *nod;
260
258
if (!tree->with_delete)
261
259
return 1; /* not allowed */
264
262
*parent= &tree->root; element= tree->root;
265
263
for (;;)
266
264
{
265
int cmp;
266
267
267
if (element == &tree->null_element)
268
268
return 1; /* Was not in tree */
269
269
if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
280
280
}
281
281
if (element->left == &tree->null_element)
282
282
{
283
(**parent)=element->right;
283
(**parent)= element->right;
284
284
remove_colour= element->colour;
285
285
}
286
286
else if (element->right == &tree->null_element)
287
287
{
288
(**parent)=element->left;
288
(**parent)= element->left;
289
289
remove_colour= element->colour;
290
290
}
291
291
else
296
296
{
297
297
*++parent= &nod->left; nod= nod->left;
298
298
}
299
(**parent)=nod->right; /* unlink nod from tree */
299
(**parent)= nod->right; /* unlink nod from tree */
300
300
remove_colour= nod->colour;
301
org_parent[0][0]=nod; /* put y in place of element */
301
org_parent[0][0]= nod; /* put y in place of element */
302
302
org_parent[1]= &nod->right;
303
nod->left=element->left;
304
nod->right=element->right;
305
nod->colour=element->colour;
303
nod->left= element->left;
304
nod->right= element->right;
305
nod->colour= element->colour;
306
306
}
307
307
if (remove_colour == BLACK)
308
308
rb_delete_fixup(tree,parent);
311
311
tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
312
312
free((unsigned char*) element);
313
313
tree->elements_in_tree--;
314
314
315
return 0;
315
316
}
316
317
318
319
void *tree_search(TREE *tree, void *key, void *custom_arg)
319
320
{
320
321
int cmp;
321
TREE_ELEMENT *element=tree->root;
322
TREE_ELEMENT *element= tree->root;
322
323
323
324
for (;;)
324
325
{
325
326
if (element == &tree->null_element)
326
327
return (void*) 0;
327
if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
328
key)) == 0)
328
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
329
key)) == 0)
329
330
return ELEMENT_KEY(tree,element);
330
331
if (cmp < 0)
331
element=element->right;
332
element= element->right;
332
333
else
333
element=element->left;
334
element= element->left;
334
335
}
335
336
}
336
337
338
339
TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
339
340
enum ha_rkey_function flag, void *custom_arg)
340
341
{
341
int cmp;
342
342
TREE_ELEMENT *element= tree->root;
343
343
TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
344
344
TREE_ELEMENT **last_equal_element= NULL;
350
350
*parents = &tree->null_element;
351
351
while (element != &tree->null_element)
352
352
{
353
int cmp;
354
353
355
*++parents= element;
356
354
357
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
355
358
key)) == 0)
356
359
{
404
407
default:
405
408
return NULL;
406
409
}
410
407
411
return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
408
412
}
409
413
461
465
ha_rows tree_record_pos(TREE *tree, const void *key,
462
466
enum ha_rkey_function flag, void *custom_arg)
463
467
{
464
int cmp;
465
468
TREE_ELEMENT *element= tree->root;
466
469
double left= 1;
467
470
double right= tree->elements_in_tree;
468
471
469
472
while (element != &tree->null_element)
470
473
{
474
int cmp;
475
471
476
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
472
477
key)) == 0)
473
478
{
494
499
right= (left + right) / 2;
495
500
}
496
501
}
502
497
503
switch (flag) {
498
504
case HA_READ_KEY_EXACT:
499
505
case HA_READ_BEFORE_KEY:
513
519
case right_root_left:
514
520
return tree_walk_right_root_left(tree,tree->root,action,argument);
515
521
}
522
516
523
return 0; /* Keep gcc happy */
517
524
}
518
525
529
536
error=tree_walk_left_root_right(tree,element->right,action,argument);
530
537
return error;
531
538
}
539
532
540
return 0;
533
541
}
534
542
545
553
error=tree_walk_right_root_left(tree,element->left,action,argument);
546
554
return error;
547
555
}
556
548
557
return 0;
549
558
}
550
559
551
560
552
/* Functions to fix up the tree after insert and delete */
561
/* Functions to fix up the tree after insert and delete */
553
562
554
563
static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
555
564
{
556
565
TREE_ELEMENT *y;
557
566
558
y=leaf->right;
559
leaf->right=y->left;
560
parent[0]=y;
561
y->left=leaf;
567
y= leaf->right;
568
leaf->right= y->left;
569
parent[0]= y;
570
y->left= leaf;
562
571
}
563
572
564
573
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
565
574
{
566
575
TREE_ELEMENT *x;
567
576
568
x=leaf->left;
569
leaf->left=x->right;
570
parent[0]=x;
571
x->right=leaf;
577
x= leaf->left;
578
leaf->left= x->right;
579
parent[0]= x;
580
x->right= leaf;
572
581
}
573
582
574
583
static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
583
592
y= par2->right;
584
593
if (y->colour == RED)
585
594
{
586
par->colour=BLACK;
587
y->colour=BLACK;
588
leaf=par2;
589
parent-=2;
590
leaf->colour=RED; /* And the loop continues */
595
par->colour= BLACK;
596
y->colour= BLACK;
597
leaf= par2;
598
parent-= 2;
599
leaf->colour= RED; /* And the loop continues */
591
600
}
592
601
else
593
602
{
594
603
if (leaf == par->right)
595
604
{
596
605
left_rotate(parent[-1],par);
597
par=leaf; /* leaf is now parent to old leaf */
606
par= leaf; /* leaf is now parent to old leaf */
598
607
}
599
par->colour=BLACK;
600
par2->colour=RED;
608
par->colour= BLACK;
609
par2->colour= RED;
601
610
right_rotate(parent[-2],par2);
602
611
break;
603
612
}
607
616
y= par2->left;
608
617
if (y->colour == RED)
609
618
{
610
par->colour=BLACK;
611
y->colour=BLACK;
612
leaf=par2;
613
parent-=2;
614
leaf->colour=RED; /* And the loop continues */
619
par->colour= BLACK;
620
y->colour= BLACK;
621
leaf= par2;
622
parent-= 2;
623
leaf->colour= RED; /* And the loop continues */
615
624
}
616
625
else
617
626
{
618
627
if (leaf == par->left)
619
628
{
620
629
right_rotate(parent[-1],par);
621
par=leaf;
630
par= leaf;
622
631
}
623
par->colour=BLACK;
624
par2->colour=RED;
632
par->colour= BLACK;
633
par2->colour= RED;
625
634
left_rotate(parent[-2],par2);
626
635
break;
627
636
}
639
648
{
640
649
if (x == (par=parent[-1][0])->left)
641
650
{
642
w=par->right;
651
w= par->right;
643
652
if (w->colour == RED)
644
653
{
645
w->colour=BLACK;
646
par->colour=RED;
654
w->colour= BLACK;
655
par->colour= RED;
647
656
left_rotate(parent[-1],par);
648
657
parent[0]= &w->left;
649
658
*++parent= &par->left;
650
w=par->right;
659
w= par->right;
651
660
}
652
661
if (w->left->colour == BLACK && w->right->colour == BLACK)
653
662
{
654
w->colour=RED;
655
x=par;
663
w->colour= RED;
664
x= par;
656
665
parent--;
657
666
}
658
667
else
659
668
{
660
669
if (w->right->colour == BLACK)
661
670
{
662
w->left->colour=BLACK;
663
w->colour=RED;
671
w->left->colour= BLACK;
672
w->colour= RED;
664
673
right_rotate(&par->right,w);
665
w=par->right;
674
w= par->right;
666
675
}
667
w->colour=par->colour;
668
par->colour=BLACK;
669
w->right->colour=BLACK;
676
w->colour= par->colour;
677
par->colour= BLACK;
678
w->right->colour= BLACK;
670
679
left_rotate(parent[-1],par);
671
x=tree->root;
680
x= tree->root;
672
681
break;
673
682
}
674
683
}
677
686
w=par->left;
678
687
if (w->colour == RED)
679
688
{
680
w->colour=BLACK;
681
par->colour=RED;
689
w->colour= BLACK;
690
par->colour= RED;
682
691
right_rotate(parent[-1],par);
683
692
parent[0]= &w->right;
684
693
*++parent= &par->right;
685
w=par->left;
694
w= par->left;
686
695
}
687
696
if (w->right->colour == BLACK && w->left->colour == BLACK)
688
697
{
689
w->colour=RED;
690
x=par;
698
w->colour= RED;
699
x= par;
691
700
parent--;
692
701
}
693
702
else
694
703
{
695
704
if (w->left->colour == BLACK)
696
705
{
697
w->right->colour=BLACK;
698
w->colour=RED;
706
w->right->colour= BLACK;
707
w->colour= RED;
699
708
left_rotate(&par->left,w);
700
w=par->left;
709
w= par->left;
701
710
}
702
w->colour=par->colour;
703
par->colour=BLACK;
704
w->left->colour=BLACK;
711
w->colour= par->colour;
712
par->colour= BLACK;
713
w->left->colour= BLACK;
705
714
right_rotate(parent[-1],par);
706
x=tree->root;
715
x= tree->root;
707
716
break;
708
717
}
709
718
}
710
719
}
711
x->colour=BLACK;
720
x->colour= BLACK;
712
721
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1