00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056 #include <config.h>
00057
00058 #include <drizzled/tree.h>
00059 #include <drizzled/internal/my_sys.h>
00060 #include <drizzled/internal/m_string.h>
00061 #include <drizzled/memory/root.h>
00062
00063 #define BLACK 1
00064 #define RED 0
00065 #define DEFAULT_ALLOC_SIZE 8192
00066 #define DEFAULT_ALIGN_SIZE 8192
00067
00068 #define ELEMENT_KEY(tree,element)\
00069 (tree->offset_to_key ? (void*)((unsigned char*) element+tree->offset_to_key) :\
00070 *((void**) (element+1)))
00071 #define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
00072
00073 namespace drizzled
00074 {
00075
00076
00077 static void delete_tree_element(TREE *,TREE_ELEMENT *);
00078 static int tree_walk_left_root_right(TREE *,TREE_ELEMENT *,
00079 tree_walk_action,void *);
00080 static int tree_walk_right_root_left(TREE *,TREE_ELEMENT *,
00081 tree_walk_action,void *);
00082 static void left_rotate(TREE_ELEMENT **parent,TREE_ELEMENT *leaf);
00083 static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
00084 static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
00085 TREE_ELEMENT *leaf);
00086 static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
00087
00088
00089 void init_tree(TREE *tree, size_t default_alloc_size, uint32_t memory_limit,
00090 uint32_t size, qsort_cmp2 compare, bool with_delete,
00091 tree_element_free free_element, void *custom_arg)
00092 {
00093 if (default_alloc_size < DEFAULT_ALLOC_SIZE)
00094 default_alloc_size= DEFAULT_ALLOC_SIZE;
00095 default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
00096 memset(&tree->null_element, 0, sizeof(tree->null_element));
00097 tree->root= &tree->null_element;
00098 tree->compare= compare;
00099 tree->size_of_element= size > 0 ? (uint32_t) size : 0;
00100 tree->memory_limit= memory_limit;
00101 tree->free= free_element;
00102 tree->allocated= 0;
00103 tree->elements_in_tree= 0;
00104 tree->custom_arg = custom_arg;
00105 tree->null_element.colour= BLACK;
00106 tree->null_element.left=tree->null_element.right= 0;
00107 tree->flag= 0;
00108 if (!free_element &&
00109 (size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
00110 {
00111
00112
00113
00114
00115
00116 tree->offset_to_key= sizeof(TREE_ELEMENT);
00117
00118 default_alloc_size/= (sizeof(TREE_ELEMENT)+size);
00119 if (!default_alloc_size)
00120 default_alloc_size= 1;
00121 default_alloc_size*= (sizeof(TREE_ELEMENT)+size);
00122 }
00123 else
00124 {
00125 tree->offset_to_key= 0;
00126 tree->size_of_element+= sizeof(void*);
00127 }
00128 if (! (tree->with_delete= with_delete))
00129 {
00130 tree->mem_root.init_alloc_root(default_alloc_size);
00131 tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
00132 }
00133 }
00134
00135 static void free_tree(TREE *tree, myf free_flags)
00136 {
00137 if (tree->root)
00138 {
00139 if (tree->with_delete)
00140 delete_tree_element(tree,tree->root);
00141 else
00142 {
00143 if (tree->free)
00144 {
00145 if (tree->memory_limit)
00146 (*tree->free)(NULL, free_init, tree->custom_arg);
00147 delete_tree_element(tree,tree->root);
00148 if (tree->memory_limit)
00149 (*tree->free)(NULL, free_end, tree->custom_arg);
00150 }
00151 tree->mem_root.free_root(free_flags);
00152 }
00153 }
00154 tree->root= &tree->null_element;
00155 tree->elements_in_tree= 0;
00156 tree->allocated= 0;
00157 }
00158
00159 void delete_tree(TREE* tree)
00160 {
00161 free_tree(tree, MYF(0));
00162 }
00163
00164 void reset_tree(TREE* tree)
00165 {
00166
00167 free_tree(tree, MYF(memory::MARK_BLOCKS_FREE));
00168 }
00169
00170
00171 static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
00172 {
00173 if (element != &tree->null_element)
00174 {
00175 delete_tree_element(tree,element->left);
00176 if (tree->free)
00177 (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
00178 delete_tree_element(tree,element->right);
00179 if (tree->with_delete)
00180 free((char*) element);
00181 }
00182 }
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193 TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size,
00194 void* custom_arg)
00195 {
00196 int cmp;
00197 TREE_ELEMENT *element,***parent;
00198
00199 parent= tree->parents;
00200 *parent = &tree->root; element= tree->root;
00201 for (;;)
00202 {
00203 if (element == &tree->null_element ||
00204 (cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
00205 key)) == 0)
00206 break;
00207 if (cmp < 0)
00208 {
00209 *++parent= &element->right; element= element->right;
00210 }
00211 else
00212 {
00213 *++parent = &element->left; element= element->left;
00214 }
00215 }
00216 if (element == &tree->null_element)
00217 {
00218 size_t alloc_size= sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
00219 tree->allocated+= alloc_size;
00220
00221 if (tree->memory_limit && tree->elements_in_tree
00222 && tree->allocated > tree->memory_limit)
00223 {
00224 reset_tree(tree);
00225 return tree_insert(tree, key, key_size, custom_arg);
00226 }
00227
00228 key_size+= tree->size_of_element;
00229 if (tree->with_delete)
00230 element= (TREE_ELEMENT *) malloc(alloc_size);
00231 else
00232 element= (TREE_ELEMENT *) tree->mem_root.alloc_root(alloc_size);
00233 if (!element)
00234 return(NULL);
00235 **parent= element;
00236 element->left= element->right= &tree->null_element;
00237 if (!tree->offset_to_key)
00238 {
00239 if (key_size == sizeof(void*))
00240 *((void**) (element+1))= key;
00241 else
00242 {
00243 *((void**) (element+1))= (void*) ((void **) (element+1)+1);
00244 memcpy(*((void **) (element+1)),key, key_size - sizeof(void*));
00245 }
00246 }
00247 else
00248 memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
00249 element->count= 1;
00250 tree->elements_in_tree++;
00251 rb_insert(tree,parent,element);
00252 }
00253 else
00254 {
00255 if (tree->flag & TREE_NO_DUPS)
00256 return(NULL);
00257 element->count++;
00258
00259 if (! element->count)
00260 element->count--;
00261 }
00262
00263 return element;
00264 }
00265
00266 int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
00267 {
00268 int remove_colour;
00269 TREE_ELEMENT *element,***parent, ***org_parent, *nod;
00270 if (!tree->with_delete)
00271 return 1;
00272
00273 parent= tree->parents;
00274 *parent= &tree->root; element= tree->root;
00275 for (;;)
00276 {
00277 int cmp;
00278
00279 if (element == &tree->null_element)
00280 return 1;
00281 if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
00282 key)) == 0)
00283 break;
00284 if (cmp < 0)
00285 {
00286 *++parent= &element->right; element= element->right;
00287 }
00288 else
00289 {
00290 *++parent = &element->left; element= element->left;
00291 }
00292 }
00293 if (element->left == &tree->null_element)
00294 {
00295 (**parent)= element->right;
00296 remove_colour= element->colour;
00297 }
00298 else if (element->right == &tree->null_element)
00299 {
00300 (**parent)= element->left;
00301 remove_colour= element->colour;
00302 }
00303 else
00304 {
00305 org_parent= parent;
00306 *++parent= &element->right; nod= element->right;
00307 while (nod->left != &tree->null_element)
00308 {
00309 *++parent= &nod->left; nod= nod->left;
00310 }
00311 (**parent)= nod->right;
00312 remove_colour= nod->colour;
00313 org_parent[0][0]= nod;
00314 org_parent[1]= &nod->right;
00315 nod->left= element->left;
00316 nod->right= element->right;
00317 nod->colour= element->colour;
00318 }
00319 if (remove_colour == BLACK)
00320 rb_delete_fixup(tree,parent);
00321 if (tree->free)
00322 (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
00323 tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
00324 free((unsigned char*) element);
00325 tree->elements_in_tree--;
00326
00327 return 0;
00328 }
00329
00330 void *tree_search_key(TREE *tree, const void *key,
00331 TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
00332 enum ha_rkey_function flag, void *custom_arg)
00333 {
00334 TREE_ELEMENT *element= tree->root;
00335 TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
00336 TREE_ELEMENT **last_equal_element= NULL;
00337
00338
00339
00340
00341
00342 *parents = &tree->null_element;
00343 while (element != &tree->null_element)
00344 {
00345 int cmp;
00346
00347 *++parents= element;
00348
00349 if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
00350 key)) == 0)
00351 {
00352 switch (flag) {
00353 case HA_READ_KEY_EXACT:
00354 case HA_READ_KEY_OR_NEXT:
00355 case HA_READ_BEFORE_KEY:
00356 last_equal_element= parents;
00357 cmp= 1;
00358 break;
00359 case HA_READ_AFTER_KEY:
00360 cmp= -1;
00361 break;
00362 case HA_READ_PREFIX_LAST:
00363 case HA_READ_PREFIX_LAST_OR_PREV:
00364 last_equal_element= parents;
00365 cmp= -1;
00366 break;
00367 default:
00368 return NULL;
00369 }
00370 }
00371 if (cmp < 0)
00372 {
00373 last_right_step_parent= parents;
00374 element= element->right;
00375 }
00376 else
00377 {
00378 last_left_step_parent= parents;
00379 element= element->left;
00380 }
00381 }
00382 switch (flag) {
00383 case HA_READ_KEY_EXACT:
00384 case HA_READ_PREFIX_LAST:
00385 *last_pos= last_equal_element;
00386 break;
00387 case HA_READ_KEY_OR_NEXT:
00388 *last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
00389 break;
00390 case HA_READ_AFTER_KEY:
00391 *last_pos= last_left_step_parent;
00392 break;
00393 case HA_READ_PREFIX_LAST_OR_PREV:
00394 *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
00395 break;
00396 case HA_READ_BEFORE_KEY:
00397 *last_pos= last_right_step_parent;
00398 break;
00399 default:
00400 return NULL;
00401 }
00402
00403 return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
00404 }
00405
00406
00407
00408
00409 void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
00410 TREE_ELEMENT ***last_pos, int child_offs)
00411 {
00412 TREE_ELEMENT *element= tree->root;
00413
00414 *parents= &tree->null_element;
00415 while (element != &tree->null_element)
00416 {
00417 *++parents= element;
00418 element= ELEMENT_CHILD(element, child_offs);
00419 }
00420 *last_pos= parents;
00421 return **last_pos != &tree->null_element ?
00422 ELEMENT_KEY(tree, **last_pos) : NULL;
00423 }
00424
00425 void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
00426 int r_offs)
00427 {
00428 TREE_ELEMENT *x= **last_pos;
00429
00430 if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
00431 {
00432 x= ELEMENT_CHILD(x, r_offs);
00433 *++*last_pos= x;
00434 while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
00435 {
00436 x= ELEMENT_CHILD(x, l_offs);
00437 *++*last_pos= x;
00438 }
00439 return ELEMENT_KEY(tree, x);
00440 }
00441 else
00442 {
00443 TREE_ELEMENT *y= *--*last_pos;
00444 while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
00445 {
00446 x= y;
00447 y= *--*last_pos;
00448 }
00449 return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
00450 }
00451 }
00452
00453
00454
00455
00456
00457 ha_rows tree_record_pos(TREE *tree, const void *key,
00458 enum ha_rkey_function flag, void *custom_arg)
00459 {
00460 TREE_ELEMENT *element= tree->root;
00461 double left= 1;
00462 double right= tree->elements_in_tree;
00463
00464 while (element != &tree->null_element)
00465 {
00466 int cmp;
00467
00468 if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
00469 key)) == 0)
00470 {
00471 switch (flag) {
00472 case HA_READ_KEY_EXACT:
00473 case HA_READ_BEFORE_KEY:
00474 cmp= 1;
00475 break;
00476 case HA_READ_AFTER_KEY:
00477 cmp= -1;
00478 break;
00479 default:
00480 return HA_POS_ERROR;
00481 }
00482 }
00483 if (cmp < 0)
00484 {
00485 element= element->right;
00486 left= (left + right) / 2;
00487 }
00488 else
00489 {
00490 element= element->left;
00491 right= (left + right) / 2;
00492 }
00493 }
00494
00495 switch (flag) {
00496 case HA_READ_KEY_EXACT:
00497 case HA_READ_BEFORE_KEY:
00498 return (ha_rows) right;
00499 case HA_READ_AFTER_KEY:
00500 return (ha_rows) left;
00501 default:
00502 return HA_POS_ERROR;
00503 }
00504 }
00505
00506 int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
00507 {
00508 switch (visit) {
00509 case left_root_right:
00510 return tree_walk_left_root_right(tree,tree->root,action,argument);
00511 case right_root_left:
00512 return tree_walk_right_root_left(tree,tree->root,action,argument);
00513 }
00514
00515 return 0;
00516 }
00517
00518 static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
00519 {
00520 int error;
00521 if (element->left)
00522 {
00523 if ((error=tree_walk_left_root_right(tree,element->left,action,
00524 argument)) == 0 &&
00525 (error=(*action)(ELEMENT_KEY(tree,element),
00526 element->count,
00527 argument)) == 0)
00528 error=tree_walk_left_root_right(tree,element->right,action,argument);
00529 return error;
00530 }
00531
00532 return 0;
00533 }
00534
00535 static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
00536 {
00537 int error;
00538 if (element->right)
00539 {
00540 if ((error=tree_walk_right_root_left(tree,element->right,action,
00541 argument)) == 0 &&
00542 (error=(*action)(ELEMENT_KEY(tree,element),
00543 element->count,
00544 argument)) == 0)
00545 error=tree_walk_right_root_left(tree,element->left,action,argument);
00546 return error;
00547 }
00548
00549 return 0;
00550 }
00551
00552
00553
00554
00555 static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
00556 {
00557 TREE_ELEMENT *y;
00558
00559 y= leaf->right;
00560 leaf->right= y->left;
00561 parent[0]= y;
00562 y->left= leaf;
00563 }
00564
00565 static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
00566 {
00567 TREE_ELEMENT *x;
00568
00569 x= leaf->left;
00570 leaf->left= x->right;
00571 parent[0]= x;
00572 x->right= leaf;
00573 }
00574
00575 static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
00576 {
00577 TREE_ELEMENT *y,*par,*par2;
00578
00579 leaf->colour=RED;
00580 while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
00581 {
00582 if (par == (par2=parent[-2][0])->left)
00583 {
00584 y= par2->right;
00585 if (y->colour == RED)
00586 {
00587 par->colour= BLACK;
00588 y->colour= BLACK;
00589 leaf= par2;
00590 parent-= 2;
00591 leaf->colour= RED;
00592 }
00593 else
00594 {
00595 if (leaf == par->right)
00596 {
00597 left_rotate(parent[-1],par);
00598 par= leaf;
00599 }
00600 par->colour= BLACK;
00601 par2->colour= RED;
00602 right_rotate(parent[-2],par2);
00603 break;
00604 }
00605 }
00606 else
00607 {
00608 y= par2->left;
00609 if (y->colour == RED)
00610 {
00611 par->colour= BLACK;
00612 y->colour= BLACK;
00613 leaf= par2;
00614 parent-= 2;
00615 leaf->colour= RED;
00616 }
00617 else
00618 {
00619 if (leaf == par->left)
00620 {
00621 right_rotate(parent[-1],par);
00622 par= leaf;
00623 }
00624 par->colour= BLACK;
00625 par2->colour= RED;
00626 left_rotate(parent[-2],par2);
00627 break;
00628 }
00629 }
00630 }
00631 tree->root->colour=BLACK;
00632 }
00633
00634 static void rb_delete_fixup(TREE *tree, TREE_ELEMENT ***parent)
00635 {
00636 TREE_ELEMENT *x,*w,*par;
00637
00638 x= **parent;
00639 while (x != tree->root && x->colour == BLACK)
00640 {
00641 if (x == (par=parent[-1][0])->left)
00642 {
00643 w= par->right;
00644 if (w->colour == RED)
00645 {
00646 w->colour= BLACK;
00647 par->colour= RED;
00648 left_rotate(parent[-1],par);
00649 parent[0]= &w->left;
00650 *++parent= &par->left;
00651 w= par->right;
00652 }
00653 if (w->left->colour == BLACK && w->right->colour == BLACK)
00654 {
00655 w->colour= RED;
00656 x= par;
00657 parent--;
00658 }
00659 else
00660 {
00661 if (w->right->colour == BLACK)
00662 {
00663 w->left->colour= BLACK;
00664 w->colour= RED;
00665 right_rotate(&par->right,w);
00666 w= par->right;
00667 }
00668 w->colour= par->colour;
00669 par->colour= BLACK;
00670 w->right->colour= BLACK;
00671 left_rotate(parent[-1],par);
00672 x= tree->root;
00673 break;
00674 }
00675 }
00676 else
00677 {
00678 w=par->left;
00679 if (w->colour == RED)
00680 {
00681 w->colour= BLACK;
00682 par->colour= RED;
00683 right_rotate(parent[-1],par);
00684 parent[0]= &w->right;
00685 *++parent= &par->right;
00686 w= par->left;
00687 }
00688 if (w->right->colour == BLACK && w->left->colour == BLACK)
00689 {
00690 w->colour= RED;
00691 x= par;
00692 parent--;
00693 }
00694 else
00695 {
00696 if (w->left->colour == BLACK)
00697 {
00698 w->right->colour= BLACK;
00699 w->colour= RED;
00700 left_rotate(&par->left,w);
00701 w= par->left;
00702 }
00703 w->colour= par->colour;
00704 par->colour= BLACK;
00705 w->left->colour= BLACK;
00706 right_rotate(parent[-1],par);
00707 x= tree->root;
00708 break;
00709 }
00710 }
00711 }
00712 x->colour= BLACK;
00713 }
00714
00715 }