58
58
#include <drizzled/tree.h>
59
59
#include <drizzled/internal/my_sys.h>
60
60
#include <drizzled/internal/m_string.h>
61
#include <drizzled/memory/root.h>
65
64
#define DEFAULT_ALLOC_SIZE 8192
66
65
#define DEFAULT_ALIGN_SIZE 8192
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))
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,
86
static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
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)
72
* Tree class public methods
75
void Tree::init_tree(size_t default_alloc_size, uint32_t mem_limit,
76
uint32_t size, qsort_cmp2 compare_callback, bool free_with_tree,
77
tree_element_free free_callback, void *caller_arg)
93
79
if (default_alloc_size < DEFAULT_ALLOC_SIZE)
94
80
default_alloc_size= DEFAULT_ALLOC_SIZE;
95
81
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;
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;
82
memset(&this->null_element, 0, sizeof(this->null_element));
83
root= &this->null_element;
84
compare= compare_callback;
85
size_of_element= size > 0 ? (uint32_t) size : 0;
86
memory_limit= mem_limit;
90
custom_arg = caller_arg;
91
null_element.colour= BLACK;
92
null_element.left=this->null_element.right= 0;
109
95
(size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
112
98
We know that the data doesn't have to be aligned (like if the key
113
99
contains a double), so we can store the data combined with the
116
tree->offset_to_key= sizeof(TREE_ELEMENT); /* Put key after element */
102
offset_to_key= sizeof(Tree_Element); /* Put key after element */
117
103
/* Fix allocation size so that we don't lose any memory */
118
default_alloc_size/= (sizeof(TREE_ELEMENT)+size);
104
default_alloc_size/= (sizeof(Tree_Element)+size);
119
105
if (!default_alloc_size)
120
106
default_alloc_size= 1;
121
default_alloc_size*= (sizeof(TREE_ELEMENT)+size);
107
default_alloc_size*= (sizeof(Tree_Element)+size);
125
tree->offset_to_key= 0; /* use key through pointer */
126
tree->size_of_element+= sizeof(void*);
128
if (! (tree->with_delete= with_delete))
130
tree->mem_root.init_alloc_root(default_alloc_size);
131
tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
135
static void free_tree(TREE *tree, myf free_flags)
137
if (tree->root) /* If initialized */
139
if (tree->with_delete)
140
delete_tree_element(tree,tree->root);
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);
151
tree->mem_root.free_root(free_flags);
154
tree->root= &tree->null_element;
155
tree->elements_in_tree= 0;
159
void delete_tree(TREE* tree)
161
free_tree(tree, MYF(0)); /* free() mem_root if applicable */
164
void reset_tree(TREE* tree)
111
offset_to_key= 0; /* use key through pointer */
112
size_of_element+= sizeof(void*);
114
if (! (with_delete= free_with_tree))
116
mem_root.init(default_alloc_size);
117
mem_root.min_malloc= (sizeof(Tree_Element)+size_of_element);
121
void Tree::delete_tree()
123
free_tree(MYF(0)); /* free() mem_root if applicable */
126
void Tree::reset_tree()
166
128
/* do not free mem_root, just mark blocks as free */
167
free_tree(tree, MYF(memory::MARK_BLOCKS_FREE));
171
static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
173
if (element != &tree->null_element)
175
delete_tree_element(tree,element->left);
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);
186
insert, search and delete of elements
188
The following should be true:
189
parent[0] = & parent[-1][0]->left ||
190
parent[0] = & parent[-1][0]->right
193
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size,
129
free_tree(MYF(memory::MARK_BLOCKS_FREE));
132
Tree_Element* Tree::tree_insert(void* key, uint32_t key_size, void* caller_arg)
197
TREE_ELEMENT *element,***parent;
135
Tree_Element *element,***parent;
199
parent= tree->parents;
200
*parent = &tree->root; element= tree->root;
137
parent= this->parents;
138
*parent = &this->root; element= this->root;
203
if (element == &tree->null_element ||
204
(cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
141
if (element == &this->null_element ||
142
(cmp = (*compare)(caller_arg, element_key(element), key)) == 0)
266
int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
269
TREE_ELEMENT *element,***parent, ***org_parent, *nod;
270
if (!tree->with_delete)
271
return 1; /* not allowed */
273
parent= tree->parents;
274
*parent= &tree->root; element= tree->root;
279
if (element == &tree->null_element)
280
return 1; /* Was not in tree */
281
if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
286
*++parent= &element->right; element= element->right;
290
*++parent = &element->left; element= element->left;
293
if (element->left == &tree->null_element)
295
(**parent)= element->right;
296
remove_colour= element->colour;
298
else if (element->right == &tree->null_element)
300
(**parent)= element->left;
301
remove_colour= element->colour;
306
*++parent= &element->right; nod= element->right;
307
while (nod->left != &tree->null_element)
309
*++parent= &nod->left; nod= nod->left;
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;
319
if (remove_colour == BLACK)
320
rb_delete_fixup(tree,parent);
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--;
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)
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;
339
TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
342
*parents = &tree->null_element;
343
while (element != &tree->null_element)
349
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
353
case HA_READ_KEY_EXACT:
354
case HA_READ_KEY_OR_NEXT:
355
case HA_READ_BEFORE_KEY:
356
last_equal_element= parents;
359
case HA_READ_AFTER_KEY:
362
case HA_READ_PREFIX_LAST:
363
case HA_READ_PREFIX_LAST_OR_PREV:
364
last_equal_element= parents;
371
if (cmp < 0) /* element < key */
373
last_right_step_parent= parents;
374
element= element->right;
378
last_left_step_parent= parents;
379
element= element->left;
383
case HA_READ_KEY_EXACT:
384
case HA_READ_PREFIX_LAST:
385
*last_pos= last_equal_element;
387
case HA_READ_KEY_OR_NEXT:
388
*last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
390
case HA_READ_AFTER_KEY:
391
*last_pos= last_left_step_parent;
393
case HA_READ_PREFIX_LAST_OR_PREV:
394
*last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
396
case HA_READ_BEFORE_KEY:
397
*last_pos= last_right_step_parent;
403
return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
407
Search first (the most left) or last (the most right) tree element
409
void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
410
TREE_ELEMENT ***last_pos, int child_offs)
412
TREE_ELEMENT *element= tree->root;
414
*parents= &tree->null_element;
415
while (element != &tree->null_element)
418
element= ELEMENT_CHILD(element, child_offs);
421
return **last_pos != &tree->null_element ?
422
ELEMENT_KEY(tree, **last_pos) : NULL;
425
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
428
TREE_ELEMENT *x= **last_pos;
430
if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
432
x= ELEMENT_CHILD(x, r_offs);
434
while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
436
x= ELEMENT_CHILD(x, l_offs);
439
return ELEMENT_KEY(tree, x);
443
TREE_ELEMENT *y= *--*last_pos;
444
while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
449
return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
454
Expected that tree is fully balanced
455
(each path from root to leaf has the same length)
457
ha_rows tree_record_pos(TREE *tree, const void *key,
458
enum ha_rkey_function flag, void *custom_arg)
460
TREE_ELEMENT *element= tree->root;
462
double right= tree->elements_in_tree;
464
while (element != &tree->null_element)
468
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
472
case HA_READ_KEY_EXACT:
473
case HA_READ_BEFORE_KEY:
476
case HA_READ_AFTER_KEY:
483
if (cmp < 0) /* element < key */
485
element= element->right;
486
left= (left + right) / 2;
490
element= element->left;
491
right= (left + right) / 2;
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;
506
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK 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);
201
int Tree::tree_walk(tree_walk_action action, void *argument, TREE_WALK visit)
204
case left_root_right:
205
return tree_walk_left_root_right(root,action,argument);
206
case right_root_left:
207
return tree_walk_right_root_left(root,action,argument);
515
210
return 0; /* Keep gcc happy */
518
static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
214
* Tree class private methods
217
void Tree::free_tree(myf free_flags)
219
if (root) /* If initialized */
222
delete_tree_element(root);
228
(*free)(NULL, free_init, custom_arg);
229
delete_tree_element(root);
231
(*free)(NULL, free_end, custom_arg);
233
mem_root.free_root(free_flags);
241
void* Tree::element_key(Tree_Element* element)
243
return offset_to_key ? (void*)((unsigned char*) element + offset_to_key)
244
: *((void**)(element + 1));
247
void Tree::delete_tree_element(Tree_Element *element)
249
if (element != &null_element)
251
delete_tree_element(element->left);
253
(*free)(element_key(element), free_free, custom_arg);
254
delete_tree_element(element->right);
260
int Tree::tree_walk_left_root_right(Tree_Element *element, tree_walk_action action, void *argument)
521
263
if (element->left) /* Not null_element */
523
if ((error=tree_walk_left_root_right(tree,element->left,action,
265
if ((error=tree_walk_left_root_right(element->left,action,
524
266
argument)) == 0 &&
525
(error=(*action)(ELEMENT_KEY(tree,element),
528
error=tree_walk_left_root_right(tree,element->right,action,argument);
267
(error=(*action)(element_key(element), element->count, argument)) == 0)
268
error=tree_walk_left_root_right(element->right,action,argument);
535
static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
275
int Tree::tree_walk_right_root_left(Tree_Element *element, tree_walk_action action, void *argument)
538
278
if (element->right) /* Not null_element */
540
if ((error=tree_walk_right_root_left(tree,element->right,action,
280
if ((error=tree_walk_right_root_left(element->right,action,
541
281
argument)) == 0 &&
542
(error=(*action)(ELEMENT_KEY(tree,element),
282
(error=(*action)(element_key(element),
545
error=tree_walk_right_root_left(tree,element->left,action,argument);
285
error=tree_walk_right_root_left(element->left,action,argument);
553
/* Functions to fix up the tree after insert and delete */
555
static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
292
void Tree::left_rotate(Tree_Element **parent, Tree_Element *element)
560
leaf->right= y->left;
297
element->right= y->left;
565
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
302
void Tree::right_rotate(Tree_Element **parent, Tree_Element *element)
570
leaf->left= x->right;
307
element->left= x->right;
575
static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
312
void Tree::rb_insert(Tree_Element ***parent, Tree_Element *element)
577
TREE_ELEMENT *y,*par,*par2;
314
Tree_Element *y,*par,*par2;
580
while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
317
while (element != root && (par=parent[-1][0])->colour == RED)
582
319
if (par == (par2=parent[-2][0])->left)