tree.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:19k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /* Copyright (C) 2000 MySQL AB
  2.    This program is free software; you can redistribute it and/or modify
  3.    it under the terms of the GNU General Public License as published by
  4.    the Free Software Foundation; either version 2 of the License, or
  5.    (at your option) any later version.
  6.    This program is distributed in the hope that it will be useful,
  7.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  8.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  9.    GNU General Public License for more details.
  10.    You should have received a copy of the GNU General Public License
  11.    along with this program; if not, write to the Free Software
  12.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  13. /*
  14.   Code for handling red-black (balanced) binary trees.
  15.   key in tree is allocated accrding to following:
  16.   1) If size < 0 then tree will not allocate keys and only a pointer to
  17.      each key is saved in tree.
  18.      compare and search functions uses and returns key-pointer
  19.   2) If size == 0 then there are two options:
  20.        - key_size != 0 to tree_insert: The key will be stored in the tree.
  21.        - key_size == 0 to tree_insert:  A pointer to the key is stored.
  22.      compare and search functions uses and returns key-pointer.
  23.   3) if key_size is given to init_tree then each node will continue the
  24.      key and calls to insert_key may increase length of key.
  25.      if key_size > sizeof(pointer) and key_size is a multiple of 8 (double
  26.      allign) then key will be put on a 8 alligned adress. Else
  27.      the key will be on adress (element+1). This is transparent for user
  28.      compare and search functions uses a pointer to given key-argument.
  29.   - If you use a free function for tree-elements and you are freeing
  30.     the element itself, you should use key_size = 0 to init_tree and
  31.     tree_search
  32.   The actual key in TREE_ELEMENT is saved as a pointer or after the
  33.   TREE_ELEMENT struct.
  34.   If one uses only pointers in tree one can use tree_set_pointer() to
  35.   change address of data.
  36.   Implemented by monty.
  37. */
  38. /*
  39.   NOTE:
  40.   tree->compare function should be ALWAYS called as
  41.     (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element), key)
  42.   and not other way around, as
  43.     (*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
  44.   ft_boolean_search.c (at least) relies on that.
  45. */
  46. #include "mysys_priv.h"
  47. #include <m_string.h>
  48. #include <my_tree.h>
  49. #include "my_base.h"
  50. #define BLACK 1
  51. #define RED 0
  52. #define DEFAULT_ALLOC_SIZE 8192
  53. #define DEFAULT_ALIGN_SIZE 8192
  54. static void delete_tree_element(TREE *,TREE_ELEMENT *);
  55. static int tree_walk_left_root_right(TREE *,TREE_ELEMENT *,
  56.      tree_walk_action,void *);
  57. static int tree_walk_right_root_left(TREE *,TREE_ELEMENT *,
  58.      tree_walk_action,void *);
  59. static void left_rotate(TREE_ELEMENT **parent,TREE_ELEMENT *leaf);
  60. static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
  61. static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
  62.       TREE_ELEMENT *leaf);
  63. static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
  64. /* The actuall code for handling binary trees */
  65. #ifndef DBUG_OFF
  66. static int test_rb_tree(TREE_ELEMENT *element);
  67. #endif
  68. void init_tree(TREE *tree, uint default_alloc_size, uint memory_limit,
  69.                int size, qsort_cmp2 compare, my_bool with_delete,
  70.        tree_element_free free_element, void *custom_arg)
  71. {
  72.   DBUG_ENTER("init_tree");
  73.   DBUG_PRINT("enter",("tree: 0x%lx  size: %d",tree,size));
  74.   if (default_alloc_size < DEFAULT_ALLOC_SIZE)
  75.     default_alloc_size= DEFAULT_ALLOC_SIZE;
  76.   default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
  77.   bzero((gptr) &tree->null_element,sizeof(tree->null_element));
  78.   tree->root= &tree->null_element;
  79.   tree->compare=compare;
  80.   tree->size_of_element=size > 0 ? (uint) size : 0;
  81.   tree->memory_limit=memory_limit;
  82.   tree->free=free_element;
  83.   tree->allocated=0;
  84.   tree->elements_in_tree=0;
  85.   tree->custom_arg = custom_arg;
  86.   tree->null_element.colour=BLACK;
  87.   tree->null_element.left=tree->null_element.right=0;
  88.   tree->flag= 0;
  89.   if (!free_element && size >= 0 &&
  90.       ((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1))))
  91.   {
  92.     /*
  93.       We know that the data doesn't have to be aligned (like if the key
  94.       contains a double), so we can store the data combined with the
  95.       TREE_ELEMENT.
  96.     */
  97.     tree->offset_to_key=sizeof(TREE_ELEMENT); /* Put key after element */
  98.     /* Fix allocation size so that we don't lose any memory */
  99.     default_alloc_size/=(sizeof(TREE_ELEMENT)+size);
  100.     if (!default_alloc_size)
  101.       default_alloc_size=1;
  102.     default_alloc_size*=(sizeof(TREE_ELEMENT)+size);
  103.   }
  104.   else
  105.   {
  106.     tree->offset_to_key=0; /* use key through pointer */
  107.     tree->size_of_element+=sizeof(void*);
  108.   }
  109.   if (!(tree->with_delete=with_delete))
  110.   {
  111.     init_alloc_root(&tree->mem_root, default_alloc_size,0);
  112.     tree->mem_root.min_malloc=(sizeof(TREE_ELEMENT)+tree->size_of_element);
  113.   }
  114.   DBUG_VOID_RETURN;
  115. }
  116. static void free_tree(TREE *tree, myf free_flags)
  117. {
  118.   DBUG_ENTER("free_tree");
  119.   DBUG_PRINT("enter",("tree: 0x%lx",tree));
  120.   if (tree->root) /* If initialized */
  121.   {
  122.     if (tree->with_delete)
  123.       delete_tree_element(tree,tree->root);
  124.     else
  125.     {
  126.       if (tree->free)
  127.       {
  128.         if (tree->memory_limit)
  129.           (*tree->free)(NULL, free_init, tree->custom_arg);
  130. delete_tree_element(tree,tree->root);
  131.         if (tree->memory_limit)
  132.           (*tree->free)(NULL, free_end, tree->custom_arg);
  133.       }
  134.       free_root(&tree->mem_root, free_flags);
  135.     }
  136.   }
  137.   tree->root= &tree->null_element;
  138.   tree->elements_in_tree=0;
  139.   tree->allocated=0;
  140.   DBUG_VOID_RETURN;
  141. }
  142. void delete_tree(TREE* tree)
  143. {
  144.   free_tree(tree, MYF(0)); /* my_free() mem_root if applicable */
  145. }
  146. void reset_tree(TREE* tree)
  147. {
  148.   /* do not free mem_root, just mark blocks as free */
  149.   free_tree(tree, MYF(MY_MARK_BLOCKS_FREE));
  150. }
  151. static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
  152. {
  153.   if (element != &tree->null_element)
  154.   {
  155.     delete_tree_element(tree,element->left);
  156.     if (tree->free)
  157.       (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
  158.     delete_tree_element(tree,element->right);
  159.     if (tree->with_delete)
  160.       my_free((char*) element,MYF(0));
  161.   }
  162. }
  163. /*
  164.   insert, search and delete of elements
  165.   The following should be true:
  166.     parent[0] = & parent[-1][0]->left ||
  167.     parent[0] = & parent[-1][0]->right
  168. */
  169. TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size, 
  170.                           void* custom_arg)
  171. {
  172.   int cmp;
  173.   TREE_ELEMENT *element,***parent;
  174.   parent= tree->parents;
  175.   *parent = &tree->root; element= tree->root;
  176.   for (;;)
  177.   {
  178.     if (element == &tree->null_element ||
  179. (cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
  180.                                 key)) == 0)
  181.       break;
  182.     if (cmp < 0)
  183.     {
  184.       *++parent= &element->right; element= element->right;
  185.     }
  186.     else
  187.     {
  188.       *++parent = &element->left; element= element->left;
  189.     }
  190.   }
  191.   if (element == &tree->null_element)
  192.   {
  193.     uint alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
  194.     tree->allocated+=alloc_size;
  195.     if (tree->memory_limit && tree->elements_in_tree
  196.                            && tree->allocated > tree->memory_limit)
  197.     {
  198.       reset_tree(tree);
  199.       return tree_insert(tree, key, key_size, custom_arg);
  200.     }
  201.     key_size+=tree->size_of_element;
  202.     if (tree->with_delete)
  203.       element=(TREE_ELEMENT *) my_malloc(alloc_size, MYF(MY_WME));
  204.     else
  205.       element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
  206.     if (!element)
  207.       return(NULL);
  208.     **parent=element;
  209.     element->left=element->right= &tree->null_element;
  210.     if (!tree->offset_to_key)
  211.     {
  212.       if (key_size == sizeof(void*))  /* no length, save pointer */
  213. *((void**) (element+1))=key;
  214.       else
  215.       {
  216. *((void**) (element+1))= (void*) ((void **) (element+1)+1);
  217. memcpy((byte*) *((void **) (element+1)),key,
  218.        (size_t) (key_size-sizeof(void*)));
  219.       }
  220.     }
  221.     else
  222.       memcpy((byte*) element+tree->offset_to_key,key,(size_t) key_size);
  223.     element->count=1; /* May give warning in purify */
  224.     tree->elements_in_tree++;
  225.     rb_insert(tree,parent,element); /* rebalance tree */
  226.   }
  227.   else
  228.   {
  229.     if (tree->flag & TREE_NO_DUPS)
  230.       return(NULL);
  231.     element->count++;
  232.   }
  233.   DBUG_EXECUTE("check_tree", test_rb_tree(tree->root););
  234.   return element;
  235. }
  236. int tree_delete(TREE *tree, void *key, void *custom_arg)
  237. {
  238.   int cmp,remove_colour;
  239.   TREE_ELEMENT *element,***parent, ***org_parent, *nod;
  240.   if (!tree->with_delete)
  241.     return 1; /* not allowed */
  242.   parent= tree->parents;
  243.   *parent= &tree->root; element= tree->root;
  244.   for (;;)
  245.   {
  246.     if (element == &tree->null_element)
  247.       return 1; /* Was not in tree */
  248.     if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
  249.                                 key)) == 0)
  250.       break;
  251.     if (cmp < 0)
  252.     {
  253.       *++parent= &element->right; element= element->right;
  254.     }
  255.     else
  256.     {
  257.       *++parent = &element->left; element= element->left;
  258.     }
  259.   }
  260.   if (element->left == &tree->null_element)
  261.   {
  262.     (**parent)=element->right;
  263.     remove_colour= element->colour;
  264.   }
  265.   else if (element->right == &tree->null_element)
  266.   {
  267.     (**parent)=element->left;
  268.     remove_colour= element->colour;
  269.   }
  270.   else
  271.   {
  272.     org_parent= parent;
  273.     *++parent= &element->right; nod= element->right;
  274.     while (nod->left != &tree->null_element)
  275.     {
  276.       *++parent= &nod->left; nod= nod->left;
  277.     }
  278.     (**parent)=nod->right; /* unlink nod from tree */
  279.     remove_colour= nod->colour;
  280.     org_parent[0][0]=nod; /* put y in place of element */
  281.     org_parent[1]= &nod->right;
  282.     nod->left=element->left;
  283.     nod->right=element->right;
  284.     nod->colour=element->colour;
  285.   }
  286.   if (remove_colour == BLACK)
  287.     rb_delete_fixup(tree,parent);
  288.   if (tree->free)
  289.     (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
  290.   /* This doesn't include key_size, but better than nothing */
  291.   tree->allocated-= sizeof(TREE_ELEMENT)+tree->size_of_element;
  292.   my_free((gptr) element,MYF(0));
  293.   tree->elements_in_tree--;
  294.   return 0;
  295. }
  296. void *tree_search(TREE *tree, void *key, void *custom_arg)
  297. {
  298.   int cmp;
  299.   TREE_ELEMENT *element=tree->root;
  300.   for (;;)
  301.   {
  302.     if (element == &tree->null_element)
  303.       return (void*) 0;
  304.     if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
  305.                                 key)) == 0)
  306.       return ELEMENT_KEY(tree,element);
  307.     if (cmp < 0)
  308.       element=element->right;
  309.     else
  310.       element=element->left;
  311.   }
  312. }
  313. void *tree_search_key(TREE *tree, const void *key, 
  314.                       TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
  315.                       enum ha_rkey_function flag, void *custom_arg)
  316. {
  317.   int cmp;
  318.   TREE_ELEMENT *element= tree->root;
  319.   TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
  320.   TREE_ELEMENT **last_equal_element= NULL;
  321. /* 
  322.   TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
  323. */
  324.   *parents = &tree->null_element;
  325.   while (element != &tree->null_element)
  326.   {
  327.     *++parents= element;
  328.     if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
  329.        key)) == 0)
  330.     {
  331.       switch (flag) {
  332.       case HA_READ_KEY_EXACT:
  333.       case HA_READ_KEY_OR_NEXT:
  334.       case HA_READ_BEFORE_KEY:
  335. last_equal_element= parents;
  336. cmp= 1;
  337. break;
  338.       case HA_READ_AFTER_KEY:
  339. cmp= -1;
  340. break;
  341.       case HA_READ_PREFIX_LAST:
  342.       case HA_READ_PREFIX_LAST_OR_PREV:
  343. last_equal_element= parents;
  344. cmp= -1;
  345. break;
  346.       default:
  347. return NULL;
  348.       }
  349.     }
  350.     if (cmp < 0) /* element < key */
  351.     {
  352.       last_right_step_parent= parents;
  353.       element= element->right;
  354.     }
  355.     else
  356.     {
  357.       last_left_step_parent= parents;
  358.       element= element->left;
  359.     }
  360.   }
  361.   switch (flag) {
  362.   case HA_READ_KEY_EXACT:
  363.   case HA_READ_PREFIX_LAST:
  364.     *last_pos= last_equal_element;
  365.     break;
  366.   case HA_READ_KEY_OR_NEXT:
  367.     *last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
  368.     break;
  369.   case HA_READ_AFTER_KEY:
  370.     *last_pos= last_left_step_parent;
  371.     break;
  372.   case HA_READ_PREFIX_LAST_OR_PREV:
  373.     *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
  374.     break;
  375.   case HA_READ_BEFORE_KEY:
  376.     *last_pos= last_right_step_parent;
  377.     break;
  378.   default:
  379.     return NULL;
  380.   }
  381.   return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
  382. }
  383. /* 
  384.   Search first (the most left) or last (the most right) tree element 
  385. */
  386. void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
  387.        TREE_ELEMENT ***last_pos, int child_offs)
  388. {
  389.   TREE_ELEMENT *element= tree->root;
  390.   
  391.   *parents= &tree->null_element;
  392.   while (element != &tree->null_element)
  393.   {
  394.     *++parents= element;
  395.     element= ELEMENT_CHILD(element, child_offs);
  396.   }
  397.   *last_pos= parents;
  398.   return **last_pos != &tree->null_element ? 
  399.     ELEMENT_KEY(tree, **last_pos) : NULL;
  400. }
  401. void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
  402.                        int r_offs)
  403. {
  404.   TREE_ELEMENT *x= **last_pos;
  405.   
  406.   if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
  407.   {
  408.     x= ELEMENT_CHILD(x, r_offs);
  409.     *++*last_pos= x;
  410.     while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
  411.     {
  412.       x= ELEMENT_CHILD(x, l_offs);
  413.       *++*last_pos= x;
  414.     }
  415.     return ELEMENT_KEY(tree, x);
  416.   }
  417.   else
  418.   {
  419.     TREE_ELEMENT *y= *--*last_pos;
  420.     while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
  421.     {
  422.       x= y;
  423.       y= *--*last_pos;
  424.     }
  425.     return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
  426.   }
  427. }
  428. /*
  429.   Expected that tree is fully balanced
  430.   (each path from root to leaf has the same length)
  431. */
  432. ha_rows tree_record_pos(TREE *tree, const void *key, 
  433. enum ha_rkey_function flag, void *custom_arg)
  434. {
  435.   int cmp;
  436.   TREE_ELEMENT *element= tree->root;
  437.   double left= 1;
  438.   double right= tree->elements_in_tree;
  439.   while (element != &tree->null_element)
  440.   {
  441.     if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
  442.        key)) == 0)
  443.     {
  444.       switch (flag) {
  445.       case HA_READ_KEY_EXACT:
  446.       case HA_READ_BEFORE_KEY:
  447.         cmp= 1;
  448.         break;
  449.       case HA_READ_AFTER_KEY:
  450.         cmp= -1;
  451.         break;
  452.       default:
  453.         return HA_POS_ERROR;
  454.       }
  455.     }
  456.     if (cmp < 0) /* element < key */
  457.     {
  458.       element= element->right;
  459.       left= (left + right) / 2;
  460.     }
  461.     else
  462.     {
  463.       element= element->left;
  464.       right= (left + right) / 2;
  465.     }
  466.   }
  467.   switch (flag) {
  468.   case HA_READ_KEY_EXACT:
  469.   case HA_READ_BEFORE_KEY:
  470.     return (ha_rows) right;
  471.   case HA_READ_AFTER_KEY:
  472.     return (ha_rows) left;
  473.   default:
  474.     return HA_POS_ERROR;
  475.   }
  476. }
  477. int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
  478. {
  479.   switch (visit) {
  480.   case left_root_right:
  481.     return tree_walk_left_root_right(tree,tree->root,action,argument);
  482.   case right_root_left:
  483.     return tree_walk_right_root_left(tree,tree->root,action,argument);
  484.   }
  485.   return 0; /* Keep gcc happy */
  486. }
  487. static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
  488. {
  489.   int error;
  490.   if (element->left) /* Not null_element */
  491.   {
  492.     if ((error=tree_walk_left_root_right(tree,element->left,action,
  493.   argument)) == 0 &&
  494. (error=(*action)(ELEMENT_KEY(tree,element),
  495.   (element_count) element->count,
  496.   argument)) == 0)
  497.       error=tree_walk_left_root_right(tree,element->right,action,argument);
  498.     return error;
  499.   }
  500.   return 0;
  501. }
  502. static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
  503. {
  504.   int error;
  505.   if (element->right) /* Not null_element */
  506.   {
  507.     if ((error=tree_walk_right_root_left(tree,element->right,action,
  508.   argument)) == 0 &&
  509. (error=(*action)(ELEMENT_KEY(tree,element),
  510.   (element_count) element->count,
  511.   argument)) == 0)
  512.      error=tree_walk_right_root_left(tree,element->left,action,argument);
  513.     return error;
  514.   }
  515.   return 0;
  516. }
  517. /* Functions to fix up the tree after insert and delete */
  518. static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
  519. {
  520.   TREE_ELEMENT *y;
  521.   y=leaf->right;
  522.   leaf->right=y->left;
  523.   parent[0]=y;
  524.   y->left=leaf;
  525. }
  526. static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
  527. {
  528.   TREE_ELEMENT *x;
  529.   x=leaf->left;
  530.   leaf->left=x->right;
  531.   parent[0]=x;
  532.   x->right=leaf;
  533. }
  534. static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
  535. {
  536.   TREE_ELEMENT *y,*par,*par2;
  537.   leaf->colour=RED;
  538.   while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
  539.   {
  540.     if (par == (par2=parent[-2][0])->left)
  541.     {
  542.       y= par2->right;
  543.       if (y->colour == RED)
  544.       {
  545. par->colour=BLACK;
  546. y->colour=BLACK;
  547. leaf=par2;
  548. parent-=2;
  549. leaf->colour=RED; /* And the loop continues */
  550.       }
  551.       else
  552.       {
  553. if (leaf == par->right)
  554. {
  555.   left_rotate(parent[-1],par);
  556.   par=leaf; /* leaf is now parent to old leaf */
  557. }
  558. par->colour=BLACK;
  559. par2->colour=RED;
  560. right_rotate(parent[-2],par2);
  561. break;
  562.       }
  563.     }
  564.     else
  565.     {
  566.       y= par2->left;
  567.       if (y->colour == RED)
  568.       {
  569. par->colour=BLACK;
  570. y->colour=BLACK;
  571. leaf=par2;
  572. parent-=2;
  573. leaf->colour=RED; /* And the loop continues */
  574.       }
  575.       else
  576.       {
  577. if (leaf == par->left)
  578. {
  579.   right_rotate(parent[-1],par);
  580.   par=leaf;
  581. }
  582. par->colour=BLACK;
  583. par2->colour=RED;
  584. left_rotate(parent[-2],par2);
  585. break;
  586.       }
  587.     }
  588.   }
  589.   tree->root->colour=BLACK;
  590. }
  591. static void rb_delete_fixup(TREE *tree, TREE_ELEMENT ***parent)
  592. {
  593.   TREE_ELEMENT *x,*w,*par;
  594.   x= **parent;
  595.   while (x != tree->root && x->colour == BLACK)
  596.   {
  597.     if (x == (par=parent[-1][0])->left)
  598.     {
  599.       w=par->right;
  600.       if (w->colour == RED)
  601.       {
  602. w->colour=BLACK;
  603. par->colour=RED;
  604. left_rotate(parent[-1],par);
  605. parent[0]= &w->left;
  606. *++parent= &par->left;
  607. w=par->right;
  608.       }
  609.       if (w->left->colour == BLACK && w->right->colour == BLACK)
  610.       {
  611. w->colour=RED;
  612. x=par;
  613. parent--;
  614.       }
  615.       else
  616.       {
  617. if (w->right->colour == BLACK)
  618. {
  619.   w->left->colour=BLACK;
  620.   w->colour=RED;
  621.   right_rotate(&par->right,w);
  622.   w=par->right;
  623. }
  624. w->colour=par->colour;
  625. par->colour=BLACK;
  626. w->right->colour=BLACK;
  627. left_rotate(parent[-1],par);
  628. x=tree->root;
  629. break;
  630.       }
  631.     }
  632.     else
  633.     {
  634.       w=par->left;
  635.       if (w->colour == RED)
  636.       {
  637. w->colour=BLACK;
  638. par->colour=RED;
  639. right_rotate(parent[-1],par);
  640. parent[0]= &w->right;
  641. *++parent= &par->right;
  642. w=par->left;
  643.       }
  644.       if (w->right->colour == BLACK && w->left->colour == BLACK)
  645.       {
  646. w->colour=RED;
  647. x=par;
  648. parent--;
  649.       }
  650.       else
  651.       {
  652. if (w->left->colour == BLACK)
  653. {
  654.   w->right->colour=BLACK;
  655.   w->colour=RED;
  656.   left_rotate(&par->left,w);
  657.   w=par->left;
  658. }
  659. w->colour=par->colour;
  660. par->colour=BLACK;
  661. w->left->colour=BLACK;
  662. right_rotate(parent[-1],par);
  663. x=tree->root;
  664. break;
  665.       }
  666.     }
  667.   }
  668.   x->colour=BLACK;
  669. }
  670. #ifndef DBUG_OFF
  671. /* Test that the proporties for a red-black tree holds */
  672. static int test_rb_tree(TREE_ELEMENT *element)
  673. {
  674.   int count_l,count_r;
  675.   if (!element->left)
  676.     return 0; /* Found end of tree */
  677.   if (element->colour == RED &&
  678.       (element->left->colour == RED || element->right->colour == RED))
  679.   {
  680.     printf("Wrong tree: Found two red in a rown");
  681.     return -1;
  682.   }
  683.   count_l=test_rb_tree(element->left);
  684.   count_r=test_rb_tree(element->right);
  685.   if (count_l >= 0 && count_r >= 0)
  686.   {
  687.     if (count_l == count_r)
  688.       return count_l+(element->colour == BLACK);
  689.     printf("Wrong tree: Incorrect black-count: %d - %dn",count_l,count_r);
  690.   }
  691.   return -1;
  692. }
  693. #endif