home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / myisam / mi_delete.c < prev    next >
C/C++ Source or Header  |  2000-09-20  |  25KB  |  784 lines
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.    
  3.    This program is free software; you can redistribute it and/or modify
  4.    it under the terms of the GNU General Public License as published by
  5.    the Free Software Foundation; either version 2 of the License, or
  6.    (at your option) any later version.
  7.    
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.    GNU General Public License for more details.
  12.    
  13.    You should have received a copy of the GNU General Public License
  14.    along with this program; if not, write to the Free Software
  15.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  16.  
  17. /* Remove a row from a MyISAM table */
  18.  
  19. #include "fulltext.h"
  20. #ifdef    __WIN__
  21. #include <errno.h>
  22. #endif
  23.  
  24. static int d_search(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *key,
  25.             uint key_length, my_off_t page, uchar *anc_buff);
  26. static int del(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *key,uchar *anc_buff,
  27.            my_off_t leaf_page,uchar *leaf_buff,uchar *keypos,
  28.            my_off_t next_block,uchar *ret_key);
  29. static int underflow(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *anc_buff,
  30.              my_off_t leaf_page, uchar *leaf_buff,uchar *keypos);
  31. static uint remove_key(MI_KEYDEF *keyinfo,uint nod_flag,uchar *keypos,
  32.                uchar *lastkey,uchar *page_end,
  33.                my_off_t *next_block);
  34.  
  35.  
  36. int mi_delete(MI_INFO *info,const byte *record)
  37. {
  38.   uint i;
  39.   uchar *old_key;
  40.   int save_errno;
  41.   char lastpos[8];
  42.  
  43.   MYISAM_SHARE *share=info->s;
  44.   DBUG_ENTER("mi_delete");
  45.  
  46.     /* Test if record is in datafile */
  47.  
  48.   if (!(info->update & HA_STATE_AKTIV))
  49.   {
  50.     DBUG_RETURN(my_errno=HA_ERR_KEY_NOT_FOUND);    /* No database read */
  51.   }
  52.   if (share->options & HA_OPTION_READ_ONLY_DATA)
  53.   {
  54.     DBUG_RETURN(my_errno=EACCES);
  55.   }
  56.   if (_mi_readinfo(info,F_WRLCK,1))
  57.     DBUG_RETURN(my_errno);
  58.   if (info->s->calc_checksum)
  59.     info->checksum=(*info->s->calc_checksum)(info,record);
  60.   if ((*share->compare_record)(info,record))
  61.     goto err;                /* Error on read-check */
  62.  
  63.   if (_mi_mark_file_changed(info))
  64.     goto err;
  65.  
  66.     /* Remove all keys from the .ISAM file */
  67.  
  68.   old_key=info->lastkey2;
  69.   for (i=0 ; i < share->base.keys ; i++ )
  70.   {
  71.     if (((ulonglong) 1 << i) & info->s->state.key_map)
  72.     {
  73.       info->s->keyinfo[i].version++;
  74.       /* The following code block is for text searching by SerG */
  75.       if (info->s->keyinfo[i].flag & HA_FULLTEXT )
  76.       {
  77.         if (_mi_ft_del(info,i,(char*) old_key,record,info->lastpos))
  78.           goto err;
  79.       }
  80.       else
  81.       {
  82.     uint key_length=_mi_make_key(info,i,old_key,record,info->lastpos);
  83.     if (_mi_ck_delete(info,i,old_key,key_length))
  84.       goto err;
  85.       }
  86.     }
  87.   }
  88.  
  89.   if ((*share->delete_record)(info))
  90.     goto err;                /* Remove record from database */
  91.   info->s->state.checksum-=info->checksum;
  92.  
  93.   info->update= HA_STATE_CHANGED+HA_STATE_DELETED+HA_STATE_ROW_CHANGED;
  94.   info->state->records--;
  95.  
  96.   mi_sizestore(lastpos,info->lastpos);
  97.   myisam_log_command(MI_LOG_DELETE,info,(byte*) lastpos,sizeof(lastpos),0);
  98.   VOID(_mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE));
  99.   allow_break();            /* Allow SIGHUP & SIGINT */
  100.   DBUG_RETURN(0);
  101.  
  102. err:
  103.   save_errno=my_errno;
  104.   mi_sizestore(lastpos,info->lastpos);
  105.   myisam_log_command(MI_LOG_DELETE,info,(byte*) lastpos, sizeof(lastpos),0);
  106.   if (save_errno != HA_ERR_RECORD_CHANGED)
  107.     mi_mark_crashed(info);        /* mark table crashed */
  108.   VOID(_mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE));
  109.   info->update|=HA_STATE_WRITTEN;    /* Buffer changed */
  110.   allow_break();            /* Allow SIGHUP & SIGINT */
  111.   my_errno=save_errno;
  112.   if (save_errno == HA_ERR_KEY_NOT_FOUND)
  113.     my_errno=HA_ERR_CRASHED;
  114.  
  115.   DBUG_RETURN(my_errno);
  116. } /* mi_delete */
  117.  
  118.  
  119.     /* Remove a key from the btree index */
  120.  
  121. int _mi_ck_delete(register MI_INFO *info, uint keynr, uchar *key,
  122.           uint key_length)
  123. {
  124.   int error;
  125.   uint nod_flag;
  126.   my_off_t old_root;
  127.   uchar *root_buff;
  128.   MI_KEYDEF *keyinfo;
  129.   DBUG_ENTER("_mi_ck_delete");
  130.  
  131.   if ((old_root=info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
  132.   {
  133.     DBUG_RETURN(my_errno=HA_ERR_CRASHED);
  134.   }
  135.   keyinfo=info->s->keyinfo+keynr;
  136.   if (!(root_buff= (uchar*) my_alloca((uint) keyinfo->block_length+
  137.                       MI_MAX_KEY_BUFF*2)))
  138.   {
  139.     DBUG_PRINT("error",("Couldn't allocate memory"));
  140.     DBUG_RETURN(my_errno=ENOMEM);
  141.   }
  142.   DBUG_PRINT("info",("root_page: %ld",old_root));
  143.   if (!_mi_fetch_keypage(info,keyinfo,old_root,root_buff,0))
  144.   {
  145.     error= -1;
  146.     goto err;
  147.   }
  148.   if ((error=d_search(info,keyinfo,key,key_length,old_root,root_buff)) >0)
  149.   {
  150.     if (error == 2)
  151.     {
  152.       DBUG_PRINT("test",("Enlarging of root when deleting"));
  153.       error=_mi_enlarge_root(info,keynr,key);
  154.     }
  155.     else /* error == 1 */
  156.     {
  157.       if (mi_getint(root_buff) <= (nod_flag=mi_test_if_nod(root_buff))+3)
  158.       {
  159.     error=0;
  160.     if (nod_flag)
  161.       info->s->state.key_root[keynr]=_mi_kpos(nod_flag,
  162.                           root_buff+2+nod_flag);
  163.     else
  164.       info->s->state.key_root[keynr]= HA_OFFSET_ERROR;
  165.     if (_mi_dispose(info,keyinfo,old_root))
  166.       error= -1;
  167.       }
  168.       else
  169.     error=_mi_write_keypage(info,keyinfo,old_root,root_buff);
  170.     }
  171.   }
  172. err:
  173.   my_afree((gptr) root_buff);
  174.   DBUG_RETURN(error);
  175. } /* _mi_ck_delete */
  176.  
  177.  
  178.     /*
  179.     ** Remove key below key root
  180.     ** Return values:
  181.     ** 1 if there are less buffers;  In this case anc_buff is not saved
  182.     ** 2 if there are more buffers
  183.     ** -1 on errors
  184.     */
  185.  
  186. static int d_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
  187.             uchar *key, uint key_length, my_off_t page,
  188.             uchar *anc_buff)
  189. {
  190.   int flag,ret_value,save_flag;
  191.   uint length,nod_flag;
  192.   my_bool last_key;
  193.   uchar *leaf_buff,*keypos;
  194.   my_off_t leaf_page,next_block;
  195.   uchar lastkey[MI_MAX_KEY_BUFF];
  196.   DBUG_ENTER("d_search");
  197.   DBUG_DUMP("page",(byte*) anc_buff,mi_getint(anc_buff));
  198.  
  199.   flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key,key_length,SEARCH_SAME,
  200.                   &keypos, lastkey, &last_key);
  201.   if (flag == MI_FOUND_WRONG_KEY)
  202.   {
  203.     DBUG_PRINT("error",("Found wrong key"));
  204.     DBUG_RETURN(-1);
  205.   }
  206.   nod_flag=mi_test_if_nod(anc_buff);
  207.  
  208.   leaf_buff=0;
  209.   LINT_INIT(leaf_page);
  210.   if (nod_flag)
  211.   {
  212.     leaf_page=_mi_kpos(nod_flag,keypos);
  213.     if (!(leaf_buff= (uchar*) my_alloca((uint) keyinfo->block_length+
  214.                     MI_MAX_KEY_BUFF*2)))
  215.     {
  216.       DBUG_PRINT("error",("Couldn't allocate memory"));
  217.       my_errno=ENOMEM;
  218.       DBUG_RETURN(-1);
  219.     }
  220.     if (!_mi_fetch_keypage(info,keyinfo,leaf_page,leaf_buff,0))
  221.       goto err;
  222.   }
  223.  
  224.   if (flag != 0)
  225.   {
  226.     if (!nod_flag)
  227.     {
  228.       DBUG_PRINT("error",("Didn't find key"));
  229.       my_errno=HA_ERR_CRASHED;        /* This should newer happend */
  230.       goto err;
  231.     }
  232.     save_flag=0;
  233.     ret_value=d_search(info,keyinfo,key,key_length,leaf_page,leaf_buff);
  234.   }
  235.   else
  236.   {                        /* Found key */
  237.     uint tmp;
  238.     length=mi_getint(anc_buff);
  239.     tmp=remove_key(keyinfo,nod_flag,keypos,lastkey,anc_buff+length,
  240.            &next_block);
  241.     if (tmp == 0)
  242.       DBUG_RETURN(0);
  243.     length-= tmp;
  244.  
  245.     mi_putint(anc_buff,length,nod_flag);
  246.     if (!nod_flag)
  247.     {                        /* On leaf page */
  248.       if (_mi_write_keypage(info,keyinfo,page,anc_buff))
  249.     DBUG_RETURN(-1);
  250.       /* Page will be update later if we return 1 */
  251.       DBUG_RETURN(test(length <= (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
  252.                   (uint) keyinfo->underflow_block_length)));
  253.     }
  254.     save_flag=1;
  255.     ret_value=del(info,keyinfo,key,anc_buff,leaf_page,leaf_buff,keypos,
  256.           next_block,lastkey);
  257.   }
  258.   if (ret_value >0)
  259.   {
  260.     save_flag=1;
  261.     if (ret_value == 1)
  262.       ret_value= underflow(info,keyinfo,anc_buff,leaf_page,leaf_buff,keypos);
  263.     else
  264.     {                /* This happens only with packed keys */
  265.       DBUG_PRINT("test",("Enlarging of key when deleting"));
  266.       if (!_mi_get_last_key(info,keyinfo,anc_buff,lastkey,keypos,&length))
  267.       {
  268.     goto err;
  269.       }
  270.       ret_value=_mi_insert(info,keyinfo,key,anc_buff,keypos,lastkey,
  271.                (uchar*) 0,(uchar*) 0,(my_off_t) 0,(my_bool) 0);
  272.     }
  273.   }
  274.   if (ret_value == 0 && mi_getint(anc_buff) > keyinfo->block_length)
  275.   {
  276.     save_flag=1;
  277.     ret_value=_mi_split_page(info,keyinfo,key,anc_buff,lastkey,0) | 2;
  278.   }
  279.   if (save_flag && ret_value != 1)
  280.     ret_value|=_mi_write_keypage(info,keyinfo,page,anc_buff);
  281.   else
  282.   {
  283.     DBUG_DUMP("page",(byte*) anc_buff,mi_getint(anc_buff));
  284.   }
  285.   my_afree((byte*) leaf_buff);
  286.   DBUG_RETURN(ret_value);
  287. err:
  288.   my_afree((byte*) leaf_buff);
  289.   DBUG_PRINT("exit",("Error: %d",my_errno));
  290.   DBUG_RETURN (-1);
  291. } /* d_search */
  292.  
  293.  
  294.     /* Remove a key that has a page-reference */
  295.  
  296. static int del(register MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *key,
  297.            uchar *anc_buff, my_off_t leaf_page, uchar *leaf_buff,
  298.            uchar *keypos,        /* Pos to where deleted key was */
  299.            my_off_t next_block,
  300.            uchar *ret_key)        /* key before keypos in anc_buff */
  301. {
  302.   int ret_value,length;
  303.   uint a_length,nod_flag,tmp;
  304.   my_off_t next_page;
  305.   uchar keybuff[MI_MAX_KEY_BUFF],*endpos,*next_buff,*key_start, *prev_key;
  306.   MYISAM_SHARE *share=info->s;
  307.   MI_KEY_PARAM s_temp;
  308.   DBUG_ENTER("del");
  309.   DBUG_PRINT("enter",("leaf_page: %ld   keypos: %lx",leaf_page,keypos));
  310.   DBUG_DUMP("leaf_buff",(byte*) leaf_buff,mi_getint(leaf_buff));
  311.  
  312.   endpos=leaf_buff+mi_getint(leaf_buff);
  313.   if (!(key_start=_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
  314.                    &tmp)))
  315.     DBUG_RETURN(-1);
  316.  
  317.   if ((nod_flag=mi_test_if_nod(leaf_buff)))
  318.   {
  319.     next_page= _mi_kpos(nod_flag,endpos);
  320.     if (!(next_buff= (uchar*) my_alloca((uint) keyinfo->block_length+
  321.                     MI_MAX_KEY_BUFF*2)))
  322.       DBUG_RETURN(-1);
  323.     if (!_mi_fetch_keypage(info,keyinfo,next_page,next_buff,0))
  324.       ret_value= -1;
  325.     else
  326.     {
  327.       DBUG_DUMP("next_page",(byte*) next_buff,mi_getint(next_buff));
  328.       if ((ret_value=del(info,keyinfo,key,anc_buff,next_page,next_buff,
  329.              keypos,next_block,ret_key)) >0)
  330.       {
  331.     endpos=leaf_buff+mi_getint(leaf_buff);
  332.     if (ret_value == 1)
  333.     {
  334.       ret_value=underflow(info,keyinfo,leaf_buff,next_page,
  335.                   next_buff,endpos);
  336.       if (ret_value == 0 && mi_getint(leaf_buff) > keyinfo->block_length)
  337.       {
  338.         ret_value=_mi_split_page(info,keyinfo,key,leaf_buff,ret_key,0) | 2;
  339.       }
  340.     }
  341.     else
  342.     {
  343.       DBUG_PRINT("test",("Inserting of key when deleting"));
  344.       if (_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
  345.                 &tmp))
  346.         goto err;
  347.       ret_value=_mi_insert(info,keyinfo,key,leaf_buff,endpos,keybuff,
  348.                    (uchar*) 0,(uchar*) 0,(my_off_t) 0,0);
  349.     }
  350.       }
  351.       if (_mi_write_keypage(info,keyinfo,leaf_page,leaf_buff))
  352.     goto err;
  353.     }
  354.     my_afree((byte*) next_buff);
  355.     DBUG_RETURN(ret_value);
  356.   }
  357.  
  358.     /* Remove last key from leaf page */
  359.  
  360.   mi_putint(leaf_buff,key_start-leaf_buff,nod_flag);
  361.   if (_mi_write_keypage(info,keyinfo,leaf_page,leaf_buff))
  362.     goto err;
  363.  
  364.     /* Place last key in ancestor page on deleted key position */
  365.  
  366.   a_length=mi_getint(anc_buff);
  367.   endpos=anc_buff+a_length;
  368.   if (keypos != anc_buff+2+share->base.key_reflength &&
  369.       !_mi_get_last_key(info,keyinfo,anc_buff,ret_key,keypos,&tmp))
  370.     goto err;
  371.   prev_key=(keypos == anc_buff+2+share->base.key_reflength ?
  372.         0 : ret_key);
  373.   length=(*keyinfo->pack_key)(keyinfo,share->base.key_reflength,
  374.                   keypos == endpos ? (uchar*) 0 : keypos,
  375.                   prev_key, prev_key,
  376.                   keybuff,&s_temp);
  377.   if (length > 0)
  378.     bmove_upp((byte*) endpos+length,(byte*) endpos,(uint) (endpos-keypos));
  379.   else
  380.     bmove(keypos,keypos-length, (int) (endpos-keypos)+length);
  381.   (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
  382.   /* Save pointer to next leaf */
  383.   if (!(*keyinfo->get_key)(keyinfo,share->base.key_reflength,&keypos,ret_key))
  384.     goto err;
  385.   _mi_kpointer(info,keypos - share->base.key_reflength,next_block);
  386.   mi_putint(anc_buff,a_length+length,share->base.key_reflength);
  387.  
  388.   DBUG_RETURN( mi_getint(leaf_buff) <=
  389.            (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
  390.         (uint) keyinfo->underflow_block_length));
  391. err:
  392.   DBUG_RETURN(-1);
  393. } /* del */
  394.  
  395.  
  396.     /* Balances adjacent pages if underflow occours */
  397.  
  398. static int underflow(register MI_INFO *info, register MI_KEYDEF *keyinfo,
  399.              uchar *anc_buff,
  400.              my_off_t leaf_page,/* Ancestor page and underflow page */
  401.              uchar *leaf_buff,
  402.              uchar *keypos)    /* Position to pos after key */
  403. {
  404.   int t_length;
  405.   uint length,anc_length,buff_length,leaf_length,p_length,s_length,nod_flag,
  406.        key_reflength,key_length;
  407.   my_off_t next_page;
  408.   uchar anc_key[MI_MAX_KEY_BUFF],leaf_key[MI_MAX_KEY_BUFF],
  409.         *buff,*endpos,*next_keypos,*anc_pos,*half_pos,*temp_pos,*prev_key,
  410.         *after_key;
  411.   MI_KEY_PARAM s_temp;
  412.   MYISAM_SHARE *share=info->s;
  413.   DBUG_ENTER("underflow");
  414.   DBUG_PRINT("enter",("leaf_page: %ld   keypos: %lx",(long) leaf_page,keypos));
  415.   DBUG_DUMP("anc_buff",(byte*) anc_buff,mi_getint(anc_buff));
  416.   DBUG_DUMP("leaf_buff",(byte*) leaf_buff,mi_getint(leaf_buff));
  417.  
  418.   buff=info->buff;
  419.   info->buff_used=1;
  420.   next_keypos=keypos;
  421.   nod_flag=mi_test_if_nod(leaf_buff);
  422.   p_length=nod_flag+2;
  423.   anc_length=mi_getint(anc_buff);
  424.   leaf_length=mi_getint(leaf_buff);
  425.   key_reflength=share->base.key_reflength;
  426.   if (info->s->keyinfo+info->lastinx == keyinfo)
  427.     info->page_changed=1;
  428.  
  429.   if ((keypos < anc_buff+anc_length && (share->rnd++ & 1)) ||
  430.       keypos == anc_buff+2+key_reflength)
  431.   {                    /* Use page right of anc-page */
  432.     DBUG_PRINT("test",("use right page"));
  433.  
  434.     if (keyinfo->flag & HA_BINARY_PACK_KEY)
  435.     {
  436.       if (!(next_keypos=_mi_get_key(info, keyinfo,
  437.                     anc_buff, buff, keypos, &length)))
  438.     goto err;
  439.     }
  440.     else
  441.     {
  442.       /* Got to end of found key */
  443.       buff[0]=buff[1]=0;    /* Avoid length error check if packed key */
  444.       if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
  445.                    buff))
  446.       goto err;
  447.     }
  448.     next_page= _mi_kpos(key_reflength,next_keypos);
  449.     if (!_mi_fetch_keypage(info,keyinfo,next_page,buff,0))
  450.       goto err;
  451.     buff_length=mi_getint(buff);
  452.     DBUG_DUMP("next",(byte*) buff,buff_length);
  453.  
  454.     /* find keys to make a big key-page */
  455.     bmove((byte*) next_keypos-key_reflength,(byte*) buff+2,
  456.       key_reflength);
  457.     if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_key,next_keypos,&length)
  458.     || !_mi_get_last_key(info,keyinfo,leaf_buff,leaf_key,
  459.                  leaf_buff+leaf_length,&length))
  460.       goto err;
  461.  
  462.     /* merge pages and put parting key from anc_buff between */
  463.     prev_key=(leaf_length == p_length ? (uchar*) 0 : leaf_key);
  464.     t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,buff+p_length,
  465.                   prev_key, prev_key,
  466.                   anc_key, &s_temp);
  467.     length=buff_length-p_length;
  468.     endpos=buff+length+leaf_length+t_length;
  469.     /* buff will always be larger than before !*/
  470.     bmove_upp((byte*) endpos, (byte*) buff+buff_length,length);
  471.     memcpy((byte*) buff, (byte*) leaf_buff,(size_t) leaf_length);
  472.     (*keyinfo->store_key)(keyinfo,buff+leaf_length,&s_temp);
  473.     buff_length=(uint) (endpos-buff);
  474.     mi_putint(buff,buff_length,nod_flag);
  475.  
  476.     /* remove key from anc_buff */
  477.  
  478.     s_length=remove_key(keyinfo,key_reflength,keypos,anc_key,
  479.             anc_buff+anc_length,(my_off_t *) 0);
  480.     if (!s_length)
  481.       goto err;
  482.     anc_length-=s_length;
  483.     mi_putint(anc_buff,anc_length,key_reflength);
  484.  
  485.     if (buff_length <= keyinfo->block_length)
  486.     {                        /* Keys in one page */
  487.       memcpy((byte*) leaf_buff,(byte*) buff,(size_t) buff_length);
  488.       if (_mi_dispose(info,keyinfo,next_page))
  489.        goto err;
  490.     }
  491.     else
  492.     {                        /* Page is full */
  493.       endpos=anc_buff+anc_length;
  494.       DBUG_PRINT("test",("anc_buff: %lx  endpos: %lx",anc_buff,endpos));
  495.       if (keypos != anc_buff+2+key_reflength &&
  496.       !_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length))
  497.     goto err;
  498.       if (!(half_pos=_mi_find_half_pos(nod_flag, keyinfo, buff, leaf_key,
  499.                        &key_length, &after_key)))
  500.     goto err;
  501.       length=(uint) (half_pos-buff);
  502.       memcpy((byte*) leaf_buff,(byte*) buff,(size_t) length);
  503.       mi_putint(leaf_buff,length,nod_flag);
  504.  
  505.       /* Correct new keypointer to leaf_page */
  506.       half_pos=after_key;
  507.       _mi_kpointer(info,leaf_key+key_length,next_page);
  508.       /* Save key in anc_buff */
  509.       prev_key=(keypos == anc_buff+2+key_reflength ? (uchar*) 0 : anc_key),
  510.       t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
  511.                     (keypos == endpos ? (uchar*) 0 :
  512.                      keypos),
  513.                     prev_key, prev_key,
  514.                     leaf_key, &s_temp);
  515.       if (t_length >= 0)
  516.     bmove_upp((byte*) endpos+t_length,(byte*) endpos,
  517.           (uint) (endpos-keypos));
  518.       else
  519.     bmove(keypos,keypos-t_length,(uint) (endpos-keypos)+t_length);
  520.       (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
  521.       mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
  522.  
  523.     /* Store key first in new page */
  524.       if (nod_flag)
  525.     bmove((byte*) buff+2,(byte*) half_pos-nod_flag,(size_t) nod_flag);
  526.       if (!(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key))
  527.     goto err;
  528.       t_length=(int) (*keyinfo->pack_key)(keyinfo, nod_flag, (uchar*) 0,
  529.                       (uchar*) 0, (uchar *) 0,
  530.                       leaf_key, &s_temp);
  531.       /* t_length will always be > 0 for a new page !*/
  532.       length=(uint) ((buff+mi_getint(buff))-half_pos);
  533.       bmove((byte*) buff+p_length+t_length,(byte*) half_pos,(size_t) length);
  534.       (*keyinfo->store_key)(keyinfo,buff+p_length,&s_temp);
  535.       mi_putint(buff,length+t_length+p_length,nod_flag);
  536.  
  537.       if (_mi_write_keypage(info,keyinfo,next_page,buff))
  538.     goto err;
  539.     }
  540.     if (_mi_write_keypage(info,keyinfo,leaf_page,leaf_buff))
  541.       goto err;
  542.     DBUG_RETURN(anc_length <= ((info->quick_mode ? MI_MIN_BLOCK_LENGTH :
  543.                 (uint) keyinfo->underflow_block_length)));
  544.   }
  545.  
  546.   DBUG_PRINT("test",("use left page"));
  547.  
  548.   keypos=_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length);
  549.   if (!keypos)
  550.     goto err;
  551.   next_page= _mi_kpos(key_reflength,keypos);
  552.   if (!_mi_fetch_keypage(info,keyinfo,next_page,buff,0))
  553.       goto err;
  554.   buff_length=mi_getint(buff);
  555.   endpos=buff+buff_length;
  556.   DBUG_DUMP("prev",(byte*) buff,buff_length);
  557.  
  558.   /* find keys to make a big key-page */
  559.   bmove((byte*) next_keypos - key_reflength,(byte*) leaf_buff+2,
  560.     key_reflength);
  561.   next_keypos=keypos;
  562.   if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
  563.                anc_key))
  564.     goto err;
  565.   if (!_mi_get_last_key(info,keyinfo,buff,leaf_key,endpos,&length))
  566.     goto err;
  567.  
  568.   /* merge pages and put parting key from anc_buff between */
  569.   prev_key=(leaf_length == p_length ? (uchar*) 0 : leaf_key);
  570.   t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,
  571.                 (leaf_length == p_length ?
  572.                                  (uchar*) 0 : leaf_buff+p_length),
  573.                 prev_key, prev_key,
  574.                 anc_key, &s_temp);
  575.   if (t_length >= 0)
  576.     bmove((byte*) endpos+t_length,(byte*) leaf_buff+p_length,
  577.         (size_t) (leaf_length-p_length));
  578.   else                        /* We gained space */
  579.     bmove((byte*) endpos,(byte*) leaf_buff+((int) p_length-t_length),
  580.       (size_t) (leaf_length-p_length+t_length));
  581.  
  582.   (*keyinfo->store_key)(keyinfo,endpos,&s_temp);
  583.   buff_length=buff_length+leaf_length-p_length+t_length;
  584.   mi_putint(buff,buff_length,nod_flag);
  585.  
  586.   /* remove key from anc_buff */
  587.   s_length=remove_key(keyinfo,key_reflength,keypos,anc_key,
  588.               anc_buff+anc_length,(my_off_t *) 0);
  589.   if (!s_length)
  590.     goto err;
  591.   anc_length-=s_length;
  592.   mi_putint(anc_buff,anc_length,key_reflength);
  593.  
  594.   if (buff_length <= keyinfo->block_length)
  595.   {                        /* Keys in one page */
  596.     if (_mi_dispose(info,keyinfo,leaf_page))
  597.       goto err;
  598.   }
  599.   else
  600.   {                        /* Page is full */
  601.     if (keypos == anc_buff+2+key_reflength)
  602.       anc_pos=0;                /* First key */
  603.     else if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_pos=anc_key,keypos,
  604.                    &length))
  605.       goto err;
  606.     endpos=_mi_find_half_pos(nod_flag,keyinfo,buff,leaf_key,
  607.                  &key_length, &half_pos);
  608.     if (!endpos)
  609.       goto err;
  610.     _mi_kpointer(info,leaf_key+key_length,leaf_page);
  611.     /* Save key in anc_buff */
  612.     DBUG_DUMP("anc_buff",(byte*) anc_buff,anc_length);
  613.     DBUG_DUMP("key_to_anc",(byte*) leaf_key,key_length);
  614.  
  615.     temp_pos=anc_buff+anc_length;
  616.     t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
  617.                   keypos == temp_pos ? (uchar*) 0
  618.                   : keypos,
  619.                   anc_pos, anc_pos,
  620.                   leaf_key,&s_temp);
  621.     if (t_length > 0)
  622.       bmove_upp((byte*) temp_pos+t_length,(byte*) temp_pos,
  623.         (uint) (temp_pos-keypos));
  624.     else
  625.       bmove(keypos,keypos-t_length,(uint) (temp_pos-keypos)+t_length);
  626.     (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
  627.     mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
  628.  
  629.     /* Store first key on new page */
  630.     if (nod_flag)
  631.       bmove((byte*) leaf_buff+2,(byte*) half_pos-nod_flag,(size_t) nod_flag);
  632.     if (!(length=(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key)))
  633.       goto err;
  634.     DBUG_DUMP("key_to_leaf",(byte*) leaf_key,length);
  635.     t_length=(*keyinfo->pack_key)(keyinfo,nod_flag, (uchar*) 0,
  636.                   (uchar*) 0, (uchar*) 0, leaf_key, &s_temp);
  637.     length=(uint) ((buff+buff_length)-half_pos);
  638.     DBUG_PRINT("info",("t_length: %d  length: %d",t_length,(int) length));
  639.     bmove((byte*) leaf_buff+p_length+t_length,(byte*) half_pos,
  640.       (size_t) length);
  641.     (*keyinfo->store_key)(keyinfo,leaf_buff+p_length,&s_temp);
  642.     mi_putint(leaf_buff,length+t_length+p_length,nod_flag);
  643.     if (_mi_write_keypage(info,keyinfo,leaf_page,leaf_buff))
  644.       goto err;
  645.     mi_putint(buff,endpos-buff,nod_flag);
  646.   }
  647.   if (_mi_write_keypage(info,keyinfo,next_page,buff))
  648.     goto err;
  649.   DBUG_RETURN(anc_length <= (uint) keyinfo->block_length/2);
  650. err:
  651.   DBUG_RETURN(-1);
  652. } /* underflow */
  653.  
  654.  
  655.     /*
  656.       remove a key from packed buffert
  657.       The current code doesn't handle the case that the next key may be
  658.       packed better against the previous key if there is a case difference
  659.       returns how many chars was removed or 0 on error
  660.     */
  661.  
  662. static uint remove_key(MI_KEYDEF *keyinfo, uint nod_flag,
  663.                uchar *keypos,    /* Where key starts */
  664.                uchar *lastkey,    /* key to be removed */
  665.                uchar *page_end, /* End of page */
  666.                my_off_t *next_block)    /* ptr to next block */
  667. {
  668.   int s_length;
  669.   uchar *start;
  670.   DBUG_ENTER("remove_key");
  671.   DBUG_PRINT("enter",("keypos: %lx  page_end: %lx",keypos,page_end));
  672.  
  673.   start=keypos;
  674.   if (!(keyinfo->flag &
  675.     (HA_PACK_KEY | HA_SPACE_PACK_USED | HA_VAR_LENGTH_KEY |
  676.      HA_BINARY_PACK_KEY)))
  677.   {
  678.     s_length=(int) (keyinfo->keylength+nod_flag);
  679.     if (next_block && nod_flag)
  680.       *next_block= _mi_kpos(nod_flag,keypos+s_length);
  681.   }
  682.   else
  683.   {                     /* Let keypos point at next key */
  684.     /* Calculate length of key */
  685.     if (!(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey))
  686.       DBUG_RETURN(0);                /* Error */
  687.     if (next_block && nod_flag)
  688.       *next_block= _mi_kpos(nod_flag,keypos);
  689.     s_length=(int) (keypos-start);
  690.     if (keypos != page_end)
  691.     {
  692.       if (keyinfo->flag & HA_BINARY_PACK_KEY)
  693.       {
  694.     uchar *old_key=start;
  695.     uint next_length,prev_length,prev_pack_length;
  696.     get_key_length(next_length,keypos);
  697.     get_key_pack_length(prev_length,prev_pack_length,old_key);
  698.     if (next_length > prev_length)
  699.     {
  700.       /* We have to copy data from the current key to the next key */
  701.       bmove_upp((char*) keypos,(char*) (lastkey+next_length),
  702.             (next_length-prev_length));
  703.       keypos-=(next_length-prev_length)+prev_pack_length;
  704.       store_key_length(keypos,prev_length);
  705.       s_length=(int) (keypos-start);
  706.     }
  707.       }
  708.       else
  709.       {
  710.     /* A variable length first key part */
  711.     if (*keypos & 128)            /* Next key is packed */
  712.     {
  713.       uint next_length,prev_length,prev_pack_length,lastkey_length,
  714.         rest_length;
  715.       if (keyinfo->seg[0].length >= 127)
  716.       {
  717.         if (!(prev_length=mi_uint2korr(start) & 32767))
  718.           goto end;
  719.         next_length=mi_uint2korr(keypos) & 32767;
  720.         keypos+=2;
  721.         prev_pack_length=2;
  722.       }
  723.       else
  724.       {
  725.         if (!(prev_length= *start & 127))
  726.           goto end;                /* Same key as previous*/
  727.         next_length= *keypos & 127;
  728.         keypos++;
  729.         prev_pack_length=1;
  730.       }
  731.       if (!(*start & 128))
  732.         prev_length=0;            /* prev key not packed */
  733.       if (keyinfo->seg[0].flag & HA_NULL_PART)
  734.         lastkey++;                /* Skipp null marker */
  735.       get_key_length(lastkey_length,lastkey);
  736.       if (!next_length)            /* Same key after */
  737.       {
  738.         next_length=lastkey_length;
  739.         rest_length=0;
  740.       }
  741.       else
  742.         get_key_length(rest_length,keypos);
  743.  
  744.       if (next_length > prev_length)
  745.       {        /* Key after is based on deleted key */
  746.         uint pack_length,tmp;
  747.         bmove_upp((char*) keypos,(char*) (lastkey+next_length),
  748.               tmp=(next_length-prev_length));
  749.         rest_length+=tmp;
  750.         pack_length= prev_length ? get_pack_length(rest_length): 0;
  751.         keypos-=tmp+pack_length+prev_pack_length;
  752.         s_length=(int) (keypos-start);
  753.         if (prev_length)            /* Pack against prev key */
  754.         {
  755.           *keypos++= start[0];
  756.           if (prev_pack_length == 2)
  757.         *keypos++= start[1];
  758.           store_key_length(keypos,rest_length);
  759.         }
  760.         else
  761.         {
  762.           /* Next key is not packed anymore */
  763.           if (keyinfo->seg[0].flag & HA_NULL_PART)
  764.           {
  765.         rest_length++;            /* Mark not null */
  766.           }
  767.           if (prev_pack_length == 2)
  768.           {
  769.         mi_int2store(keypos,rest_length);
  770.           }
  771.           else
  772.         *keypos= rest_length;
  773.         }
  774.       }
  775.     }
  776.       }
  777.     }
  778.   }
  779.   end:
  780.   bmove((byte*) start,(byte*) start+s_length,
  781.     (uint) (page_end-start-s_length));
  782.   DBUG_RETURN((uint) s_length);
  783. } /* remove_key */
  784.