home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / mysys / tree.c < prev    next >
C/C++ Source or Header  |  2000-09-12  |  13KB  |  514 lines
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.    
  3.    This library is free software; you can redistribute it and/or
  4.    modify it under the terms of the GNU Library General Public
  5.    License as published by the Free Software Foundation; either
  6.    version 2 of the License, or (at your option) any later version.
  7.    
  8.    This library is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11.    Library General Public License for more details.
  12.    
  13.    You should have received a copy of the GNU Library General Public
  14.    License along with this library; if not, write to the Free
  15.    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  16.    MA 02111-1307, USA */
  17.  
  18. /*
  19.   Code for handling red-black (balanced) binary trees.
  20.   key in tree is allocated accrding to following:
  21.   1) If free_element function is given to init_tree or size < 0 then tree
  22.      will not allocate keys and only a pointer to each key is saved in tree.
  23.      key_sizes must be 0 to init and search.
  24.      compare and search functions uses and returns key-pointer.
  25.   2) if key_size is given to init_tree then each node will continue the
  26.      key and calls to insert_key may increase length of key.
  27.      if key_size > sizeof(pointer) and key_size is a multiple of 8 (double
  28.      allign) then key will be put on a 8 alligned adress. Else
  29.      the key will be on adress (element+1). This is transparent for user
  30.      compare and search functions uses a pointer to given key-argument.
  31.   3) If init_tree - keysize is 0 then key_size must be given to tree_insert
  32.      and tree_insert will alloc space for key.
  33.      compare and search functions uses a pointer to given key-argument.
  34.  
  35.   The actual key in TREE_ELEMENT is saved as a pointer or after the
  36.   TREE_ELEMENT struct.
  37.   If one uses only pointers in tree one can use tree_set_pointer() to
  38.   change address of data.
  39.   Copyright Monty Program KB.
  40.   By monty.
  41. */
  42.  
  43. #include "mysys_priv.h"
  44. #include <m_string.h>
  45. #include <my_tree.h>
  46.  
  47. #define BLACK        1
  48. #define RED        0
  49. #define DEFAULT_ALLOC_SIZE (8192-MALLOC_OVERHEAD)
  50.  
  51. static void delete_tree_element(TREE *,TREE_ELEMENT *);
  52. static int tree_walk_left_root_right(TREE *,TREE_ELEMENT *,
  53.                      tree_walk_action,void *);
  54. static int tree_walk_right_root_left(TREE *,TREE_ELEMENT *,
  55.                      tree_walk_action,void *);
  56. static void left_rotate(TREE_ELEMENT **parent,TREE_ELEMENT *leaf);
  57. static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
  58. static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
  59.               TREE_ELEMENT *leaf);
  60. static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
  61.  
  62.  
  63.     /* The actuall code for handling binary trees */
  64.  
  65. void init_tree(TREE *tree, uint default_alloc_size, int size,
  66.            qsort_cmp compare, my_bool with_delete,
  67.            void (*free_element) (void *))
  68. {
  69.   DBUG_ENTER("init_tree");
  70.   DBUG_PRINT("enter",("tree: %lx  size: %d",tree,size));
  71.  
  72.   if (!default_alloc_size)
  73.     default_alloc_size= DEFAULT_ALLOC_SIZE;
  74.   bzero((gptr) &tree->null_element,sizeof(tree->null_element));
  75.   tree->root= &tree->null_element;
  76.   tree->compare=compare;
  77.   tree->size_of_element=size > 0 ? (uint) size : 0;
  78.   tree->free=free_element;
  79.   tree->elements_in_tree=0;
  80.   tree->null_element.colour=BLACK;
  81.   tree->null_element.left=tree->null_element.right=0;
  82.   if (!free_element && size >= 0 &&
  83.       ((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1))))
  84.   {
  85.     tree->offset_to_key=sizeof(TREE_ELEMENT); /* Put key after element */
  86.     /* Fix allocation size so that we don't loose any memory */
  87.     default_alloc_size/=(sizeof(TREE_ELEMENT)+size);
  88.     if (!default_alloc_size)
  89.       default_alloc_size=1;
  90.     default_alloc_size*=(sizeof(TREE_ELEMENT)+size);
  91.   }
  92.   else
  93.   {
  94.     tree->offset_to_key=0;        /* use key through pointer */
  95.     tree->size_of_element+=sizeof(void*);
  96.   }
  97.   if (!(tree->with_delete=with_delete))
  98.   {
  99.     init_alloc_root(&tree->mem_root, default_alloc_size,0);
  100.     tree->mem_root.min_malloc=(sizeof(TREE_ELEMENT)+tree->size_of_element);
  101.   }
  102.   DBUG_VOID_RETURN;
  103. }
  104.  
  105. void delete_tree(TREE *tree)
  106. {
  107.   DBUG_ENTER("delete_tree");
  108.   DBUG_PRINT("enter",("tree: %lx",tree));
  109.  
  110.   if (tree->root)                /* If initialized */
  111.   {
  112.     if (tree->with_delete)
  113.       delete_tree_element(tree,tree->root);
  114.     else
  115.     {
  116.       if (tree->free)
  117.     delete_tree_element(tree,tree->root);
  118.       free_root(&tree->mem_root,MYF(0));
  119.     }
  120.   }
  121.   tree->root= &tree->null_element;
  122.   tree->elements_in_tree=0;
  123.  
  124.   DBUG_VOID_RETURN;
  125. }
  126.  
  127. static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
  128. {
  129.   if (element != &tree->null_element)
  130.   {
  131.     delete_tree_element(tree,element->left);
  132.     delete_tree_element(tree,element->right);
  133.     if (tree->free)
  134.       (*tree->free)(ELEMENT_KEY(tree,element));
  135.     if (tree->with_delete)
  136.       my_free((void*) element,MYF(0));
  137.   }
  138. }
  139.  
  140.     /* Code for insert, search and delete of elements */
  141.     /*   parent[0] = & parent[-1][0]->left ||
  142.          parent[0] = & parent[-1][0]->right */
  143.  
  144.  
  145. TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
  146. {
  147.   int cmp;
  148.   TREE_ELEMENT *element,***parent;
  149.  
  150.   parent= tree->parents;
  151.   *parent = &tree->root; element= tree->root;
  152.   for (;;)
  153.   {
  154.     if (element == &tree->null_element ||
  155.     (cmp=(*tree->compare)(ELEMENT_KEY(tree,element),key)) == 0)
  156.       break;
  157.     if (cmp < 0)
  158.     {
  159.       *++parent= &element->right; element= element->right;
  160.     }
  161.     else
  162.     {
  163.       *++parent = &element->left; element= element->left;
  164.     }
  165.   }
  166.   if (element == &tree->null_element)
  167.   {
  168.     key_size+=tree->size_of_element;
  169.     if (tree->with_delete)
  170.       element=(TREE_ELEMENT *) my_malloc(sizeof(TREE_ELEMENT)+key_size,
  171.                      MYF(MY_WME));
  172.     else
  173.       element=(TREE_ELEMENT *)
  174.     alloc_root(&tree->mem_root,sizeof(TREE_ELEMENT)+key_size);
  175.     if (!element)
  176.       return(NULL);
  177.     **parent=element;
  178.     element->left=element->right= &tree->null_element;
  179.     if (!tree->offset_to_key)
  180.     {
  181.       if (key_size == sizeof(void*))         /* no length, save pointer */
  182.     *((void**) (element+1))=key;
  183.       else
  184.       {
  185.     *((void**) (element+1))= (void*) ((void **) (element+1)+1);
  186.     memcpy((byte*) *((void **) (element+1)),key,
  187.            (size_t) (key_size-sizeof(void*)));
  188.       }
  189.     }
  190.     else
  191.       memcpy((byte*) element+tree->offset_to_key,key,(size_t) key_size);
  192.     element->count=1;                /* May give warning in purify */
  193.     tree->elements_in_tree++;
  194.     rb_insert(tree,parent,element);        /* rebalance tree */
  195.   }
  196.   else
  197.     element->count++;
  198.   return element;
  199. }
  200.  
  201.  
  202. int tree_delete(TREE *tree, void *key)
  203. {
  204.   int cmp,remove_colour;
  205.   TREE_ELEMENT *element,***parent, ***org_parent, *nod;
  206.   if (!tree->with_delete)
  207.     return 1;                    /* not allowed */
  208.  
  209.   parent= tree->parents;
  210.   *parent= &tree->root; element= tree->root;
  211.   for (;;)
  212.   {
  213.     if (element == &tree->null_element)
  214.       return 1;                /* Was not in tree */
  215.     if ((cmp=(*tree->compare)(ELEMENT_KEY(tree,element),key)) == 0)
  216.       break;
  217.     if (cmp < 0)
  218.     {
  219.       *++parent= &element->right; element= element->right;
  220.     }
  221.     else
  222.     {
  223.       *++parent = &element->left; element= element->left;
  224.     }
  225.   }
  226.   if (element->left == &tree->null_element)
  227.   {
  228.     (**parent)=element->right;
  229.     remove_colour= element->colour;
  230.   }
  231.   else if (element->right == &tree->null_element)
  232.   {
  233.     (**parent)=element->left;
  234.     remove_colour= element->colour;
  235.   }
  236.   else
  237.   {
  238.     org_parent= parent;
  239.     *++parent= &element->right; nod= element->right;
  240.     while (nod->left != &tree->null_element)
  241.     {
  242.       *++parent= &nod->left; nod= nod->left;
  243.     }
  244.     (**parent)=nod->right;        /* unlink nod from tree */
  245.     remove_colour= nod->colour;
  246.     org_parent[0][0]=nod;        /* put y in place of element */
  247.     org_parent[1]= &nod->right;
  248.     nod->left=element->left;
  249.     nod->right=element->right;
  250.     nod->colour=element->colour;
  251.   }
  252.   if (remove_colour == BLACK)
  253.     rb_delete_fixup(tree,parent);
  254.   my_free((gptr) element,MYF(0));
  255.   tree->elements_in_tree--;
  256.   return 0;
  257. }
  258.  
  259.  
  260. void *tree_search(TREE *tree, void *key)
  261. {
  262.   int cmp;
  263.   TREE_ELEMENT *element=tree->root;
  264.  
  265.   for (;;)
  266.   {
  267.     if (element == &tree->null_element)
  268.       return (void*) 0;
  269.     if ((cmp=(*tree->compare)(ELEMENT_KEY(tree,element),key)) == 0)
  270.       return ELEMENT_KEY(tree,element);
  271.     if (cmp < 0)
  272.       element=element->right;
  273.     else
  274.       element=element->left;
  275.   }
  276. }
  277.  
  278.  
  279. int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
  280. {
  281.   switch (visit) {
  282.   case left_root_right:
  283.     return tree_walk_left_root_right(tree,tree->root,action,argument);
  284.   case right_root_left:
  285.     return tree_walk_right_root_left(tree,tree->root,action,argument);
  286.   }
  287.   return 0;            /* Keep gcc happy */
  288. }
  289.  
  290. static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
  291. {
  292.   int error;
  293.   if (element->left)                /* Not null_element */
  294.   {
  295.     if ((error=tree_walk_left_root_right(tree,element->left,action,
  296.                       argument)) == 0 &&
  297.     (error=(*action)(ELEMENT_KEY(tree,element),
  298.               (element_count) element->count,
  299.               argument)) == 0)
  300.       error=tree_walk_left_root_right(tree,element->right,action,argument);
  301.     return error;
  302.   }
  303.   return 0;
  304. }
  305.  
  306. static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
  307. {
  308.   int error;
  309.   if (element->right)                /* Not null_element */
  310.   {
  311.     if ((error=tree_walk_right_root_left(tree,element->right,action,
  312.                       argument)) == 0 &&
  313.     (error=(*action)(ELEMENT_KEY(tree,element),
  314.               (element_count) element->count,
  315.               argument)) == 0)
  316.      error=tree_walk_right_root_left(tree,element->left,action,argument);
  317.     return error;
  318.   }
  319.   return 0;
  320. }
  321.  
  322.  
  323.     /* Functions to fix up the tree after insert and delete */
  324.  
  325. static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
  326. {
  327.   TREE_ELEMENT *y;
  328.  
  329.   y=leaf->right;
  330.   leaf->right=y->left;
  331.   parent[0]=y;
  332.   y->left=leaf;
  333. }
  334.  
  335. static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
  336. {
  337.   TREE_ELEMENT *x;
  338.  
  339.   x=leaf->left;
  340.   leaf->left=x->right;
  341.   parent[0]=x;
  342.   x->right=leaf;
  343. }
  344.  
  345. static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
  346. {
  347.   TREE_ELEMENT *y,*par,*par2;
  348.  
  349.   leaf->colour=RED;
  350.   while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
  351.   {
  352.     if (par == (par2=parent[-2][0])->left)
  353.     {
  354.       y= par2->right;
  355.       if (y->colour == RED)
  356.       {
  357.     par->colour=BLACK;
  358.     y->colour=BLACK;
  359.     leaf=par2;
  360.     parent-=2;
  361.     leaf->colour=RED;        /* And the loop continues */
  362.       }
  363.       else
  364.       {
  365.     if (leaf == par->right)
  366.     {
  367.       left_rotate(parent[-1],par);
  368.       par=leaf;            /* leaf is now parent to old leaf */
  369.     }
  370.     par->colour=BLACK;
  371.     par2->colour=RED;
  372.     right_rotate(parent[-2],par2);
  373.     break;
  374.       }
  375.     }
  376.     else
  377.     {
  378.       y= par2->left;
  379.       if (y->colour == RED)
  380.       {
  381.     par->colour=BLACK;
  382.     y->colour=BLACK;
  383.     leaf=par2;
  384.     parent-=2;
  385.     leaf->colour=RED;        /* And the loop continues */
  386.       }
  387.       else
  388.       {
  389.     if (leaf == par->left)
  390.     {
  391.       right_rotate(parent[-1],par);
  392.       par=leaf;
  393.     }
  394.     par->colour=BLACK;
  395.     par2->colour=RED;
  396.     left_rotate(parent[-2],par2);
  397.     break;
  398.       }
  399.     }
  400.   }
  401.   tree->root->colour=BLACK;
  402. }
  403.  
  404. static void rb_delete_fixup(TREE *tree, TREE_ELEMENT ***parent)
  405. {
  406.   TREE_ELEMENT *x,*w,*par;
  407.  
  408.   x= **parent;
  409.   while (x != tree->root && x->colour == BLACK)
  410.   {
  411.     if (x == (par=parent[-1][0])->left)
  412.     {
  413.       w=par->right;
  414.       if (w->colour == RED)
  415.       {
  416.     w->colour=BLACK;
  417.     par->colour=RED;
  418.     left_rotate(parent[-1],par);
  419.     parent[0]= &w->left;
  420.     *++parent= &par->left;
  421.     w=par->right;
  422.       }
  423.       if (w->left->colour == BLACK && w->right->colour == BLACK)
  424.       {
  425.     w->colour=RED;
  426.     x=par;
  427.     parent--;
  428.       }
  429.       else
  430.       {
  431.     if (w->right->colour == BLACK)
  432.     {
  433.       w->left->colour=BLACK;
  434.       w->colour=RED;
  435.       right_rotate(&par->right,w);
  436.       w=par->right;
  437.     }
  438.     w->colour=par->colour;
  439.     par->colour=BLACK;
  440.     w->right->colour=BLACK;
  441.     left_rotate(parent[-1],par);
  442.     x=tree->root;
  443.     break;
  444.       }
  445.     }
  446.     else
  447.     {
  448.       w=par->left;
  449.       if (w->colour == RED)
  450.       {
  451.     w->colour=BLACK;
  452.     par->colour=RED;
  453.     right_rotate(parent[-1],par);
  454.     parent[0]= &w->right;
  455.     *++parent= &par->right;
  456.     w=par->left;
  457.       }
  458.       if (w->right->colour == BLACK && w->left->colour == BLACK)
  459.       {
  460.     w->colour=RED;
  461.     x=par;
  462.     parent--;
  463.       }
  464.       else
  465.       {
  466.     if (w->left->colour == BLACK)
  467.     {
  468.       w->right->colour=BLACK;
  469.       w->colour=RED;
  470.       left_rotate(&par->left,w);
  471.       w=par->left;
  472.     }
  473.     w->colour=par->colour;
  474.     par->colour=BLACK;
  475.     w->left->colour=BLACK;
  476.     right_rotate(parent[-1],par);
  477.     x=tree->root;
  478.     break;
  479.       }
  480.     }
  481.   }
  482.   x->colour=BLACK;
  483. }
  484.  
  485.  
  486. #ifdef TESTING_TREES
  487.  
  488.     /* Test that the proporties for a red-black tree holds */
  489.  
  490. static int test_rb_tree(TREE_ELEMENT *element)
  491. {
  492.   int count_l,count_r;
  493.  
  494.   if (!element->left)
  495.     return 0;                /* Found end of tree */
  496.   if (element->colour == RED &&
  497.       (element->left->colour == RED || element->right->colour == RED))
  498.   {
  499.     printf("Wrong tree: Found two red in a row\n");
  500.     return -1;
  501.   }
  502.   count_l=test_rb_tree(element->left);
  503.   count_r=test_rb_tree(element->right);
  504.   if (count_l >= 0 && count_r >= 0)
  505.   {
  506.     if (count_l == count_r)
  507.       return count_l+(element->colour == BLACK);
  508.     printf("Wrong tree: Incorrect black-count: %d - %d\n",count_l,count_r);
  509.   }
  510.   return -1;
  511. }
  512.  
  513. #endif
  514.