← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/tree.c

  • Committer: Monty Taylor
  • Date: 2008-08-02 01:03:15 UTC
  • mto: (236.1.42 codestyle)
  • mto: This revision was merged to the branch mainline in revision 261.
  • Revision ID: monty@inaugust.com-20080802010315-65h5938pymg9d99z
Moved m4 macros to top-level m4 dir, per GNU standards (and where gettext wanted it :)

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/tree.c
74
74
static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
75
75
 
76
76
 
77
 
void init_tree(TREE *tree, uint32_t default_alloc_size, uint32_t memory_limit,
 
77
void init_tree(TREE *tree, ulong default_alloc_size, ulong memory_limit,
78
78
               int size, qsort_cmp2 compare, bool with_delete,
79
79
               tree_element_free free_element, void *custom_arg)
80
80
{
81
81
  if (default_alloc_size < DEFAULT_ALLOC_SIZE)
82
82
    default_alloc_size= DEFAULT_ALLOC_SIZE;
83
83
  default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
84
 
  memset(&tree->null_element, 0, sizeof(tree->null_element));
 
84
  memset((uchar*) &tree->null_element, 0, sizeof(tree->null_element));
85
85
  tree->root= &tree->null_element;
86
86
  tree->compare=compare;
87
87
  tree->size_of_element=size > 0 ? (uint) size : 0;
149
149
 
150
150
void delete_tree(TREE* tree)
151
151
{
152
 
  free_tree(tree, MYF(0)); /* free() mem_root if applicable */
 
152
  free_tree(tree, MYF(0)); /* my_free() mem_root if applicable */
153
153
}
154
154
 
155
155
void reset_tree(TREE* tree)
168
168
      (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
169
169
    delete_tree_element(tree,element->right);
170
170
    if (tree->with_delete)
171
 
      free((char*) element);
 
171
      my_free((char*) element,MYF(0));
172
172
  }
173
173
}
174
174
 
181
181
    parent[0] = & parent[-1][0]->right
182
182
*/
183
183
 
184
 
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint32_t key_size,
 
184
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size, 
185
185
                          void* custom_arg)
186
186
{
187
187
  int cmp;
206
206
  }
207
207
  if (element == &tree->null_element)
208
208
  {
209
 
    uint32_t alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
 
209
    uint alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
210
210
    tree->allocated+=alloc_size;
211
211
 
212
212
    if (tree->memory_limit && tree->elements_in_tree
218
218
 
219
219
    key_size+=tree->size_of_element;
220
220
    if (tree->with_delete)
221
 
      element=(TREE_ELEMENT *) malloc(alloc_size);
 
221
      element=(TREE_ELEMENT *) my_malloc(alloc_size, MYF(MY_WME));
222
222
    else
223
223
      element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
224
224
    if (!element)
232
232
      else
233
233
      {
234
234
        *((void**) (element+1))= (void*) ((void **) (element+1)+1);
235
 
        memcpy(*((void **) (element+1)),key, key_size - sizeof(void*));
 
235
        memcpy((uchar*) *((void **) (element+1)),key,
 
236
               (size_t) (key_size-sizeof(void*)));
236
237
      }
237
238
    }
238
239
    else
239
 
      memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
 
240
      memcpy((uchar*) element+tree->offset_to_key,key,(size_t) key_size);
240
241
    element->count=1;                   /* May give warning in purify */
241
242
    tree->elements_in_tree++;
242
243
    rb_insert(tree,parent,element);     /* rebalance tree */
253
254
  return element;
254
255
}
255
256
 
256
 
int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
 
257
int tree_delete(TREE *tree, void *key, uint key_size, void *custom_arg)
257
258
{
258
259
  int cmp,remove_colour;
259
260
  TREE_ELEMENT *element,***parent, ***org_parent, *nod;
309
310
  if (tree->free)
310
311
    (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
311
312
  tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
312
 
  free((unsigned char*) element);
 
313
  my_free((uchar*) element,MYF(0));
313
314
  tree->elements_in_tree--;
314
315
  return 0;
315
316
}
334
335
  }
335
336
}
336
337
 
337
 
void *tree_search_key(TREE *tree, const void *key,
 
338
void *tree_search_key(TREE *tree, const void *key, 
338
339
                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
339
340
                      enum ha_rkey_function flag, void *custom_arg)
340
341
{
343
344
  TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
344
345
  TREE_ELEMENT **last_equal_element= NULL;
345
346
 
346
 
/*
 
347
/* 
347
348
  TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
348
349
*/
349
350
 
351
352
  while (element != &tree->null_element)
352
353
  {
353
354
    *++parents= element;
354
 
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
 
355
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
355
356
                               key)) == 0)
356
357
    {
357
358
      switch (flag) {
407
408
  return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
408
409
}
409
410
 
410
 
/*
411
 
  Search first (the most left) or last (the most right) tree element
 
411
/* 
 
412
  Search first (the most left) or last (the most right) tree element 
412
413
*/
413
 
void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
 
414
void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
414
415
                       TREE_ELEMENT ***last_pos, int child_offs)
415
416
{
416
417
  TREE_ELEMENT *element= tree->root;
417
 
 
 
418
  
418
419
  *parents= &tree->null_element;
419
420
  while (element != &tree->null_element)
420
421
  {
422
423
    element= ELEMENT_CHILD(element, child_offs);
423
424
  }
424
425
  *last_pos= parents;
425
 
  return **last_pos != &tree->null_element ?
 
426
  return **last_pos != &tree->null_element ? 
426
427
    ELEMENT_KEY(tree, **last_pos) : NULL;
427
428
}
428
429
 
429
 
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
 
430
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
430
431
                       int r_offs)
431
432
{
432
433
  TREE_ELEMENT *x= **last_pos;
433
 
 
 
434
  
434
435
  if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
435
436
  {
436
437
    x= ELEMENT_CHILD(x, r_offs);
458
459
  Expected that tree is fully balanced
459
460
  (each path from root to leaf has the same length)
460
461
*/
461
 
ha_rows tree_record_pos(TREE *tree, const void *key,
 
462
ha_rows tree_record_pos(TREE *tree, const void *key, 
462
463
                        enum ha_rkey_function flag, void *custom_arg)
463
464
{
464
465
  int cmp;
468
469
 
469
470
  while (element != &tree->null_element)
470
471
  {
471
 
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
 
472
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
472
473
                               key)) == 0)
473
474
    {
474
475
      switch (flag) {