Drizzled Public API Documentation

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 
26 namespace drizzled {
27 
28 /* Functions to fix up the tree after insert and delete */
29 static 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 
44 static 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 */
60 optimizer::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 */
92 optimizer::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 */
99 optimizer::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 */
106 bool 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 */
123 bool 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 
139 void 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 
146 void 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 
152 void 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 
159 int 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 
181 int 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 
202 int 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 
222 int 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 
239 optimizer::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 
258 void 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 
267 optimizer::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 
289 optimizer::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 
316 optimizer::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 
354 optimizer::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 
364 optimizer::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 
375 optimizer::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 
391 optimizer::SEL_ARG *
392 optimizer::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 */
440 optimizer::SEL_ARG *
441 optimizer::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 */
477 optimizer::SEL_ARG *
478 optimizer::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 
545 optimizer::SEL_ARG *
546 optimizer::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 
612 optimizer::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 */