Adding upstream version 1:10.11.6.upstream/1%10.11.6upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 804 insertions, 0 deletions

diff --git a/mysys/tree.c b/mysys/tree.c
new file mode 100644
index 00000000..cd44f779
--- /dev/null
+++ b/mysys/tree.c
@@ -0,0 +1,804 @@
+/* Copyright (c) 2000, 2016, Oracle and/or its affiliates.
+   Copyright (c) 2010, 2016, MariaDB
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/*
+  Code for handling red-black (balanced) binary trees.
+  key in tree is allocated accrding to following:
+
+  1) If size < 0 then tree will not allocate keys and only a pointer to
+     each key is saved in tree.
+     compare and search functions uses and returns key-pointer
+
+  2) If size == 0 then there are two options:
+       - key_size != 0 to tree_insert: The key will be stored in the tree.
+       - key_size == 0 to tree_insert:  A pointer to the key is stored.
+     compare and search functions uses and returns key-pointer.
+
+  3) if key_size is given to init_tree then each node will continue the
+     key and calls to insert_key may increase length of key.
+     if key_size > sizeof(pointer) and key_size is a multiple of 8 (double
+     align) then key will be put on a 8 aligned address. Else
+     the key will be on address (element+1). This is transparent for user
+     compare and search functions uses a pointer to given key-argument.
+
+  - If you use a free function for tree-elements and you are freeing
+    the element itself, you should use key_size = 0 to init_tree and
+    tree_search
+
+  The actual key in TREE_ELEMENT is saved as a pointer or after the
+  TREE_ELEMENT struct.
+  If one uses only pointers in tree one can use tree_set_pointer() to
+  change address of data.
+
+  Implemented by monty.
+*/
+
+/*
+  NOTE:
+  tree->compare function should be ALWAYS called as
+    (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element), key)
+  and not other way around, as
+    (*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
+
+  ft_boolean_search.c (at least) relies on that.
+*/
+
+#include "mysys_priv.h"
+#include <m_string.h>
+#include <my_tree.h>
+#include "my_base.h"
+
+#define BLACK		1
+#define RED		0
+#define DEFAULT_ALLOC_SIZE 8192
+#define DEFAULT_ALIGN_SIZE 8192
+
+static int delete_tree_element(TREE *,TREE_ELEMENT *, my_bool abort);
+static int tree_walk_left_root_right(TREE *,TREE_ELEMENT *,
+				     tree_walk_action,void *);
+static int tree_walk_right_root_left(TREE *,TREE_ELEMENT *,
+				     tree_walk_action,void *);
+static void left_rotate(TREE_ELEMENT **parent,TREE_ELEMENT *leaf);
+static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
+static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
+		      TREE_ELEMENT *leaf);
+static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
+
+static TREE_ELEMENT null_element= { NULL, NULL, 0, BLACK };
+
+/* The actual code for handling binary trees */
+
+#ifndef DBUG_OFF
+static int test_rb_tree(TREE_ELEMENT *element);
+#endif
+
+void init_tree(TREE *tree, size_t default_alloc_size, size_t memory_limit,
+               int size, qsort_cmp2 compare,
+	       tree_element_free free_element, void *custom_arg,
+               myf my_flags)
+{
+  DBUG_ENTER("init_tree");
+  DBUG_PRINT("enter",("tree: %p  size: %d", tree, size));
+
+  if (default_alloc_size < DEFAULT_ALLOC_SIZE)
+    default_alloc_size= DEFAULT_ALLOC_SIZE;
+  default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
+  tree->root= &null_element;
+  tree->compare=compare;
+  tree->size_of_element= size > 0 ? (uint) size : 0;
+  tree->memory_limit=memory_limit;
+  tree->free=free_element;
+  tree->allocated=0;
+  tree->elements_in_tree=0;
+  tree->custom_arg = custom_arg;
+  tree->my_flags= my_flags;
+  tree->flag= 0;
+  if (!free_element && size >= 0 &&
+      ((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1))))
+  {
+    /*
+      We know that the data doesn't have to be aligned (like if the key
+      contains a double), so we can store the data combined with the
+      TREE_ELEMENT.
+    */
+    tree->offset_to_key=sizeof(TREE_ELEMENT); /* Put key after element */
+    /* Fix allocation size so that we don't lose any memory */
+    default_alloc_size/=(sizeof(TREE_ELEMENT)+size);
+    if (!default_alloc_size)
+      default_alloc_size=1;
+    default_alloc_size*=(sizeof(TREE_ELEMENT)+size);
+  }
+  else
+  {
+    tree->offset_to_key=0;		/* use key through pointer */
+    tree->size_of_element+=sizeof(void*);
+  }
+  if (!(tree->with_delete= MY_TEST(my_flags & MY_TREE_WITH_DELETE)))
+  {
+    init_alloc_root(key_memory_TREE, &tree->mem_root, default_alloc_size, 0,
+                    MYF(my_flags));
+    tree->mem_root.min_malloc= sizeof(TREE_ELEMENT)+tree->size_of_element;
+  }
+  DBUG_VOID_RETURN;
+}
+
+static int free_tree(TREE *tree, my_bool abort, myf free_flags)
+{
+  int error, first_error= 0;
+  DBUG_ENTER("free_tree");
+  DBUG_PRINT("enter",("tree: %p", tree));
+
+  if (tree->root)				/* If initialized */
+  {
+    if (tree->with_delete)
+    {
+      if ((error= delete_tree_element(tree, tree->root, abort)))
+      {
+        first_error= first_error ? first_error : error;
+        abort= 1;
+      }
+    }
+    else
+    {
+      if (tree->free)
+      {
+        if (tree->memory_limit)
+          (*tree->free)(NULL, free_init, tree->custom_arg);
+	if ((error= delete_tree_element(tree, tree->root, abort)))
+          first_error= first_error ? first_error : error;
+        if (tree->memory_limit)
+          (*tree->free)(NULL, free_end, tree->custom_arg);
+      }
+      free_root(&tree->mem_root, free_flags);
+    }
+  }
+  tree->root= &null_element;
+  tree->elements_in_tree=0;
+  tree->allocated=0;
+
+  DBUG_RETURN(first_error);
+}
+
+
+/**
+  Delete tree.
+
+  @param tree     Tree
+  @param abort    0 if normal, 1 if tree->free should not be called.
+
+  @return         0 ok
+                  <> 0  Returns first <> 0 from (tree->free)(*,free_free,*)
+
+ @Notes
+   If one (tree->free)(,free_free,) returns <> 0, no future
+   tree->free(*,free_free,*) will be called.
+   Other tree->free operations (free_init, free_end) will be called
+*/
+
+
+int delete_tree(TREE* tree, my_bool abort)
+{
+  return free_tree(tree, abort, MYF(0)); /* my_free() mem_root if applicable */
+}
+
+int reset_tree(TREE* tree)
+{
+  /* do not free mem_root, just mark blocks as free */
+  return free_tree(tree, 0, MYF(MY_MARK_BLOCKS_FREE));
+}
+
+
+static int delete_tree_element(TREE *tree, TREE_ELEMENT *element,
+                               my_bool abort)
+{
+  int error, first_error= 0;
+  if (element != &null_element)
+  {
+    if ((first_error= delete_tree_element(tree, element->left, abort)))
+      abort= 1;
+    if (!abort && tree->free)
+    {
+      if ((error= (*tree->free)(ELEMENT_KEY(tree,element), free_free,
+                                tree->custom_arg)))
+      {
+        first_error= first_error ? first_error : error;
+        abort= 1;
+      }
+    }
+    if ((error= delete_tree_element(tree, element->right, abort)))
+      first_error= first_error ? first_error : error;
+    if (tree->with_delete)
+      my_free(element);
+  }
+  return first_error;
+}
+
+
+/*
+  insert, search and delete of elements
+
+  The following should be true:
+    parent[0] = & parent[-1][0]->left ||
+    parent[0] = & parent[-1][0]->right
+*/
+
+TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size, 
+                          void* custom_arg)
+{
+  int cmp;
+  TREE_ELEMENT *element,***parent;
+
+  parent= tree->parents;
+  *parent = &tree->root; element= tree->root;
+  for (;;)
+  {
+    if (element == &null_element ||
+	(cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
+      break;
+    if (cmp < 0)
+    {
+      *++parent= &element->right; element= element->right;
+    }
+    else
+    {
+      *++parent = &element->left; element= element->left;
+    }
+  }
+  if (element == &null_element)
+  {
+    uint alloc_size;
+    if (tree->flag & TREE_ONLY_DUPS)
+      return TREE_ELEMENT_UNIQUE;
+    alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
+    tree->allocated+=alloc_size;
+
+    if (tree->memory_limit && tree->elements_in_tree
+                           && tree->allocated > tree->memory_limit)
+    {
+      reset_tree(tree);
+      return tree_insert(tree, key, key_size, custom_arg);
+    }
+
+    key_size+=tree->size_of_element;
+    if (tree->with_delete)
+      element=(TREE_ELEMENT *) my_malloc(key_memory_TREE, alloc_size,
+                                         MYF(tree->my_flags | MY_WME));
+    else
+      element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
+    if (!element)
+      return(NULL);
+    **parent=element;
+    element->left=element->right= &null_element;
+    if (!tree->offset_to_key)
+    {
+      if (key_size == sizeof(void*))		 /* no length, save pointer */
+	*((void**) (element+1))=key;
+      else
+      {
+	*((void**) (element+1))= (void*) ((void **) (element+1)+1);
+	memcpy((uchar*) *((void **) (element+1)),key,
+	       (size_t) (key_size-sizeof(void*)));
+      }
+    }
+    else
+      memcpy((uchar*) element+tree->offset_to_key,key,(size_t) key_size);
+    element->count=1;			/* May give warning in purify */
+    tree->elements_in_tree++;
+    rb_insert(tree,parent,element);	/* rebalance tree */
+  }
+  else
+  {
+    if (tree->flag & TREE_NO_DUPS)
+      return(NULL);
+    element->count++;
+    /* Avoid a wrap over of the count. */
+    if (! element->count)
+      element->count--;
+  }
+  DBUG_EXECUTE("check_tree", test_rb_tree(tree->root););
+  return element;
+}
+
+int tree_delete(TREE *tree, void *key, uint key_size, void *custom_arg)
+{
+  int cmp,remove_colour;
+  TREE_ELEMENT *element,***parent, ***org_parent, *nod;
+  if (!tree->with_delete)
+    return 1;					/* not allowed */
+
+  parent= tree->parents;
+  *parent= &tree->root; element= tree->root;
+  for (;;)
+  {
+    if (element == &null_element)
+      return 1;				/* Was not in tree */
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
+      break;
+    if (cmp < 0)
+    {
+      *++parent= &element->right; element= element->right;
+    }
+    else
+    {
+      *++parent = &element->left; element= element->left;
+    }
+  }
+  if (element->left == &null_element)
+  {
+    (**parent)=element->right;
+    remove_colour= element->colour;
+  }
+  else if (element->right == &null_element)
+  {
+    (**parent)=element->left;
+    remove_colour= element->colour;
+  }
+  else
+  {
+    org_parent= parent;
+    *++parent= &element->right; nod= element->right;
+    while (nod->left != &null_element)
+    {
+      *++parent= &nod->left; nod= nod->left;
+    }
+    (**parent)=nod->right;		/* unlink nod from tree */
+    remove_colour= nod->colour;
+    org_parent[0][0]=nod;		/* put y in place of element */
+    org_parent[1]= &nod->right;
+    nod->left=element->left;
+    nod->right=element->right;
+    nod->colour=element->colour;
+  }
+  if (remove_colour == BLACK)
+    rb_delete_fixup(tree,parent);
+  if (tree->free)
+    (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
+  tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
+  my_free(element);
+  tree->elements_in_tree--;
+  return 0;
+}
+
+
+void *tree_search(TREE *tree, void *key, void *custom_arg)
+{
+  int cmp;
+  TREE_ELEMENT *element=tree->root;
+
+  for (;;)
+  {
+    if (element == &null_element)
+      return (void*) 0;
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
+      return ELEMENT_KEY(tree,element);
+    if (cmp < 0)
+      element=element->right;
+    else
+      element=element->left;
+  }
+}
+
+void *tree_search_key(TREE *tree, const void *key, 
+                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
+                      enum ha_rkey_function flag, void *custom_arg)
+{
+  int cmp;
+  TREE_ELEMENT *element= tree->root;
+  TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
+  TREE_ELEMENT **last_equal_element= NULL;
+
+/* 
+  TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
+*/
+
+  *parents = &null_element;
+  while (element != &null_element)
+  {
+    *++parents= element;
+    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
+			       key)) == 0)
+    {
+      switch (flag) {
+      case HA_READ_KEY_EXACT:
+      case HA_READ_KEY_OR_NEXT:
+      case HA_READ_BEFORE_KEY:
+      case HA_READ_KEY_OR_PREV:
+	last_equal_element= parents;
+	cmp= 1;
+	break;
+      case HA_READ_AFTER_KEY:
+	cmp= -1;
+	break;
+      case HA_READ_PREFIX_LAST:
+      case HA_READ_PREFIX_LAST_OR_PREV:
+	last_equal_element= parents;
+	cmp= -1;
+	break;
+      default:
+	return NULL;
+      }
+    }
+    if (cmp < 0) /* element < key */
+    {
+      last_right_step_parent= parents;
+      element= element->right;
+    }
+    else
+    {
+      last_left_step_parent= parents;
+      element= element->left;
+    }
+  }
+  switch (flag) {
+  case HA_READ_KEY_EXACT:
+  case HA_READ_PREFIX_LAST:
+    *last_pos= last_equal_element;
+    break;
+  case HA_READ_KEY_OR_NEXT:
+    *last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
+    break;
+  case HA_READ_AFTER_KEY:
+    *last_pos= last_left_step_parent;
+    break;
+  case HA_READ_PREFIX_LAST_OR_PREV:
+    *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
+    break;
+  case HA_READ_BEFORE_KEY:
+    *last_pos= last_right_step_parent;
+    break;
+  case HA_READ_KEY_OR_PREV:
+    *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
+    break;
+  default:
+    return NULL;
+  }
+  return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
+}
+
+/* 
+  Search first (the most left) or last (the most right) tree element 
+*/
+void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
+		       TREE_ELEMENT ***last_pos, int child_offs)
+{
+  TREE_ELEMENT *element= tree->root;
+  
+  *parents= &null_element;
+  while (element != &null_element)
+  {
+    *++parents= element;
+    element= ELEMENT_CHILD(element, child_offs);
+  }
+  *last_pos= parents;
+  return **last_pos != &null_element ? 
+    ELEMENT_KEY(tree, **last_pos) : NULL;
+}
+
+void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
+                       int r_offs)
+{
+  TREE_ELEMENT *x= **last_pos;
+  
+  if (ELEMENT_CHILD(x, r_offs) != &null_element)
+  {
+    x= ELEMENT_CHILD(x, r_offs);
+    *++*last_pos= x;
+    while (ELEMENT_CHILD(x, l_offs) != &null_element)
+    {
+      x= ELEMENT_CHILD(x, l_offs);
+      *++*last_pos= x;
+    }
+    return ELEMENT_KEY(tree, x);
+  }
+  else
+  {
+    TREE_ELEMENT *y= *--*last_pos;
+    while (y != &null_element && x == ELEMENT_CHILD(y, r_offs))
+    {
+      x= y;
+      y= *--*last_pos;
+    }
+    return y == &null_element ? NULL : ELEMENT_KEY(tree, y);
+  }
+}
+
+/*
+  Expected that tree is fully balanced
+  (each path from root to leaf has the same length)
+*/
+ha_rows tree_record_pos(TREE *tree, const void *key, 
+			enum ha_rkey_function flag, void *custom_arg)
+{
+  int cmp;
+  TREE_ELEMENT *element= tree->root;
+  double left= 1;
+  double right= tree->elements_in_tree;
+
+  while (element != &null_element)
+  {
+    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
+			       key)) == 0)
+    {
+      switch (flag) {
+      case HA_READ_KEY_EXACT:
+      case HA_READ_BEFORE_KEY:
+        cmp= 1;
+        break;
+      case HA_READ_AFTER_KEY:
+        cmp= -1;
+        break;
+      default:
+        return HA_POS_ERROR;
+      }
+    }
+    if (cmp < 0) /* element < key */
+    {
+      element= element->right;
+      left= (left + right) / 2;
+    }
+    else
+    {
+      element= element->left;
+      right= (left + right) / 2;
+    }
+  }
+  switch (flag) {
+  case HA_READ_KEY_EXACT:
+  case HA_READ_BEFORE_KEY:
+    return (ha_rows) right;
+  case HA_READ_AFTER_KEY:
+    return (ha_rows) left;
+  default:
+    return HA_POS_ERROR;
+  }
+}
+
+int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
+{
+  switch (visit) {
+  case left_root_right:
+    return tree_walk_left_root_right(tree,tree->root,action,argument);
+  case right_root_left:
+    return tree_walk_right_root_left(tree,tree->root,action,argument);
+  }
+  return 0;			/* Keep gcc happy */
+}
+
+static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
+{
+  int error;
+  if (element->left)				/* Not null_element */
+  {
+    if ((error=tree_walk_left_root_right(tree,element->left,action,
+					  argument)) == 0 &&
+	(error=(*action)(ELEMENT_KEY(tree,element),
+			  (element_count) element->count,
+			  argument)) == 0)
+      error=tree_walk_left_root_right(tree,element->right,action,argument);
+    return error;
+  }
+  return 0;
+}
+
+static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
+{
+  int error;
+  if (element->right)				/* Not null_element */
+  {
+    if ((error=tree_walk_right_root_left(tree,element->right,action,
+					  argument)) == 0 &&
+	(error=(*action)(ELEMENT_KEY(tree,element),
+			  (element_count) element->count,
+			  argument)) == 0)
+     error=tree_walk_right_root_left(tree,element->left,action,argument);
+    return error;
+  }
+  return 0;
+}
+
+
+	/* Functions to fix up the tree after insert and delete */
+
+static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
+{
+  TREE_ELEMENT *y;
+
+  y=leaf->right;
+  leaf->right=y->left;
+  parent[0]=y;
+  y->left=leaf;
+}
+
+static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
+{
+  TREE_ELEMENT *x;
+
+  x=leaf->left;
+  leaf->left=x->right;
+  parent[0]=x;
+  x->right=leaf;
+}
+
+static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
+{
+  TREE_ELEMENT *y,*par,*par2;
+
+  leaf->colour=RED;
+  while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
+  {
+    if (par == (par2=parent[-2][0])->left)
+    {
+      y= par2->right;
+      if (y->colour == RED)
+      {
+	par->colour=BLACK;
+	y->colour=BLACK;
+	leaf=par2;
+	parent-=2;
+	leaf->colour=RED;		/* And the loop continues */
+      }
+      else
+      {
+	if (leaf == par->right)
+	{
+	  left_rotate(parent[-1],par);
+	  par=leaf;			/* leaf is now parent to old leaf */
+	}
+	par->colour=BLACK;
+	par2->colour=RED;
+	right_rotate(parent[-2],par2);
+	break;
+      }
+    }
+    else
+    {
+      y= par2->left;
+      if (y->colour == RED)
+      {
+	par->colour=BLACK;
+	y->colour=BLACK;
+	leaf=par2;
+	parent-=2;
+	leaf->colour=RED;		/* And the loop continues */
+      }
+      else
+      {
+	if (leaf == par->left)
+	{
+	  right_rotate(parent[-1],par);
+	  par=leaf;
+	}
+	par->colour=BLACK;
+	par2->colour=RED;
+	left_rotate(parent[-2],par2);
+	break;
+      }
+    }
+  }
+  tree->root->colour=BLACK;
+}
+
+static void rb_delete_fixup(TREE *tree, TREE_ELEMENT ***parent)
+{
+  TREE_ELEMENT *x,*w,*par;
+
+  x= **parent;
+  while (x != tree->root && x->colour == BLACK)
+  {
+    if (x == (par=parent[-1][0])->left)
+    {
+      w=par->right;
+      if (w->colour == RED)
+      {
+	w->colour=BLACK;
+	par->colour=RED;
+	left_rotate(parent[-1],par);
+	parent[0]= &w->left;
+	*++parent= &par->left;
+	w=par->right;
+      }
+      if (w->left->colour == BLACK && w->right->colour == BLACK)
+      {
+	w->colour=RED;
+	x=par;
+	parent--;
+      }
+      else
+      {
+	if (w->right->colour == BLACK)
+	{
+	  w->left->colour=BLACK;
+	  w->colour=RED;
+	  right_rotate(&par->right,w);
+	  w=par->right;
+	}
+	w->colour=par->colour;
+	par->colour=BLACK;
+	w->right->colour=BLACK;
+	left_rotate(parent[-1],par);
+	x=tree->root;
+	break;
+      }
+    }
+    else
+    {
+      w=par->left;
+      if (w->colour == RED)
+      {
+	w->colour=BLACK;
+	par->colour=RED;
+	right_rotate(parent[-1],par);
+	parent[0]= &w->right;
+	*++parent= &par->right;
+	w=par->left;
+      }
+      if (w->right->colour == BLACK && w->left->colour == BLACK)
+      {
+	w->colour=RED;
+	x=par;
+	parent--;
+      }
+      else
+      {
+	if (w->left->colour == BLACK)
+	{
+	  w->right->colour=BLACK;
+	  w->colour=RED;
+	  left_rotate(&par->left,w);
+	  w=par->left;
+	}
+	w->colour=par->colour;
+	par->colour=BLACK;
+	w->left->colour=BLACK;
+	right_rotate(parent[-1],par);
+	x=tree->root;
+	break;
+      }
+    }
+  }
+  x->colour=BLACK;
+}
+
+#ifndef DBUG_OFF
+
+	/* Test that the proporties for a red-black tree holds */
+
+static int test_rb_tree(TREE_ELEMENT *element)
+{
+  int count_l,count_r;
+
+  if (!element->left)
+    return 0;				/* Found end of tree */
+  if (element->colour == RED &&
+      (element->left->colour == RED || element->right->colour == RED))
+  {
+    printf("Wrong tree: Found two red in a row\n");
+    return -1;
+  }
+  count_l=test_rb_tree(element->left);
+  count_r=test_rb_tree(element->right);
+  if (count_l >= 0 && count_r >= 0)
+  {
+    if (count_l == count_r)
+      return count_l+(element->colour == BLACK);
+    printf("Wrong tree: Incorrect black-count: %d - %d\n",count_l,count_r);
+  }
+  return -1;
+}
+#endif