~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/tree.cc

  • Committer: Ivo Roper
  • Date: 2011-11-19 00:03:07 UTC
  • mfrom: (2455.1.5 drizzle-tree-refactor)
  • mto: This revision was merged to the branch mainline in revision 2479.
  • Revision ID: ivolucien@gmail.com-20111119000307-kxxoqfok9t0qv4v7
refactored TREE struct into Tree class, updating calling code appropriately

Show diffs side-by-side

added added

removed removed

Lines of Context:
15
15
 
16
16
/*
17
17
  Code for handling red-black (balanced) binary trees.
18
 
  key in tree is allocated accrding to following:
 
18
  key in tree is allocated according to following:
19
19
 
20
20
  1) If size < 0 then tree will not allocate keys and only a pointer to
21
21
     each key is saved in tree.
29
29
  3) if key_size is given to init_tree then each node will continue the
30
30
     key and calls to insert_key may increase length of key.
31
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
 
32
     align) then key will be put on a 8 aligned address. Else
 
33
     the key will be on address (element+1). This is transparent for user
34
34
     compare and search functions uses a pointer to given key-argument.
35
35
 
36
36
  - If you use a free function for tree-elements and you are freeing
48
48
/*
49
49
  NOTE:
50
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))
 
51
    (*compare)(custom_arg, element_key(element), key)
 
52
  and NOT the other way around, as
 
53
    (*compare)(custom_arg, key, element_key(element))
54
54
*/
55
55
 
56
56
#include <config.h>
58
58
#include <drizzled/tree.h>
59
59
#include <drizzled/internal/my_sys.h>
60
60
#include <drizzled/internal/m_string.h>
61
 
#include <drizzled/memory/root.h>
62
61
 
63
62
#define BLACK           1
64
63
#define RED             0
65
64
#define DEFAULT_ALLOC_SIZE 8192
66
65
#define DEFAULT_ALIGN_SIZE 8192
67
66
 
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
67
 
73
68
namespace drizzled
74
69
{
75
70
 
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
 
 
87
 
 
88
 
void init_tree(TREE *tree, size_t default_alloc_size, uint32_t memory_limit,
89
 
               uint32_t size, qsort_cmp2 compare, bool with_delete,
90
 
               tree_element_free free_element, void *custom_arg)
 
71
/**
 
72
 * Tree class public methods
 
73
 */
 
74
 
 
75
void Tree::init_tree(size_t default_alloc_size, uint32_t mem_limit,
 
76
               uint32_t size, qsort_cmp2 compare_callback, bool free_with_tree,
 
77
               tree_element_free free_callback, void *caller_arg)
91
78
{
92
79
  if (default_alloc_size < DEFAULT_ALLOC_SIZE)
93
80
    default_alloc_size= DEFAULT_ALLOC_SIZE;
94
81
  default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
95
 
  memset(&tree->null_element, 0, sizeof(tree->null_element));
96
 
  tree->root= &tree->null_element;
97
 
  tree->compare= compare;
98
 
  tree->size_of_element= size > 0 ? (uint32_t) size : 0;
99
 
  tree->memory_limit= memory_limit;
100
 
  tree->free= free_element;
101
 
  tree->allocated= 0;
102
 
  tree->elements_in_tree= 0;
103
 
  tree->custom_arg = custom_arg;
104
 
  tree->null_element.colour= BLACK;
105
 
  tree->null_element.left=tree->null_element.right= 0;
106
 
  tree->flag= 0;
107
 
  if (!free_element &&
 
82
  memset(&this->null_element, 0, sizeof(this->null_element));
 
83
  root= &this->null_element;
 
84
  compare= compare_callback;
 
85
  size_of_element= size > 0 ? (uint32_t) size : 0;
 
86
  memory_limit= mem_limit;
 
87
  free= free_callback;
 
88
  allocated= 0;
 
89
  elements_in_tree= 0;
 
90
  custom_arg = caller_arg;
 
91
  null_element.colour= BLACK;
 
92
  null_element.left=this->null_element.right= 0;
 
93
  flag= 0;
 
94
  if (!free_callback &&
108
95
      (size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
109
96
  {
110
97
    /*
111
98
      We know that the data doesn't have to be aligned (like if the key
112
99
      contains a double), so we can store the data combined with the
113
 
      TREE_ELEMENT.
 
100
      Tree_Element.
114
101
    */
115
 
    tree->offset_to_key= sizeof(TREE_ELEMENT); /* Put key after element */
 
102
    offset_to_key= sizeof(Tree_Element); /* Put key after element */
116
103
    /* Fix allocation size so that we don't lose any memory */
117
 
    default_alloc_size/= (sizeof(TREE_ELEMENT)+size);
 
104
    default_alloc_size/= (sizeof(Tree_Element)+size);
118
105
    if (!default_alloc_size)
119
106
      default_alloc_size= 1;
120
 
    default_alloc_size*= (sizeof(TREE_ELEMENT)+size);
 
107
    default_alloc_size*= (sizeof(Tree_Element)+size);
121
108
  }
122
109
  else
123
110
  {
124
 
    tree->offset_to_key= 0;             /* use key through pointer */
125
 
    tree->size_of_element+= sizeof(void*);
126
 
  }
127
 
  if (! (tree->with_delete= with_delete))
128
 
  {
129
 
    tree->mem_root.init(default_alloc_size);
130
 
    tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
131
 
  }
132
 
}
133
 
 
134
 
static void free_tree(TREE *tree, myf free_flags)
135
 
{
136
 
  if (tree->root)                               /* If initialized */
137
 
  {
138
 
    if (tree->with_delete)
139
 
      delete_tree_element(tree,tree->root);
140
 
    else
141
 
    {
142
 
      if (tree->free)
143
 
      {
144
 
        if (tree->memory_limit)
145
 
          (*tree->free)(NULL, free_init, tree->custom_arg);
146
 
        delete_tree_element(tree,tree->root);
147
 
        if (tree->memory_limit)
148
 
          (*tree->free)(NULL, free_end, tree->custom_arg);
149
 
      }
150
 
      tree->mem_root.free_root(free_flags);
151
 
    }
152
 
  }
153
 
  tree->root= &tree->null_element;
154
 
  tree->elements_in_tree= 0;
155
 
  tree->allocated= 0;
156
 
}
157
 
 
158
 
void delete_tree(TREE* tree)
159
 
{
160
 
  free_tree(tree, MYF(0)); /* free() mem_root if applicable */
161
 
}
162
 
 
163
 
void reset_tree(TREE* tree)
 
111
    offset_to_key= 0;           /* use key through pointer */
 
112
    size_of_element+= sizeof(void*);
 
113
  }
 
114
  if (! (with_delete= free_with_tree))
 
115
  {
 
116
    mem_root.init(default_alloc_size);
 
117
    mem_root.min_malloc= (sizeof(Tree_Element)+size_of_element);
 
118
  }
 
119
}
 
120
 
 
121
void Tree::delete_tree()
 
122
{
 
123
  free_tree(MYF(0)); /* free() mem_root if applicable */
 
124
}
 
125
 
 
126
void Tree::reset_tree()
164
127
{
165
128
  /* do not free mem_root, just mark blocks as free */
166
 
  free_tree(tree, MYF(memory::MARK_BLOCKS_FREE));
167
 
}
168
 
 
169
 
 
170
 
static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
171
 
{
172
 
  if (element != &tree->null_element)
173
 
  {
174
 
    delete_tree_element(tree,element->left);
175
 
    if (tree->free)
176
 
      (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
177
 
    delete_tree_element(tree,element->right);
178
 
    if (tree->with_delete)
179
 
      free((char*) element);
180
 
  }
181
 
}
182
 
 
183
 
 
184
 
/*
185
 
  insert, search and delete of elements
186
 
 
187
 
  The following should be true:
188
 
    parent[0] = & parent[-1][0]->left ||
189
 
    parent[0] = & parent[-1][0]->right
190
 
*/
191
 
 
192
 
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size,
193
 
                          void* custom_arg)
 
129
  free_tree(MYF(memory::MARK_BLOCKS_FREE));
 
130
}
 
131
 
 
132
Tree_Element* Tree::tree_insert(void* key, uint32_t key_size, void* caller_arg)
194
133
{
195
134
  int cmp;
196
 
  TREE_ELEMENT *element,***parent;
 
135
  Tree_Element *element,***parent;
197
136
 
198
 
  parent= tree->parents;
199
 
  *parent = &tree->root; element= tree->root;
 
137
  parent= this->parents;
 
138
  *parent = &this->root; element= this->root;
200
139
  for (;;)
201
140
  {
202
 
    if (element == &tree->null_element ||
203
 
        (cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
204
 
                                key)) == 0)
 
141
    if (element == &this->null_element ||
 
142
        (cmp = (*compare)(caller_arg, element_key(element), key)) == 0)
205
143
      break;
206
144
    if (cmp < 0)
207
145
    {
212
150
      *++parent = &element->left; element= element->left;
213
151
    }
214
152
  }
215
 
  if (element == &tree->null_element)
 
153
  if (element == &this->null_element)
216
154
  {
217
 
    size_t alloc_size= sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
218
 
    tree->allocated+= alloc_size;
 
155
    size_t alloc_size= sizeof(Tree_Element)+key_size+this->size_of_element;
 
156
    this->allocated+= alloc_size;
219
157
 
220
 
    if (tree->memory_limit && tree->elements_in_tree
221
 
                           && tree->allocated > tree->memory_limit)
 
158
    if (this->memory_limit && this->elements_in_tree
 
159
                           && this->allocated > this->memory_limit)
222
160
    {
223
 
      reset_tree(tree);
224
 
      return tree_insert(tree, key, key_size, custom_arg);
 
161
      reset_tree();
 
162
      return tree_insert(key, key_size, caller_arg);
225
163
    }
226
164
 
227
 
    key_size+= tree->size_of_element;
228
 
    if (tree->with_delete)
229
 
      element= (TREE_ELEMENT *) malloc(alloc_size);
 
165
    key_size+= this->size_of_element;
 
166
    if (this->with_delete)
 
167
      element= (Tree_Element *) malloc(alloc_size);
230
168
    else
231
 
      element= (TREE_ELEMENT *) tree->mem_root.alloc(alloc_size);
 
169
      element= (Tree_Element *) this->mem_root.alloc(alloc_size);
232
170
    **parent= element;
233
 
    element->left= element->right= &tree->null_element;
234
 
    if (!tree->offset_to_key)
 
171
    element->left= element->right= &this->null_element;
 
172
    if (!this->offset_to_key)
235
173
    {
236
174
      if (key_size == sizeof(void*))             /* no length, save pointer */
237
175
        *((void**) (element+1))= key;
242
180
      }
243
181
    }
244
182
    else
245
 
      memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
 
183
      memcpy((unsigned char*) element + this->offset_to_key, key, key_size);
246
184
    element->count= 1;                  /* May give warning in purify */
247
 
    tree->elements_in_tree++;
248
 
    rb_insert(tree,parent,element);     /* rebalance tree */
 
185
    this->elements_in_tree++;
 
186
    rb_insert(parent,element);  /* rebalance tree */
249
187
  }
250
188
  else
251
189
  {
252
 
    if (tree->flag & TREE_NO_DUPS)
 
190
    if (this->flag & TREE_NO_DUPS)
253
191
      return(NULL);
254
192
    element->count++;
255
193
    /* Avoid a wrap over of the count. */
260
198
  return element;
261
199
}
262
200
 
263
 
void *tree_search_key(TREE *tree, const void *key,
264
 
                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
265
 
                      enum ha_rkey_function flag, void *custom_arg)
266
 
{
267
 
  TREE_ELEMENT *element= tree->root;
268
 
  TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
269
 
  TREE_ELEMENT **last_equal_element= NULL;
270
 
 
271
 
/*
272
 
  TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
273
 
*/
274
 
 
275
 
  *parents = &tree->null_element;
276
 
  while (element != &tree->null_element)
277
 
  {
278
 
    int cmp;
279
 
 
280
 
    *++parents= element;
281
 
 
282
 
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
283
 
                               key)) == 0)
284
 
    {
285
 
      switch (flag) {
286
 
      case HA_READ_KEY_EXACT:
287
 
      case HA_READ_KEY_OR_NEXT:
288
 
      case HA_READ_BEFORE_KEY:
289
 
        last_equal_element= parents;
290
 
        cmp= 1;
291
 
        break;
292
 
      case HA_READ_AFTER_KEY:
293
 
        cmp= -1;
294
 
        break;
295
 
      case HA_READ_PREFIX_LAST:
296
 
      case HA_READ_PREFIX_LAST_OR_PREV:
297
 
        last_equal_element= parents;
298
 
        cmp= -1;
299
 
        break;
300
 
      default:
301
 
        return NULL;
302
 
      }
303
 
    }
304
 
    if (cmp < 0) /* element < key */
305
 
    {
306
 
      last_right_step_parent= parents;
307
 
      element= element->right;
308
 
    }
309
 
    else
310
 
    {
311
 
      last_left_step_parent= parents;
312
 
      element= element->left;
313
 
    }
314
 
  }
315
 
  switch (flag) {
316
 
  case HA_READ_KEY_EXACT:
317
 
  case HA_READ_PREFIX_LAST:
318
 
    *last_pos= last_equal_element;
319
 
    break;
320
 
  case HA_READ_KEY_OR_NEXT:
321
 
    *last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
322
 
    break;
323
 
  case HA_READ_AFTER_KEY:
324
 
    *last_pos= last_left_step_parent;
325
 
    break;
326
 
  case HA_READ_PREFIX_LAST_OR_PREV:
327
 
    *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
328
 
    break;
329
 
  case HA_READ_BEFORE_KEY:
330
 
    *last_pos= last_right_step_parent;
331
 
    break;
332
 
  default:
333
 
    return NULL;
334
 
  }
335
 
 
336
 
  return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
337
 
}
338
 
 
339
 
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
340
 
                       int r_offs)
341
 
{
342
 
  TREE_ELEMENT *x= **last_pos;
343
 
 
344
 
  if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
345
 
  {
346
 
    x= ELEMENT_CHILD(x, r_offs);
347
 
    *++*last_pos= x;
348
 
    while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
349
 
    {
350
 
      x= ELEMENT_CHILD(x, l_offs);
351
 
      *++*last_pos= x;
352
 
    }
353
 
    return ELEMENT_KEY(tree, x);
354
 
  }
355
 
  else
356
 
  {
357
 
    TREE_ELEMENT *y= *--*last_pos;
358
 
    while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
359
 
    {
360
 
      x= y;
361
 
      y= *--*last_pos;
362
 
    }
363
 
    return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
364
 
  }
365
 
}
366
 
 
367
 
/*
368
 
  Expected that tree is fully balanced
369
 
  (each path from root to leaf has the same length)
370
 
*/
371
 
ha_rows tree_record_pos(TREE *tree, const void *key,
372
 
                        enum ha_rkey_function flag, void *custom_arg)
373
 
{
374
 
  TREE_ELEMENT *element= tree->root;
375
 
  double left= 1;
376
 
  double right= tree->elements_in_tree;
377
 
 
378
 
  while (element != &tree->null_element)
379
 
  {
380
 
    int cmp;
381
 
 
382
 
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
383
 
                               key)) == 0)
384
 
    {
385
 
      switch (flag) {
386
 
      case HA_READ_KEY_EXACT:
387
 
      case HA_READ_BEFORE_KEY:
388
 
        cmp= 1;
389
 
        break;
390
 
      case HA_READ_AFTER_KEY:
391
 
        cmp= -1;
392
 
        break;
393
 
      default:
394
 
        return HA_POS_ERROR;
395
 
      }
396
 
    }
397
 
    if (cmp < 0) /* element < key */
398
 
    {
399
 
      element= element->right;
400
 
      left= (left + right) / 2;
401
 
    }
402
 
    else
403
 
    {
404
 
      element= element->left;
405
 
      right= (left + right) / 2;
406
 
    }
407
 
  }
408
 
 
409
 
  switch (flag) {
410
 
  case HA_READ_KEY_EXACT:
411
 
  case HA_READ_BEFORE_KEY:
412
 
    return (ha_rows) right;
413
 
  case HA_READ_AFTER_KEY:
414
 
    return (ha_rows) left;
415
 
  default:
416
 
    return HA_POS_ERROR;
417
 
  }
418
 
}
419
 
 
420
 
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
421
 
{
422
 
  switch (visit) {
423
 
  case left_root_right:
424
 
    return tree_walk_left_root_right(tree,tree->root,action,argument);
425
 
  case right_root_left:
426
 
    return tree_walk_right_root_left(tree,tree->root,action,argument);
 
201
int Tree::tree_walk(tree_walk_action action, void *argument, TREE_WALK visit)
 
202
{
 
203
          switch (visit) {
 
204
          case left_root_right:
 
205
            return tree_walk_left_root_right(root,action,argument);
 
206
          case right_root_left:
 
207
            return tree_walk_right_root_left(root,action,argument);
427
208
  }
428
209
 
429
210
  return 0;                     /* Keep gcc happy */
430
211
}
431
212
 
432
 
static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
 
213
/**
 
214
 * Tree class private methods
 
215
 */
 
216
 
 
217
void Tree::free_tree(myf free_flags)
 
218
{
 
219
  if (root)                             /* If initialized */
 
220
  {
 
221
    if (with_delete)
 
222
      delete_tree_element(root);
 
223
    else
 
224
    {
 
225
      if (free)
 
226
      {
 
227
        if (memory_limit)
 
228
          (*free)(NULL, free_init, custom_arg);
 
229
        delete_tree_element(root);
 
230
        if (memory_limit)
 
231
          (*free)(NULL, free_end, custom_arg);
 
232
      }
 
233
      mem_root.free_root(free_flags);
 
234
    }
 
235
  }
 
236
  root= &null_element;
 
237
  elements_in_tree= 0;
 
238
  allocated= 0;
 
239
}
 
240
 
 
241
void* Tree::element_key(Tree_Element* element)
 
242
{
 
243
        return offset_to_key ? (void*)((unsigned char*) element + offset_to_key)
 
244
                                                 : *((void**)(element + 1));
 
245
}
 
246
 
 
247
void Tree::delete_tree_element(Tree_Element *element)
 
248
{
 
249
  if (element != &null_element)
 
250
  {
 
251
    delete_tree_element(element->left);
 
252
    if (free)
 
253
      (*free)(element_key(element), free_free, custom_arg);
 
254
    delete_tree_element(element->right);
 
255
    if (with_delete)
 
256
      delete element;
 
257
  }
 
258
}
 
259
 
 
260
int Tree::tree_walk_left_root_right(Tree_Element *element, tree_walk_action action, void *argument)
433
261
{
434
262
  int error;
435
263
  if (element->left)                            /* Not null_element */
436
264
  {
437
 
    if ((error=tree_walk_left_root_right(tree,element->left,action,
 
265
    if ((error=tree_walk_left_root_right(element->left,action,
438
266
                                          argument)) == 0 &&
439
 
        (error=(*action)(ELEMENT_KEY(tree,element),
440
 
                          element->count,
441
 
                          argument)) == 0)
442
 
      error=tree_walk_left_root_right(tree,element->right,action,argument);
 
267
        (error=(*action)(element_key(element), element->count, argument)) == 0)
 
268
      error=tree_walk_left_root_right(element->right,action,argument);
443
269
    return error;
444
270
  }
445
271
 
446
272
  return 0;
447
273
}
448
274
 
449
 
static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
 
275
int Tree::tree_walk_right_root_left(Tree_Element *element, tree_walk_action action, void *argument)
450
276
{
451
277
  int error;
452
278
  if (element->right)                           /* Not null_element */
453
279
  {
454
 
    if ((error=tree_walk_right_root_left(tree,element->right,action,
 
280
    if ((error=tree_walk_right_root_left(element->right,action,
455
281
                                          argument)) == 0 &&
456
 
        (error=(*action)(ELEMENT_KEY(tree,element),
 
282
        (error=(*action)(element_key(element),
457
283
                          element->count,
458
284
                          argument)) == 0)
459
 
     error=tree_walk_right_root_left(tree,element->left,action,argument);
 
285
     error=tree_walk_right_root_left(element->left,action,argument);
460
286
    return error;
461
287
  }
462
288
 
463
289
  return 0;
464
290
}
465
291
 
466
 
 
467
 
/* Functions to fix up the tree after insert and delete */
468
 
 
469
 
static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
 
292
void Tree::left_rotate(Tree_Element **parent, Tree_Element *element)
470
293
{
471
 
  TREE_ELEMENT *y;
 
294
  Tree_Element *y;
472
295
 
473
 
  y= leaf->right;
474
 
  leaf->right= y->left;
 
296
  y= element->right;
 
297
  element->right= y->left;
475
298
  parent[0]= y;
476
 
  y->left= leaf;
 
299
  y->left= element;
477
300
}
478
301
 
479
 
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
 
302
void Tree::right_rotate(Tree_Element **parent, Tree_Element *element)
480
303
{
481
 
  TREE_ELEMENT *x;
 
304
        Tree_Element *x;
482
305
 
483
 
  x= leaf->left;
484
 
  leaf->left= x->right;
 
306
  x= element->left;
 
307
  element->left= x->right;
485
308
  parent[0]= x;
486
 
  x->right= leaf;
 
309
  x->right= element;
487
310
}
488
311
 
489
 
static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
 
312
void Tree::rb_insert(Tree_Element ***parent, Tree_Element *element)
490
313
{
491
 
  TREE_ELEMENT *y,*par,*par2;
 
314
        Tree_Element *y,*par,*par2;
492
315
 
493
 
  leaf->colour=RED;
494
 
  while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
 
316
  element->colour=RED;
 
317
  while (element != root && (par=parent[-1][0])->colour == RED)
495
318
  {
496
319
    if (par == (par2=parent[-2][0])->left)
497
320
    {
500
323
      {
501
324
        par->colour= BLACK;
502
325
        y->colour= BLACK;
503
 
        leaf= par2;
 
326
        element= par2;
504
327
        parent-= 2;
505
 
        leaf->colour= RED;              /* And the loop continues */
 
328
        element->colour= RED;           /* And the loop continues */
506
329
      }
507
330
      else
508
331
      {
509
 
        if (leaf == par->right)
 
332
        if (element == par->right)
510
333
        {
511
334
          left_rotate(parent[-1],par);
512
 
          par= leaf;                    /* leaf is now parent to old leaf */
 
335
          par= element;                 /* element is now parent to old element */
513
336
        }
514
337
        par->colour= BLACK;
515
338
        par2->colour= RED;
524
347
      {
525
348
        par->colour= BLACK;
526
349
        y->colour= BLACK;
527
 
        leaf= par2;
 
350
        element= par2;
528
351
        parent-= 2;
529
 
        leaf->colour= RED;              /* And the loop continues */
 
352
        element->colour= RED;           /* And the loop continues */
530
353
      }
531
354
      else
532
355
      {
533
 
        if (leaf == par->left)
 
356
        if (element == par->left)
534
357
        {
535
358
          right_rotate(parent[-1],par);
536
 
          par= leaf;
 
359
          par= element;
537
360
        }
538
361
        par->colour= BLACK;
539
362
        par2->colour= RED;
542
365
      }
543
366
    }
544
367
  }
545
 
  tree->root->colour=BLACK;
 
368
  root->colour=BLACK;
546
369
}
547
370
 
548
371
} /* namespace drizzled */