Merge mysql.com:/home/svoj/devel/bk/mysql-5.0

into  mysql.com:/home/svoj/devel/mysql/BUG26881/mysql-5.0-engines

3 files changed, 95 insertions, 35 deletions

diff --git a/myisam/rt_index.c b/myisam/rt_index.c
index edb33ec10b9..cf144839dd1 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,18 +627,19 @@ 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)
   {
     if ((old_root = _mi_new(info, keyinfo, DFLT_INIT_HITS)) == HA_OFFSET_ERROR)
-      return -1;
+      DBUG_RETURN(-1);
     info->buff_used = 1;
     mi_putint(info->buff, 2, 0);
     res = rtree_add_key(info, keyinfo, key, key_length, info->buff, NULL);
     if (_mi_write_keypage(info, keyinfo, old_root, DFLT_INIT_HITS, info->buff))
-      return 1;
+      DBUG_RETURN(1);
     info->s->state.key_root[keynr] = old_root;
-    return res;
+    DBUG_RETURN(res);
   }
 
   switch ((res = rtree_insert_req(info, keyinfo, key, key_length, 
@@ -651,11 +656,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);
@@ -681,12 +687,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 */
@@ -694,7 +702,7 @@ err1:
       break;
     }
   }
-  return res;
+  DBUG_RETURN(res);
 }
 
 
@@ -708,8 +716,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);
 }
 
 
@@ -724,6 +734,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;
@@ -735,10 +747,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 */
 }
 
 
@@ -762,15 +774,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);
@@ -791,6 +806,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;
@@ -800,10 +816,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))
@@ -863,11 +892,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 */
 }
 
 
@@ -885,12 +914,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;
@@ -899,12 +931,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;
@@ -923,16 +955,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)
+          {
+            ulong 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,
@@ -959,20 +1009,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 */
     }
   }
 }
diff --git a/myisam/rt_key.c b/myisam/rt_key.c
index cb6a82c51f6..fe59af3c605 100644
--- a/myisam/rt_key.c
+++ b/myisam/rt_key.c
@@ -34,6 +34,7 @@ int rtree_add_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
 {
   uint page_size = mi_getint(page_buf);
   uint nod_flag = mi_test_if_nod(page_buf);
+  DBUG_ENTER("rtree_add_key");
 
   if (page_size + key_length + info->s->base.rec_reflength <=
       keyinfo->block_length)
@@ -42,22 +43,26 @@ int rtree_add_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
     if (nod_flag)
     {
       /* save key */
+      DBUG_ASSERT(_mi_kpos(nod_flag, key) < info->state->key_file_length);
       memcpy(rt_PAGE_END(page_buf), key - nod_flag, key_length + nod_flag); 
       page_size += key_length + nod_flag;
     }
     else
     {
       /* save key */
+      DBUG_ASSERT(_mi_dpos(info, nod_flag, key + key_length +
+                           info->s->base.rec_reflength) <
+                  info->state->data_file_length + info->s->base.pack_reclength);
       memcpy(rt_PAGE_END(page_buf), key, key_length + 
                                          info->s->base.rec_reflength);
       page_size += key_length + info->s->base.rec_reflength;
     }
     mi_putint(page_buf, page_size, nod_flag);
-    return 0;
+    DBUG_RETURN(0);
   }
 
-  return (rtree_split_page(info, keyinfo, page_buf, key, key_length,
-			   new_page) ? -1 : 1);
+  DBUG_RETURN((rtree_split_page(info, keyinfo, page_buf, key, key_length,
+                                new_page) ? -1 : 1));
 }
 
 /*
@@ -89,11 +94,13 @@ int rtree_delete_key(MI_INFO *info, uchar *page_buf, uchar *key,
 int rtree_set_key_mbr(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
 		      uint key_length, my_off_t child_page)
 {
+  DBUG_ENTER("rtree_set_key_mbr");
+
   if (!_mi_fetch_keypage(info, keyinfo, child_page,
                          DFLT_INIT_HITS, info->buff, 0))
-    return -1;
+    DBUG_RETURN(-1); /* purecov: inspected */
 
-  return rtree_page_mbr(info, keyinfo->seg, info->buff, key, key_length);
+  DBUG_RETURN(rtree_page_mbr(info, keyinfo->seg, info->buff, key, key_length));
 }
 
 #endif /*HAVE_RTREE_KEYS*/
diff --git a/myisam/rt_split.c b/myisam/rt_split.c
index 9f25ee608d8..0f6dc872958 100644
--- a/myisam/rt_split.c
+++ b/myisam/rt_split.c
@@ -264,13 +264,15 @@ int rtree_split_page(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page, uchar *key,
   uint full_length= key_length + (nod_flag ? nod_flag : 
                                   info->s->base.rec_reflength);
   int max_keys= (mi_getint(page)-2) / (full_length);
+  DBUG_ENTER("rtree_split_page");
+  DBUG_PRINT("rtree", ("splitting block"));
 
   n_dim = keyinfo->keysegs / 2;
   
   if (!(coord_buf= (double*) my_alloca(n_dim * 2 * sizeof(double) *
                                        (max_keys + 1 + 4) +
                                        sizeof(SplitStruct) * (max_keys + 1))))
-    return -1;
+    DBUG_RETURN(-1); /* purecov: inspected */
 
   task= (SplitStruct *)(coord_buf + n_dim * 2 * (max_keys + 1 + 4));
 
@@ -341,12 +343,13 @@ int rtree_split_page(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page, uchar *key,
   else
     err_code= _mi_write_keypage(info, keyinfo, *new_page_offs,
                                 DFLT_INIT_HITS, new_page);
+  DBUG_PRINT("rtree", ("split new block: %lu", (ulong) *new_page_offs));
 
   my_afree((byte*)new_page);
 
 split_err:
   my_afree((byte*) coord_buf);
-  return err_code;
+  DBUG_RETURN(err_code);
 }
 
 #endif /*HAVE_RTREE_KEYS*/