← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/tree.c

Removed/replaced DBUG symbols and TRUE/FALSE

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/tree.c
51
51
    (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element), key)
52
52
  and not other way around, as
53
53
    (*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
 
54
 
 
55
  ft_boolean_search.c (at least) relies on that.
54
56
*/
55
57
 
56
58
#include "mysys_priv.h"
75
77
static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
76
78
 
77
79
 
 
80
        /* The actuall code for handling binary trees */
 
81
 
 
82
#ifndef DBUG_OFF
 
83
static int test_rb_tree(TREE_ELEMENT *element);
 
84
#endif
 
85
 
78
86
void init_tree(TREE *tree, ulong default_alloc_size, ulong memory_limit,
79
 
               int size, qsort_cmp2 compare, bool with_delete,
 
87
               int size, qsort_cmp2 compare, my_bool with_delete,
80
88
               tree_element_free free_element, void *custom_arg)
81
89
{
 
90
  DBUG_ENTER("init_tree");
 
91
  DBUG_PRINT("enter",("tree: 0x%lx  size: %d", (long) tree, size));
 
92
 
82
93
  if (default_alloc_size < DEFAULT_ALLOC_SIZE)
83
94
    default_alloc_size= DEFAULT_ALLOC_SIZE;
84
95
  default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
119
130
    init_alloc_root(&tree->mem_root, (uint) default_alloc_size, 0);
120
131
    tree->mem_root.min_malloc=(sizeof(TREE_ELEMENT)+tree->size_of_element);
121
132
  }
122
 
  return;
 
133
  DBUG_VOID_RETURN;
123
134
}
124
135
 
125
136
static void free_tree(TREE *tree, myf free_flags)
126
137
{
 
138
  DBUG_ENTER("free_tree");
 
139
  DBUG_PRINT("enter",("tree: 0x%lx", (long) tree));
 
140
 
127
141
  if (tree->root)                               /* If initialized */
128
142
  {
129
143
    if (tree->with_delete)
145
159
  tree->elements_in_tree=0;
146
160
  tree->allocated=0;
147
161
 
148
 
  return;
 
162
  DBUG_VOID_RETURN;
149
163
}
150
164
 
151
165
void delete_tree(TREE* tree)
252
266
    if (! element->count)
253
267
      element->count--;
254
268
  }
 
269
  DBUG_EXECUTE("check_tree", test_rb_tree(tree->root););
255
270
  return element;
256
271
}
257
272
 
712
727
  }
713
728
  x->colour=BLACK;
714
729
}
 
730
 
 
731
#ifndef DBUG_OFF
 
732
 
 
733
        /* Test that the proporties for a red-black tree holds */
 
734
 
 
735
static int test_rb_tree(TREE_ELEMENT *element)
 
736
{
 
737
  int count_l,count_r;
 
738
 
 
739
  if (!element->left)
 
740
    return 0;                           /* Found end of tree */
 
741
  if (element->colour == RED &&
 
742
      (element->left->colour == RED || element->right->colour == RED))
 
743
  {
 
744
    printf("Wrong tree: Found two red in a row\n");
 
745
    return -1;
 
746
  }
 
747
  count_l=test_rb_tree(element->left);
 
748
  count_r=test_rb_tree(element->right);
 
749
  if (count_l >= 0 && count_r >= 0)
 
750
  {
 
751
    if (count_l == count_r)
 
752
      return count_l+(element->colour == BLACK);
 
753
    printf("Wrong tree: Incorrect black-count: %d - %d\n",count_l,count_r);
 
754
  }
 
755
  return -1;
 
756
}
 
757
#endif