« back to all changes in this revision
Viewing changes to drizzled/optimizer/sel_arg.cc
- browse files at revision 1237.13.6
- compare with another revision
- compare with revision 2466
- download diff
- download tarball
- view history from revision 1237.13.6
- Committer: Padraig O'Sullivan
- Date: 2009-12-08 00:22:46 UTC
- mto: (1192.3.76 pandora-build) (1240.3.1 build) (1241.2.6 build)
- mto: This revision was merged to the branch mainline in revision 1241.
- Revision ID: osullivan.padraig@gmail.com-20091208002246-uxc0f5ralh958u1v
Moved the SEL_ARG class into its own header and implementation files. Cleaned up a bunch of style
issues in the code for that class. Next commit will clean up more style issues in that class.
issues in the code for that class. Next commit will clean up more style issues in that class.
added
removed
drizzled/optimizer/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
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 "drizzled/server_includes.h"
21
#include "drizzled/optimizer/range.h"
22
#include "drizzled/optimizer/range_param.h"
23
#include "drizzled/optimizer/sel_arg.h"
24
25
using namespace drizzled;
26
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; flag_min=arg->min_flag;
75
}
76
if (cmp_max_to_max(arg) <= 0)
77
{
78
new_max= max_value;
79
flag_max= max_flag;
80
}
81
else
82
{
83
new_max= arg->max_value;
84
flag_max= arg->max_flag;
85
}
86
return (new SEL_ARG(field,
87
part,
88
new_min,
89
new_max,
90
flag_min,
91
flag_max,
92
test(maybe_flag && arg->maybe_flag)));
93
}
94
95
96
/* min <= X , arg->min */
97
optimizer::SEL_ARG *optimizer::SEL_ARG::clone_first(optimizer::SEL_ARG *arg)
98
{
99
return (new SEL_ARG(field,part,
100
min_value,
101
arg->min_value,
102
min_flag,
103
arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
104
maybe_flag | arg->maybe_flag));
105
}
106
107
108
/* min <= X <= key_max */
109
optimizer::SEL_ARG *optimizer::SEL_ARG::clone_last(optimizer::SEL_ARG *arg)
110
{
111
return (new SEL_ARG(field,
112
part,
113
min_value,
114
arg->max_value,
115
min_flag,
116
arg->max_flag,
117
maybe_flag | arg->maybe_flag));
118
}
119
120
121
/* Get overlapping range */
122
bool optimizer::SEL_ARG::copy_min(optimizer::SEL_ARG *arg)
123
{
124
if (cmp_min_to_min(arg) > 0)
125
{
126
min_value= arg->min_value;
127
min_flag=arg->min_flag;
128
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
129
(NO_MAX_RANGE | NO_MIN_RANGE))
130
{
131
return 1; // Full range
132
}
133
}
134
maybe_flag|= arg->maybe_flag;
135
return 0;
136
}
137
138
/* Get overlapping range */
139
bool optimizer::SEL_ARG::copy_max(optimizer::SEL_ARG *arg)
140
{
141
if (cmp_max_to_max(arg) <= 0)
142
{
143
max_value= arg->max_value;
144
max_flag= arg->max_flag;
145
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
146
(NO_MAX_RANGE | NO_MIN_RANGE))
147
{
148
return 1; // Full range
149
}
150
}
151
maybe_flag|= arg->maybe_flag;
152
return 0;
153
}
154
155
void optimizer::SEL_ARG::copy_min_to_min(optimizer::SEL_ARG *arg)
156
{
157
min_value= arg->min_value;
158
min_flag= arg->min_flag;
159
}
160
161
162
void optimizer::SEL_ARG::copy_min_to_max(optimizer::SEL_ARG *arg)
163
{
164
max_value= arg->min_value;
165
max_flag= arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
166
}
167
168
void optimizer::SEL_ARG::copy_max_to_min(optimizer::SEL_ARG *arg)
169
{
170
min_value= arg->max_value;
171
min_flag= arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
172
}
173
174
175
int optimizer::SEL_ARG::store_min(uint32_t length, unsigned char **min_key, uint32_t min_key_flag)
176
{
177
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
178
if ((! (min_flag & NO_MIN_RANGE) &&
179
! (min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
180
{
181
if (maybe_null && *min_value)
182
{
183
**min_key= 1;
184
memset(*min_key+1, 0, length-1);
185
}
186
else
187
{
188
memcpy(*min_key,min_value,length);
189
}
190
(*min_key)+= length;
191
return 1;
192
}
193
return 0;
194
}
195
196
197
int optimizer::SEL_ARG::store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
198
{
199
if (! (max_flag & NO_MAX_RANGE) &&
200
! (max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
201
{
202
if (maybe_null && *max_value)
203
{
204
**max_key= 1;
205
memset(*max_key + 1, 0, length-1);
206
}
207
else
208
{
209
memcpy(*max_key,max_value,length);
210
}
211
(*max_key)+= length;
212
return 1;
213
}
214
return 0;
215
}
216
217
218
int optimizer::SEL_ARG::store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
219
{
220
optimizer::SEL_ARG *key_tree= first();
221
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
222
range_key,
223
*range_key_flag);
224
*range_key_flag|= key_tree->min_flag;
225
226
if (key_tree->next_key_part &&
227
key_tree->next_key_part->part == key_tree->part+1 &&
228
! (*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
229
key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
230
{
231
res+= key_tree->next_key_part->store_min_key(key,
232
range_key,
233
range_key_flag);
234
}
235
return res;
236
}
237
238
int optimizer::SEL_ARG::store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
239
{
240
SEL_ARG *key_tree= last();
241
uint32_t res= key_tree->store_max(key[key_tree->part].store_length,
242
range_key,
243
*range_key_flag);
244
(*range_key_flag)|= key_tree->max_flag;
245
if (key_tree->next_key_part &&
246
key_tree->next_key_part->part == key_tree->part+1 &&
247
! (*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
248
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
249
res+= key_tree->next_key_part->store_max_key(key,
250
range_key,
251
range_key_flag);
252
return res;
253
}
254
255
optimizer::SEL_ARG::SEL_ARG(optimizer::SEL_ARG &arg)
256
:
257
Sql_alloc()
258
{
259
type= arg.type;
260
min_flag= arg.min_flag;
261
max_flag= arg.max_flag;
262
maybe_flag= arg.maybe_flag;
263
maybe_null= arg.maybe_null;
264
part= arg.part;
265
field= arg.field;
266
min_value= arg.min_value;
267
max_value= arg.max_value;
268
next_key_part= arg.next_key_part;
269
use_count=1;
270
elements=1;
271
}
272
273
274
void optimizer::SEL_ARG::make_root()
275
{
276
left= right= &optimizer::null_element;
277
color= BLACK;
278
next= prev =0;
279
use_count= 0;
280
elements= 1;
281
}
282
283
optimizer::SEL_ARG::SEL_ARG(Field *f,
284
const unsigned char *min_value_arg,
285
const unsigned char *max_value_arg)
286
:
287
min_flag(0),
288
max_flag(0),
289
maybe_flag(0),
290
maybe_null(f->real_maybe_null()),
291
elements(1),
292
use_count(1),
293
field(f),
294
min_value((unsigned char*) min_value_arg),
295
max_value((unsigned char*) max_value_arg),
296
next(0),
297
prev(0),
298
next_key_part(0),
299
color(BLACK),
300
type(KEY_RANGE)
301
{
302
left= right= &optimizer::null_element;
303
}
304
305
optimizer::SEL_ARG::SEL_ARG(Field *field_,
306
uint8_t part_,
307
unsigned char *min_value_,
308
unsigned char *max_value_,
309
uint8_t min_flag_,
310
uint8_t max_flag_,
311
uint8_t maybe_flag_)
312
:
313
min_flag(min_flag_),
314
max_flag(max_flag_),
315
maybe_flag(maybe_flag_),
316
part(part_),
317
maybe_null(field_->real_maybe_null()),
318
elements(1),
319
use_count(1),
320
field(field_),
321
min_value(min_value_),
322
max_value(max_value_),
323
next(0),
324
prev(0),
325
next_key_part(0),
326
color(BLACK),
327
type(KEY_RANGE)
328
{
329
left= right= &optimizer::null_element;
330
}
331
332
optimizer::SEL_ARG *optimizer::SEL_ARG::clone(RANGE_OPT_PARAM *param,
333
optimizer::SEL_ARG *new_parent,
334
optimizer::SEL_ARG **next_arg)
335
{
336
optimizer::SEL_ARG *tmp= NULL;
337
338
/* Bail out if we have already generated too many SEL_ARGs */
339
if (++param->alloced_sel_args > MAX_SEL_ARGS)
340
return 0;
341
342
if (type != KEY_RANGE)
343
{
344
if (! (tmp= new (param->mem_root) optimizer::SEL_ARG(type)))
345
return 0; // out of memory
346
tmp->prev= *next_arg; // Link into next/prev chain
347
(*next_arg)->next= tmp;
348
(*next_arg)= tmp;
349
}
350
else
351
{
352
if (! (tmp= new (param->mem_root) optimizer::SEL_ARG(field,
353
part,
354
min_value,
355
max_value,
356
min_flag,
357
max_flag,
358
maybe_flag)))
359
return 0; // OOM
360
tmp->parent= new_parent;
361
tmp->next_key_part= next_key_part;
362
if (left != &optimizer::null_element)
363
if (! (tmp->left= left->clone(param, tmp, next_arg)))
364
return 0; // OOM
365
366
tmp->prev= *next_arg; // Link into next/prev chain
367
(*next_arg)->next= tmp;
368
(*next_arg)= tmp;
369
370
if (right != &optimizer::null_element)
371
if (! (tmp->right= right->clone(param, tmp, next_arg)))
372
return 0; // OOM
373
}
374
increment_use_count(1);
375
tmp->color= color;
376
tmp->elements= this->elements;
377
return tmp;
378
}
379
380
optimizer::SEL_ARG *optimizer::SEL_ARG::first()
381
{
382
optimizer::SEL_ARG *next_arg= this;
383
if (! next_arg->left)
384
return 0; // MAYBE_KEY
385
while (next_arg->left != &optimizer::null_element)
386
next_arg= next_arg->left;
387
return next_arg;
388
}
389
390
optimizer::SEL_ARG *optimizer::SEL_ARG::last()
391
{
392
SEL_ARG *next_arg= this;
393
if (! next_arg->right)
394
return 0; // MAYBE_KEY
395
while (next_arg->right != &optimizer::null_element)
396
next_arg=next_arg->right;
397
return next_arg;
398
}
399
400
401
optimizer::SEL_ARG *optimizer::SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
402
{
403
optimizer::SEL_ARG tmp_link;
404
optimizer::SEL_ARG*next_arg= NULL;
405
optimizer::SEL_ARG *root= NULL;
406
next_arg= &tmp_link;
407
if (! (root= clone(param, (SEL_ARG *) 0, &next_arg)))
408
return 0;
409
next_arg->next= 0; // Fix last link
410
tmp_link.next->prev= 0; // Fix first link
411
if (root) // If not OOM
412
root->use_count= 0;
413
return root;
414
}
415
416
417
optimizer::SEL_ARG *
418
optimizer::SEL_ARG::insert(optimizer::SEL_ARG *key)
419
{
420
optimizer::SEL_ARG *element= NULL;
421
optimizer::SEL_ARG **par= NULL;
422
optimizer::SEL_ARG *last_element= NULL;
423
424
for (element= this; element != &optimizer::null_element; )
425
{
426
last_element= element;
427
if (key->cmp_min_to_min(element) > 0)
428
{
429
par= &element->right; element= element->right;
430
}
431
else
432
{
433
par= &element->left; element= element->left;
434
}
435
}
436
*par= key;
437
key->parent= last_element;
438
/* Link in list */
439
if (par == &last_element->left)
440
{
441
key->next= last_element;
442
if ((key->prev=last_element->prev))
443
key->prev->next= key;
444
last_element->prev= key;
445
}
446
else
447
{
448
if ((key->next= last_element->next))
449
key->next->prev= key;
450
key->prev= last_element;
451
last_element->next= key;
452
}
453
key->left= key->right= &optimizer::null_element;
454
optimizer::SEL_ARG *root= rb_insert(key); // rebalance tree
455
root->use_count= this->use_count; // copy root info
456
root->elements= this->elements+1;
457
root->maybe_flag= this->maybe_flag;
458
return root;
459
}
460
461
462
/*
463
** Find best key with min <= given key
464
** Because the call context this should never return 0 to get_range
465
*/
466
optimizer::SEL_ARG *
467
optimizer::SEL_ARG::find_range(optimizer::SEL_ARG *key)
468
{
469
optimizer::SEL_ARG *element= this;
470
optimizer::SEL_ARG *found= NULL;
471
472
for (;;)
473
{
474
if (element == &optimizer::null_element)
475
return found;
476
int cmp= element->cmp_min_to_min(key);
477
if (cmp == 0)
478
return element;
479
if (cmp < 0)
480
{
481
found= element;
482
element= element->right;
483
}
484
else
485
element= element->left;
486
}
487
}
488
489
490
/*
491
Remove a element from the tree
492
493
SYNOPSIS
494
tree_delete()
495
key Key that is to be deleted from tree (this)
496
497
NOTE
498
This also frees all sub trees that is used by the element
499
500
RETURN
501
root of new tree (with key deleted)
502
*/
503
optimizer::SEL_ARG *
504
optimizer::SEL_ARG::tree_delete(optimizer::SEL_ARG *key)
505
{
506
enum leaf_color remove_color;
507
optimizer::SEL_ARG *root= NULL;
508
optimizer::SEL_ARG *nod= NULL;
509
optimizer::SEL_ARG **par= NULL;
510
optimizer::SEL_ARG *fix_par= NULL;
511
512
root= this;
513
this->parent= 0;
514
515
/* Unlink from list */
516
if (key->prev)
517
key->prev->next= key->next;
518
if (key->next)
519
key->next->prev= key->prev;
520
key->increment_use_count(-1);
521
if (! key->parent)
522
par= &root;
523
else
524
par= key->parent_ptr();
525
526
if (key->left == &optimizer::null_element)
527
{
528
*par= nod= key->right;
529
fix_par= key->parent;
530
if (nod != &optimizer::null_element)
531
nod->parent= fix_par;
532
remove_color= key->color;
533
}
534
else if (key->right == &optimizer::null_element)
535
{
536
*par= nod= key->left;
537
nod->parent= fix_par= key->parent;
538
remove_color= key->color;
539
}
540
else
541
{
542
optimizer::SEL_ARG *tmp= key->next; // next bigger key (exist!)
543
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
544
fix_par= tmp->parent;
545
if (nod != &optimizer::null_element)
546
nod->parent= fix_par;
547
remove_color= tmp->color;
548
549
tmp->parent= key->parent; // Move node in place of key
550
(tmp->left= key->left)->parent= tmp;
551
if ((tmp->right=key->right) != &optimizer::null_element)
552
tmp->right->parent= tmp;
553
tmp->color= key->color;
554
*par= tmp;
555
if (fix_par == key) // key->right == key->next
556
fix_par= tmp; // new parent of nod
557
}
558
559
if (root == &optimizer::null_element)
560
return 0; // Maybe root later
561
if (remove_color == BLACK)
562
root= rb_delete_fixup(root, nod, fix_par);
563
564
root->use_count= this->use_count; // Fix root counters
565
root->elements= this->elements-1;
566
root->maybe_flag= this->maybe_flag;
567
return root;
568
}
569
570
571
optimizer::SEL_ARG *
572
optimizer::SEL_ARG::rb_insert(optimizer::SEL_ARG *leaf)
573
{
574
optimizer::SEL_ARG *y= NULL;
575
optimizer::SEL_ARG *par= NULL;
576
optimizer::SEL_ARG *par2= NULL;
577
optimizer::SEL_ARG *root= NULL;
578
579
root= this;
580
root->parent= 0;
581
582
leaf->color= RED;
583
while (leaf != root && (par= leaf->parent)->color == RED)
584
{ // This can't be root or 1 level under
585
if (par == (par2= leaf->parent->parent)->left)
586
{
587
y= par2->right;
588
if (y->color == RED)
589
{
590
par->color= BLACK;
591
y->color= BLACK;
592
leaf= par2;
593
leaf->color= RED; /* And the loop continues */
594
}
595
else
596
{
597
if (leaf == par->right)
598
{
599
left_rotate(&root,leaf->parent);
600
par= leaf; /* leaf is now parent to old leaf */
601
}
602
par->color= BLACK;
603
par2->color= RED;
604
right_rotate(&root, par2);
605
break;
606
}
607
}
608
else
609
{
610
y= par2->left;
611
if (y->color == RED)
612
{
613
par->color= BLACK;
614
y->color= BLACK;
615
leaf= par2;
616
leaf->color= RED; /* And the loop continues */
617
}
618
else
619
{
620
if (leaf == par->left)
621
{
622
right_rotate(&root,par);
623
par= leaf;
624
}
625
par->color= BLACK;
626
par2->color= RED;
627
left_rotate(&root, par2);
628
break;
629
}
630
}
631
}
632
root->color= BLACK;
633
634
return root;
635
}
636
637
638
optimizer::SEL_ARG *optimizer::rb_delete_fixup(optimizer::SEL_ARG *root,
639
optimizer::SEL_ARG *key,
640
optimizer::SEL_ARG *par)
641
{
642
optimizer::SEL_ARG *x= NULL;
643
optimizer::SEL_ARG *w= NULL;
644
root->parent= 0;
645
646
x= key;
647
while (x != root && x->color == optimizer::SEL_ARG::BLACK)
648
{
649
if (x == par->left)
650
{
651
w= par->right;
652
if (w->color == optimizer::SEL_ARG::RED)
653
{
654
w->color= optimizer::SEL_ARG::BLACK;
655
par->color= optimizer::SEL_ARG::RED;
656
left_rotate(&root, par);
657
w= par->right;
658
}
659
if (w->left->color == optimizer::SEL_ARG::BLACK &&
660
w->right->color == optimizer::SEL_ARG::BLACK)
661
{
662
w->color= optimizer::SEL_ARG::RED;
663
x= par;
664
}
665
else
666
{
667
if (w->right->color == optimizer::SEL_ARG::BLACK)
668
{
669
w->left->color= optimizer::SEL_ARG::BLACK;
670
w->color= optimizer::SEL_ARG::RED;
671
right_rotate(&root, w);
672
w= par->right;
673
}
674
w->color= par->color;
675
par->color= optimizer::SEL_ARG::BLACK;
676
w->right->color= optimizer::SEL_ARG::BLACK;
677
left_rotate(&root, par);
678
x= root;
679
break;
680
}
681
}
682
else
683
{
684
w= par->left;
685
if (w->color == optimizer::SEL_ARG::RED)
686
{
687
w->color= optimizer::SEL_ARG::BLACK;
688
par->color= optimizer::SEL_ARG::RED;
689
right_rotate(&root, par);
690
w= par->left;
691
}
692
if (w->right->color == optimizer::SEL_ARG::BLACK &&
693
w->left->color == optimizer::SEL_ARG::BLACK)
694
{
695
w->color= optimizer::SEL_ARG::RED;
696
x= par;
697
}
698
else
699
{
700
if (w->left->color == SEL_ARG::BLACK)
701
{
702
w->right->color= optimizer::SEL_ARG::BLACK;
703
w->color= optimizer::SEL_ARG::RED;
704
left_rotate(&root, w);
705
w= par->left;
706
}
707
w->color= par->color;
708
par->color= optimizer::SEL_ARG::BLACK;
709
w->left->color= optimizer::SEL_ARG::BLACK;
710
right_rotate(&root, par);
711
x= root;
712
break;
713
}
714
}
715
par= x->parent;
716
}
717
x->color= optimizer::SEL_ARG::BLACK;
718
return root;
719
}
720
721
Loggerhead is a web-based interface for Breezy
Version: 2.0.1