merged

BitKeeper/etc/logging_ok:
  auto-union
configure.in:
  Auto merged
libmysqld/Makefile.am:
  Auto merged
myisam/Makefile.am:
  Auto merged
myisam/mi_check.c:
  Auto merged
myisam/myisampack.c:
  Auto merged
mysql-test/r/fulltext.result:
  Auto merged
mysys/Makefile.am:
  Auto merged
sql/Makefile.am:
  Auto merged
sql/sql_delete.cc:
  Auto merged
sql/sql_update.cc:
  Auto merged
strings/Makefile.am:
  Auto merged

1 files changed, 195 insertions, 20 deletions

diff --git a/mysys/tree.c b/mysys/tree.c
index 2ac2c88fd66..f72a4961312 100644
--- a/mysys/tree.c
+++ b/mysys/tree.c
@@ -17,31 +17,39 @@
 /*
   Code for handling red-black (balanced) binary trees.
   key in tree is allocated accrding to following:
-  1) If free_element function is given to init_tree or size < 0 then tree
-     will not allocate keys and only a pointer to each key is saved in tree.
-     key_sizes must be 0 to init and search.
+
+  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.
-  2) if key_size is given to init_tree then each node will continue the
+
+  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
      allign) then key will be put on a 8 alligned adress. Else
      the key will be on adress (element+1). This is transparent for user
      compare and search functions uses a pointer to given key-argument.
-  3) If init_tree - keysize is 0 then key_size must be given to tree_insert
-     and tree_insert will alloc space for key.
-     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.
-  Copyright Monty Program KB.
-  By monty.
+
+  Implemented by monty.
 */
 
 #include "mysys_priv.h"
 #include <m_string.h>
 #include <my_tree.h>
+#include "my_base.h"
 
 #define BLACK		1
 #define RED		0
@@ -85,6 +93,7 @@ void init_tree(TREE *tree, uint default_alloc_size, uint memory_limit,
   tree->custom_arg = custom_arg;
   tree->null_element.colour=BLACK;
   tree->null_element.left=tree->null_element.right=0;
+  tree->flag= 0;
   if (!free_element && size >= 0 &&
       ((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1))))
   {
@@ -167,7 +176,8 @@ static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
 	     parent[0] = & parent[-1][0]->right */
 
 
-TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
+TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size, 
+                          void* custom_arg)
 {
   int cmp;
   TREE_ELEMENT *element,***parent;
@@ -177,8 +187,8 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
   for (;;)
   {
     if (element == &tree->null_element ||
-	(cmp=(*tree->compare)(tree->custom_arg,
-			      ELEMENT_KEY(tree,element),key)) == 0)
+	(cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
       break;
     if (cmp < 0)
     {
@@ -198,7 +208,7 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
                            && tree->allocated > tree->memory_limit)
     {
       reset_tree(tree);
-      return tree_insert(tree, key, key_size);
+      return tree_insert(tree, key, key_size, custom_arg);
     }
 
     key_size+=tree->size_of_element;
@@ -229,13 +239,16 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
     rb_insert(tree,parent,element);		/* rebalance tree */
   }
   else
+  {
+    if (tree->flag & TREE_NO_DUPS)
+      return(NULL);
     element->count++;
+  }
   DBUG_EXECUTE("check_tree", test_rb_tree(tree->root););
   return element;
 }
 
-
-int tree_delete(TREE *tree, void *key)
+int tree_delete(TREE *tree, void *key, void *custom_arg)
 {
   int cmp,remove_colour;
   TREE_ELEMENT *element,***parent, ***org_parent, *nod;
@@ -248,8 +261,8 @@ int tree_delete(TREE *tree, void *key)
   {
     if (element == &tree->null_element)
       return 1;				/* Was not in tree */
-    if ((cmp=(*tree->compare)(tree->custom_arg,
-			      ELEMENT_KEY(tree,element),key)) == 0)
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
       break;
     if (cmp < 0)
     {
@@ -296,7 +309,7 @@ int tree_delete(TREE *tree, void *key)
 }
 
 
-void *tree_search(TREE *tree, void *key)
+void *tree_search(TREE *tree, void *key, void *custom_arg)
 {
   int cmp;
   TREE_ELEMENT *element=tree->root;
@@ -305,8 +318,8 @@ void *tree_search(TREE *tree, void *key)
   {
     if (element == &tree->null_element)
       return (void*) 0;
-    if ((cmp=(*tree->compare)(tree->custom_arg,
-			      ELEMENT_KEY(tree,element),key)) == 0)
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
       return ELEMENT_KEY(tree,element);
     if (cmp < 0)
       element=element->right;
@@ -315,6 +328,168 @@ void *tree_search(TREE *tree, void *key)
   }
 }
 
+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;
+  TREE_ELEMENT **last_equal_element = NULL;
+
+/* 
+  TODO: handle HA_READ_KEY_OR_PREV, HA_READ_BEFORE_KEY, HA_READ_PREFIX, 
+  HA_READ_PREFIX_LAST flags if needed.
+*/
+
+  *parents = &tree->null_element;
+  while (element != &tree->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:
+        last_equal_element = parents;
+        cmp = 1;
+        break;
+      case HA_READ_AFTER_KEY:
+        cmp = -1;
+        break;
+      default:
+        return NULL;
+      }
+    }
+    if (cmp < 0) /* element < key */
+    {
+      element = element->right;
+    }
+    else
+    {
+      last_left_step_parent = parents;
+      element = element->left;
+    }
+  }
+  switch (flag) {
+  case HA_READ_KEY_EXACT:
+    *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;
+  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= &tree->null_element;
+  while (element != &tree->null_element)
+  {
+    *++parents= element;
+    element= ELEMENT_CHILD(element, child_offs);
+  }
+  *last_pos= parents;
+  return **last_pos != &tree->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) != &tree->null_element)
+  {
+    x= ELEMENT_CHILD(x, r_offs);
+    *++*last_pos= x;
+    while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
+    {
+      x= ELEMENT_CHILD(x, l_offs);
+      *++*last_pos= x;
+    }
+    return ELEMENT_KEY(tree, x);
+  }
+  else
+  {
+    TREE_ELEMENT *y= *--*last_pos;
+    while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
+    {
+      x= y;
+      y= *--*last_pos;
+    }
+    return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
+  }
+}
+
+/*
+  Expected that tree is fully balanced
+  (each path from root to leaf has the same length)
+*/
+uint 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;
+  uint last_equal_pos= HA_POS_ERROR;
+
+  while (element != &tree->null_element)
+  {
+    if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
+			       key)) == 0)
+    {
+      switch (flag) {
+      case HA_READ_KEY_EXACT:
+        last_equal_pos= (left + right) / 2;
+        cmp= 1;
+        break;
+      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:
+    return last_equal_pos;
+  case HA_READ_BEFORE_KEY:
+    return (uint) right;
+  case HA_READ_AFTER_KEY:
+    return (uint) left;
+  default:
+    return HA_POS_ERROR;
+  }
+}
 
 int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
 {