← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_tree.cc

Small fixes

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/my_tree.cc
53
53
    (*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
54
54
*/
55
55
 
56
 
#include "mysys_priv.h"
 
56
#include "mysys/mysys_priv.h"
57
57
#include <mystrings/m_string.h>
58
58
#include <mysys/my_tree.h>
59
59
 
75
75
 
76
76
 
77
77
void init_tree(TREE *tree, uint32_t default_alloc_size, uint32_t memory_limit,
78
 
               int size, qsort_cmp2 compare, bool with_delete,
 
78
               uint32_t 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)
83
83
  default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
84
84
  memset(&tree->null_element, 0, sizeof(tree->null_element));
85
85
  tree->root= &tree->null_element;
86
 
  tree->compare=compare;
87
 
  tree->size_of_element=size > 0 ? (uint) size : 0;
88
 
  tree->memory_limit=memory_limit;
89
 
  tree->free=free_element;
90
 
  tree->allocated=0;
91
 
  tree->elements_in_tree=0;
 
86
  tree->compare= compare;
 
87
  tree->size_of_element= size > 0 ? (uint32_t) size : 0;
 
88
  tree->memory_limit= memory_limit;
 
89
  tree->free= free_element;
 
90
  tree->allocated= 0;
 
91
  tree->elements_in_tree= 0;
92
92
  tree->custom_arg = custom_arg;
93
 
  tree->null_element.colour=BLACK;
94
 
  tree->null_element.left=tree->null_element.right=0;
 
93
  tree->null_element.colour= BLACK;
 
94
  tree->null_element.left=tree->null_element.right= 0;
95
95
  tree->flag= 0;
96
 
  if (!free_element && size >= 0 &&
97
 
      ((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1))))
 
96
  if (!free_element &&
 
97
      (size <= sizeof(void*) || ((uint32_t) size & (sizeof(void*)-1))))
98
98
  {
99
99
    /*
100
100
      We know that the data doesn't have to be aligned (like if the key
101
101
      contains a double), so we can store the data combined with the
102
102
      TREE_ELEMENT.
103
103
    */
104
 
    tree->offset_to_key=sizeof(TREE_ELEMENT); /* Put key after element */
 
104
    tree->offset_to_key= sizeof(TREE_ELEMENT); /* Put key after element */
105
105
    /* Fix allocation size so that we don't lose any memory */
106
 
    default_alloc_size/=(sizeof(TREE_ELEMENT)+size);
 
106
    default_alloc_size/= (sizeof(TREE_ELEMENT)+size);
107
107
    if (!default_alloc_size)
108
 
      default_alloc_size=1;
109
 
    default_alloc_size*=(sizeof(TREE_ELEMENT)+size);
 
108
      default_alloc_size= 1;
 
109
    default_alloc_size*= (sizeof(TREE_ELEMENT)+size);
110
110
  }
111
111
  else
112
112
  {
113
 
    tree->offset_to_key=0;              /* use key through pointer */
114
 
    tree->size_of_element+=sizeof(void*);
 
113
    tree->offset_to_key= 0;             /* use key through pointer */
 
114
    tree->size_of_element+= sizeof(void*);
115
115
  }
116
 
  if (!(tree->with_delete=with_delete))
 
116
  if (! (tree->with_delete= with_delete))
117
117
  {
118
 
    init_alloc_root(&tree->mem_root, (uint) default_alloc_size, 0);
119
 
    tree->mem_root.min_malloc=(sizeof(TREE_ELEMENT)+tree->size_of_element);
 
118
    init_alloc_root(&tree->mem_root, (uint32_t) default_alloc_size, 0);
 
119
    tree->mem_root.min_malloc= (sizeof(TREE_ELEMENT)+tree->size_of_element);
120
120
  }
121
 
  return;
122
121
}
123
122
 
124
123
static void free_tree(TREE *tree, myf free_flags)
141
140
    }
142
141
  }
143
142
  tree->root= &tree->null_element;
144
 
  tree->elements_in_tree=0;
145
 
  tree->allocated=0;
146
 
 
147
 
  return;
 
143
  tree->elements_in_tree= 0;
 
144
  tree->allocated= 0;
148
145
}
149
146
 
150
147
void delete_tree(TREE* tree)
206
203
  }
207
204
  if (element == &tree->null_element)
208
205
  {
209
 
    uint32_t alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
210
 
    tree->allocated+=alloc_size;
 
206
    size_t alloc_size= sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
 
207
    tree->allocated+= alloc_size;
211
208
 
212
209
    if (tree->memory_limit && tree->elements_in_tree
213
210
                           && tree->allocated > tree->memory_limit)
216
213
      return tree_insert(tree, key, key_size, custom_arg);
217
214
    }
218
215
 
219
 
    key_size+=tree->size_of_element;
 
216
    key_size+= tree->size_of_element;
220
217
    if (tree->with_delete)
221
 
      element=(TREE_ELEMENT *) malloc(alloc_size);
 
218
      element= (TREE_ELEMENT *) malloc(alloc_size);
222
219
    else
223
 
      element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
 
220
      element= (TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
224
221
    if (!element)
225
222
      return(NULL);
226
 
    **parent=element;
227
 
    element->left=element->right= &tree->null_element;
 
223
    **parent= element;
 
224
    element->left= element->right= &tree->null_element;
228
225
    if (!tree->offset_to_key)
229
226
    {
230
227
      if (key_size == sizeof(void*))             /* no length, save pointer */
231
 
        *((void**) (element+1))=key;
 
228
        *((void**) (element+1))= key;
232
229
      else
233
230
      {
234
231
        *((void**) (element+1))= (void*) ((void **) (element+1)+1);
237
234
    }
238
235
    else
239
236
      memcpy((unsigned char*) element + tree->offset_to_key, key, key_size);
240
 
    element->count=1;                   /* May give warning in purify */
 
237
    element->count= 1;                  /* May give warning in purify */
241
238
    tree->elements_in_tree++;
242
239
    rb_insert(tree,parent,element);     /* rebalance tree */
243
240
  }
250
247
    if (! element->count)
251
248
      element->count--;
252
249
  }
 
250
 
253
251
  return element;
254
252
}
255
253
 
256
254
int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg)
257
255
{
258
 
  int cmp,remove_colour;
 
256
  int remove_colour;
259
257
  TREE_ELEMENT *element,***parent, ***org_parent, *nod;
260
258
  if (!tree->with_delete)
261
259
    return 1;                                   /* not allowed */
264
262
  *parent= &tree->root; element= tree->root;
265
263
  for (;;)
266
264
  {
 
265
    int cmp;
 
266
 
267
267
    if (element == &tree->null_element)
268
268
      return 1;                         /* Was not in tree */
269
269
    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
280
280
  }
281
281
  if (element->left == &tree->null_element)
282
282
  {
283
 
    (**parent)=element->right;
 
283
    (**parent)= element->right;
284
284
    remove_colour= element->colour;
285
285
  }
286
286
  else if (element->right == &tree->null_element)
287
287
  {
288
 
    (**parent)=element->left;
 
288
    (**parent)= element->left;
289
289
    remove_colour= element->colour;
290
290
  }
291
291
  else
296
296
    {
297
297
      *++parent= &nod->left; nod= nod->left;
298
298
    }
299
 
    (**parent)=nod->right;              /* unlink nod from tree */
 
299
    (**parent)= nod->right;             /* unlink nod from tree */
300
300
    remove_colour= nod->colour;
301
 
    org_parent[0][0]=nod;               /* put y in place of element */
 
301
    org_parent[0][0]= nod;              /* put y in place of element */
302
302
    org_parent[1]= &nod->right;
303
 
    nod->left=element->left;
304
 
    nod->right=element->right;
305
 
    nod->colour=element->colour;
 
303
    nod->left= element->left;
 
304
    nod->right= element->right;
 
305
    nod->colour= element->colour;
306
306
  }
307
307
  if (remove_colour == BLACK)
308
308
    rb_delete_fixup(tree,parent);
311
311
  tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
312
312
  free((unsigned char*) element);
313
313
  tree->elements_in_tree--;
 
314
 
314
315
  return 0;
315
316
}
316
317
 
317
 
 
318
 
void *tree_search(TREE *tree, void *key, void *custom_arg)
319
 
{
320
 
  int cmp;
321
 
  TREE_ELEMENT *element=tree->root;
322
 
 
323
 
  for (;;)
324
 
  {
325
 
    if (element == &tree->null_element)
326
 
      return (void*) 0;
327
 
    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
328
 
                                key)) == 0)
329
 
      return ELEMENT_KEY(tree,element);
330
 
    if (cmp < 0)
331
 
      element=element->right;
332
 
    else
333
 
      element=element->left;
334
 
  }
335
 
}
336
 
 
337
318
void *tree_search_key(TREE *tree, const void *key,
338
319
                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
339
320
                      enum ha_rkey_function flag, void *custom_arg)
340
321
{
341
 
  int cmp;
342
322
  TREE_ELEMENT *element= tree->root;
343
323
  TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
344
324
  TREE_ELEMENT **last_equal_element= NULL;
350
330
  *parents = &tree->null_element;
351
331
  while (element != &tree->null_element)
352
332
  {
 
333
    int cmp;
 
334
 
353
335
    *++parents= element;
 
336
 
354
337
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
355
338
                               key)) == 0)
356
339
    {
404
387
  default:
405
388
    return NULL;
406
389
  }
 
390
 
407
391
  return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
408
392
}
409
393
 
461
445
ha_rows tree_record_pos(TREE *tree, const void *key,
462
446
                        enum ha_rkey_function flag, void *custom_arg)
463
447
{
464
 
  int cmp;
465
448
  TREE_ELEMENT *element= tree->root;
466
449
  double left= 1;
467
450
  double right= tree->elements_in_tree;
468
451
 
469
452
  while (element != &tree->null_element)
470
453
  {
 
454
    int cmp;
 
455
 
471
456
    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
472
457
                               key)) == 0)
473
458
    {
494
479
      right= (left + right) / 2;
495
480
    }
496
481
  }
 
482
 
497
483
  switch (flag) {
498
484
  case HA_READ_KEY_EXACT:
499
485
  case HA_READ_BEFORE_KEY:
513
499
  case right_root_left:
514
500
    return tree_walk_right_root_left(tree,tree->root,action,argument);
515
501
  }
 
502
 
516
503
  return 0;                     /* Keep gcc happy */
517
504
}
518
505
 
529
516
      error=tree_walk_left_root_right(tree,element->right,action,argument);
530
517
    return error;
531
518
  }
 
519
 
532
520
  return 0;
533
521
}
534
522
 
545
533
     error=tree_walk_right_root_left(tree,element->left,action,argument);
546
534
    return error;
547
535
  }
 
536
 
548
537
  return 0;
549
538
}
550
539
 
551
540
 
552
 
        /* Functions to fix up the tree after insert and delete */
 
541
/* Functions to fix up the tree after insert and delete */
553
542
 
554
543
static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
555
544
{
556
545
  TREE_ELEMENT *y;
557
546
 
558
 
  y=leaf->right;
559
 
  leaf->right=y->left;
560
 
  parent[0]=y;
561
 
  y->left=leaf;
 
547
  y= leaf->right;
 
548
  leaf->right= y->left;
 
549
  parent[0]= y;
 
550
  y->left= leaf;
562
551
}
563
552
 
564
553
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
565
554
{
566
555
  TREE_ELEMENT *x;
567
556
 
568
 
  x=leaf->left;
569
 
  leaf->left=x->right;
570
 
  parent[0]=x;
571
 
  x->right=leaf;
 
557
  x= leaf->left;
 
558
  leaf->left= x->right;
 
559
  parent[0]= x;
 
560
  x->right= leaf;
572
561
}
573
562
 
574
563
static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
583
572
      y= par2->right;
584
573
      if (y->colour == RED)
585
574
      {
586
 
        par->colour=BLACK;
587
 
        y->colour=BLACK;
588
 
        leaf=par2;
589
 
        parent-=2;
590
 
        leaf->colour=RED;               /* And the loop continues */
 
575
        par->colour= BLACK;
 
576
        y->colour= BLACK;
 
577
        leaf= par2;
 
578
        parent-= 2;
 
579
        leaf->colour= RED;              /* And the loop continues */
591
580
      }
592
581
      else
593
582
      {
594
583
        if (leaf == par->right)
595
584
        {
596
585
          left_rotate(parent[-1],par);
597
 
          par=leaf;                     /* leaf is now parent to old leaf */
 
586
          par= leaf;                    /* leaf is now parent to old leaf */
598
587
        }
599
 
        par->colour=BLACK;
600
 
        par2->colour=RED;
 
588
        par->colour= BLACK;
 
589
        par2->colour= RED;
601
590
        right_rotate(parent[-2],par2);
602
591
        break;
603
592
      }
607
596
      y= par2->left;
608
597
      if (y->colour == RED)
609
598
      {
610
 
        par->colour=BLACK;
611
 
        y->colour=BLACK;
612
 
        leaf=par2;
613
 
        parent-=2;
614
 
        leaf->colour=RED;               /* And the loop continues */
 
599
        par->colour= BLACK;
 
600
        y->colour= BLACK;
 
601
        leaf= par2;
 
602
        parent-= 2;
 
603
        leaf->colour= RED;              /* And the loop continues */
615
604
      }
616
605
      else
617
606
      {
618
607
        if (leaf == par->left)
619
608
        {
620
609
          right_rotate(parent[-1],par);
621
 
          par=leaf;
 
610
          par= leaf;
622
611
        }
623
 
        par->colour=BLACK;
624
 
        par2->colour=RED;
 
612
        par->colour= BLACK;
 
613
        par2->colour= RED;
625
614
        left_rotate(parent[-2],par2);
626
615
        break;
627
616
      }
639
628
  {
640
629
    if (x == (par=parent[-1][0])->left)
641
630
    {
642
 
      w=par->right;
 
631
      w= par->right;
643
632
      if (w->colour == RED)
644
633
      {
645
 
        w->colour=BLACK;
646
 
        par->colour=RED;
 
634
        w->colour= BLACK;
 
635
        par->colour= RED;
647
636
        left_rotate(parent[-1],par);
648
637
        parent[0]= &w->left;
649
638
        *++parent= &par->left;
650
 
        w=par->right;
 
639
        w= par->right;
651
640
      }
652
641
      if (w->left->colour == BLACK && w->right->colour == BLACK)
653
642
      {
654
 
        w->colour=RED;
655
 
        x=par;
 
643
        w->colour= RED;
 
644
        x= par;
656
645
        parent--;
657
646
      }
658
647
      else
659
648
      {
660
649
        if (w->right->colour == BLACK)
661
650
        {
662
 
          w->left->colour=BLACK;
663
 
          w->colour=RED;
 
651
          w->left->colour= BLACK;
 
652
          w->colour= RED;
664
653
          right_rotate(&par->right,w);
665
 
          w=par->right;
 
654
          w= par->right;
666
655
        }
667
 
        w->colour=par->colour;
668
 
        par->colour=BLACK;
669
 
        w->right->colour=BLACK;
 
656
        w->colour= par->colour;
 
657
        par->colour= BLACK;
 
658
        w->right->colour= BLACK;
670
659
        left_rotate(parent[-1],par);
671
 
        x=tree->root;
 
660
        x= tree->root;
672
661
        break;
673
662
      }
674
663
    }
677
666
      w=par->left;
678
667
      if (w->colour == RED)
679
668
      {
680
 
        w->colour=BLACK;
681
 
        par->colour=RED;
 
669
        w->colour= BLACK;
 
670
        par->colour= RED;
682
671
        right_rotate(parent[-1],par);
683
672
        parent[0]= &w->right;
684
673
        *++parent= &par->right;
685
 
        w=par->left;
 
674
        w= par->left;
686
675
      }
687
676
      if (w->right->colour == BLACK && w->left->colour == BLACK)
688
677
      {
689
 
        w->colour=RED;
690
 
        x=par;
 
678
        w->colour= RED;
 
679
        x= par;
691
680
        parent--;
692
681
      }
693
682
      else
694
683
      {
695
684
        if (w->left->colour == BLACK)
696
685
        {
697
 
          w->right->colour=BLACK;
698
 
          w->colour=RED;
 
686
          w->right->colour= BLACK;
 
687
          w->colour= RED;
699
688
          left_rotate(&par->left,w);
700
 
          w=par->left;
 
689
          w= par->left;
701
690
        }
702
 
        w->colour=par->colour;
703
 
        par->colour=BLACK;
704
 
        w->left->colour=BLACK;
 
691
        w->colour= par->colour;
 
692
        par->colour= BLACK;
 
693
        w->left->colour= BLACK;
705
694
        right_rotate(parent[-1],par);
706
 
        x=tree->root;
 
695
        x= tree->root;
707
696
        break;
708
697
      }
709
698
    }
710
699
  }
711
 
  x->colour=BLACK;
 
700
  x->colour= BLACK;
712
701
}