← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/sel_arg.cc

  • Committer: Padraig O'Sullivan
  • Date: 2009-09-13 01:03:01 UTC
  • mto: (1126.9.2 captain-20090915-01)
  • mto: This revision was merged to the branch mainline in revision 1133.
  • Revision ID: osullivan.padraig@gmail.com-20090913010301-tcvvezipx1124acy
Added calls to the dtrace delete begin/end probes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 "config.h"
21
 
#include "drizzled/optimizer/range.h"
22
 
#include "drizzled/optimizer/range_param.h"
23
 
#include "drizzled/optimizer/sel_arg.h"
24
 
 
25
 
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
 
    memory::SqlAlloc()
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(RangeParameter *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(RangeParameter *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
 
 
722
 
} /* namespace drizzled */