← Back to branch summary

~ubuntu-branches/ubuntu/trusty/drizzle/trusty

« back to all changes in this revision

Viewing changes to drizzled/my_tree.cc

  • Committer: Bazaar Package Importer
  • Author(s): Monty Taylor
  • Date: 2010-10-02 14:17:48 UTC
  • mfrom: (1.1.1 upstream)
  • mto: (2.1.17 sid)
  • mto: This revision was merged to the branch mainline in revision 3.
  • Revision ID: james.westby@ubuntu.com-20101002141748-m6vbfbfjhrw1153e
Tags: 2010.09.1802-1
* New upstream release.
* Removed pid-file argument hack.
* Updated GPL-2 address to be new address.
* Directly copy in drizzledump.1 since debian doesn't have sphinx 1.0 yet.
* Link to jquery from libjs-jquery. Add it as a depend.
* Add drizzled.8 symlink to the install files.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/my_tree.cc
1
 
/* Copyright (C) 2000 MySQL AB
2
 
 
3
 
   This program is free software; you can redistribute it and/or modify
4
 
   it under the terms of the GNU General Public License as published by
5
 
   the Free Software Foundation; version 2 of the License.
6
 
 
7
 
   This program is distributed in the hope that it will be useful,
8
 
   but WITHOUT ANY WARRANTY; without even the implied warranty of
9
 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10
 
   GNU General Public License for more details.
11
 
 
12
 
   You should have received a copy of the GNU General Public License
13
 
   along with this program; if not, write to the Free Software
14
 
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
15
 
 
16
 
/*
17
 
  Code for handling red-black (balanced) binary trees.
18
 
  key in tree is allocated accrding to following:
19
 
 
20
 
  1) If size < 0 then tree will not allocate keys and only a pointer to
21
 
     each key is saved in tree.
22
 
     compare and search functions uses and returns key-pointer
23
 
 
24
 
  2) If size == 0 then there are two options:
25
 
       - key_size != 0 to tree_insert: The key will be stored in the tree.
26
 
       - key_size == 0 to tree_insert:  A pointer to the key is stored.
27
 
     compare and search functions uses and returns key-pointer.
28
 
 
29
 
  3) if key_size is given to init_tree then each node will continue the
30
 
     key and calls to insert_key may increase length of key.
31
 
     if key_size > sizeof(pointer) and key_size is a multiple of 8 (double
32
 
     allign) then key will be put on a 8 alligned adress. Else
33
 
     the key will be on adress (element+1). This is transparent for user
34
 
     compare and search functions uses a pointer to given key-argument.
35
 
 
36
 
  - If you use a free function for tree-elements and you are freeing
37
 
    the element itself, you should use key_size = 0 to init_tree and
38
 
    tree_search
39
 
 
40
 
  The actual key in TREE_ELEMENT is saved as a pointer or after the
41
 
  TREE_ELEMENT struct.
42
 
  If one uses only pointers in tree one can use tree_set_pointer() to
43
 
  change address of data.
44
 
 
45
 
  Implemented by monty.
46
 
*/
47
 
 
48
 
/*
49
 
  NOTE:
50
 
  tree->compare function should be ALWAYS called as
51
 
    (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element), key)
52
 
  and not other way around, as
53
 
    (*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
54
 
*/
55
 
 
56
 
#include "config.h"
57
 
 
58
 
#include "drizzled/my_tree.h"
59
 
#include "drizzled/internal/my_sys.h"
60
 
#include "drizzled/internal/m_string.h"
61
 
#include "drizzled/memory/root.h"
62
 
 
63
 
#define BLACK           1
64
 
#define RED             0
65
 
#define DEFAULT_ALLOC_SIZE 8192
66
 
#define DEFAULT_ALIGN_SIZE 8192
67
 
 
68
 
#define ELEMENT_KEY(tree,element)\
69
 
(tree->offset_to_key ? (void*)((unsigned char*) element+tree->offset_to_key) :\
70
 
                        *((void**) (element+1)))
71
 
#define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
72
 
 
73
 
namespace drizzled
74
 
{
75
 
 
76
 
 
77
 
static void delete_tree_element(TREE *,TREE_ELEMENT *);
78
 
static int tree_walk_left_root_right(TREE *,TREE_ELEMENT *,
79
 
                                     tree_walk_action,void *);
80
 
static int tree_walk_right_root_left(TREE *,TREE_ELEMENT *,
81
 
                                     tree_walk_action,void *);
82
 
static void left_rotate(TREE_ELEMENT **parent,TREE_ELEMENT *leaf);
83
 
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
84
 
static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
85
 
                      TREE_ELEMENT *leaf);
86
 
static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
87
 
 
88
 
 
89
 
void init_tree(TREE *tree, size_t default_alloc_size, uint32_t memory_limit,
90
 
               uint32_t size, qsort_cmp2 compare, bool with_delete,
91
 
               tree_element_free free_element, void *custom_arg)
92
 
{
93
 
  if (default_alloc_size < DEFAULT_ALLOC_SIZE)
94
 
    default_alloc_size= DEFAULT_ALLOC_SIZE;
95
 
  default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
96
 
  memset(&tree->null_element, 0, sizeof(tree->null_element));
97
 
  tree->root= &tree->null_element;
98
 
  tree->compare= compare;
99
 
  tree->size_of_element= size > 0 ? (uint32_t) size : 0;
100
 
  tree->memory_limit= memory_limit;
101
 
  tree->free= free_element;
102
 
  tree->allocated= 0;
103
 
  tree->elements_in_tree= 0;
104
 
  tree->custom_arg = custom_arg;
105
 
  tree->null_element.colour= BLACK;
106
 
  tree->null_element.left=tree->null_element.right= 0;
107
 
  tree->flag= 0;
108
 
  if (!free_element &&
109
 
      (size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
110
 
  {
111
 
    /*
112
 
      We know that the data doesn't have to be aligned (like if the key
113
 
      contains a double), so we can store the data combined with the
114
 
      TREE_ELEMENT.
115
 
    */
116
 
    tree->offset_to_key= sizeof(TREE_ELEMENT); /* Put key after element */
117
 
    /* Fix allocation size so that we don't lose any memory */
118
 
    default_alloc_size/= (sizeof(TREE_ELEMENT)+size);
119
 
    if (!default_alloc_size)
120
 
      default_alloc_size= 1;
121
 
    default_alloc_size*= (sizeof(TREE_ELEMENT)+size);
122
 
  }
123
 
  else
124
 
  {
125
 
    tree->offset_to_key= 0;             /* use key through pointer */
126
 
    tree->size_of_element+= sizeof(void*);
127
 
  }
128
 
  if (! (tree->with_delete= with_delete))
129
 
  {
130
 
    init_alloc_root(&tree->mem_root, default_alloc_size);
131
 
    tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
132
 
  }
133
 
}
134
 
 
135
 
static void free_tree(TREE *tree, myf free_flags)
136
 
{
137
 
  if (tree->root)                               /* If initialized */
138
 
  {
139
 
    if (tree->with_delete)
140
 
      delete_tree_element(tree,tree->root);
141
 
    else
142
 
    {
143
 
      if (tree->free)
144
 
      {
145
 
        if (tree->memory_limit)
146
 
          (*tree->free)(NULL, free_init, tree->custom_arg);
147
 
        delete_tree_element(tree,tree->root);
148
 
        if (tree->memory_limit)
149
 
          (*tree->free)(NULL, free_end, tree->custom_arg);
150
 
      }
151
 
      free_root(&tree->mem_root, free_flags);
152
 
    }
153
 
  }
154
 
  tree->root= &tree->null_element;
155
 
  tree->elements_in_tree= 0;
156
 
  tree->allocated= 0;
157
 
}
158
 
 
159
 
void delete_tree(TREE* tree)
160
 
{
161
 
  free_tree(tree, MYF(0)); /* free() mem_root if applicable */
162
 
}
163
 
 
164
 
void reset_tree(TREE* tree)
165
 
{
166
 
  /* do not free mem_root, just mark blocks as free */
167
 
  free_tree(tree, MYF(memory::MARK_BLOCKS_FREE));
168
 
}
169
 
 
170
 
 
171
 
static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
172
 
{
173
 
  if (element != &tree->null_element)
174
 
  {
175
 
    delete_tree_element(tree,element->left);
176
 
    if (tree->free)
177
 
      (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
178
 
    delete_tree_element(tree,element->right);
179
 
    if (tree->with_delete)
180
 
      free((char*) element);
181
 
  }
182
 
}
183
 
 
184
 
 
185
 
/*
186
 
  insert, search and delete of elements
187
 
 
188
 
  The following should be true:
189
 
    parent[0] = & parent[-1][0]->left ||
190
 
    parent[0] = & parent[-1][0]->right
191
 
*/
192
 
 
193
 
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size,
194
 
                          void* custom_arg)
195
 
{
196
 
  int cmp;
197
 
  TREE_ELEMENT *element,***parent;
198
 
 
199
 
  parent= tree->parents;
200
 
  *parent = &tree->root; element= tree->root;
201
 
  for (;;)
202
 
  {
203
 
    if (element == &tree->null_element ||
204
 
        (cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
205
 
                                key)) == 0)
206
 
      break;
207
 
    if (cmp < 0)
208
 
    {
209
 
      *++parent= &element->right; element= element->right;
210
 
    }
211
 
    else
212
 
    {
213
 
      *++parent = &element->left; element= element->left;
214
 
    }
215
 
  }
216
 
  if (element == &tree->null_element)
217
 
  {
218
 
    size_t alloc_size= sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
219
 
    tree->allocated+= alloc_size;
220
 
 
221
 
    if (tree->memory_limit && tree->elements_in_tree
222
 
                           && tree->allocated > tree->memory_limit)
223
 
    {
224
 
      reset_tree(tree);
225
 
      return tree_insert(tree, key, key_size, custom_arg);
226
 
    }
227
 
 
228
 
    key_size+= tree->size_of_element;
229
 
    if (tree->with_delete)
230
 
      element= (TREE_ELEMENT *) malloc(alloc_size);
231
 
    else
232
 
      element= (TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
233
 
    if (!element)
234
 
      return(NULL);
235
 
    **parent= element;
236
 
    element->left= element->right= &tree->null_element;
237
 
    if (!tree->offset_to_key)
238
 
    {
239
 
      if (key_size == sizeof(void*))             /* no length, save pointer */
240
 
        *((void**) (element+1))= key;
241
 
      else
242
 
      {
243
 
        *((void**) (element+1))= (void*) ((void **) (element+1)+1);
244
 
        memcpy(*((void **) (element+1)),key, key_size - sizeof(void*));
245
 
      }
246
 
    }
247
 
    else
248
 
      memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
249
 
    element->count= 1;                  /* May give warning in purify */
250
 
    tree->elements_in_tree++;
251
 
    rb_insert(tree,parent,element);     /* rebalance tree */
252
 
  }
253
 
  else
254
 
  {
255
 
    if (tree->flag & TREE_NO_DUPS)
256
 
      return(NULL);
257
 
    element->count++;
258
 
    /* Avoid a wrap over of the count. */
259
 
    if (! element->count)
260
 
      element->count--;
261
 
  }
262
 
 
263
 
  return element;
264
 
}
265
 
 
266
 
int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
267
 
{
268
 
  int remove_colour;
269
 
  TREE_ELEMENT *element,***parent, ***org_parent, *nod;
270
 
  if (!tree->with_delete)
271
 
    return 1;                                   /* not allowed */
272
 
 
273
 
  parent= tree->parents;
274
 
  *parent= &tree->root; element= tree->root;
275
 
  for (;;)
276
 
  {
277
 
    int cmp;
278
 
 
279
 
    if (element == &tree->null_element)
280
 
      return 1;                         /* Was not in tree */
281
 
    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
282
 
                                key)) == 0)
283
 
      break;
284
 
    if (cmp < 0)
285
 
    {
286
 
      *++parent= &element->right; element= element->right;
287
 
    }
288
 
    else
289
 
    {
290
 
      *++parent = &element->left; element= element->left;
291
 
    }
292
 
  }
293
 
  if (element->left == &tree->null_element)
294
 
  {
295
 
    (**parent)= element->right;
296
 
    remove_colour= element->colour;
297
 
  }
298
 
  else if (element->right == &tree->null_element)
299
 
  {
300
 
    (**parent)= element->left;
301
 
    remove_colour= element->colour;
302
 
  }
303
 
  else
304
 
  {
305
 
    org_parent= parent;
306
 
    *++parent= &element->right; nod= element->right;
307
 
    while (nod->left != &tree->null_element)
308
 
    {
309
 
      *++parent= &nod->left; nod= nod->left;
310
 
    }
311
 
    (**parent)= nod->right;             /* unlink nod from tree */
312
 
    remove_colour= nod->colour;
313
 
    org_parent[0][0]= nod;              /* put y in place of element */
314
 
    org_parent[1]= &nod->right;
315
 
    nod->left= element->left;
316
 
    nod->right= element->right;
317
 
    nod->colour= element->colour;
318
 
  }
319
 
  if (remove_colour == BLACK)
320
 
    rb_delete_fixup(tree,parent);
321
 
  if (tree->free)
322
 
    (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
323
 
  tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
324
 
  free((unsigned char*) element);
325
 
  tree->elements_in_tree--;
326
 
 
327
 
  return 0;
328
 
}
329
 
 
330
 
void *tree_search_key(TREE *tree, const void *key,
331
 
                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
332
 
                      enum ha_rkey_function flag, void *custom_arg)
333
 
{
334
 
  TREE_ELEMENT *element= tree->root;
335
 
  TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
336
 
  TREE_ELEMENT **last_equal_element= NULL;
337
 
 
338
 
/*
339
 
  TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
340
 
*/
341
 
 
342
 
  *parents = &tree->null_element;
343
 
  while (element != &tree->null_element)
344
 
  {
345
 
    int cmp;
346
 
 
347
 
    *++parents= element;
348
 
 
349
 
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
350
 
                               key)) == 0)
351
 
    {
352
 
      switch (flag) {
353
 
      case HA_READ_KEY_EXACT:
354
 
      case HA_READ_KEY_OR_NEXT:
355
 
      case HA_READ_BEFORE_KEY:
356
 
        last_equal_element= parents;
357
 
        cmp= 1;
358
 
        break;
359
 
      case HA_READ_AFTER_KEY:
360
 
        cmp= -1;
361
 
        break;
362
 
      case HA_READ_PREFIX_LAST:
363
 
      case HA_READ_PREFIX_LAST_OR_PREV:
364
 
        last_equal_element= parents;
365
 
        cmp= -1;
366
 
        break;
367
 
      default:
368
 
        return NULL;
369
 
      }
370
 
    }
371
 
    if (cmp < 0) /* element < key */
372
 
    {
373
 
      last_right_step_parent= parents;
374
 
      element= element->right;
375
 
    }
376
 
    else
377
 
    {
378
 
      last_left_step_parent= parents;
379
 
      element= element->left;
380
 
    }
381
 
  }
382
 
  switch (flag) {
383
 
  case HA_READ_KEY_EXACT:
384
 
  case HA_READ_PREFIX_LAST:
385
 
    *last_pos= last_equal_element;
386
 
    break;
387
 
  case HA_READ_KEY_OR_NEXT:
388
 
    *last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
389
 
    break;
390
 
  case HA_READ_AFTER_KEY:
391
 
    *last_pos= last_left_step_parent;
392
 
    break;
393
 
  case HA_READ_PREFIX_LAST_OR_PREV:
394
 
    *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
395
 
    break;
396
 
  case HA_READ_BEFORE_KEY:
397
 
    *last_pos= last_right_step_parent;
398
 
    break;
399
 
  default:
400
 
    return NULL;
401
 
  }
402
 
 
403
 
  return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
404
 
}
405
 
 
406
 
/*
407
 
  Search first (the most left) or last (the most right) tree element
408
 
*/
409
 
void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
410
 
                       TREE_ELEMENT ***last_pos, int child_offs)
411
 
{
412
 
  TREE_ELEMENT *element= tree->root;
413
 
 
414
 
  *parents= &tree->null_element;
415
 
  while (element != &tree->null_element)
416
 
  {
417
 
    *++parents= element;
418
 
    element= ELEMENT_CHILD(element, child_offs);
419
 
  }
420
 
  *last_pos= parents;
421
 
  return **last_pos != &tree->null_element ?
422
 
    ELEMENT_KEY(tree, **last_pos) : NULL;
423
 
}
424
 
 
425
 
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
426
 
                       int r_offs)
427
 
{
428
 
  TREE_ELEMENT *x= **last_pos;
429
 
 
430
 
  if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
431
 
  {
432
 
    x= ELEMENT_CHILD(x, r_offs);
433
 
    *++*last_pos= x;
434
 
    while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
435
 
    {
436
 
      x= ELEMENT_CHILD(x, l_offs);
437
 
      *++*last_pos= x;
438
 
    }
439
 
    return ELEMENT_KEY(tree, x);
440
 
  }
441
 
  else
442
 
  {
443
 
    TREE_ELEMENT *y= *--*last_pos;
444
 
    while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
445
 
    {
446
 
      x= y;
447
 
      y= *--*last_pos;
448
 
    }
449
 
    return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
450
 
  }
451
 
}
452
 
 
453
 
/*
454
 
  Expected that tree is fully balanced
455
 
  (each path from root to leaf has the same length)
456
 
*/
457
 
ha_rows tree_record_pos(TREE *tree, const void *key,
458
 
                        enum ha_rkey_function flag, void *custom_arg)
459
 
{
460
 
  TREE_ELEMENT *element= tree->root;
461
 
  double left= 1;
462
 
  double right= tree->elements_in_tree;
463
 
 
464
 
  while (element != &tree->null_element)
465
 
  {
466
 
    int cmp;
467
 
 
468
 
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
469
 
                               key)) == 0)
470
 
    {
471
 
      switch (flag) {
472
 
      case HA_READ_KEY_EXACT:
473
 
      case HA_READ_BEFORE_KEY:
474
 
        cmp= 1;
475
 
        break;
476
 
      case HA_READ_AFTER_KEY:
477
 
        cmp= -1;
478
 
        break;
479
 
      default:
480
 
        return HA_POS_ERROR;
481
 
      }
482
 
    }
483
 
    if (cmp < 0) /* element < key */
484
 
    {
485
 
      element= element->right;
486
 
      left= (left + right) / 2;
487
 
    }
488
 
    else
489
 
    {
490
 
      element= element->left;
491
 
      right= (left + right) / 2;
492
 
    }
493
 
  }
494
 
 
495
 
  switch (flag) {
496
 
  case HA_READ_KEY_EXACT:
497
 
  case HA_READ_BEFORE_KEY:
498
 
    return (ha_rows) right;
499
 
  case HA_READ_AFTER_KEY:
500
 
    return (ha_rows) left;
501
 
  default:
502
 
    return HA_POS_ERROR;
503
 
  }
504
 
}
505
 
 
506
 
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
507
 
{
508
 
  switch (visit) {
509
 
  case left_root_right:
510
 
    return tree_walk_left_root_right(tree,tree->root,action,argument);
511
 
  case right_root_left:
512
 
    return tree_walk_right_root_left(tree,tree->root,action,argument);
513
 
  }
514
 
 
515
 
  return 0;                     /* Keep gcc happy */
516
 
}
517
 
 
518
 
static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
519
 
{
520
 
  int error;
521
 
  if (element->left)                            /* Not null_element */
522
 
  {
523
 
    if ((error=tree_walk_left_root_right(tree,element->left,action,
524
 
                                          argument)) == 0 &&
525
 
        (error=(*action)(ELEMENT_KEY(tree,element),
526
 
                          element->count,
527
 
                          argument)) == 0)
528
 
      error=tree_walk_left_root_right(tree,element->right,action,argument);
529
 
    return error;
530
 
  }
531
 
 
532
 
  return 0;
533
 
}
534
 
 
535
 
static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
536
 
{
537
 
  int error;
538
 
  if (element->right)                           /* Not null_element */
539
 
  {
540
 
    if ((error=tree_walk_right_root_left(tree,element->right,action,
541
 
                                          argument)) == 0 &&
542
 
        (error=(*action)(ELEMENT_KEY(tree,element),
543
 
                          element->count,
544
 
                          argument)) == 0)
545
 
     error=tree_walk_right_root_left(tree,element->left,action,argument);
546
 
    return error;
547
 
  }
548
 
 
549
 
  return 0;
550
 
}
551
 
 
552
 
 
553
 
/* Functions to fix up the tree after insert and delete */
554
 
 
555
 
static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
556
 
{
557
 
  TREE_ELEMENT *y;
558
 
 
559
 
  y= leaf->right;
560
 
  leaf->right= y->left;
561
 
  parent[0]= y;
562
 
  y->left= leaf;
563
 
}
564
 
 
565
 
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
566
 
{
567
 
  TREE_ELEMENT *x;
568
 
 
569
 
  x= leaf->left;
570
 
  leaf->left= x->right;
571
 
  parent[0]= x;
572
 
  x->right= leaf;
573
 
}
574
 
 
575
 
static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
576
 
{
577
 
  TREE_ELEMENT *y,*par,*par2;
578
 
 
579
 
  leaf->colour=RED;
580
 
  while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
581
 
  {
582
 
    if (par == (par2=parent[-2][0])->left)
583
 
    {
584
 
      y= par2->right;
585
 
      if (y->colour == RED)
586
 
      {
587
 
        par->colour= BLACK;
588
 
        y->colour= BLACK;
589
 
        leaf= par2;
590
 
        parent-= 2;
591
 
        leaf->colour= RED;              /* And the loop continues */
592
 
      }
593
 
      else
594
 
      {
595
 
        if (leaf == par->right)
596
 
        {
597
 
          left_rotate(parent[-1],par);
598
 
          par= leaf;                    /* leaf is now parent to old leaf */
599
 
        }
600
 
        par->colour= BLACK;
601
 
        par2->colour= RED;
602
 
        right_rotate(parent[-2],par2);
603
 
        break;
604
 
      }
605
 
    }
606
 
    else
607
 
    {
608
 
      y= par2->left;
609
 
      if (y->colour == RED)
610
 
      {
611
 
        par->colour= BLACK;
612
 
        y->colour= BLACK;
613
 
        leaf= par2;
614
 
        parent-= 2;
615
 
        leaf->colour= RED;              /* And the loop continues */
616
 
      }
617
 
      else
618
 
      {
619
 
        if (leaf == par->left)
620
 
        {
621
 
          right_rotate(parent[-1],par);
622
 
          par= leaf;
623
 
        }
624
 
        par->colour= BLACK;
625
 
        par2->colour= RED;
626
 
        left_rotate(parent[-2],par2);
627
 
        break;
628
 
      }
629
 
    }
630
 
  }
631
 
  tree->root->colour=BLACK;
632
 
}
633
 
 
634
 
static void rb_delete_fixup(TREE *tree, TREE_ELEMENT ***parent)
635
 
{
636
 
  TREE_ELEMENT *x,*w,*par;
637
 
 
638
 
  x= **parent;
639
 
  while (x != tree->root && x->colour == BLACK)
640
 
  {
641
 
    if (x == (par=parent[-1][0])->left)
642
 
    {
643
 
      w= par->right;
644
 
      if (w->colour == RED)
645
 
      {
646
 
        w->colour= BLACK;
647
 
        par->colour= RED;
648
 
        left_rotate(parent[-1],par);
649
 
        parent[0]= &w->left;
650
 
        *++parent= &par->left;
651
 
        w= par->right;
652
 
      }
653
 
      if (w->left->colour == BLACK && w->right->colour == BLACK)
654
 
      {
655
 
        w->colour= RED;
656
 
        x= par;
657
 
        parent--;
658
 
      }
659
 
      else
660
 
      {
661
 
        if (w->right->colour == BLACK)
662
 
        {
663
 
          w->left->colour= BLACK;
664
 
          w->colour= RED;
665
 
          right_rotate(&par->right,w);
666
 
          w= par->right;
667
 
        }
668
 
        w->colour= par->colour;
669
 
        par->colour= BLACK;
670
 
        w->right->colour= BLACK;
671
 
        left_rotate(parent[-1],par);
672
 
        x= tree->root;
673
 
        break;
674
 
      }
675
 
    }
676
 
    else
677
 
    {
678
 
      w=par->left;
679
 
      if (w->colour == RED)
680
 
      {
681
 
        w->colour= BLACK;
682
 
        par->colour= RED;
683
 
        right_rotate(parent[-1],par);
684
 
        parent[0]= &w->right;
685
 
        *++parent= &par->right;
686
 
        w= par->left;
687
 
      }
688
 
      if (w->right->colour == BLACK && w->left->colour == BLACK)
689
 
      {
690
 
        w->colour= RED;
691
 
        x= par;
692
 
        parent--;
693
 
      }
694
 
      else
695
 
      {
696
 
        if (w->left->colour == BLACK)
697
 
        {
698
 
          w->right->colour= BLACK;
699
 
          w->colour= RED;
700
 
          left_rotate(&par->left,w);
701
 
          w= par->left;
702
 
        }
703
 
        w->colour= par->colour;
704
 
        par->colour= BLACK;
705
 
        w->left->colour= BLACK;
706
 
        right_rotate(parent[-1],par);
707
 
        x= tree->root;
708
 
        break;
709
 
      }
710
 
    }
711
 
  }
712
 
  x->colour= BLACK;
713
 
}
714
 
 
715
 
} /* namespace drizzled */