← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/optimizer/sel_arg.cc

  • Committer: Brian Aker
  • Date: 2009-01-07 09:27:07 UTC
  • Revision ID: brian@tangent.org-20090107092707-bn67qpdllfcyh3j9
Removing dead field translator code.

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