← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/tree.c

Removed dead variable, sorted authors file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/tree.c
54
54
*/
55
55
 
56
56
#include "mysys_priv.h"
57
 
#include <mystrings/m_string.h>
58
 
#include <mysys/my_tree.h>
 
57
#include <m_string.h>
 
58
#include <my_tree.h>
 
59
#include "my_base.h"
59
60
 
60
61
#define BLACK           1
61
62
#define RED             0
74
75
static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
75
76
 
76
77
 
77
 
void init_tree(TREE *tree, uint32_t default_alloc_size, uint32_t memory_limit,
 
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
void init_tree(TREE *tree, ulong default_alloc_size, ulong memory_limit,
78
85
               int size, qsort_cmp2 compare, bool with_delete,
79
86
               tree_element_free free_element, void *custom_arg)
80
87
{
 
88
  DBUG_ENTER("init_tree");
 
89
  DBUG_PRINT("enter",("tree: 0x%lx  size: %d", (long) tree, size));
 
90
 
81
91
  if (default_alloc_size < DEFAULT_ALLOC_SIZE)
82
92
    default_alloc_size= DEFAULT_ALLOC_SIZE;
83
93
  default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
84
 
  memset(&tree->null_element, 0, sizeof(tree->null_element));
 
94
  bzero((uchar*) &tree->null_element,sizeof(tree->null_element));
85
95
  tree->root= &tree->null_element;
86
96
  tree->compare=compare;
87
97
  tree->size_of_element=size > 0 ? (uint) size : 0;
118
128
    init_alloc_root(&tree->mem_root, (uint) default_alloc_size, 0);
119
129
    tree->mem_root.min_malloc=(sizeof(TREE_ELEMENT)+tree->size_of_element);
120
130
  }
121
 
  return;
 
131
  DBUG_VOID_RETURN;
122
132
}
123
133
 
124
134
static void free_tree(TREE *tree, myf free_flags)
125
135
{
 
136
  DBUG_ENTER("free_tree");
 
137
  DBUG_PRINT("enter",("tree: 0x%lx", (long) tree));
 
138
 
126
139
  if (tree->root)                               /* If initialized */
127
140
  {
128
141
    if (tree->with_delete)
144
157
  tree->elements_in_tree=0;
145
158
  tree->allocated=0;
146
159
 
147
 
  return;
 
160
  DBUG_VOID_RETURN;
148
161
}
149
162
 
150
163
void delete_tree(TREE* tree)
151
164
{
152
 
  free_tree(tree, MYF(0)); /* free() mem_root if applicable */
 
165
  free_tree(tree, MYF(0)); /* my_free() mem_root if applicable */
153
166
}
154
167
 
155
168
void reset_tree(TREE* tree)
168
181
      (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
169
182
    delete_tree_element(tree,element->right);
170
183
    if (tree->with_delete)
171
 
      free((char*) element);
 
184
      my_free((char*) element,MYF(0));
172
185
  }
173
186
}
174
187
 
181
194
    parent[0] = & parent[-1][0]->right
182
195
*/
183
196
 
184
 
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size,
 
197
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size, 
185
198
                          void* custom_arg)
186
199
{
187
200
  int cmp;
206
219
  }
207
220
  if (element == &tree->null_element)
208
221
  {
209
 
    uint32_t alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
 
222
    uint alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
210
223
    tree->allocated+=alloc_size;
211
224
 
212
225
    if (tree->memory_limit && tree->elements_in_tree
218
231
 
219
232
    key_size+=tree->size_of_element;
220
233
    if (tree->with_delete)
221
 
      element=(TREE_ELEMENT *) malloc(alloc_size);
 
234
      element=(TREE_ELEMENT *) my_malloc(alloc_size, MYF(MY_WME));
222
235
    else
223
236
      element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
224
237
    if (!element)
232
245
      else
233
246
      {
234
247
        *((void**) (element+1))= (void*) ((void **) (element+1)+1);
235
 
        memcpy(*((void **) (element+1)),key, key_size - sizeof(void*));
 
248
        memcpy((uchar*) *((void **) (element+1)),key,
 
249
               (size_t) (key_size-sizeof(void*)));
236
250
      }
237
251
    }
238
252
    else
239
 
      memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
 
253
      memcpy((uchar*) element+tree->offset_to_key,key,(size_t) key_size);
240
254
    element->count=1;                   /* May give warning in purify */
241
255
    tree->elements_in_tree++;
242
256
    rb_insert(tree,parent,element);     /* rebalance tree */
250
264
    if (! element->count)
251
265
      element->count--;
252
266
  }
 
267
  DBUG_EXECUTE("check_tree", test_rb_tree(tree->root););
253
268
  return element;
254
269
}
255
270
 
256
 
int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
 
271
int tree_delete(TREE *tree, void *key, uint key_size, void *custom_arg)
257
272
{
258
273
  int cmp,remove_colour;
259
274
  TREE_ELEMENT *element,***parent, ***org_parent, *nod;
309
324
  if (tree->free)
310
325
    (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
311
326
  tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
312
 
  free((unsigned char*) element);
 
327
  my_free((uchar*) element,MYF(0));
313
328
  tree->elements_in_tree--;
314
329
  return 0;
315
330
}
334
349
  }
335
350
}
336
351
 
337
 
void *tree_search_key(TREE *tree, const void *key,
 
352
void *tree_search_key(TREE *tree, const void *key, 
338
353
                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
339
354
                      enum ha_rkey_function flag, void *custom_arg)
340
355
{
343
358
  TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
344
359
  TREE_ELEMENT **last_equal_element= NULL;
345
360
 
346
 
/*
 
361
/* 
347
362
  TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
348
363
*/
349
364
 
351
366
  while (element != &tree->null_element)
352
367
  {
353
368
    *++parents= element;
354
 
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
 
369
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
355
370
                               key)) == 0)
356
371
    {
357
372
      switch (flag) {
407
422
  return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
408
423
}
409
424
 
410
 
/*
411
 
  Search first (the most left) or last (the most right) tree element
 
425
/* 
 
426
  Search first (the most left) or last (the most right) tree element 
412
427
*/
413
 
void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
 
428
void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
414
429
                       TREE_ELEMENT ***last_pos, int child_offs)
415
430
{
416
431
  TREE_ELEMENT *element= tree->root;
417
 
 
 
432
  
418
433
  *parents= &tree->null_element;
419
434
  while (element != &tree->null_element)
420
435
  {
422
437
    element= ELEMENT_CHILD(element, child_offs);
423
438
  }
424
439
  *last_pos= parents;
425
 
  return **last_pos != &tree->null_element ?
 
440
  return **last_pos != &tree->null_element ? 
426
441
    ELEMENT_KEY(tree, **last_pos) : NULL;
427
442
}
428
443
 
429
 
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
 
444
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
430
445
                       int r_offs)
431
446
{
432
447
  TREE_ELEMENT *x= **last_pos;
433
 
 
 
448
  
434
449
  if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
435
450
  {
436
451
    x= ELEMENT_CHILD(x, r_offs);
458
473
  Expected that tree is fully balanced
459
474
  (each path from root to leaf has the same length)
460
475
*/
461
 
ha_rows tree_record_pos(TREE *tree, const void *key,
 
476
ha_rows tree_record_pos(TREE *tree, const void *key, 
462
477
                        enum ha_rkey_function flag, void *custom_arg)
463
478
{
464
479
  int cmp;
468
483
 
469
484
  while (element != &tree->null_element)
470
485
  {
471
 
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
 
486
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
472
487
                               key)) == 0)
473
488
    {
474
489
      switch (flag) {
710
725
  }
711
726
  x->colour=BLACK;
712
727
}
 
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