« back to all changes in this revision
Viewing changes to drizzled/tree.cc
- browse files at revision 1410.4.2
- compare with another revision
- compare with revision 1840.1.3
- download diff
- download tarball
- view history from revision 1410.4.2
- Committer: Djellel E. Difallah
- Date: 2010-03-30 07:41:39 UTC
- mto: (1410.3.4 ded_rm_my)
- mto: This revision was merged to the branch mainline in revision 1440.
- Revision ID: ded@ubuntu-20100330074139-a3twb05p1fmvg0gk
removing my
added
removed
drizzled/tree.cc
1
/* Copyright (C) 2000 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 handling red-black (balanced) binary trees.
18
key in tree is allocated accrding to following:
19
20
1) If size < 0 then tree will not allocate keys and only a pointer to
21
each key is saved in tree.
22
compare and search functions uses and returns key-pointer
23
24
2) If size == 0 then there are two options:
25
- key_size != 0 to tree_insert: The key will be stored in the tree.
26
- key_size == 0 to tree_insert: A pointer to the key is stored.
27
compare and search functions uses and returns key-pointer.
28
29
3) if key_size is given to init_tree then each node will continue the
30
key and calls to insert_key may increase length of key.
31
if key_size > sizeof(pointer) and key_size is a multiple of 8 (double
32
allign) then key will be put on a 8 alligned adress. Else
33
the key will be on adress (element+1). This is transparent for user
34
compare and search functions uses a pointer to given key-argument.
35
36
- If you use a free function for tree-elements and you are freeing
37
the element itself, you should use key_size = 0 to init_tree and
38
tree_search
39
40
The actual key in TREE_ELEMENT is saved as a pointer or after the
41
TREE_ELEMENT struct.
42
If one uses only pointers in tree one can use tree_set_pointer() to
43
change address of data.
44
45
Implemented by monty.
46
*/
47
48
/*
49
NOTE:
50
tree->compare function should be ALWAYS called as
51
(*tree->compare)(custom_arg, ELEMENT_KEY(tree,element), key)
52
and not other way around, as
53
(*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
54
*/
55
56
#include "config.h"
57
58
#include "drizzled/tree.h"
59
#include "drizzled/internal/my_sys.h"
60
#include "drizzled/internal/m_string.h"
61
#include "drizzled/memory/root.h"
62
63
#define BLACK 1
64
#define RED 0
65
#define DEFAULT_ALLOC_SIZE 8192
66
#define DEFAULT_ALIGN_SIZE 8192
67
68
#define ELEMENT_KEY(tree,element)\
69
(tree->offset_to_key ? (void*)((unsigned char*) element+tree->offset_to_key) :\
70
*((void**) (element+1)))
71
#define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
72
73
namespace drizzled
74
{
75
76
77
static void delete_tree_element(TREE *,TREE_ELEMENT *);
78
static int tree_walk_left_root_right(TREE *,TREE_ELEMENT *,
79
tree_walk_action,void *);
80
static int tree_walk_right_root_left(TREE *,TREE_ELEMENT *,
81
tree_walk_action,void *);
82
static void left_rotate(TREE_ELEMENT **parent,TREE_ELEMENT *leaf);
83
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
84
static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
85
TREE_ELEMENT *leaf);
86
static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
87
88
89
void init_tree(TREE *tree, size_t default_alloc_size, uint32_t memory_limit,
90
uint32_t size, qsort_cmp2 compare, bool with_delete,
91
tree_element_free free_element, void *custom_arg)
92
{
93
if (default_alloc_size < DEFAULT_ALLOC_SIZE)
94
default_alloc_size= DEFAULT_ALLOC_SIZE;
95
default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
96
memset(&tree->null_element, 0, sizeof(tree->null_element));
97
tree->root= &tree->null_element;
98
tree->compare= compare;
99
tree->size_of_element= size > 0 ? (uint32_t) size : 0;
100
tree->memory_limit= memory_limit;
101
tree->free= free_element;
102
tree->allocated= 0;
103
tree->elements_in_tree= 0;
104
tree->custom_arg = custom_arg;
105
tree->null_element.colour= BLACK;
106
tree->null_element.left=tree->null_element.right= 0;
107
tree->flag= 0;
108
if (!free_element &&
109
(size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
110
{
111
/*
112
We know that the data doesn't have to be aligned (like if the key
113
contains a double), so we can store the data combined with the
114
TREE_ELEMENT.
115
*/
116
tree->offset_to_key= sizeof(TREE_ELEMENT); /* Put key after element */
117
/* Fix allocation size so that we don't lose any memory */
118
default_alloc_size/= (sizeof(TREE_ELEMENT)+size);
119
if (!default_alloc_size)
120
default_alloc_size= 1;
121
default_alloc_size*= (sizeof(TREE_ELEMENT)+size);
122
}
123
else
124
{
125
tree->offset_to_key= 0; /* use key through pointer */
126
tree->size_of_element+= sizeof(void*);
127
}
128
if (! (tree->with_delete= with_delete))
129
{
130
init_alloc_root(&tree->mem_root, default_alloc_size);
131
tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
132
}
133
}
134
135
static void free_tree(TREE *tree, myf free_flags)
136
{
137
if (tree->root) /* If initialized */
138
{
139
if (tree->with_delete)
140
delete_tree_element(tree,tree->root);
141
else
142
{
143
if (tree->free)
144
{
145
if (tree->memory_limit)
146
(*tree->free)(NULL, free_init, tree->custom_arg);
147
delete_tree_element(tree,tree->root);
148
if (tree->memory_limit)
149
(*tree->free)(NULL, free_end, tree->custom_arg);
150
}
151
free_root(&tree->mem_root, free_flags);
152
}
153
}
154
tree->root= &tree->null_element;
155
tree->elements_in_tree= 0;
156
tree->allocated= 0;
157
}
158
159
void delete_tree(TREE* tree)
160
{
161
free_tree(tree, MYF(0)); /* free() mem_root if applicable */
162
}
163
164
void reset_tree(TREE* tree)
165
{
166
/* do not free mem_root, just mark blocks as free */
167
free_tree(tree, MYF(memory::MARK_BLOCKS_FREE));
168
}
169
170
171
static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
172
{
173
if (element != &tree->null_element)
174
{
175
delete_tree_element(tree,element->left);
176
if (tree->free)
177
(*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
178
delete_tree_element(tree,element->right);
179
if (tree->with_delete)
180
free((char*) element);
181
}
182
}
183
184
185
/*
186
insert, search and delete of elements
187
188
The following should be true:
189
parent[0] = & parent[-1][0]->left ||
190
parent[0] = & parent[-1][0]->right
191
*/
192
193
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size,
194
void* custom_arg)
195
{
196
int cmp;
197
TREE_ELEMENT *element,***parent;
198
199
parent= tree->parents;
200
*parent = &tree->root; element= tree->root;
201
for (;;)
202
{
203
if (element == &tree->null_element ||
204
(cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
205
key)) == 0)
206
break;
207
if (cmp < 0)
208
{
209
*++parent= &element->right; element= element->right;
210
}
211
else
212
{
213
*++parent = &element->left; element= element->left;
214
}
215
}
216
if (element == &tree->null_element)
217
{
218
size_t alloc_size= sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
219
tree->allocated+= alloc_size;
220
221
if (tree->memory_limit && tree->elements_in_tree
222
&& tree->allocated > tree->memory_limit)
223
{
224
reset_tree(tree);
225
return tree_insert(tree, key, key_size, custom_arg);
226
}
227
228
key_size+= tree->size_of_element;
229
if (tree->with_delete)
230
element= (TREE_ELEMENT *) malloc(alloc_size);
231
else
232
element= (TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
233
if (!element)
234
return(NULL);
235
**parent= element;
236
element->left= element->right= &tree->null_element;
237
if (!tree->offset_to_key)
238
{
239
if (key_size == sizeof(void*)) /* no length, save pointer */
240
*((void**) (element+1))= key;
241
else
242
{
243
*((void**) (element+1))= (void*) ((void **) (element+1)+1);
244
memcpy(*((void **) (element+1)),key, key_size - sizeof(void*));
245
}
246
}
247
else
248
memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
249
element->count= 1; /* May give warning in purify */
250
tree->elements_in_tree++;
251
rb_insert(tree,parent,element); /* rebalance tree */
252
}
253
else
254
{
255
if (tree->flag & TREE_NO_DUPS)
256
return(NULL);
257
element->count++;
258
/* Avoid a wrap over of the count. */
259
if (! element->count)
260
element->count--;
261
}
262
263
return element;
264
}
265
266
int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
267
{
268
int remove_colour;
269
TREE_ELEMENT *element,***parent, ***org_parent, *nod;
270
if (!tree->with_delete)
271
return 1; /* not allowed */
272
273
parent= tree->parents;
274
*parent= &tree->root; element= tree->root;
275
for (;;)
276
{
277
int cmp;
278
279
if (element == &tree->null_element)
280
return 1; /* Was not in tree */
281
if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
282
key)) == 0)
283
break;
284
if (cmp < 0)
285
{
286
*++parent= &element->right; element= element->right;
287
}
288
else
289
{
290
*++parent = &element->left; element= element->left;
291
}
292
}
293
if (element->left == &tree->null_element)
294
{
295
(**parent)= element->right;
296
remove_colour= element->colour;
297
}
298
else if (element->right == &tree->null_element)
299
{
300
(**parent)= element->left;
301
remove_colour= element->colour;
302
}
303
else
304
{
305
org_parent= parent;
306
*++parent= &element->right; nod= element->right;
307
while (nod->left != &tree->null_element)
308
{
309
*++parent= &nod->left; nod= nod->left;
310
}
311
(**parent)= nod->right; /* unlink nod from tree */
312
remove_colour= nod->colour;
313
org_parent[0][0]= nod; /* put y in place of element */
314
org_parent[1]= &nod->right;
315
nod->left= element->left;
316
nod->right= element->right;
317
nod->colour= element->colour;
318
}
319
if (remove_colour == BLACK)
320
rb_delete_fixup(tree,parent);
321
if (tree->free)
322
(*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
323
tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
324
free((unsigned char*) element);
325
tree->elements_in_tree--;
326
327
return 0;
328
}
329
330
void *tree_search_key(TREE *tree, const void *key,
331
TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
332
enum ha_rkey_function flag, void *custom_arg)
333
{
334
TREE_ELEMENT *element= tree->root;
335
TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
336
TREE_ELEMENT **last_equal_element= NULL;
337
338
/*
339
TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
340
*/
341
342
*parents = &tree->null_element;
343
while (element != &tree->null_element)
344
{
345
int cmp;
346
347
*++parents= element;
348
349
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
350
key)) == 0)
351
{
352
switch (flag) {
353
case HA_READ_KEY_EXACT:
354
case HA_READ_KEY_OR_NEXT:
355
case HA_READ_BEFORE_KEY:
356
last_equal_element= parents;
357
cmp= 1;
358
break;
359
case HA_READ_AFTER_KEY:
360
cmp= -1;
361
break;
362
case HA_READ_PREFIX_LAST:
363
case HA_READ_PREFIX_LAST_OR_PREV:
364
last_equal_element= parents;
365
cmp= -1;
366
break;
367
default:
368
return NULL;
369
}
370
}
371
if (cmp < 0) /* element < key */
372
{
373
last_right_step_parent= parents;
374
element= element->right;
375
}
376
else
377
{
378
last_left_step_parent= parents;
379
element= element->left;
380
}
381
}
382
switch (flag) {
383
case HA_READ_KEY_EXACT:
384
case HA_READ_PREFIX_LAST:
385
*last_pos= last_equal_element;
386
break;
387
case HA_READ_KEY_OR_NEXT:
388
*last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
389
break;
390
case HA_READ_AFTER_KEY:
391
*last_pos= last_left_step_parent;
392
break;
393
case HA_READ_PREFIX_LAST_OR_PREV:
394
*last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
395
break;
396
case HA_READ_BEFORE_KEY:
397
*last_pos= last_right_step_parent;
398
break;
399
default:
400
return NULL;
401
}
402
403
return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
404
}
405
406
/*
407
Search first (the most left) or last (the most right) tree element
408
*/
409
void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
410
TREE_ELEMENT ***last_pos, int child_offs)
411
{
412
TREE_ELEMENT *element= tree->root;
413
414
*parents= &tree->null_element;
415
while (element != &tree->null_element)
416
{
417
*++parents= element;
418
element= ELEMENT_CHILD(element, child_offs);
419
}
420
*last_pos= parents;
421
return **last_pos != &tree->null_element ?
422
ELEMENT_KEY(tree, **last_pos) : NULL;
423
}
424
425
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
426
int r_offs)
427
{
428
TREE_ELEMENT *x= **last_pos;
429
430
if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
431
{
432
x= ELEMENT_CHILD(x, r_offs);
433
*++*last_pos= x;
434
while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
435
{
436
x= ELEMENT_CHILD(x, l_offs);
437
*++*last_pos= x;
438
}
439
return ELEMENT_KEY(tree, x);
440
}
441
else
442
{
443
TREE_ELEMENT *y= *--*last_pos;
444
while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
445
{
446
x= y;
447
y= *--*last_pos;
448
}
449
return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
450
}
451
}
452
453
/*
454
Expected that tree is fully balanced
455
(each path from root to leaf has the same length)
456
*/
457
ha_rows tree_record_pos(TREE *tree, const void *key,
458
enum ha_rkey_function flag, void *custom_arg)
459
{
460
TREE_ELEMENT *element= tree->root;
461
double left= 1;
462
double right= tree->elements_in_tree;
463
464
while (element != &tree->null_element)
465
{
466
int cmp;
467
468
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
469
key)) == 0)
470
{
471
switch (flag) {
472
case HA_READ_KEY_EXACT:
473
case HA_READ_BEFORE_KEY:
474
cmp= 1;
475
break;
476
case HA_READ_AFTER_KEY:
477
cmp= -1;
478
break;
479
default:
480
return HA_POS_ERROR;
481
}
482
}
483
if (cmp < 0) /* element < key */
484
{
485
element= element->right;
486
left= (left + right) / 2;
487
}
488
else
489
{
490
element= element->left;
491
right= (left + right) / 2;
492
}
493
}
494
495
switch (flag) {
496
case HA_READ_KEY_EXACT:
497
case HA_READ_BEFORE_KEY:
498
return (ha_rows) right;
499
case HA_READ_AFTER_KEY:
500
return (ha_rows) left;
501
default:
502
return HA_POS_ERROR;
503
}
504
}
505
506
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
507
{
508
switch (visit) {
509
case left_root_right:
510
return tree_walk_left_root_right(tree,tree->root,action,argument);
511
case right_root_left:
512
return tree_walk_right_root_left(tree,tree->root,action,argument);
513
}
514
515
return 0; /* Keep gcc happy */
516
}
517
518
static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
519
{
520
int error;
521
if (element->left) /* Not null_element */
522
{
523
if ((error=tree_walk_left_root_right(tree,element->left,action,
524
argument)) == 0 &&
525
(error=(*action)(ELEMENT_KEY(tree,element),
526
element->count,
527
argument)) == 0)
528
error=tree_walk_left_root_right(tree,element->right,action,argument);
529
return error;
530
}
531
532
return 0;
533
}
534
535
static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
536
{
537
int error;
538
if (element->right) /* Not null_element */
539
{
540
if ((error=tree_walk_right_root_left(tree,element->right,action,
541
argument)) == 0 &&
542
(error=(*action)(ELEMENT_KEY(tree,element),
543
element->count,
544
argument)) == 0)
545
error=tree_walk_right_root_left(tree,element->left,action,argument);
546
return error;
547
}
548
549
return 0;
550
}
551
552
553
/* Functions to fix up the tree after insert and delete */
554
555
static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
556
{
557
TREE_ELEMENT *y;
558
559
y= leaf->right;
560
leaf->right= y->left;
561
parent[0]= y;
562
y->left= leaf;
563
}
564
565
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
566
{
567
TREE_ELEMENT *x;
568
569
x= leaf->left;
570
leaf->left= x->right;
571
parent[0]= x;
572
x->right= leaf;
573
}
574
575
static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
576
{
577
TREE_ELEMENT *y,*par,*par2;
578
579
leaf->colour=RED;
580
while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
581
{
582
if (par == (par2=parent[-2][0])->left)
583
{
584
y= par2->right;
585
if (y->colour == RED)
586
{
587
par->colour= BLACK;
588
y->colour= BLACK;
589
leaf= par2;
590
parent-= 2;
591
leaf->colour= RED; /* And the loop continues */
592
}
593
else
594
{
595
if (leaf == par->right)
596
{
597
left_rotate(parent[-1],par);
598
par= leaf; /* leaf is now parent to old leaf */
599
}
600
par->colour= BLACK;
601
par2->colour= RED;
602
right_rotate(parent[-2],par2);
603
break;
604
}
605
}
606
else
607
{
608
y= par2->left;
609
if (y->colour == RED)
610
{
611
par->colour= BLACK;
612
y->colour= BLACK;
613
leaf= par2;
614
parent-= 2;
615
leaf->colour= RED; /* And the loop continues */
616
}
617
else
618
{
619
if (leaf == par->left)
620
{
621
right_rotate(parent[-1],par);
622
par= leaf;
623
}
624
par->colour= BLACK;
625
par2->colour= RED;
626
left_rotate(parent[-2],par2);
627
break;
628
}
629
}
630
}
631
tree->root->colour=BLACK;
632
}
633
634
static void rb_delete_fixup(TREE *tree, TREE_ELEMENT ***parent)
635
{
636
TREE_ELEMENT *x,*w,*par;
637
638
x= **parent;
639
while (x != tree->root && x->colour == BLACK)
640
{
641
if (x == (par=parent[-1][0])->left)
642
{
643
w= par->right;
644
if (w->colour == RED)
645
{
646
w->colour= BLACK;
647
par->colour= RED;
648
left_rotate(parent[-1],par);
649
parent[0]= &w->left;
650
*++parent= &par->left;
651
w= par->right;
652
}
653
if (w->left->colour == BLACK && w->right->colour == BLACK)
654
{
655
w->colour= RED;
656
x= par;
657
parent--;
658
}
659
else
660
{
661
if (w->right->colour == BLACK)
662
{
663
w->left->colour= BLACK;
664
w->colour= RED;
665
right_rotate(&par->right,w);
666
w= par->right;
667
}
668
w->colour= par->colour;
669
par->colour= BLACK;
670
w->right->colour= BLACK;
671
left_rotate(parent[-1],par);
672
x= tree->root;
673
break;
674
}
675
}
676
else
677
{
678
w=par->left;
679
if (w->colour == RED)
680
{
681
w->colour= BLACK;
682
par->colour= RED;
683
right_rotate(parent[-1],par);
684
parent[0]= &w->right;
685
*++parent= &par->right;
686
w= par->left;
687
}
688
if (w->right->colour == BLACK && w->left->colour == BLACK)
689
{
690
w->colour= RED;
691
x= par;
692
parent--;
693
}
694
else
695
{
696
if (w->left->colour == BLACK)
697
{
698
w->right->colour= BLACK;
699
w->colour= RED;
700
left_rotate(&par->left,w);
701
w= par->left;
702
}
703
w->colour= par->colour;
704
par->colour= BLACK;
705
w->left->colour= BLACK;
706
right_rotate(parent[-1],par);
707
x= tree->root;
708
break;
709
}
710
}
711
}
712
x->colour= BLACK;
713
}
714
715
} /* namespace drizzled */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1