00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include <config.h>
00021 #include <drizzled/optimizer/range.h>
00022 #include <drizzled/optimizer/range_param.h>
00023 #include <drizzled/optimizer/sel_arg.h>
00024 #include <drizzled/util/test.h>
00025
00026 namespace drizzled
00027 {
00028
00029
00030 static void left_rotate(optimizer::SEL_ARG **root, optimizer::SEL_ARG *leaf)
00031 {
00032 optimizer::SEL_ARG *y= leaf->right;
00033 leaf->right= y->left;
00034 if (y->left != &optimizer::null_element)
00035 y->left->parent= leaf;
00036 if (! (y->parent=leaf->parent))
00037 *root= y;
00038 else
00039 *leaf->parent_ptr()= y;
00040 y->left= leaf;
00041 leaf->parent= y;
00042 }
00043
00044
00045 static void right_rotate(optimizer::SEL_ARG **root, optimizer::SEL_ARG *leaf)
00046 {
00047 optimizer::SEL_ARG *y= leaf->left;
00048 leaf->left= y->right;
00049 if (y->right != &optimizer::null_element)
00050 y->right->parent= leaf;
00051 if (! (y->parent=leaf->parent))
00052 *root= y;
00053 else
00054 *leaf->parent_ptr()= y;
00055 y->right= leaf;
00056 leaf->parent= y;
00057 }
00058
00059
00060
00061 optimizer::SEL_ARG *optimizer::SEL_ARG::clone_and(optimizer::SEL_ARG *arg)
00062 {
00063 unsigned char *new_min= NULL;
00064 unsigned char *new_max= NULL;
00065 uint8_t flag_min= 0;
00066 uint8_t flag_max= 0;
00067
00068 if (cmp_min_to_min(arg) >= 0)
00069 {
00070 new_min= min_value;
00071 flag_min= min_flag;
00072 }
00073 else
00074 {
00075 new_min=arg->min_value; flag_min=arg->min_flag;
00076 }
00077 if (cmp_max_to_max(arg) <= 0)
00078 {
00079 new_max= max_value;
00080 flag_max= max_flag;
00081 }
00082 else
00083 {
00084 new_max= arg->max_value;
00085 flag_max= arg->max_flag;
00086 }
00087 return (new SEL_ARG(field,
00088 part,
00089 new_min,
00090 new_max,
00091 flag_min,
00092 flag_max,
00093 test(maybe_flag && arg->maybe_flag)));
00094 }
00095
00096
00097
00098 optimizer::SEL_ARG *optimizer::SEL_ARG::clone_first(optimizer::SEL_ARG *arg)
00099 {
00100 return (new SEL_ARG(field,part,
00101 min_value,
00102 arg->min_value,
00103 min_flag,
00104 arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
00105 maybe_flag | arg->maybe_flag));
00106 }
00107
00108
00109
00110 optimizer::SEL_ARG *optimizer::SEL_ARG::clone_last(optimizer::SEL_ARG *arg)
00111 {
00112 return (new SEL_ARG(field,
00113 part,
00114 min_value,
00115 arg->max_value,
00116 min_flag,
00117 arg->max_flag,
00118 maybe_flag | arg->maybe_flag));
00119 }
00120
00121
00122
00123 bool optimizer::SEL_ARG::copy_min(optimizer::SEL_ARG *arg)
00124 {
00125 if (cmp_min_to_min(arg) > 0)
00126 {
00127 min_value= arg->min_value;
00128 min_flag=arg->min_flag;
00129 if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
00130 (NO_MAX_RANGE | NO_MIN_RANGE))
00131 {
00132 return 1;
00133 }
00134 }
00135 maybe_flag|= arg->maybe_flag;
00136 return 0;
00137 }
00138
00139
00140 bool optimizer::SEL_ARG::copy_max(optimizer::SEL_ARG *arg)
00141 {
00142 if (cmp_max_to_max(arg) <= 0)
00143 {
00144 max_value= arg->max_value;
00145 max_flag= arg->max_flag;
00146 if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
00147 (NO_MAX_RANGE | NO_MIN_RANGE))
00148 {
00149 return 1;
00150 }
00151 }
00152 maybe_flag|= arg->maybe_flag;
00153 return 0;
00154 }
00155
00156 void optimizer::SEL_ARG::copy_min_to_min(optimizer::SEL_ARG *arg)
00157 {
00158 min_value= arg->min_value;
00159 min_flag= arg->min_flag;
00160 }
00161
00162
00163 void optimizer::SEL_ARG::copy_min_to_max(optimizer::SEL_ARG *arg)
00164 {
00165 max_value= arg->min_value;
00166 max_flag= arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
00167 }
00168
00169 void optimizer::SEL_ARG::copy_max_to_min(optimizer::SEL_ARG *arg)
00170 {
00171 min_value= arg->max_value;
00172 min_flag= arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
00173 }
00174
00175
00176 int optimizer::SEL_ARG::store_min(uint32_t length, unsigned char **min_key, uint32_t min_key_flag)
00177 {
00178
00179 if ((! (min_flag & NO_MIN_RANGE) &&
00180 ! (min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
00181 {
00182 if (maybe_null && *min_value)
00183 {
00184 **min_key= 1;
00185 memset(*min_key+1, 0, length-1);
00186 }
00187 else
00188 {
00189 memcpy(*min_key,min_value,length);
00190 }
00191 (*min_key)+= length;
00192 return 1;
00193 }
00194 return 0;
00195 }
00196
00197
00198 int optimizer::SEL_ARG::store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
00199 {
00200 if (! (max_flag & NO_MAX_RANGE) &&
00201 ! (max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
00202 {
00203 if (maybe_null && *max_value)
00204 {
00205 **max_key= 1;
00206 memset(*max_key + 1, 0, length-1);
00207 }
00208 else
00209 {
00210 memcpy(*max_key,max_value,length);
00211 }
00212 (*max_key)+= length;
00213 return 1;
00214 }
00215 return 0;
00216 }
00217
00218
00219 int optimizer::SEL_ARG::store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
00220 {
00221 optimizer::SEL_ARG *key_tree= first();
00222 uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
00223 range_key,
00224 *range_key_flag);
00225 *range_key_flag|= key_tree->min_flag;
00226
00227 if (key_tree->next_key_part &&
00228 key_tree->next_key_part->part == key_tree->part+1 &&
00229 ! (*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
00230 key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
00231 {
00232 res+= key_tree->next_key_part->store_min_key(key,
00233 range_key,
00234 range_key_flag);
00235 }
00236 return res;
00237 }
00238
00239 int optimizer::SEL_ARG::store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
00240 {
00241 SEL_ARG *key_tree= last();
00242 uint32_t res= key_tree->store_max(key[key_tree->part].store_length,
00243 range_key,
00244 *range_key_flag);
00245 (*range_key_flag)|= key_tree->max_flag;
00246 if (key_tree->next_key_part &&
00247 key_tree->next_key_part->part == key_tree->part+1 &&
00248 ! (*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
00249 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
00250 res+= key_tree->next_key_part->store_max_key(key,
00251 range_key,
00252 range_key_flag);
00253 return res;
00254 }
00255
00256 optimizer::SEL_ARG::SEL_ARG(optimizer::SEL_ARG &arg)
00257 :
00258 memory::SqlAlloc()
00259 {
00260 type= arg.type;
00261 min_flag= arg.min_flag;
00262 max_flag= arg.max_flag;
00263 maybe_flag= arg.maybe_flag;
00264 maybe_null= arg.maybe_null;
00265 part= arg.part;
00266 field= arg.field;
00267 min_value= arg.min_value;
00268 max_value= arg.max_value;
00269 next_key_part= arg.next_key_part;
00270 use_count=1;
00271 elements=1;
00272 }
00273
00274
00275 void optimizer::SEL_ARG::make_root()
00276 {
00277 left= right= &optimizer::null_element;
00278 color= BLACK;
00279 next= prev =0;
00280 use_count= 0;
00281 elements= 1;
00282 }
00283
00284 optimizer::SEL_ARG::SEL_ARG(Field *f,
00285 const unsigned char *min_value_arg,
00286 const unsigned char *max_value_arg)
00287 :
00288 min_flag(0),
00289 max_flag(0),
00290 maybe_flag(0),
00291 maybe_null(f->real_maybe_null()),
00292 elements(1),
00293 use_count(1),
00294 field(f),
00295 min_value((unsigned char*) min_value_arg),
00296 max_value((unsigned char*) max_value_arg),
00297 next(0),
00298 prev(0),
00299 next_key_part(0),
00300 color(BLACK),
00301 type(KEY_RANGE)
00302 {
00303 left= right= &optimizer::null_element;
00304 }
00305
00306 optimizer::SEL_ARG::SEL_ARG(Field *field_,
00307 uint8_t part_,
00308 unsigned char *min_value_,
00309 unsigned char *max_value_,
00310 uint8_t min_flag_,
00311 uint8_t max_flag_,
00312 uint8_t maybe_flag_)
00313 :
00314 min_flag(min_flag_),
00315 max_flag(max_flag_),
00316 maybe_flag(maybe_flag_),
00317 part(part_),
00318 maybe_null(field_->real_maybe_null()),
00319 elements(1),
00320 use_count(1),
00321 field(field_),
00322 min_value(min_value_),
00323 max_value(max_value_),
00324 next(0),
00325 prev(0),
00326 next_key_part(0),
00327 color(BLACK),
00328 type(KEY_RANGE)
00329 {
00330 left= right= &optimizer::null_element;
00331 }
00332
00333 optimizer::SEL_ARG *optimizer::SEL_ARG::clone(RangeParameter *param,
00334 optimizer::SEL_ARG *new_parent,
00335 optimizer::SEL_ARG **next_arg)
00336 {
00337 optimizer::SEL_ARG *tmp= NULL;
00338
00339
00340 if (++param->alloced_sel_args > MAX_SEL_ARGS)
00341 return 0;
00342
00343 if (type != KEY_RANGE)
00344 {
00345 if (! (tmp= new (param->mem_root) optimizer::SEL_ARG(type)))
00346 return 0;
00347 tmp->prev= *next_arg;
00348 (*next_arg)->next= tmp;
00349 (*next_arg)= tmp;
00350 }
00351 else
00352 {
00353 if (! (tmp= new (param->mem_root) optimizer::SEL_ARG(field,
00354 part,
00355 min_value,
00356 max_value,
00357 min_flag,
00358 max_flag,
00359 maybe_flag)))
00360 return 0;
00361 tmp->parent= new_parent;
00362 tmp->next_key_part= next_key_part;
00363 if (left != &optimizer::null_element)
00364 if (! (tmp->left= left->clone(param, tmp, next_arg)))
00365 return 0;
00366
00367 tmp->prev= *next_arg;
00368 (*next_arg)->next= tmp;
00369 (*next_arg)= tmp;
00370
00371 if (right != &optimizer::null_element)
00372 if (! (tmp->right= right->clone(param, tmp, next_arg)))
00373 return 0;
00374 }
00375 increment_use_count(1);
00376 tmp->color= color;
00377 tmp->elements= this->elements;
00378 return tmp;
00379 }
00380
00381 optimizer::SEL_ARG *optimizer::SEL_ARG::first()
00382 {
00383 optimizer::SEL_ARG *next_arg= this;
00384 if (! next_arg->left)
00385 return 0;
00386 while (next_arg->left != &optimizer::null_element)
00387 next_arg= next_arg->left;
00388 return next_arg;
00389 }
00390
00391 optimizer::SEL_ARG *optimizer::SEL_ARG::last()
00392 {
00393 SEL_ARG *next_arg= this;
00394 if (! next_arg->right)
00395 return 0;
00396 while (next_arg->right != &optimizer::null_element)
00397 next_arg=next_arg->right;
00398 return next_arg;
00399 }
00400
00401
00402 optimizer::SEL_ARG *optimizer::SEL_ARG::clone_tree(RangeParameter *param)
00403 {
00404 optimizer::SEL_ARG tmp_link;
00405 optimizer::SEL_ARG*next_arg= NULL;
00406 optimizer::SEL_ARG *root= NULL;
00407 next_arg= &tmp_link;
00408 if (! (root= clone(param, (SEL_ARG *) 0, &next_arg)))
00409 return 0;
00410 next_arg->next= 0;
00411 tmp_link.next->prev= 0;
00412 if (root)
00413 root->use_count= 0;
00414 return root;
00415 }
00416
00417
00418 optimizer::SEL_ARG *
00419 optimizer::SEL_ARG::insert(optimizer::SEL_ARG *key)
00420 {
00421 optimizer::SEL_ARG *element= NULL;
00422 optimizer::SEL_ARG **par= NULL;
00423 optimizer::SEL_ARG *last_element= NULL;
00424
00425 for (element= this; element != &optimizer::null_element; )
00426 {
00427 last_element= element;
00428 if (key->cmp_min_to_min(element) > 0)
00429 {
00430 par= &element->right; element= element->right;
00431 }
00432 else
00433 {
00434 par= &element->left; element= element->left;
00435 }
00436 }
00437 *par= key;
00438 key->parent= last_element;
00439
00440 if (par == &last_element->left)
00441 {
00442 key->next= last_element;
00443 if ((key->prev=last_element->prev))
00444 key->prev->next= key;
00445 last_element->prev= key;
00446 }
00447 else
00448 {
00449 if ((key->next= last_element->next))
00450 key->next->prev= key;
00451 key->prev= last_element;
00452 last_element->next= key;
00453 }
00454 key->left= key->right= &optimizer::null_element;
00455 optimizer::SEL_ARG *root= rb_insert(key);
00456 root->use_count= this->use_count;
00457 root->elements= this->elements+1;
00458 root->maybe_flag= this->maybe_flag;
00459 return root;
00460 }
00461
00462
00463
00464
00465
00466
00467 optimizer::SEL_ARG *
00468 optimizer::SEL_ARG::find_range(optimizer::SEL_ARG *key)
00469 {
00470 optimizer::SEL_ARG *element= this;
00471 optimizer::SEL_ARG *found= NULL;
00472
00473 for (;;)
00474 {
00475 if (element == &optimizer::null_element)
00476 return found;
00477 int cmp= element->cmp_min_to_min(key);
00478 if (cmp == 0)
00479 return element;
00480 if (cmp < 0)
00481 {
00482 found= element;
00483 element= element->right;
00484 }
00485 else
00486 element= element->left;
00487 }
00488 }
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504 optimizer::SEL_ARG *
00505 optimizer::SEL_ARG::tree_delete(optimizer::SEL_ARG *key)
00506 {
00507 enum leaf_color remove_color;
00508 optimizer::SEL_ARG *root= NULL;
00509 optimizer::SEL_ARG *nod= NULL;
00510 optimizer::SEL_ARG **par= NULL;
00511 optimizer::SEL_ARG *fix_par= NULL;
00512
00513 root= this;
00514 this->parent= 0;
00515
00516
00517 if (key->prev)
00518 key->prev->next= key->next;
00519 if (key->next)
00520 key->next->prev= key->prev;
00521 key->increment_use_count(-1);
00522 if (! key->parent)
00523 par= &root;
00524 else
00525 par= key->parent_ptr();
00526
00527 if (key->left == &optimizer::null_element)
00528 {
00529 *par= nod= key->right;
00530 fix_par= key->parent;
00531 if (nod != &optimizer::null_element)
00532 nod->parent= fix_par;
00533 remove_color= key->color;
00534 }
00535 else if (key->right == &optimizer::null_element)
00536 {
00537 *par= nod= key->left;
00538 nod->parent= fix_par= key->parent;
00539 remove_color= key->color;
00540 }
00541 else
00542 {
00543 optimizer::SEL_ARG *tmp= key->next;
00544 nod= *tmp->parent_ptr()= tmp->right;
00545 fix_par= tmp->parent;
00546 if (nod != &optimizer::null_element)
00547 nod->parent= fix_par;
00548 remove_color= tmp->color;
00549
00550 tmp->parent= key->parent;
00551 (tmp->left= key->left)->parent= tmp;
00552 if ((tmp->right=key->right) != &optimizer::null_element)
00553 tmp->right->parent= tmp;
00554 tmp->color= key->color;
00555 *par= tmp;
00556 if (fix_par == key)
00557 fix_par= tmp;
00558 }
00559
00560 if (root == &optimizer::null_element)
00561 return 0;
00562 if (remove_color == BLACK)
00563 root= rb_delete_fixup(root, nod, fix_par);
00564
00565 root->use_count= this->use_count;
00566 root->elements= this->elements-1;
00567 root->maybe_flag= this->maybe_flag;
00568 return root;
00569 }
00570
00571
00572 optimizer::SEL_ARG *
00573 optimizer::SEL_ARG::rb_insert(optimizer::SEL_ARG *leaf)
00574 {
00575 optimizer::SEL_ARG *y= NULL;
00576 optimizer::SEL_ARG *par= NULL;
00577 optimizer::SEL_ARG *par2= NULL;
00578 optimizer::SEL_ARG *root= NULL;
00579
00580 root= this;
00581 root->parent= 0;
00582
00583 leaf->color= RED;
00584 while (leaf != root && (par= leaf->parent)->color == RED)
00585 {
00586 if (par == (par2= leaf->parent->parent)->left)
00587 {
00588 y= par2->right;
00589 if (y->color == RED)
00590 {
00591 par->color= BLACK;
00592 y->color= BLACK;
00593 leaf= par2;
00594 leaf->color= RED;
00595 }
00596 else
00597 {
00598 if (leaf == par->right)
00599 {
00600 left_rotate(&root,leaf->parent);
00601 par= leaf;
00602 }
00603 par->color= BLACK;
00604 par2->color= RED;
00605 right_rotate(&root, par2);
00606 break;
00607 }
00608 }
00609 else
00610 {
00611 y= par2->left;
00612 if (y->color == RED)
00613 {
00614 par->color= BLACK;
00615 y->color= BLACK;
00616 leaf= par2;
00617 leaf->color= RED;
00618 }
00619 else
00620 {
00621 if (leaf == par->left)
00622 {
00623 right_rotate(&root,par);
00624 par= leaf;
00625 }
00626 par->color= BLACK;
00627 par2->color= RED;
00628 left_rotate(&root, par2);
00629 break;
00630 }
00631 }
00632 }
00633 root->color= BLACK;
00634
00635 return root;
00636 }
00637
00638
00639 optimizer::SEL_ARG *optimizer::rb_delete_fixup(optimizer::SEL_ARG *root,
00640 optimizer::SEL_ARG *key,
00641 optimizer::SEL_ARG *par)
00642 {
00643 optimizer::SEL_ARG *x= NULL;
00644 optimizer::SEL_ARG *w= NULL;
00645 root->parent= 0;
00646
00647 x= key;
00648 while (x != root && x->color == optimizer::SEL_ARG::BLACK)
00649 {
00650 if (x == par->left)
00651 {
00652 w= par->right;
00653 if (w->color == optimizer::SEL_ARG::RED)
00654 {
00655 w->color= optimizer::SEL_ARG::BLACK;
00656 par->color= optimizer::SEL_ARG::RED;
00657 left_rotate(&root, par);
00658 w= par->right;
00659 }
00660 if (w->left->color == optimizer::SEL_ARG::BLACK &&
00661 w->right->color == optimizer::SEL_ARG::BLACK)
00662 {
00663 w->color= optimizer::SEL_ARG::RED;
00664 x= par;
00665 }
00666 else
00667 {
00668 if (w->right->color == optimizer::SEL_ARG::BLACK)
00669 {
00670 w->left->color= optimizer::SEL_ARG::BLACK;
00671 w->color= optimizer::SEL_ARG::RED;
00672 right_rotate(&root, w);
00673 w= par->right;
00674 }
00675 w->color= par->color;
00676 par->color= optimizer::SEL_ARG::BLACK;
00677 w->right->color= optimizer::SEL_ARG::BLACK;
00678 left_rotate(&root, par);
00679 x= root;
00680 break;
00681 }
00682 }
00683 else
00684 {
00685 w= par->left;
00686 if (w->color == optimizer::SEL_ARG::RED)
00687 {
00688 w->color= optimizer::SEL_ARG::BLACK;
00689 par->color= optimizer::SEL_ARG::RED;
00690 right_rotate(&root, par);
00691 w= par->left;
00692 }
00693 if (w->right->color == optimizer::SEL_ARG::BLACK &&
00694 w->left->color == optimizer::SEL_ARG::BLACK)
00695 {
00696 w->color= optimizer::SEL_ARG::RED;
00697 x= par;
00698 }
00699 else
00700 {
00701 if (w->left->color == SEL_ARG::BLACK)
00702 {
00703 w->right->color= optimizer::SEL_ARG::BLACK;
00704 w->color= optimizer::SEL_ARG::RED;
00705 left_rotate(&root, w);
00706 w= par->left;
00707 }
00708 w->color= par->color;
00709 par->color= optimizer::SEL_ARG::BLACK;
00710 w->left->color= optimizer::SEL_ARG::BLACK;
00711 right_rotate(&root, par);
00712 x= root;
00713 break;
00714 }
00715 }
00716 par= x->parent;
00717 }
00718 x->color= optimizer::SEL_ARG::BLACK;
00719 return root;
00720 }
00721
00722
00723 }