home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / isam / delete.c < prev    next >
C/C++ Source or Header  |  2000-08-31  |  21KB  |  618 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. /* Tar bort ett record fr}n en isam-databas */
  18.  
  19. #include "isamdef.h"
  20. #ifdef    __WIN__
  21. #include <errno.h>
  22. #endif
  23. #include <assert.h>
  24.  
  25. static int d_search(N_INFO *info,N_KEYDEF *keyinfo,uchar *key,ulong page,
  26.             uchar *anc_buff);
  27. static int del(N_INFO *info,N_KEYDEF *keyinfo,uchar *key,uchar *anc_buff,
  28.            ulong leaf_page,uchar *leaf_buff,uchar *keypos,
  29.            ulong next_block,uchar *ret_key);
  30. static int underflow(N_INFO *info,N_KEYDEF *keyinfo,uchar *anc_buff,
  31.              ulong leaf_page, uchar *leaf_buff,uchar *keypos);
  32. static uint remove_key(N_KEYDEF *keyinfo,uint nod_flag,uchar *keypos,
  33.                uchar *lastkey,uchar *page_end);
  34.  
  35.  
  36. int nisam_delete(N_INFO *info,const byte *record)
  37. {
  38.   uint i;
  39.   uchar *old_key;
  40.   int save_errno;
  41.   uint32 lastpos;
  42.   ISAM_SHARE *share=info->s;
  43.   DBUG_ENTER("nisam_delete");
  44.  
  45.     /* Test if record is in datafile */
  46.  
  47.   if (!(info->update & HA_STATE_AKTIV))
  48.   {
  49.     my_errno=HA_ERR_KEY_NOT_FOUND;        /* No database read */
  50.     DBUG_RETURN(-1);
  51.   }
  52.   if (share->base.options & HA_OPTION_READ_ONLY_DATA)
  53.   {
  54.     my_errno=EACCES;
  55.     DBUG_RETURN(-1);
  56.   }
  57. #ifndef NO_LOCKING
  58.   if (_nisam_readinfo(info,F_WRLCK,1)) DBUG_RETURN(-1);
  59. #endif
  60.   if ((*share->compare_record)(info,record))
  61.     goto err;                /* Fel vid kontroll-l{sning */
  62.  
  63.     /* Remove all keys from the .ISAM file */
  64.  
  65.   old_key=info->lastkey+share->base.max_key_length;
  66.   for (i=0 ; i < share->state.keys ; i++ )
  67.   {
  68.     VOID(_nisam_make_key(info,i,old_key,record,info->lastpos));
  69.     if (_nisam_ck_delete(info,i,old_key)) goto err;
  70.   }
  71.  
  72.   if ((*share->delete_record)(info))
  73.     goto err;                /* Remove record from database */
  74.  
  75.   info->update= HA_STATE_CHANGED | HA_STATE_ROW_CHANGED | HA_STATE_DELETED;
  76.   share->state.records--;
  77.  
  78.   lastpos= (uint32) info->lastpos;
  79.   nisam_log_command(LOG_DELETE,info,(byte*) &lastpos,sizeof(lastpos),0);
  80.   VOID(_nisam_writeinfo(info,1));
  81.   allow_break();            /* Allow SIGHUP & SIGINT */
  82.   DBUG_RETURN(0);
  83.  
  84. err:
  85.   save_errno=my_errno;
  86.   lastpos= (uint32) info->lastpos;
  87.   nisam_log_command(LOG_DELETE,info,(byte*) &lastpos, sizeof(lastpos),0);
  88.   VOID(_nisam_writeinfo(info,1));
  89.   info->update|=HA_STATE_WRITTEN;    /* Buffer changed */
  90.   allow_break();            /* Allow SIGHUP & SIGINT */
  91.   my_errno=save_errno;
  92.   if (save_errno == HA_ERR_KEY_NOT_FOUND)
  93.     my_errno=HA_ERR_CRASHED;
  94.  
  95.   DBUG_RETURN(-1);
  96. } /* nisam_delete */
  97.  
  98.  
  99.     /* Tar bort en nyckel till isam-nyckelfilen */
  100.  
  101. int _nisam_ck_delete(register N_INFO *info, uint keynr, uchar *key)
  102. {
  103.   int error;
  104.   uint nod_flag;
  105.   ulong old_root;
  106.   uchar *root_buff;
  107.   N_KEYDEF *keyinfo;
  108.   DBUG_ENTER("_nisam_ck_delete");
  109.  
  110.   if ((old_root=info->s->state.key_root[keynr]) == NI_POS_ERROR)
  111.   {
  112.     my_errno=HA_ERR_CRASHED;
  113.     DBUG_RETURN(-1);
  114.   }
  115.   keyinfo=info->s->keyinfo+keynr;
  116.   if (!(root_buff= (uchar*) my_alloca((uint) keyinfo->base.block_length+
  117.                       N_MAX_KEY_BUFF*2)))
  118.     DBUG_RETURN(-1);
  119.   if (!_nisam_fetch_keypage(info,keyinfo,old_root,root_buff,0))
  120.   {
  121.     error= -1;
  122.     goto err;
  123.   }
  124.   if ((error=d_search(info,keyinfo,key,old_root,root_buff)) >0)
  125.   {
  126.     if (error == 2)
  127.     {
  128.       DBUG_PRINT("test",("Enlarging of root when deleting"));
  129.       error=_nisam_enlarge_root(info,keynr,key);
  130.     }
  131.     else
  132.     {
  133.       error=0;
  134.       if (getint(root_buff) <= (nod_flag=test_if_nod(root_buff))+3)
  135.       {
  136.     if (nod_flag)
  137.       info->s->state.key_root[keynr]=_nisam_kpos(nod_flag,
  138.                            root_buff+2+nod_flag);
  139.     else
  140.       info->s->state.key_root[keynr]= NI_POS_ERROR;
  141.     if (_nisam_dispose(info,keyinfo,old_root))
  142.       error= -1;
  143.       }
  144.     }
  145.   }
  146. err:
  147.   my_afree((gptr) root_buff);
  148.   DBUG_RETURN(error);
  149. } /* _nisam_ck_delete */
  150.  
  151.  
  152.     /* Tar bort en nyckel under root */
  153.     /* Returnerar 1 om nuvarande buffert minskade */
  154.     /* Returnerar 2 om nuvarande buffert |kar */
  155.  
  156. static int d_search(register N_INFO *info, register N_KEYDEF *keyinfo, uchar *key, ulong page, uchar *anc_buff)
  157. {
  158.   int flag,ret_value,save_flag;
  159.   uint length,nod_flag;
  160.   uchar *leaf_buff,*keypos,*next_keypos;
  161.   ulong leaf_page,next_block;
  162.   uchar lastkey[N_MAX_KEY_BUFF];
  163.   DBUG_ENTER("d_search");
  164.   DBUG_DUMP("page",(byte*) anc_buff,getint(anc_buff));
  165.  
  166.   flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key,0,SEARCH_SAME,&keypos,
  167.                   lastkey);
  168.   nod_flag=test_if_nod(anc_buff);
  169.  
  170.   leaf_buff=0;
  171.   LINT_INIT(leaf_page);
  172.   if (nod_flag)
  173.   {
  174.     leaf_page=_nisam_kpos(nod_flag,keypos);
  175.     if (!(leaf_buff= (uchar*) my_alloca((uint) keyinfo->base.block_length+
  176.                     N_MAX_KEY_BUFF*2)))
  177.     {
  178.       my_errno=ENOMEM;
  179.       DBUG_RETURN(-1);
  180.     }
  181.     if (!_nisam_fetch_keypage(info,keyinfo,leaf_page,leaf_buff,0))
  182.       goto err;
  183.   }
  184.  
  185.   if (flag != 0)
  186.   {
  187.     if (!nod_flag)
  188.     {
  189.       my_errno=HA_ERR_CRASHED;        /* This should newer happend */
  190.       goto err;
  191.     }
  192.     save_flag=0;
  193.     ret_value=d_search(info,keyinfo,key,leaf_page,leaf_buff);
  194.   }
  195.   else
  196.   {                        /* Found key */
  197.     next_keypos=keypos;                /* Find where next block is */
  198.     VOID((*keyinfo->get_key)(keyinfo,nod_flag,&next_keypos,lastkey));
  199.     next_block=_nisam_kpos(nod_flag,next_keypos);
  200.     length=getint(anc_buff);
  201.     length-= remove_key(keyinfo,nod_flag,keypos,lastkey,anc_buff+length);
  202.     putint(anc_buff,length,nod_flag);
  203.     if (!nod_flag)
  204.     {                        /* On leaf page */
  205.       if (_nisam_write_keypage(info,keyinfo,page,anc_buff))
  206.     DBUG_RETURN(-1);
  207.       DBUG_RETURN(length <= (uint) keyinfo->base.block_length/2);
  208.     }
  209.     save_flag=1;
  210.     ret_value=del(info,keyinfo,key,anc_buff,leaf_page,leaf_buff,keypos,
  211.           next_block,lastkey);
  212.   }
  213.   if (ret_value >0)
  214.   {
  215.     save_flag=1;
  216.     if (ret_value == 1)
  217.       ret_value= underflow(info,keyinfo,anc_buff,leaf_page,leaf_buff,keypos);
  218.     else
  219.     {                /* This happens only with packed keys */
  220.       DBUG_PRINT("test",("Enlarging of key when deleting"));
  221.       VOID(_nisam_get_last_key(info,keyinfo,anc_buff,lastkey,keypos));
  222.       ret_value=_nisam_insert(info,keyinfo,key,anc_buff,keypos,lastkey,
  223.                (uchar*) 0,(uchar*) 0,0L);
  224.     }
  225.   }
  226.   if (ret_value == 0 && getint(anc_buff) > keyinfo->base.block_length)
  227.   {
  228.     save_flag=1;
  229.     ret_value=_nisam_splitt_page(info,keyinfo,key,anc_buff,lastkey) | 2;
  230.   }
  231.   if (save_flag)
  232.     ret_value|=_nisam_write_keypage(info,keyinfo,page,anc_buff);
  233.   else
  234.   {
  235.     DBUG_DUMP("page",(byte*) anc_buff,getint(anc_buff));
  236.   }
  237.   my_afree((byte*) leaf_buff);
  238.   DBUG_RETURN(ret_value);
  239. err:
  240.   my_afree((byte*) leaf_buff);
  241.   DBUG_PRINT("exit",("Error: %d",my_errno));
  242.   DBUG_RETURN (-1);
  243. } /* d_search */
  244.  
  245.  
  246.     /* Remove a key that has a page-reference */
  247.  
  248. static int del(register N_INFO *info, register N_KEYDEF *keyinfo, uchar *key,
  249.            uchar *anc_buff, ulong leaf_page, uchar *leaf_buff,
  250.            uchar *keypos,        /* Pos to where deleted key was */
  251.            ulong next_block,
  252.            uchar *ret_key)        /* key before keypos in anc_buff */
  253. {
  254.   int ret_value,length;
  255.   uint a_length,nod_flag;
  256.   ulong next_page;
  257.   uchar keybuff[N_MAX_KEY_BUFF],*endpos,*next_buff,*key_start;
  258.   ISAM_SHARE *share=info->s;
  259.   S_PARAM s_temp;
  260.   DBUG_ENTER("del");
  261.   DBUG_PRINT("enter",("leaf_page: %ld   keypos: %lx",leaf_page,keypos));
  262.   DBUG_DUMP("leaf_buff",(byte*) leaf_buff,getint(leaf_buff));
  263.  
  264.   endpos=leaf_buff+getint(leaf_buff);
  265.   key_start=_nisam_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos);
  266.  
  267.   if ((nod_flag=test_if_nod(leaf_buff)))
  268.   {
  269.     next_page= _nisam_kpos(nod_flag,endpos);
  270.     if (!(next_buff= (uchar*) my_alloca((uint) keyinfo->base.block_length+
  271.                     N_MAX_KEY_BUFF)))
  272.       DBUG_RETURN(-1);
  273.     if (!_nisam_fetch_keypage(info,keyinfo,next_page,next_buff,0))
  274.       ret_value= -1;
  275.     else
  276.     {
  277.       DBUG_DUMP("next_page",(byte*) next_buff,getint(next_buff));
  278.       if ((ret_value=del(info,keyinfo,key,anc_buff,next_page,next_buff,
  279.              keypos,next_block,ret_key)) >0)
  280.       {
  281.     endpos=leaf_buff+getint(leaf_buff);
  282.     if (ret_value == 1)
  283.     {
  284.       ret_value=underflow(info,keyinfo,leaf_buff,next_page,
  285.                   next_buff,endpos);
  286.       if (ret_value == 0 && getint(leaf_buff) > keyinfo->base.block_length)
  287.       {
  288.         ret_value=_nisam_splitt_page(info,keyinfo,key,leaf_buff,ret_key) | 2;
  289.       }
  290.     }
  291.     else
  292.     {
  293.       DBUG_PRINT("test",("Inserting of key when deleting"));
  294.       VOID(_nisam_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos));
  295.       ret_value=_nisam_insert(info,keyinfo,key,leaf_buff,endpos,keybuff,
  296.                    (uchar*) 0,(uchar*) 0,0L);
  297.     }
  298.       }
  299.       if (_nisam_write_keypage(info,keyinfo,leaf_page,leaf_buff))
  300.     goto err;
  301.     }
  302.     my_afree((byte*) next_buff);
  303.     DBUG_RETURN(ret_value);
  304.   }
  305.  
  306.     /* Remove last key from leaf page */
  307.  
  308.   putint(leaf_buff,key_start-leaf_buff,nod_flag);
  309.   if (_nisam_write_keypage(info,keyinfo,leaf_page,leaf_buff))
  310.     goto err;
  311.  
  312.     /* Place last key in ancestor page on deleted key position */
  313.  
  314.   a_length=getint(anc_buff);
  315.   endpos=anc_buff+a_length;
  316.   VOID(_nisam_get_last_key(info,keyinfo,anc_buff,ret_key,keypos));
  317.   length=_nisam_get_pack_key_length(keyinfo,share->base.key_reflength,
  318.                  keypos == endpos ? (uchar*) 0 : keypos,
  319.                  ret_key,keybuff,&s_temp);
  320.   if (length > 0)
  321.     bmove_upp((byte*) endpos+length,(byte*) endpos,(uint) (endpos-keypos));
  322.   else
  323.     bmove(keypos,keypos-length, (int) (endpos-keypos)+length);
  324.   _nisam_store_key(keyinfo,keypos,&s_temp);
  325.     /* Save pointer to next leaf */
  326.   VOID((*keyinfo->get_key)(keyinfo,share->base.key_reflength,&keypos,ret_key));
  327.   _nisam_kpointer(info,keypos - share->base.key_reflength,next_block);
  328.   putint(anc_buff,a_length+length,share->base.key_reflength);
  329.  
  330.   DBUG_RETURN( getint(leaf_buff) <= (uint) keyinfo->base.block_length/2 );
  331. err:
  332.   DBUG_RETURN(-1);
  333. } /* del */
  334.  
  335.  
  336.     /* Balances adjacent pages if underflow occours */
  337.  
  338. static int underflow(register N_INFO *info, register N_KEYDEF *keyinfo,
  339.              uchar *anc_buff,
  340.              ulong leaf_page,    /* Ancestor page and underflow page */
  341.              uchar *leaf_buff,
  342.              uchar *keypos)    /* Position to pos after key */
  343. {
  344.   int t_length;
  345.   uint length,anc_length,buff_length,leaf_length,p_length,s_length,nod_flag;
  346.   ulong next_page;
  347.   uchar anc_key[N_MAX_KEY_BUFF],leaf_key[N_MAX_KEY_BUFF],
  348.     *buff,*endpos,*next_keypos,*half_pos,*temp_pos;
  349.   S_PARAM s_temp;
  350.   ISAM_SHARE *share=info->s;
  351.   DBUG_ENTER("underflow");
  352.   DBUG_PRINT("enter",("leaf_page: %ld   keypos: %lx",leaf_page,keypos));
  353.   DBUG_DUMP("anc_buff",(byte*) anc_buff,getint(anc_buff));
  354.   DBUG_DUMP("leaf_buff",(byte*) leaf_buff,getint(leaf_buff));
  355.  
  356.   buff=info->buff;
  357.   next_keypos=keypos;
  358.   nod_flag=test_if_nod(leaf_buff);
  359.   p_length=2+nod_flag;
  360.   anc_length=getint(anc_buff);
  361.   leaf_length=getint(leaf_buff);
  362.   info->page_changed=1;
  363.  
  364.   if ((keypos < anc_buff+anc_length && (share->rnd++ & 1)) ||
  365.       keypos == anc_buff+2+share->base.key_reflength)
  366.   {                    /* Use page right of anc-page */
  367.     DBUG_PRINT("test",("use right page"));
  368.  
  369.     VOID((*keyinfo->get_key)(keyinfo,share->base.key_reflength,&next_keypos,
  370.                  buff));
  371.     next_page= _nisam_kpos(share->base.key_reflength,next_keypos);
  372.     if (!_nisam_fetch_keypage(info,keyinfo,next_page,buff,0))
  373.       goto err;
  374.     buff_length=getint(buff);
  375.     DBUG_DUMP("next",(byte*) buff,buff_length);
  376.  
  377.     /* find keys to make a big key-page */
  378.     bmove((byte*) next_keypos-share->base.key_reflength,(byte*) buff+2,
  379.       share->base.key_reflength);
  380.     VOID(_nisam_get_last_key(info,keyinfo,anc_buff,anc_key,next_keypos));
  381.     VOID(_nisam_get_last_key(info,keyinfo,leaf_buff,leaf_key,
  382.               leaf_buff+leaf_length));
  383.  
  384.     /* merge pages and put parting key from anc_buff between */
  385.     t_length=(int) _nisam_get_pack_key_length(keyinfo,nod_flag,buff+p_length,
  386.                        (leaf_length == nod_flag+2 ?
  387.                         (uchar*) 0 : leaf_key),
  388.                        anc_key,&s_temp);
  389.     length=buff_length-p_length;
  390.     endpos=buff+length+leaf_length+t_length;
  391.     bmove_upp((byte*) endpos, (byte*) buff+buff_length,length);
  392.     memcpy((byte*) buff, (byte*) leaf_buff,(size_t) leaf_length);
  393.     _nisam_store_key(keyinfo,buff+leaf_length,&s_temp);
  394.     buff_length=(uint) (endpos-buff);
  395.     putint(buff,buff_length,nod_flag);
  396.  
  397.     /* remove key from anc_buff */
  398.  
  399.     s_length=remove_key(keyinfo,share->base.key_reflength,keypos,anc_key,
  400.             anc_buff+anc_length);
  401.     putint(anc_buff,(anc_length-=s_length),share->base.key_reflength);
  402.  
  403.     if (buff_length <= keyinfo->base.block_length)
  404.     {                        /* Keys in one page */
  405.       memcpy((byte*) leaf_buff,(byte*) buff,(size_t) buff_length);
  406.       if (_nisam_dispose(info,keyinfo,next_page))
  407.        goto err;
  408.     }
  409.     else
  410.     {                        /* Page is full */
  411.       VOID(_nisam_get_last_key(info,keyinfo,anc_buff,anc_key,keypos));
  412.       half_pos=_nisam_find_half_pos(info,keyinfo,buff,leaf_key);
  413.       length=(uint) (half_pos-buff);
  414.       memcpy((byte*) leaf_buff,(byte*) buff,(size_t) length);
  415.       putint(leaf_buff,length,nod_flag);
  416.       endpos=anc_buff+anc_length;
  417.  
  418.       /* Correct new keypointer to leaf_page */
  419.       length=(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key);
  420.       _nisam_kpointer(info,leaf_key+length,next_page);
  421.       /* Save key in anc_buff */
  422.       t_length=(int) _nisam_get_pack_key_length(keyinfo,
  423.                         share->base.key_reflength,
  424.                         keypos == endpos ?
  425.                         (uchar*) 0 : keypos,
  426.                         anc_key,leaf_key,&s_temp);
  427.       if (t_length >= 0)
  428.     bmove_upp((byte*) endpos+t_length,(byte*) endpos,
  429.           (uint) (endpos-keypos));
  430.       else
  431.     bmove(keypos,keypos-t_length,(uint) (endpos-keypos)+t_length);
  432.       _nisam_store_key(keyinfo,keypos,&s_temp);
  433.       putint(anc_buff,(anc_length+=t_length),share->base.key_reflength);
  434.  
  435.     /* Store new page */
  436.       if (nod_flag)
  437.     bmove((byte*) buff+2,(byte*) half_pos-nod_flag,(size_t) nod_flag);
  438.       VOID((*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key));
  439.       t_length=(int) _nisam_get_pack_key_length(keyinfo,nod_flag,(uchar*) 0,
  440.                          (uchar*) 0, leaf_key,&s_temp);
  441.       s_temp.n_length= *half_pos;    /* For _nisam_store_key */
  442.       length=(uint) ((buff+getint(buff))-half_pos);
  443.       bmove((byte*) buff+p_length+t_length,(byte*) half_pos,(size_t) length);
  444.       _nisam_store_key(keyinfo,buff+p_length,&s_temp);
  445.       putint(buff,length+t_length+p_length,nod_flag);
  446.  
  447.       if (_nisam_write_keypage(info,keyinfo,next_page,buff))
  448.     goto err;
  449.     }
  450.     if (_nisam_write_keypage(info,keyinfo,leaf_page,leaf_buff))
  451.       goto err;
  452.     DBUG_RETURN(anc_length <= (uint) keyinfo->base.block_length/2);
  453.   }
  454.  
  455.   DBUG_PRINT("test",("use left page"));
  456.  
  457.   keypos=_nisam_get_last_key(info,keyinfo,anc_buff,anc_key,keypos);
  458.   next_page= _nisam_kpos(share->base.key_reflength,keypos);
  459.   if (!_nisam_fetch_keypage(info,keyinfo,next_page,buff,0))
  460.       goto err;
  461.   buff_length=getint(buff);
  462.   endpos=buff+buff_length;
  463.   DBUG_DUMP("prev",(byte*) buff,buff_length);
  464.  
  465.   /* find keys to make a big key-page */
  466.   bmove((byte*) next_keypos - share->base.key_reflength,(byte*) leaf_buff+2,
  467.     share->base.key_reflength);
  468.   next_keypos=keypos;
  469.   VOID((*keyinfo->get_key)(keyinfo,share->base.key_reflength,&next_keypos,
  470.                anc_key));
  471.   VOID(_nisam_get_last_key(info,keyinfo,buff,leaf_key,endpos));
  472.  
  473.   /* merge pages and put parting key from anc_buff between */
  474.   t_length=(int) _nisam_get_pack_key_length(keyinfo,nod_flag,
  475.                         leaf_buff+p_length,
  476.                         (leaf_length == nod_flag+2 ?
  477.                          (uchar*) 0 : leaf_key),
  478.                         anc_key,&s_temp);
  479.   if (t_length >= 0)
  480.     bmove((byte*) endpos+t_length,(byte*) leaf_buff+p_length,
  481.         (size_t) (leaf_length-p_length));
  482.   else                        /* We gained space */
  483.     bmove((byte*) endpos,(byte*) leaf_buff+((int) p_length-t_length),
  484.         (size_t) (leaf_length-p_length+t_length));
  485.  
  486.   _nisam_store_key(keyinfo,endpos,&s_temp);
  487.   buff_length=buff_length+leaf_length-p_length+t_length;
  488.   putint(buff,buff_length,nod_flag);
  489.  
  490.   /* remove key from anc_buff */
  491.   s_length=remove_key(keyinfo,share->base.key_reflength,keypos,anc_key,
  492.               anc_buff+anc_length);
  493.   putint(anc_buff,(anc_length-=s_length),share->base.key_reflength);
  494.  
  495.   if (buff_length <= keyinfo->base.block_length)
  496.   {                        /* Keys in one page */
  497.     if (_nisam_dispose(info,keyinfo,leaf_page))
  498.       goto err;
  499.   }
  500.   else
  501.   {                        /* Page is full */
  502.     VOID(_nisam_get_last_key(info,keyinfo,anc_buff,anc_key,keypos));
  503.     endpos=half_pos=_nisam_find_half_pos(info,keyinfo,buff,leaf_key);
  504.  
  505.     /* Correct new keypointer to leaf_page */
  506.     length=(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key);
  507.     _nisam_kpointer(info,leaf_key+length,leaf_page);
  508.     /* Save key in anc_buff */
  509.     DBUG_DUMP("anc_buff",(byte*) anc_buff,anc_length);
  510.     DBUG_DUMP("key",(byte*) leaf_key,16);
  511.  
  512.     temp_pos=anc_buff+anc_length;
  513.     t_length=(int) _nisam_get_pack_key_length(keyinfo,
  514.                           share->base.key_reflength,
  515.                           keypos == temp_pos ? (uchar*) 0
  516.                           : keypos,
  517.                           anc_key,leaf_key,&s_temp);
  518.     if (t_length > 0)
  519.       bmove_upp((byte*) temp_pos+t_length,(byte*) temp_pos,
  520.         (uint) (temp_pos-keypos));
  521.     else
  522.       bmove(keypos,keypos-t_length,(uint) (temp_pos-keypos)+t_length);
  523.     _nisam_store_key(keyinfo,keypos,&s_temp);
  524.     putint(anc_buff,(anc_length+=t_length),share->base.key_reflength);
  525.  
  526.     /* Store new page */
  527.     if (nod_flag)
  528.       bmove((byte*) leaf_buff+2,(byte*) half_pos-nod_flag,(size_t) nod_flag);
  529.     VOID((*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key));
  530.     t_length=(int) _nisam_get_pack_key_length(keyinfo,nod_flag, (uchar*) 0,
  531.                        (uchar*) 0, leaf_key, &s_temp);
  532.     s_temp.n_length= *half_pos;        /* For _nisam_store_key */
  533.     length=(uint) ((buff+buff_length)-half_pos);
  534.     bmove((byte*) leaf_buff+p_length+t_length,(byte*) half_pos,
  535.         (size_t) length);
  536.     _nisam_store_key(keyinfo,leaf_buff+p_length,&s_temp);
  537.     putint(leaf_buff,length+t_length+p_length,nod_flag);
  538.     putint(buff,endpos-buff,nod_flag);
  539.     if (_nisam_write_keypage(info,keyinfo,leaf_page,leaf_buff))
  540.     goto err;
  541.   }
  542.   if (_nisam_write_keypage(info,keyinfo,next_page,buff))
  543.     goto err;
  544.   DBUG_RETURN(anc_length <= (uint) keyinfo->base.block_length/2);
  545. err:
  546.   DBUG_RETURN(-1);
  547. } /* underflow */
  548.  
  549.  
  550.     /* remove a key from packed buffert */
  551.     /* returns how many chars was removed */
  552.  
  553. static uint remove_key(N_KEYDEF *keyinfo, uint nod_flag,
  554.                uchar *keypos,    /* Where key starts */
  555.                uchar *lastkey,    /* key to be removed */
  556.                uchar *page_end)    /* End of page */
  557. {
  558.   int r_length,s_length,first,diff_flag;
  559.   uchar *start;
  560.   DBUG_ENTER("remove_key");
  561.   DBUG_PRINT("enter",("keypos: %lx  page_end: %lx",keypos,page_end));
  562.  
  563.   start=keypos;
  564.   if (!(keyinfo->base.flag & (HA_PACK_KEY | HA_SPACE_PACK_USED)))
  565.     s_length=(int) (keyinfo->base.keylength+nod_flag);
  566.   else
  567.   {                     /* Let keypos point at next key */
  568.     VOID((*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey));
  569.     s_length=(uint) (keypos-start);
  570.     if (keyinfo->base.flag & HA_PACK_KEY)
  571.     {
  572.       diff_flag= (keyinfo->seg[0].base.flag & HA_SPACE_PACK);
  573.       first= *start;
  574.       if (keypos != page_end && *keypos & 128 && first != 128)
  575.       {                    /* Referens length */
  576.     if ((r_length= *keypos++ & 127) == 0)
  577.     {                /* Same key after */
  578.       if (first & 128)
  579.         start++;            /* Skip ref length */
  580.       if (diff_flag)
  581.         start+= *start+1;        /* Skip key length */
  582.       else
  583.         start+=keyinfo->seg[0].base.length- (first & 127);
  584.       s_length=(uint)(keypos-start); /* Remove pntrs and next-key-flag */
  585.     }
  586.     else if (! (first & 128))
  587.     {                /* Deleted key was not compressed */
  588.       if (diff_flag)
  589.       {
  590.         *start= (uchar) (r_length+ *keypos);
  591.         start+=r_length+1;        /* Let ref-part remain */
  592.         s_length=(uint) (keypos-start)+1;    /* Skip everything between */
  593.       }
  594.       else
  595.       {
  596.         start+=r_length+1;        /* Let ref-part remain */
  597.         s_length=(uint) (keypos-start);    /* Skip everything between */
  598.       }
  599.     }
  600.     else if ((first & 127) < r_length)
  601.     {                /* mid-part of key is used */
  602.       r_length-=(first & 127);
  603.       start++;            /* Ref remains the same */
  604.       if (diff_flag)
  605.         *start++= (uchar) (*keypos++ + r_length);
  606.       start+= r_length;
  607.       s_length=(uint) (keypos-start);    /* Skip everything between */
  608.     }
  609.       }
  610.     }
  611.   }
  612.   bmove((byte*) start,(byte*) start+s_length,
  613.     (uint) (page_end-start-s_length));
  614.   DBUG_RETURN((uint) s_length);
  615. } /* remove_key */
  616.  
  617.  
  618.