← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/tree.cc

  • Committer: Mark Atwood
  • Date: 2011-12-28 02:50:31 UTC
  • Revision ID: me@mark.atwood.name-20111228025031-eh4h1zwv4ig88g0i
fix tests/r/basic.result

Show diffs side-by-side

added added

removed removed

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