← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/tree.c

  • Committer: Brian Aker
  • Date: 2008-07-18 20:10:26 UTC
  • mfrom: (51.3.29 remove-dbug)
  • Revision ID: brian@tangent.org-20080718201026-tto5golt0xhwqe4a
Merging in Jay's final patch on dbug.

Show diffs side-by-side

added added

removed removed

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