← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/tree.c

merge mainline

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"
57
 
#include <mystrings/m_string.h>
58
 
#include <mysys/my_tree.h>
 
59
#include <m_string.h>
 
60
#include <my_tree.h>
 
61
#include "my_base.h"
59
62
 
60
63
#define BLACK           1
61
64
#define RED             0
74
77
static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
75
78
 
76
79
 
77
 
void init_tree(TREE *tree, uint32_t default_alloc_size, uint32_t memory_limit,
78
 
               int size, qsort_cmp2 compare, bool with_delete,
 
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
 
 
86
void init_tree(TREE *tree, ulong default_alloc_size, ulong memory_limit,
 
87
               int size, qsort_cmp2 compare, my_bool with_delete,
79
88
               tree_element_free free_element, void *custom_arg)
80
89
{
 
90
  DBUG_ENTER("init_tree");
 
91
  DBUG_PRINT("enter",("tree: 0x%lx  size: %d", (long) tree, size));
 
92
 
81
93
  if (default_alloc_size < DEFAULT_ALLOC_SIZE)
82
94
    default_alloc_size= DEFAULT_ALLOC_SIZE;
83
95
  default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
84
 
  memset(&tree->null_element, 0, sizeof(tree->null_element));
 
96
  bzero((uchar*) &tree->null_element,sizeof(tree->null_element));
85
97
  tree->root= &tree->null_element;
86
98
  tree->compare=compare;
87
99
  tree->size_of_element=size > 0 ? (uint) size : 0;
118
130
    init_alloc_root(&tree->mem_root, (uint) default_alloc_size, 0);
119
131
    tree->mem_root.min_malloc=(sizeof(TREE_ELEMENT)+tree->size_of_element);
120
132
  }
121
 
  return;
 
133
  DBUG_VOID_RETURN;
122
134
}
123
135
 
124
136
static void free_tree(TREE *tree, myf free_flags)
125
137
{
 
138
  DBUG_ENTER("free_tree");
 
139
  DBUG_PRINT("enter",("tree: 0x%lx", (long) tree));
 
140
 
126
141
  if (tree->root)                               /* If initialized */
127
142
  {
128
143
    if (tree->with_delete)
144
159
  tree->elements_in_tree=0;
145
160
  tree->allocated=0;
146
161
 
147
 
  return;
 
162
  DBUG_VOID_RETURN;
148
163
}
149
164
 
150
165
void delete_tree(TREE* tree)
151
166
{
152
 
  free_tree(tree, MYF(0)); /* free() mem_root if applicable */
 
167
  free_tree(tree, MYF(0)); /* my_free() mem_root if applicable */
153
168
}
154
169
 
155
170
void reset_tree(TREE* tree)
168
183
      (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
169
184
    delete_tree_element(tree,element->right);
170
185
    if (tree->with_delete)
171
 
      free((char*) element);
 
186
      my_free((char*) element,MYF(0));
172
187
  }
173
188
}
174
189
 
181
196
    parent[0] = & parent[-1][0]->right
182
197
*/
183
198
 
184
 
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size, 
 
199
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size, 
185
200
                          void* custom_arg)
186
201
{
187
202
  int cmp;
206
221
  }
207
222
  if (element == &tree->null_element)
208
223
  {
209
 
    uint32_t alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
 
224
    uint alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
210
225
    tree->allocated+=alloc_size;
211
226
 
212
227
    if (tree->memory_limit && tree->elements_in_tree
232
247
      else
233
248
      {
234
249
        *((void**) (element+1))= (void*) ((void **) (element+1)+1);
235
 
        memcpy(*((void **) (element+1)),key, key_size - sizeof(void*));
 
250
        memcpy((uchar*) *((void **) (element+1)),key,
 
251
               (size_t) (key_size-sizeof(void*)));
236
252
      }
237
253
    }
238
254
    else
239
 
      memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
 
255
      memcpy((uchar*) element+tree->offset_to_key,key,(size_t) key_size);
240
256
    element->count=1;                   /* May give warning in purify */
241
257
    tree->elements_in_tree++;
242
258
    rb_insert(tree,parent,element);     /* rebalance tree */
250
266
    if (! element->count)
251
267
      element->count--;
252
268
  }
 
269
  DBUG_EXECUTE("check_tree", test_rb_tree(tree->root););
253
270
  return element;
254
271
}
255
272
 
256
 
int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
 
273
int tree_delete(TREE *tree, void *key, uint key_size, void *custom_arg)
257
274
{
258
275
  int cmp,remove_colour;
259
276
  TREE_ELEMENT *element,***parent, ***org_parent, *nod;
309
326
  if (tree->free)
310
327
    (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
311
328
  tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
312
 
  free((unsigned char*) element);
 
329
  my_free((uchar*) element,MYF(0));
313
330
  tree->elements_in_tree--;
314
331
  return 0;
315
332
}
710
727
  }
711
728
  x->colour=BLACK;
712
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