drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
sel_arg.cc
1/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3 *
4 * Copyright (C) 2008-2009 Sun Microsystems, Inc.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; version 2 of the License.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 */
19
20#include <config.h>
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>
25
26namespace drizzled {
27
28/* Functions to fix up the tree after insert and delete */
29static void left_rotate(optimizer::SEL_ARG **root, optimizer::SEL_ARG *leaf)
30{
31 optimizer::SEL_ARG *y= leaf->right;
32 leaf->right= y->left;
33 if (y->left != &optimizer::null_element)
34 y->left->parent= leaf;
35 if (! (y->parent=leaf->parent))
36 *root= y;
37 else
38 *leaf->parent_ptr()= y;
39 y->left= leaf;
40 leaf->parent= y;
41}
42
43
44static void right_rotate(optimizer::SEL_ARG **root, optimizer::SEL_ARG *leaf)
45{
46 optimizer::SEL_ARG *y= leaf->left;
47 leaf->left= y->right;
48 if (y->right != &optimizer::null_element)
49 y->right->parent= leaf;
50 if (! (y->parent=leaf->parent))
51 *root= y;
52 else
53 *leaf->parent_ptr()= y;
54 y->right= leaf;
55 leaf->parent= y;
56}
57
58
59/* Get overlapping range */
60optimizer::SEL_ARG *optimizer::SEL_ARG::clone_and(optimizer::SEL_ARG *arg)
61{
62 unsigned char *new_min= NULL;
63 unsigned char *new_max= NULL;
64 uint8_t flag_min= 0;
65 uint8_t flag_max= 0;
66
67 if (cmp_min_to_min(arg) >= 0)
68 {
69 new_min= min_value;
70 flag_min= min_flag;
71 }
72 else
73 {
74 new_min=arg->min_value;
75 flag_min=arg->min_flag;
76 }
77 if (cmp_max_to_max(arg) <= 0)
78 {
79 new_max= max_value;
80 flag_max= max_flag;
81 }
82 else
83 {
84 new_max= arg->max_value;
85 flag_max= arg->max_flag;
86 }
87 return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max, test(maybe_flag && arg->maybe_flag));
88}
89
90
91/* min <= X , arg->min */
92optimizer::SEL_ARG *optimizer::SEL_ARG::clone_first(optimizer::SEL_ARG *arg)
93{
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);
95}
96
97
98/* min <= X <= key_max */
99optimizer::SEL_ARG *optimizer::SEL_ARG::clone_last(optimizer::SEL_ARG *arg)
100{
101 return new SEL_ARG(field, part, min_value, arg->max_value, min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
102}
103
104
105/* Get overlapping range */
106bool optimizer::SEL_ARG::copy_min(optimizer::SEL_ARG *arg)
107{
108 if (cmp_min_to_min(arg) > 0)
109 {
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))
114 {
115 return 1; // Full range
116 }
117 }
118 maybe_flag|= arg->maybe_flag;
119 return 0;
120}
121
122/* Get overlapping range */
123bool optimizer::SEL_ARG::copy_max(optimizer::SEL_ARG *arg)
124{
125 if (cmp_max_to_max(arg) <= 0)
126 {
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))
131 {
132 return 1; // Full range
133 }
134 }
135 maybe_flag|= arg->maybe_flag;
136 return 0;
137}
138
139void optimizer::SEL_ARG::copy_min_to_min(optimizer::SEL_ARG *arg)
140{
141 min_value= arg->min_value;
142 min_flag= arg->min_flag;
143}
144
145
146void optimizer::SEL_ARG::copy_min_to_max(optimizer::SEL_ARG *arg)
147{
148 max_value= arg->min_value;
149 max_flag= arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
150}
151
152void optimizer::SEL_ARG::copy_max_to_min(optimizer::SEL_ARG *arg)
153{
154 min_value= arg->max_value;
155 min_flag= arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
156}
157
158
159int optimizer::SEL_ARG::store_min(uint32_t length, unsigned char **min_key, uint32_t min_key_flag)
160{
161 /* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
162 if ((! (min_flag & NO_MIN_RANGE) &&
163 ! (min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
164 {
165 if (maybe_null && *min_value)
166 {
167 **min_key= 1;
168 memset(*min_key+1, 0, length-1);
169 }
170 else
171 {
172 memcpy(*min_key,min_value,length);
173 }
174 (*min_key)+= length;
175 return 1;
176 }
177 return 0;
178}
179
180
181int optimizer::SEL_ARG::store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
182{
183 if (! (max_flag & NO_MAX_RANGE) &&
184 ! (max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
185 {
186 if (maybe_null && *max_value)
187 {
188 **max_key= 1;
189 memset(*max_key + 1, 0, length-1);
190 }
191 else
192 {
193 memcpy(*max_key,max_value,length);
194 }
195 (*max_key)+= length;
196 return 1;
197 }
198 return 0;
199}
200
201
202int optimizer::SEL_ARG::store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
203{
204 optimizer::SEL_ARG *key_tree= first();
205 uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
206 range_key,
207 *range_key_flag);
208 *range_key_flag|= key_tree->min_flag;
209
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)
214 {
215 res+= key_tree->next_key_part->store_min_key(key,
216 range_key,
217 range_key_flag);
218 }
219 return res;
220}
221
222int optimizer::SEL_ARG::store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
223{
224 SEL_ARG *key_tree= last();
225 uint32_t res= key_tree->store_max(key[key_tree->part].store_length,
226 range_key,
227 *range_key_flag);
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,
234 range_key,
235 range_key_flag);
236 return res;
237}
238
239optimizer::SEL_ARG::SEL_ARG(optimizer::SEL_ARG &arg)
240 :
241 memory::SqlAlloc()
242{
243 type= arg.type;
244 min_flag= arg.min_flag;
245 max_flag= arg.max_flag;
246 maybe_flag= arg.maybe_flag;
247 maybe_null= arg.maybe_null;
248 part= arg.part;
249 field= arg.field;
250 min_value= arg.min_value;
251 max_value= arg.max_value;
252 next_key_part= arg.next_key_part;
253 use_count=1;
254 elements=1;
255}
256
257
258void optimizer::SEL_ARG::make_root()
259{
260 left= right= &optimizer::null_element;
261 color= BLACK;
262 next= prev =0;
263 use_count= 0;
264 elements= 1;
265}
266
267optimizer::SEL_ARG::SEL_ARG(Field *f,
268 const unsigned char *min_value_arg,
269 const unsigned char *max_value_arg)
270 :
271 min_flag(0),
272 max_flag(0),
273 maybe_flag(0),
274 maybe_null(f->real_maybe_null()),
275 elements(1),
276 use_count(1),
277 field(f),
278 min_value((unsigned char*) min_value_arg),
279 max_value((unsigned char*) max_value_arg),
280 next(0),
281 prev(0),
282 next_key_part(0),
283 color(BLACK),
284 type(KEY_RANGE)
285{
286 left= right= &optimizer::null_element;
287}
288
289optimizer::SEL_ARG::SEL_ARG(Field *field_,
290 uint8_t part_,
291 unsigned char *min_value_,
292 unsigned char *max_value_,
293 uint8_t min_flag_,
294 uint8_t max_flag_,
295 uint8_t maybe_flag_)
296 :
297 min_flag(min_flag_),
298 max_flag(max_flag_),
299 maybe_flag(maybe_flag_),
300 part(part_),
301 maybe_null(field_->real_maybe_null()),
302 elements(1),
303 use_count(1),
304 field(field_),
305 min_value(min_value_),
306 max_value(max_value_),
307 next(0),
308 prev(0),
309 next_key_part(0),
310 color(BLACK),
311 type(KEY_RANGE)
312{
313 left= right= &optimizer::null_element;
314}
315
316optimizer::SEL_ARG *optimizer::SEL_ARG::clone(RangeParameter *param, optimizer::SEL_ARG *new_parent, optimizer::SEL_ARG **next_arg)
317{
318 optimizer::SEL_ARG *tmp= NULL;
319
320 /* Bail out if we have already generated too many SEL_ARGs */
321 if (++param->alloced_sel_args > MAX_SEL_ARGS)
322 return 0;
323
324 if (type != KEY_RANGE)
325 {
326 tmp= new (*param->mem_root) optimizer::SEL_ARG(type);
327 tmp->prev= *next_arg; // Link into next/prev chain
328 (*next_arg)->next= tmp;
329 (*next_arg)= tmp;
330 }
331 else
332 {
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)))
338 return 0; // OOM
339
340 tmp->prev= *next_arg; // Link into next/prev chain
341 (*next_arg)->next= tmp;
342 (*next_arg)= tmp;
343
344 if (right != &optimizer::null_element)
345 if (! (tmp->right= right->clone(param, tmp, next_arg)))
346 return 0; // OOM
347 }
348 increment_use_count(1);
349 tmp->color= color;
350 tmp->elements= this->elements;
351 return tmp;
352}
353
354optimizer::SEL_ARG *optimizer::SEL_ARG::first()
355{
356 optimizer::SEL_ARG *next_arg= this;
357 if (! next_arg->left)
358 return 0; // MAYBE_KEY
359 while (next_arg->left != &optimizer::null_element)
360 next_arg= next_arg->left;
361 return next_arg;
362}
363
364optimizer::SEL_ARG *optimizer::SEL_ARG::last()
365{
366 SEL_ARG *next_arg= this;
367 if (! next_arg->right)
368 return 0; // MAYBE_KEY
369 while (next_arg->right != &optimizer::null_element)
370 next_arg=next_arg->right;
371 return next_arg;
372}
373
374
375optimizer::SEL_ARG *optimizer::SEL_ARG::clone_tree(RangeParameter *param)
376{
377 optimizer::SEL_ARG tmp_link;
378 optimizer::SEL_ARG* next_arg= NULL;
379 next_arg= &tmp_link;
380 optimizer::SEL_ARG* root= clone(param, (SEL_ARG *) 0, &next_arg);
381 if (not root)
382 return 0;
383 next_arg->next= 0; // Fix last link
384 tmp_link.next->prev= 0; // Fix first link
385 if (root) // If not OOM
386 root->use_count= 0;
387 return root;
388}
389
390
391optimizer::SEL_ARG *
392optimizer::SEL_ARG::insert(optimizer::SEL_ARG *key)
393{
394 optimizer::SEL_ARG *element= NULL;
395 optimizer::SEL_ARG **par= NULL;
396 optimizer::SEL_ARG *last_element= NULL;
397
398 for (element= this; element != &optimizer::null_element; )
399 {
400 last_element= element;
401 if (key->cmp_min_to_min(element) > 0)
402 {
403 par= &element->right; element= element->right;
404 }
405 else
406 {
407 par= &element->left; element= element->left;
408 }
409 }
410 *par= key;
411 key->parent= last_element;
412 /* Link in list */
413 if (par == &last_element->left)
414 {
415 key->next= last_element;
416 if ((key->prev=last_element->prev))
417 key->prev->next= key;
418 last_element->prev= key;
419 }
420 else
421 {
422 if ((key->next= last_element->next))
423 key->next->prev= key;
424 key->prev= last_element;
425 last_element->next= key;
426 }
427 key->left= key->right= &optimizer::null_element;
428 optimizer::SEL_ARG *root= rb_insert(key); // rebalance tree
429 root->use_count= this->use_count; // copy root info
430 root->elements= this->elements+1;
431 root->maybe_flag= this->maybe_flag;
432 return root;
433}
434
435
436/*
437** Find best key with min <= given key
438** Because the call context this should never return 0 to get_range
439*/
440optimizer::SEL_ARG *
441optimizer::SEL_ARG::find_range(optimizer::SEL_ARG *key)
442{
443 optimizer::SEL_ARG *element= this;
444 optimizer::SEL_ARG *found= NULL;
445
446 for (;;)
447 {
448 if (element == &optimizer::null_element)
449 return found;
450 int cmp= element->cmp_min_to_min(key);
451 if (cmp == 0)
452 return element;
453 if (cmp < 0)
454 {
455 found= element;
456 element= element->right;
457 }
458 else
459 element= element->left;
460 }
461}
462
463
464/*
465 Remove a element from the tree
466
467 SYNOPSIS
468 tree_delete()
469 key Key that is to be deleted from tree (this)
470
471 NOTE
472 This also frees all sub trees that is used by the element
473
474 RETURN
475 root of new tree (with key deleted)
476*/
477optimizer::SEL_ARG *
478optimizer::SEL_ARG::tree_delete(optimizer::SEL_ARG *key)
479{
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;
485
486 root= this;
487 this->parent= 0;
488
489 /* Unlink from list */
490 if (key->prev)
491 key->prev->next= key->next;
492 if (key->next)
493 key->next->prev= key->prev;
494 key->increment_use_count(-1);
495 if (! key->parent)
496 par= &root;
497 else
498 par= key->parent_ptr();
499
500 if (key->left == &optimizer::null_element)
501 {
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;
507 }
508 else if (key->right == &optimizer::null_element)
509 {
510 *par= nod= key->left;
511 nod->parent= fix_par= key->parent;
512 remove_color= key->color;
513 }
514 else
515 {
516 optimizer::SEL_ARG *tmp= key->next; // next bigger key (exist!)
517 nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
518 fix_par= tmp->parent;
519 if (nod != &optimizer::null_element)
520 nod->parent= fix_par;
521 remove_color= tmp->color;
522
523 tmp->parent= key->parent; // Move node in place of key
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;
528 *par= tmp;
529 if (fix_par == key) // key->right == key->next
530 fix_par= tmp; // new parent of nod
531 }
532
533 if (root == &optimizer::null_element)
534 return 0; // Maybe root later
535 if (remove_color == BLACK)
536 root= rb_delete_fixup(root, nod, fix_par);
537
538 root->use_count= this->use_count; // Fix root counters
539 root->elements= this->elements-1;
540 root->maybe_flag= this->maybe_flag;
541 return root;
542}
543
544
545optimizer::SEL_ARG *
546optimizer::SEL_ARG::rb_insert(optimizer::SEL_ARG *leaf)
547{
548 optimizer::SEL_ARG *y= NULL;
549 optimizer::SEL_ARG *par= NULL;
550 optimizer::SEL_ARG *par2= NULL;
551 optimizer::SEL_ARG *root= NULL;
552
553 root= this;
554 root->parent= 0;
555
556 leaf->color= RED;
557 while (leaf != root && (par= leaf->parent)->color == RED)
558 { // This can't be root or 1 level under
559 if (par == (par2= leaf->parent->parent)->left)
560 {
561 y= par2->right;
562 if (y->color == RED)
563 {
564 par->color= BLACK;
565 y->color= BLACK;
566 leaf= par2;
567 leaf->color= RED; /* And the loop continues */
568 }
569 else
570 {
571 if (leaf == par->right)
572 {
573 left_rotate(&root,leaf->parent);
574 par= leaf; /* leaf is now parent to old leaf */
575 }
576 par->color= BLACK;
577 par2->color= RED;
578 right_rotate(&root, par2);
579 break;
580 }
581 }
582 else
583 {
584 y= par2->left;
585 if (y->color == RED)
586 {
587 par->color= BLACK;
588 y->color= BLACK;
589 leaf= par2;
590 leaf->color= RED; /* And the loop continues */
591 }
592 else
593 {
594 if (leaf == par->left)
595 {
596 right_rotate(&root,par);
597 par= leaf;
598 }
599 par->color= BLACK;
600 par2->color= RED;
601 left_rotate(&root, par2);
602 break;
603 }
604 }
605 }
606 root->color= BLACK;
607
608 return root;
609}
610
611
612optimizer::SEL_ARG *optimizer::rb_delete_fixup(optimizer::SEL_ARG *root,
613 optimizer::SEL_ARG *key,
614 optimizer::SEL_ARG *par)
615{
616 optimizer::SEL_ARG *x= NULL;
617 optimizer::SEL_ARG *w= NULL;
618 root->parent= 0;
619
620 x= key;
621 while (x != root && x->color == optimizer::SEL_ARG::BLACK)
622 {
623 if (x == par->left)
624 {
625 w= par->right;
626 if (w->color == optimizer::SEL_ARG::RED)
627 {
628 w->color= optimizer::SEL_ARG::BLACK;
629 par->color= optimizer::SEL_ARG::RED;
630 left_rotate(&root, par);
631 w= par->right;
632 }
633 if (w->left->color == optimizer::SEL_ARG::BLACK &&
634 w->right->color == optimizer::SEL_ARG::BLACK)
635 {
636 w->color= optimizer::SEL_ARG::RED;
637 x= par;
638 }
639 else
640 {
641 if (w->right->color == optimizer::SEL_ARG::BLACK)
642 {
643 w->left->color= optimizer::SEL_ARG::BLACK;
644 w->color= optimizer::SEL_ARG::RED;
645 right_rotate(&root, w);
646 w= par->right;
647 }
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);
652 x= root;
653 break;
654 }
655 }
656 else
657 {
658 w= par->left;
659 if (w->color == optimizer::SEL_ARG::RED)
660 {
661 w->color= optimizer::SEL_ARG::BLACK;
662 par->color= optimizer::SEL_ARG::RED;
663 right_rotate(&root, par);
664 w= par->left;
665 }
666 if (w->right->color == optimizer::SEL_ARG::BLACK &&
667 w->left->color == optimizer::SEL_ARG::BLACK)
668 {
669 w->color= optimizer::SEL_ARG::RED;
670 x= par;
671 }
672 else
673 {
674 if (w->left->color == SEL_ARG::BLACK)
675 {
676 w->right->color= optimizer::SEL_ARG::BLACK;
677 w->color= optimizer::SEL_ARG::RED;
678 left_rotate(&root, w);
679 w= par->left;
680 }
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);
685 x= root;
686 break;
687 }
688 }
689 par= x->parent;
690 }
691 x->color= optimizer::SEL_ARG::BLACK;
692 return root;
693}
694
695
696} /* namespace drizzled */
TODO: Rename this file - func.h is stupid.