Merge chilla.local:/home/mydev/mysql-4.1-bug25673

into  chilla.local:/home/mydev/mysql-5.0-bug25673

1 files changed, 75 insertions, 25 deletions

diff --git a/myisam/rt_index.c b/myisam/rt_index.c
index 99080c22644..66e7a698df9 100644
--- a/myisam/rt_index.c
+++ b/myisam/rt_index.c
@@ -184,6 +184,7 @@ int rtree_find_first(MI_INFO *info, uint keynr, uchar *key, uint key_length,
   /*
     Save searched key, include data pointer.
     The data pointer is required if the search_flag contains MBR_DATA.
+    (minimum bounding rectangle)
   */
   memcpy(info->first_mbr_key, key, keyinfo->keylength);
   info->last_rkey_length = key_length;
@@ -538,16 +539,19 @@ static int rtree_insert_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
   uint nod_flag;
   uchar *page_buf;
   int res;
+  DBUG_ENTER("rtree_insert_req");
 
   if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length + 
                                      MI_MAX_KEY_BUFF)))
   {
     my_errno = HA_ERR_OUT_OF_MEM;
-    return -1;
+    DBUG_RETURN(-1); /* purecov: inspected */
   }
   if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
     goto err1;
   nod_flag = mi_test_if_nod(page_buf);
+  DBUG_PRINT("rtree", ("page: %lu  level: %d  ins_level: %d  nod_flag: %u",
+                       (ulong) page, level, ins_level, nod_flag));
 
   if ((ins_level == -1 && nod_flag) ||       /* key: go down to leaf */
       (ins_level > -1 && ins_level > level)) /* branch: go down to ins_level */
@@ -599,11 +603,11 @@ static int rtree_insert_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
 
 ok:
   my_afree((byte*)page_buf);
-  return res;
+  DBUG_RETURN(res);
 
 err1:
   my_afree((byte*)page_buf);
-  return -1;
+  DBUG_RETURN(-1); /* purecov: inspected */
 }
 
 
@@ -623,7 +627,8 @@ static int rtree_insert_level(MI_INFO *info, uint keynr, uchar *key,
   MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
   int res;
   my_off_t new_page;
-  
+  DBUG_ENTER("rtree_insert_level");
+
   if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
   {
     int res;
@@ -653,11 +658,12 @@ static int rtree_insert_level(MI_INFO *info, uint keynr, uchar *key,
       uchar *new_key;
       uint nod_flag = info->s->base.key_reflength;
 
+      DBUG_PRINT("rtree", ("root was split, grow a new root"));
       if (!(new_root_buf = (uchar*)my_alloca((uint)keyinfo->block_length + 
                                              MI_MAX_KEY_BUFF)))
       {
         my_errno = HA_ERR_OUT_OF_MEM;
-        return -1;
+        DBUG_RETURN(-1); /* purecov: inspected */
       }
 
       mi_putint(new_root_buf, 2, nod_flag);
@@ -683,12 +689,14 @@ static int rtree_insert_level(MI_INFO *info, uint keynr, uchar *key,
                             DFLT_INIT_HITS, new_root_buf))
         goto err1;
       info->s->state.key_root[keynr] = new_root;
+      DBUG_PRINT("rtree", ("new root page: %lu  level: %d  nod_flag: %u",
+                           (ulong) new_root, 0, mi_test_if_nod(new_root_buf)));
 
       my_afree((byte*)new_root_buf);
       break;
 err1:
       my_afree((byte*)new_root_buf);
-      return -1;
+      DBUG_RETURN(-1); /* purecov: inspected */
     }
     default:
     case -1: /* error */
@@ -696,7 +704,7 @@ err1:
       break;
     }
   }
-  return res;
+  DBUG_RETURN(res);
 }
 
 
@@ -710,8 +718,10 @@ err1:
 
 int rtree_insert(MI_INFO *info, uint keynr, uchar *key, uint key_length)
 {
-  return (!key_length ||
-	  (rtree_insert_level(info, keynr, key, key_length, -1) == -1)) ? -1 : 0;
+  DBUG_ENTER("rtree_insert");
+  DBUG_RETURN((!key_length ||
+               (rtree_insert_level(info, keynr, key, key_length, -1) == -1)) ?
+              -1 : 0);
 }
 
 
@@ -726,6 +736,8 @@ int rtree_insert(MI_INFO *info, uint keynr, uchar *key, uint key_length)
 static int rtree_fill_reinsert_list(stPageList *ReinsertList, my_off_t page, 
                                     int level)
 {
+  DBUG_ENTER("rtree_fill_reinsert_list");
+  DBUG_PRINT("rtree", ("page: %lu  level: %d", (ulong) page, level));
   if (ReinsertList->n_pages == ReinsertList->m_pages)
   {
     ReinsertList->m_pages += REINSERT_BUFFER_INC;
@@ -737,10 +749,10 @@ static int rtree_fill_reinsert_list(stPageList *ReinsertList, my_off_t page,
   ReinsertList->pages[ReinsertList->n_pages].offs = page;
   ReinsertList->pages[ReinsertList->n_pages].level = level;
   ReinsertList->n_pages++;
-  return 0;
+  DBUG_RETURN(0);
 
 err1:
-  return -1;
+  DBUG_RETURN(-1); /* purecov: inspected */
 }
 
 
@@ -764,15 +776,18 @@ static int rtree_delete_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
   uint nod_flag;
   uchar *page_buf;
   int res;
+  DBUG_ENTER("rtree_delete_req");
 
   if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
   {
     my_errno = HA_ERR_OUT_OF_MEM;
-    return -1;
+    DBUG_RETURN(-1); /* purecov: inspected */
   }
   if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
     goto err1;
   nod_flag = mi_test_if_nod(page_buf);
+  DBUG_PRINT("rtree", ("page: %lu  level: %d  nod_flag: %u",
+                       (ulong) page, level, nod_flag));
 
   k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
   last = rt_PAGE_END(page_buf);
@@ -793,6 +808,7 @@ static int rtree_delete_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
             if (*page_size + key_length >= rt_PAGE_MIN_SIZE(keyinfo->block_length)) 
             { 
               /* OK */
+              /* Calculate a new key value (MBR) for the shrinked block. */
               if (rtree_set_key_mbr(info, keyinfo, k, key_length, 
                                   _mi_kpos(nod_flag, k)))
                 goto err1;
@@ -802,10 +818,23 @@ static int rtree_delete_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
             }
             else
             { 
-              /* too small: delete key & add it descendant to reinsert list */
+              /*
+                Too small: delete key & add it descendant to reinsert list.
+                Store position and level of the block so that it can be
+                accessed later for inserting the remaining keys.
+              */
+              DBUG_PRINT("rtree", ("too small. move block to reinsert list"));
               if (rtree_fill_reinsert_list(ReinsertList, _mi_kpos(nod_flag, k),
                                            level + 1))
                 goto err1;
+              /*
+                Delete the key that references the block. This makes the
+                block disappear from the index. Hence we need to insert
+                its remaining keys later. Note: if the block is a branch
+                block, we do not only remove this block, but the whole
+                subtree. So we need to re-insert its keys on the same
+                level later to reintegrate the subtrees.
+              */
               rtree_delete_key(info, page_buf, k, key_length, nod_flag);
               if (_mi_write_keypage(info, keyinfo, page,
                                     DFLT_INIT_HITS, page_buf))
@@ -865,11 +894,11 @@ static int rtree_delete_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
 
 ok:
   my_afree((byte*)page_buf);
-  return res;
+  DBUG_RETURN(res);
 
 err1:
   my_afree((byte*)page_buf);
-  return -1;
+  DBUG_RETURN(-1); /* purecov: inspected */
 }
 
 
@@ -887,12 +916,15 @@ int rtree_delete(MI_INFO *info, uint keynr, uchar *key, uint key_length)
   stPageList ReinsertList;
   my_off_t old_root;
   MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+  DBUG_ENTER("rtree_delete");
 
   if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
   {
     my_errno= HA_ERR_END_OF_FILE;
-    return -1;
+    DBUG_RETURN(-1); /* purecov: inspected */
   }
+  DBUG_PRINT("rtree", ("starting deletion at root page: %lu",
+                       (ulong) old_root));
 
   ReinsertList.pages = NULL;
   ReinsertList.n_pages = 0;
@@ -901,12 +933,12 @@ int rtree_delete(MI_INFO *info, uint keynr, uchar *key, uint key_length)
   switch (rtree_delete_req(info, keyinfo, key, key_length, old_root, 
                                  &page_size, &ReinsertList, 0))
   {
-    case 2:
+    case 2: /* empty */
     {
       info->s->state.key_root[keynr] = HA_OFFSET_ERROR;
-      return 0;
+      DBUG_RETURN(0);
     }
-    case 0:
+    case 0: /* deleted */
     {
       uint nod_flag;
       ulong i;
@@ -926,16 +958,34 @@ int rtree_delete(MI_INFO *info, uint keynr, uchar *key, uint key_length)
                                DFLT_INIT_HITS, page_buf, 0))
           goto err1;
         nod_flag = mi_test_if_nod(page_buf);
+        DBUG_PRINT("rtree", ("reinserting keys from "
+                             "page: %lu  level: %d  nod_flag: %u",
+                             (ulong) ReinsertList.pages[i].offs,
+                             ReinsertList.pages[i].level, nod_flag));
+
         k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
         last = rt_PAGE_END(page_buf);
         for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
         {
-          if (rtree_insert_level(info, keynr, k, key_length, 
-                                 ReinsertList.pages[i].level) == -1)
+          int res;
+          if ((res= rtree_insert_level(info, keynr, k, key_length,
+                                       ReinsertList.pages[i].level)) == -1)
           {
             my_afree((byte*)page_buf);
             goto err1;
           }
+          if (res)
+          {
+            int j;
+            DBUG_PRINT("rtree", ("root has been split, adjust levels"));
+            for (j= i; j < ReinsertList.n_pages; j++)
+            {
+              ReinsertList.pages[j].level++;
+              DBUG_PRINT("rtree", ("keys from page: %lu  now level: %d",
+                                   (ulong) ReinsertList.pages[i].offs,
+                                   ReinsertList.pages[i].level));
+            }
+          }
         }
         my_afree((byte*)page_buf);
         if (_mi_dispose(info, keyinfo, ReinsertList.pages[i].offs,
@@ -962,20 +1012,20 @@ int rtree_delete(MI_INFO *info, uint keynr, uchar *key, uint key_length)
         info->s->state.key_root[keynr] = new_root;
       }
       info->update= HA_STATE_DELETED;
-      return 0;
+      DBUG_RETURN(0);
 
 err1:
-      return -1;
+      DBUG_RETURN(-1); /* purecov: inspected */
     }
     case 1: /* not found */
     {
       my_errno = HA_ERR_KEY_NOT_FOUND;
-      return -1;
+      DBUG_RETURN(-1); /* purecov: inspected */
     }
     default:
     case -1: /* error */
     {
-      return -1;
+      DBUG_RETURN(-1); /* purecov: inspected */
     }
   }
 }