← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/tree.cc

  • Committer: Mark Atwood
  • Date: 2011-08-09 01:21:52 UTC
  • mfrom: (2380.1.2 drizzle-autoconf)
  • Revision ID: me@mark.atwood.name-20110809012152-zxq2dgan8e6nsvse
merge lp:~brianaker/drizzle/autoreconf

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/tree.cc
53
53
    (*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
54
54
*/
55
55
 
56
 
#include "config.h"
 
56
#include <config.h>
57
57
 
58
 
#include "drizzled/tree.h"
59
 
#include "drizzled/internal/my_sys.h"
60
 
#include "drizzled/internal/m_string.h"
61
 
#include "drizzled/memory/root.h"
 
58
#include <drizzled/tree.h>
 
59
#include <drizzled/internal/my_sys.h>
 
60
#include <drizzled/internal/m_string.h>
 
61
#include <drizzled/memory/root.h>
62
62
 
63
63
#define BLACK           1
64
64
#define RED             0
83
83
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
84
84
static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
85
85
                      TREE_ELEMENT *leaf);
86
 
static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
87
86
 
88
87
 
89
88
void init_tree(TREE *tree, size_t default_alloc_size, uint32_t memory_limit,
127
126
  }
128
127
  if (! (tree->with_delete= with_delete))
129
128
  {
130
 
    tree->mem_root.init_alloc_root(default_alloc_size);
 
129
    tree->mem_root.init(default_alloc_size);
131
130
    tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
132
131
  }
133
132
}
229
228
    if (tree->with_delete)
230
229
      element= (TREE_ELEMENT *) malloc(alloc_size);
231
230
    else
232
 
      element= (TREE_ELEMENT *) tree->mem_root.alloc_root(alloc_size);
233
 
    if (!element)
234
 
      return(NULL);
 
231
      element= (TREE_ELEMENT *) tree->mem_root.alloc(alloc_size);
235
232
    **parent= element;
236
233
    element->left= element->right= &tree->null_element;
237
234
    if (!tree->offset_to_key)
263
260
  return element;
264
261
}
265
262
 
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
263
void *tree_search_key(TREE *tree, const void *key,
331
264
                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
332
265
                      enum ha_rkey_function flag, void *custom_arg)
403
336
  return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
404
337
}
405
338
 
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
339
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
426
340
                       int r_offs)
427
341
{
631
545
  tree->root->colour=BLACK;
632
546
}
633
547
 
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
548
} /* namespace drizzled */