21 #include <drizzled/optimizer/range.h>
22 #include <drizzled/optimizer/range_param.h>
23 #include <drizzled/optimizer/sel_arg.h>
24 #include <drizzled/util/test.h>
29 static void left_rotate(optimizer::SEL_ARG **root, optimizer::SEL_ARG *leaf)
31 optimizer::SEL_ARG *y= leaf->right;
33 if (y->left != &optimizer::null_element)
34 y->left->parent= leaf;
35 if (! (y->parent=leaf->parent))
38 *leaf->parent_ptr()= y;
44 static void right_rotate(optimizer::SEL_ARG **root, optimizer::SEL_ARG *leaf)
46 optimizer::SEL_ARG *y= leaf->left;
48 if (y->right != &optimizer::null_element)
49 y->right->parent= leaf;
50 if (! (y->parent=leaf->parent))
53 *leaf->parent_ptr()= y;
60 optimizer::SEL_ARG *optimizer::SEL_ARG::clone_and(optimizer::SEL_ARG *arg)
62 unsigned char *new_min= NULL;
63 unsigned char *new_max= NULL;
67 if (cmp_min_to_min(arg) >= 0)
74 new_min=arg->min_value;
75 flag_min=arg->min_flag;
77 if (cmp_max_to_max(arg) <= 0)
84 new_max= arg->max_value;
85 flag_max= arg->max_flag;
87 return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max, test(maybe_flag && arg->maybe_flag));
92 optimizer::SEL_ARG *optimizer::SEL_ARG::clone_first(optimizer::SEL_ARG *arg)
94 return new SEL_ARG(field,part, min_value, arg->min_value, min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX, maybe_flag | arg->maybe_flag);
99 optimizer::SEL_ARG *optimizer::SEL_ARG::clone_last(optimizer::SEL_ARG *arg)
101 return new SEL_ARG(field, part, min_value, arg->max_value, min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
106 bool optimizer::SEL_ARG::copy_min(optimizer::SEL_ARG *arg)
108 if (cmp_min_to_min(arg) > 0)
110 min_value= arg->min_value;
111 min_flag=arg->min_flag;
112 if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
113 (NO_MAX_RANGE | NO_MIN_RANGE))
118 maybe_flag|= arg->maybe_flag;
123 bool optimizer::SEL_ARG::copy_max(optimizer::SEL_ARG *arg)
125 if (cmp_max_to_max(arg) <= 0)
127 max_value= arg->max_value;
128 max_flag= arg->max_flag;
129 if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
130 (NO_MAX_RANGE | NO_MIN_RANGE))
135 maybe_flag|= arg->maybe_flag;
139 void optimizer::SEL_ARG::copy_min_to_min(optimizer::SEL_ARG *arg)
141 min_value= arg->min_value;
142 min_flag= arg->min_flag;
146 void optimizer::SEL_ARG::copy_min_to_max(optimizer::SEL_ARG *arg)
148 max_value= arg->min_value;
149 max_flag= arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
152 void optimizer::SEL_ARG::copy_max_to_min(optimizer::SEL_ARG *arg)
154 min_value= arg->max_value;
155 min_flag= arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
159 int optimizer::SEL_ARG::store_min(uint32_t length,
unsigned char **min_key, uint32_t min_key_flag)
162 if ((! (min_flag & NO_MIN_RANGE) &&
163 ! (min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
165 if (maybe_null && *min_value)
168 memset(*min_key+1, 0, length-1);
172 memcpy(*min_key,min_value,length);
181 int optimizer::SEL_ARG::store_max(uint32_t length,
unsigned char **max_key, uint32_t max_key_flag)
183 if (! (max_flag & NO_MAX_RANGE) &&
184 ! (max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
186 if (maybe_null && *max_value)
189 memset(*max_key + 1, 0, length-1);
193 memcpy(*max_key,max_value,length);
202 int optimizer::SEL_ARG::store_min_key(KEY_PART *key,
unsigned char **range_key, uint32_t *range_key_flag)
204 optimizer::SEL_ARG *key_tree= first();
205 uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
208 *range_key_flag|= key_tree->min_flag;
210 if (key_tree->next_key_part &&
211 key_tree->next_key_part->part == key_tree->part+1 &&
212 ! (*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
213 key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
215 res+= key_tree->next_key_part->store_min_key(key,
222 int optimizer::SEL_ARG::store_max_key(KEY_PART *key,
unsigned char **range_key, uint32_t *range_key_flag)
224 SEL_ARG *key_tree= last();
225 uint32_t res= key_tree->store_max(key[key_tree->part].store_length,
228 (*range_key_flag)|= key_tree->max_flag;
229 if (key_tree->next_key_part &&
230 key_tree->next_key_part->part == key_tree->part+1 &&
231 ! (*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
232 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
233 res+= key_tree->next_key_part->store_max_key(key,
239 optimizer::SEL_ARG::SEL_ARG(optimizer::SEL_ARG &arg)
244 min_flag= arg.min_flag;
245 max_flag= arg.max_flag;
246 maybe_flag= arg.maybe_flag;
247 maybe_null= arg.maybe_null;
250 min_value= arg.min_value;
251 max_value= arg.max_value;
252 next_key_part= arg.next_key_part;
258 void optimizer::SEL_ARG::make_root()
260 left= right= &optimizer::null_element;
267 optimizer::SEL_ARG::SEL_ARG(Field *f,
268 const unsigned char *min_value_arg,
269 const unsigned char *max_value_arg)
274 maybe_null(f->real_maybe_null()),
278 min_value((unsigned char*) min_value_arg),
279 max_value((unsigned char*) max_value_arg),
286 left= right= &optimizer::null_element;
289 optimizer::SEL_ARG::SEL_ARG(Field *field_,
291 unsigned char *min_value_,
292 unsigned char *max_value_,
299 maybe_flag(maybe_flag_),
301 maybe_null(field_->real_maybe_null()),
305 min_value(min_value_),
306 max_value(max_value_),
313 left= right= &optimizer::null_element;
316 optimizer::SEL_ARG *optimizer::SEL_ARG::clone(RangeParameter *param, optimizer::SEL_ARG *new_parent, optimizer::SEL_ARG **next_arg)
318 optimizer::SEL_ARG *tmp= NULL;
321 if (++param->alloced_sel_args > MAX_SEL_ARGS)
324 if (type != KEY_RANGE)
326 tmp=
new (*param->mem_root) optimizer::SEL_ARG(type);
327 tmp->prev= *next_arg;
328 (*next_arg)->next= tmp;
333 tmp=
new (*param->mem_root) optimizer::SEL_ARG(field, part, min_value, max_value, min_flag, max_flag, maybe_flag);
334 tmp->parent= new_parent;
335 tmp->next_key_part= next_key_part;
336 if (left != &optimizer::null_element)
337 if (! (tmp->left= left->clone(param, tmp, next_arg)))
340 tmp->prev= *next_arg;
341 (*next_arg)->next= tmp;
344 if (right != &optimizer::null_element)
345 if (! (tmp->right= right->clone(param, tmp, next_arg)))
348 increment_use_count(1);
350 tmp->elements= this->elements;
354 optimizer::SEL_ARG *optimizer::SEL_ARG::first()
356 optimizer::SEL_ARG *next_arg=
this;
357 if (! next_arg->left)
359 while (next_arg->left != &optimizer::null_element)
360 next_arg= next_arg->left;
364 optimizer::SEL_ARG *optimizer::SEL_ARG::last()
366 SEL_ARG *next_arg=
this;
367 if (! next_arg->right)
369 while (next_arg->right != &optimizer::null_element)
370 next_arg=next_arg->right;
375 optimizer::SEL_ARG *optimizer::SEL_ARG::clone_tree(RangeParameter *param)
377 optimizer::SEL_ARG tmp_link;
378 optimizer::SEL_ARG* next_arg= NULL;
380 optimizer::SEL_ARG* root= clone(param, (SEL_ARG *) 0, &next_arg);
384 tmp_link.next->prev= 0;
392 optimizer::SEL_ARG::insert(optimizer::SEL_ARG *key)
394 optimizer::SEL_ARG *element= NULL;
395 optimizer::SEL_ARG **par= NULL;
396 optimizer::SEL_ARG *last_element= NULL;
398 for (element=
this; element != &optimizer::null_element; )
400 last_element= element;
401 if (key->cmp_min_to_min(element) > 0)
403 par= &element->right; element= element->right;
407 par= &element->left; element= element->left;
411 key->parent= last_element;
413 if (par == &last_element->left)
415 key->next= last_element;
416 if ((key->prev=last_element->prev))
417 key->prev->next= key;
418 last_element->prev= key;
422 if ((key->next= last_element->next))
423 key->next->prev= key;
424 key->prev= last_element;
425 last_element->next= key;
427 key->left= key->right= &optimizer::null_element;
428 optimizer::SEL_ARG *root= rb_insert(key);
429 root->use_count= this->use_count;
430 root->elements= this->elements+1;
431 root->maybe_flag= this->maybe_flag;
441 optimizer::SEL_ARG::find_range(optimizer::SEL_ARG *key)
443 optimizer::SEL_ARG *element=
this;
444 optimizer::SEL_ARG *found= NULL;
448 if (element == &optimizer::null_element)
450 int cmp= element->cmp_min_to_min(key);
456 element= element->right;
459 element= element->left;
478 optimizer::SEL_ARG::tree_delete(optimizer::SEL_ARG *key)
480 enum leaf_color remove_color;
481 optimizer::SEL_ARG *root= NULL;
482 optimizer::SEL_ARG *nod= NULL;
483 optimizer::SEL_ARG **par= NULL;
484 optimizer::SEL_ARG *fix_par= NULL;
491 key->prev->next= key->next;
493 key->next->prev= key->prev;
494 key->increment_use_count(-1);
498 par= key->parent_ptr();
500 if (key->left == &optimizer::null_element)
502 *par= nod= key->right;
503 fix_par= key->parent;
504 if (nod != &optimizer::null_element)
505 nod->parent= fix_par;
506 remove_color= key->color;
508 else if (key->right == &optimizer::null_element)
510 *par= nod= key->left;
511 nod->parent= fix_par= key->parent;
512 remove_color= key->color;
516 optimizer::SEL_ARG *tmp= key->next;
517 nod= *tmp->parent_ptr()= tmp->right;
518 fix_par= tmp->parent;
519 if (nod != &optimizer::null_element)
520 nod->parent= fix_par;
521 remove_color= tmp->color;
523 tmp->parent= key->parent;
524 (tmp->left= key->left)->parent= tmp;
525 if ((tmp->right=key->right) != &optimizer::null_element)
526 tmp->right->parent= tmp;
527 tmp->color= key->color;
533 if (root == &optimizer::null_element)
535 if (remove_color == BLACK)
536 root= rb_delete_fixup(root, nod, fix_par);
538 root->use_count= this->use_count;
539 root->elements= this->elements-1;
540 root->maybe_flag= this->maybe_flag;
546 optimizer::SEL_ARG::rb_insert(optimizer::SEL_ARG *leaf)
548 optimizer::SEL_ARG *y= NULL;
549 optimizer::SEL_ARG *par= NULL;
550 optimizer::SEL_ARG *par2= NULL;
551 optimizer::SEL_ARG *root= NULL;
557 while (leaf != root && (par= leaf->parent)->color == RED)
559 if (par == (par2= leaf->parent->parent)->left)
571 if (leaf == par->right)
573 left_rotate(&root,leaf->parent);
578 right_rotate(&root, par2);
594 if (leaf == par->left)
596 right_rotate(&root,par);
601 left_rotate(&root, par2);
612 optimizer::SEL_ARG *optimizer::rb_delete_fixup(optimizer::SEL_ARG *root,
613 optimizer::SEL_ARG *key,
614 optimizer::SEL_ARG *par)
616 optimizer::SEL_ARG *x= NULL;
617 optimizer::SEL_ARG *w= NULL;
621 while (x != root && x->color == optimizer::SEL_ARG::BLACK)
626 if (w->color == optimizer::SEL_ARG::RED)
628 w->color= optimizer::SEL_ARG::BLACK;
629 par->color= optimizer::SEL_ARG::RED;
630 left_rotate(&root, par);
633 if (w->left->color == optimizer::SEL_ARG::BLACK &&
634 w->right->color == optimizer::SEL_ARG::BLACK)
636 w->color= optimizer::SEL_ARG::RED;
641 if (w->right->color == optimizer::SEL_ARG::BLACK)
643 w->left->color= optimizer::SEL_ARG::BLACK;
644 w->color= optimizer::SEL_ARG::RED;
645 right_rotate(&root, w);
648 w->color= par->color;
649 par->color= optimizer::SEL_ARG::BLACK;
650 w->right->color= optimizer::SEL_ARG::BLACK;
651 left_rotate(&root, par);
659 if (w->color == optimizer::SEL_ARG::RED)
661 w->color= optimizer::SEL_ARG::BLACK;
662 par->color= optimizer::SEL_ARG::RED;
663 right_rotate(&root, par);
666 if (w->right->color == optimizer::SEL_ARG::BLACK &&
667 w->left->color == optimizer::SEL_ARG::BLACK)
669 w->color= optimizer::SEL_ARG::RED;
674 if (w->left->color == SEL_ARG::BLACK)
676 w->right->color= optimizer::SEL_ARG::BLACK;
677 w->color= optimizer::SEL_ARG::RED;
678 left_rotate(&root, w);
681 w->color= par->color;
682 par->color= optimizer::SEL_ARG::BLACK;
683 w->left->color= optimizer::SEL_ARG::BLACK;
684 right_rotate(&root, par);
691 x->color= optimizer::SEL_ARG::BLACK;