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 / write.c < prev   
C/C++ Source or Header  |  2000-08-31  |  26KB  |  841 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. /* Skriver ett record till en isam-databas */
  18.  
  19. #include "isamdef.h"
  20. #ifdef    __WIN__
  21. #include <errno.h>
  22. #endif
  23.  
  24.     /* Functions declared in this file */
  25.  
  26. static int w_search(N_INFO *info,N_KEYDEF *keyinfo,uchar *key,
  27.             ulong pos, uchar *father_buff, uchar *father_keypos,
  28.             ulong father_page);
  29. static int _nisam_balance_page(N_INFO *info,N_KEYDEF *keyinfo,uchar *key,
  30.                 uchar *curr_buff,uchar *father_buff,
  31.                 uchar *father_keypos,ulong father_page);
  32.  
  33.  
  34.     /* Write new record to database */
  35.  
  36. int nisam_write(N_INFO *info, const byte *record)
  37. {
  38.   uint i;
  39.   ulong filepos;
  40.   uchar *buff;
  41.   DBUG_ENTER("nisam_write");
  42.   DBUG_PRINT("enter",("isam: %d  data: %d",info->s->kfile,info->dfile));
  43.  
  44.   if (info->s->base.options & HA_OPTION_READ_ONLY_DATA)
  45.   {
  46.     my_errno=EACCES;
  47.     DBUG_RETURN(-1);
  48.   }
  49. #ifndef NO_LOCKING
  50.   if (_nisam_readinfo(info,F_WRLCK,1)) DBUG_RETURN(-1);
  51. #endif
  52.   dont_break();                /* Dont allow SIGHUP or SIGINT */
  53. #if !defined(NO_LOCKING) && defined(USE_RECORD_LOCK)
  54.   if (!info->locked && my_lock(info->dfile,F_WRLCK,0L,F_TO_EOF,
  55.                    MYF(MY_SEEK_NOT_DONE) | info->lock_wait))
  56.     goto err;
  57. #endif
  58.   filepos= ((info->s->state.dellink != NI_POS_ERROR) ?
  59.         info->s->state.dellink :
  60.         info->s->state.data_file_length);
  61.  
  62.   if (info->s->base.reloc == 1L && info->s->base.records == 1L &&
  63.       info->s->state.records == 1L)
  64.   {                        /* System file */
  65.     my_errno=HA_ERR_RECORD_FILE_FULL;
  66.     goto err2;
  67.   }
  68.   if (info->s->state.key_file_length >=
  69.       info->s->base.max_key_file_length -
  70.       info->s->blocksize* INDEX_BLOCK_MARGIN *info->s->state.keys)
  71.   {
  72.     my_errno=HA_ERR_INDEX_FILE_FULL;
  73.     goto err2;
  74.   }
  75.  
  76.     /* Write all keys to indextree */
  77.   buff=info->lastkey+info->s->base.max_key_length;
  78.   for (i=0 ; i < info->s->state.keys ; i++)
  79.   {
  80.     VOID(_nisam_make_key(info,i,buff,record,filepos));
  81.     if (_nisam_ck_write(info,i,buff)) goto err;
  82.   }
  83.  
  84.   if ((*info->s->write_record)(info,record))
  85.     goto err;
  86.  
  87.   info->update= (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED |HA_STATE_AKTIV |
  88.          HA_STATE_WRITTEN);
  89.   info->s->state.records++;
  90.   info->lastpos=filepos;
  91.   nisam_log_record(LOG_WRITE,info,record,filepos,0);
  92.   VOID(_nisam_writeinfo(info,1));
  93.   allow_break();                /* Allow SIGHUP & SIGINT */
  94.   DBUG_RETURN(0);
  95.  
  96. err:
  97.   if (my_errno == HA_ERR_FOUND_DUPP_KEY || my_errno == HA_ERR_RECORD_FILE_FULL)
  98.   {
  99.     info->errkey= (int) i;
  100.     while ( i-- > 0)
  101.     {
  102.       VOID(_nisam_make_key(info,i,buff,record,filepos));
  103.       if (_nisam_ck_delete(info,i,buff))
  104.     break;
  105.     }
  106.   }
  107.   info->update=(HA_STATE_CHANGED | HA_STATE_ROW_CHANGED | HA_STATE_WRITTEN);
  108. err2:
  109.   nisam_log_record(LOG_WRITE,info,record,filepos,my_errno);
  110.   VOID(_nisam_writeinfo(info,1));
  111.   allow_break();            /* Allow SIGHUP & SIGINT */
  112.   DBUG_RETURN(-1);
  113. } /* nisam_write */
  114.  
  115.  
  116.     /* Write one key to btree */
  117.  
  118. int _nisam_ck_write(register N_INFO *info, uint keynr, uchar *key)
  119. {
  120.   int error;
  121.   DBUG_ENTER("_nisam_ck_write");
  122.  
  123.   if ((error=w_search(info,info->s->keyinfo+keynr,key,
  124.               info->s->state.key_root[keynr], (uchar *) 0, (uchar*) 0,
  125.               0L)) > 0)
  126.     error=_nisam_enlarge_root(info,keynr,key);
  127.   DBUG_RETURN(error);
  128. } /* _nisam_ck_write */
  129.  
  130.  
  131.     /* Make a new root with key as only pointer */
  132.  
  133. int _nisam_enlarge_root(register N_INFO *info, uint keynr, uchar *key)
  134. {
  135.   uint t_length,nod_flag;
  136.   reg2 N_KEYDEF *keyinfo;
  137.   S_PARAM s_temp;
  138.   ISAM_SHARE *share=info->s;
  139.   DBUG_ENTER("_nisam_enlarge_root");
  140.  
  141.   info->page_changed=1;
  142.   nod_flag= (share->state.key_root[keynr] != NI_POS_ERROR) ?
  143.     share->base.key_reflength : 0;
  144.   _nisam_kpointer(info,info->buff+2,share->state.key_root[keynr]); /* if nod */
  145.   keyinfo=share->keyinfo+keynr;
  146.   t_length=_nisam_get_pack_key_length(keyinfo,nod_flag,(uchar*) 0,(uchar*) 0,
  147.                    key,&s_temp);
  148.   putint(info->buff,t_length+2+nod_flag,nod_flag);
  149.   _nisam_store_key(keyinfo,info->buff+2+nod_flag,&s_temp);
  150.   if ((share->state.key_root[keynr]= _nisam_new(info,keyinfo)) ==
  151.       NI_POS_ERROR ||
  152.       _nisam_write_keypage(info,keyinfo,share->state.key_root[keynr],info->buff))
  153.     DBUG_RETURN(-1);
  154.   DBUG_RETURN(0);
  155. } /* _nisam_enlarge_root */
  156.  
  157.  
  158.     /* S|ker reda p} vart nyckeln skall s{ttas och placerar den dit */
  159.     /* Returnerar -1 om fel ; 0 om ok.  1 om nyckel propagerar upp}t */
  160.  
  161. static int w_search(register N_INFO *info, register N_KEYDEF *keyinfo,
  162.             uchar *key, ulong page, uchar *father_buff,
  163.             uchar *father_keypos, ulong father_page)
  164. {
  165.   int error,flag;
  166.   uint comp_flag,nod_flag;
  167.   uchar *temp_buff,*keypos;
  168.   uchar keybuff[N_MAX_KEY_BUFF];
  169.   DBUG_ENTER("w_search");
  170.   DBUG_PRINT("enter",("page: %ld",page));
  171.  
  172.   if (page == NI_POS_ERROR)
  173.     DBUG_RETURN(1);                /* No key, make new */
  174.  
  175.   if (keyinfo->base.flag & HA_SORT_ALLOWS_SAME)
  176.     comp_flag=SEARCH_BIGGER;            /* Put after same key */
  177.   else if (keyinfo->base.flag & HA_NOSAME)
  178.     comp_flag=SEARCH_FIND;            /* No dupplicates */
  179.   else
  180.     comp_flag=SEARCH_SAME;            /* Keys in rec-pos order */
  181.  
  182.   if (!(temp_buff= (uchar*) my_alloca((uint) keyinfo->base.block_length+
  183.                       N_MAX_KEY_BUFF)))
  184.     DBUG_RETURN(-1);
  185.   if (!_nisam_fetch_keypage(info,keyinfo,page,temp_buff,0))
  186.     goto err;
  187.  
  188.   flag=(*keyinfo->bin_search)(info,keyinfo,temp_buff,key,0,comp_flag,&keypos,
  189.                   keybuff);
  190.   nod_flag=test_if_nod(temp_buff);
  191.   if (flag == 0)
  192.   {
  193.     my_errno=HA_ERR_FOUND_DUPP_KEY;
  194.     /* get position to record with dupplicated key */
  195.     VOID((*keyinfo->get_key)(keyinfo,nod_flag,&keypos,keybuff));
  196.     info->dupp_key_pos=_nisam_dpos(info,test_if_nod(temp_buff),keypos);
  197.     my_afree((byte*) temp_buff);
  198.     DBUG_RETURN(-1);
  199.   }
  200.   if ((error=w_search(info,keyinfo,key,_nisam_kpos(nod_flag,keypos),
  201.               temp_buff,keypos,page)) >0)
  202.   {
  203.     error=_nisam_insert(info,keyinfo,key,temp_buff,keypos,keybuff,father_buff,
  204.              father_keypos,father_page);
  205.     if (_nisam_write_keypage(info,keyinfo,page,temp_buff))
  206.       goto err;
  207.   }
  208.   my_afree((byte*) temp_buff);
  209.   DBUG_RETURN(error);
  210. err:
  211.   my_afree((byte*) temp_buff);
  212.   DBUG_PRINT("exit",("Error: %d",my_errno));
  213.   DBUG_RETURN (-1);
  214. } /* w_search */
  215.  
  216.  
  217.     /* Insert new key at right of key_pos */
  218.     /* Returns 2 if key contains key to upper level */
  219.  
  220. int _nisam_insert(register N_INFO *info, register N_KEYDEF *keyinfo,
  221.            uchar *key, uchar *anc_buff, uchar *key_pos, uchar *key_buff,
  222.            uchar *father_buff, uchar *father_key_pos, ulong father_page)
  223. {
  224.   uint a_length,t_length,nod_flag;
  225.   uchar *endpos;
  226.   int key_offset;
  227.   S_PARAM s_temp;
  228.   DBUG_ENTER("_nisam_insert");
  229.   DBUG_PRINT("enter",("key_pos: %lx",key_pos));
  230.   DBUG_EXECUTE("key",_nisam_print_key(DBUG_FILE,keyinfo->seg,key););
  231.  
  232.   nod_flag=test_if_nod(anc_buff);
  233.   a_length=getint(anc_buff);
  234.   endpos= anc_buff+ a_length;
  235.   t_length=_nisam_get_pack_key_length(keyinfo,nod_flag,
  236.                    (key_pos == endpos ? (uchar*) 0 : key_pos),
  237.                    (key_pos == anc_buff+2+nod_flag ?
  238.                     (uchar*) 0 : key_buff),key,&s_temp);
  239. #ifndef DBUG_OFF
  240.   if (key_pos != anc_buff+2+nod_flag)
  241.     DBUG_DUMP("prev_key",(byte*) key_buff,_nisam_keylength(keyinfo,key_buff));
  242.   if (keyinfo->base.flag & HA_PACK_KEY)
  243.   {
  244.     DBUG_PRINT("test",("t_length: %d  ref_len: %d",
  245.                t_length,s_temp.ref_length));
  246.     DBUG_PRINT("test",("n_ref_len: %d  n_length: %d  key: %lx",
  247.                s_temp.n_ref_length,s_temp.n_length,s_temp.key));
  248.   }
  249. #endif
  250.   key_offset = (uint)(endpos-key_pos);
  251.   if((int) t_length < 0)
  252.     key_offset += (int) t_length;
  253.   if (key_offset < 0)
  254.   {
  255.     DBUG_PRINT("error",("Found a bug: negative key_offset %d\n", key_offset));
  256.     DBUG_RETURN(-1);
  257.   }
  258.   if ((int) t_length >= 0)        /* t_length is almost always > 0 */
  259.     bmove_upp((byte*) endpos+t_length,(byte*) endpos,(uint)key_offset );
  260.   else
  261.   {
  262.     /* This may happen if a key was deleted and the next key could be
  263.        compressed better than before */
  264.     DBUG_DUMP("anc_buff",(byte*) anc_buff,a_length);
  265.     
  266.     bmove(key_pos,key_pos - (int) t_length,(uint)key_offset);
  267.   }
  268.   _nisam_store_key(keyinfo,key_pos,&s_temp);
  269.   a_length+=t_length;
  270.   putint(anc_buff,a_length,nod_flag);
  271.   if (a_length <= keyinfo->base.block_length)
  272.     DBUG_RETURN(0);                /* There is room on page */
  273.  
  274.   /* Page is full */
  275.  
  276.   if (!(keyinfo->base.flag & (HA_PACK_KEY | HA_SPACE_PACK_USED)) &&
  277.       father_buff)
  278.     DBUG_RETURN(_nisam_balance_page(info,keyinfo,key,anc_buff,father_buff,
  279.                  father_key_pos,father_page));
  280.   DBUG_RETURN(_nisam_splitt_page(info,keyinfo,key,anc_buff,key_buff));
  281. } /* _nisam_insert */
  282.  
  283.  
  284.     /* splitt a full page in two and assign emerging item to key */
  285.  
  286. int _nisam_splitt_page(register N_INFO *info, register N_KEYDEF *keyinfo,
  287.             uchar *key, uchar *buff, uchar *key_buff)
  288. {
  289.   uint length,a_length,key_ref_length,t_length,nod_flag;
  290.   uchar *key_pos,*pos;
  291.   ulong new_pos;
  292.   S_PARAM s_temp;
  293.   DBUG_ENTER("ni_splitt_page");
  294.   DBUG_DUMP("buff",(byte*) buff,getint(buff));
  295.  
  296.   nod_flag=test_if_nod(buff);
  297.   key_ref_length=2+nod_flag;
  298.   key_pos=_nisam_find_half_pos(info,keyinfo,buff,key_buff);
  299.   length=(uint) (key_pos-buff);
  300.   a_length=getint(buff);
  301.   putint(buff,length,nod_flag);
  302.   info->page_changed=1;
  303.  
  304.     /* Correct new page pointer */
  305.   VOID((*keyinfo->get_key)(keyinfo,nod_flag,&key_pos,key_buff));
  306.   if (nod_flag)
  307.   {
  308.     DBUG_PRINT("test",("Splitting nod"));
  309.     pos=key_pos-nod_flag;
  310.     memcpy((byte*) info->buff+2,(byte*) pos,(size_t) nod_flag);
  311.   }
  312.  
  313.     /* Move midle item to key and pointer to new page */
  314.   if ((new_pos=_nisam_new(info,keyinfo)) == NI_POS_ERROR)
  315.     DBUG_RETURN(-1);
  316.   _nisam_kpointer(info,_nisam_move_key(keyinfo,key,key_buff),new_pos);
  317.  
  318.     /* Store new page */
  319.   VOID((*keyinfo->get_key)(keyinfo,nod_flag,&key_pos,key_buff));
  320.   t_length=_nisam_get_pack_key_length(keyinfo,nod_flag,(uchar *) 0, (uchar*) 0,
  321.                    key_buff, &s_temp);
  322.   s_temp.n_length= *key_pos;            /* Needed by ni_store_key */
  323.   length=(uint) ((buff+a_length)-key_pos);
  324.   memcpy((byte*) info->buff+key_ref_length+t_length,(byte*) key_pos,
  325.      (size_t) length);
  326.   _nisam_store_key(keyinfo,info->buff+key_ref_length,&s_temp);
  327.   putint(info->buff,length+t_length+key_ref_length,nod_flag);
  328.  
  329.   if (_nisam_write_keypage(info,keyinfo,new_pos,info->buff))
  330.     DBUG_RETURN(-1);
  331.   DBUG_DUMP("key",(byte*) key,_nisam_keylength(keyinfo,key));
  332.   DBUG_RETURN(2);                /* Middle key up */
  333. } /* _nisam_splitt_page */
  334.  
  335.  
  336.     /* find out how much more room a key will take */
  337.  
  338. #ifdef QQ
  339. uint _nisam_get_pack_key_length(N_KEYDEF *keyinfo, uint nod_flag, uchar *key_pos, uchar *key_buff, uchar *key, S_PARAM *s_temp)
  340.  
  341.                     /* If nod: Length of nod-pointer */
  342.                     /* Position to pos after key in buff */
  343.                     /* Last key before current key */
  344.                     /* Current key */
  345.                     /* How next key will be packed */
  346. {
  347.   reg1 N_KEYSEG *keyseg;
  348.   int length;
  349.   uint key_length,ref_length,n_length,diff_flag,same_length;
  350.   uchar *start,*end,*key_end;
  351.  
  352.   s_temp->key=key;
  353.   if (!(keyinfo->base.flag & HA_PACK_KEY))
  354.     return (s_temp->totlength=_nisam_keylength(keyinfo,key)+nod_flag);
  355.   s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
  356.   s_temp->prev_length=0;
  357.  
  358.   same_length=0; keyseg=keyinfo->seg;
  359.   key_length=_nisam_keylength(keyinfo,key)+nod_flag;
  360.  
  361.   if (keyseg->base.flag & HA_SPACE_PACK)
  362.   {
  363.     diff_flag=1;
  364.     end=key_end= key+ *key+1;
  365.     if (key_buff)
  366.     {
  367.       if (*key == *key_buff && *key)
  368.     same_length=1;            /* Don't use key-pack if length == 0 */
  369.       else if (*key > *key_buff)
  370.     end=key+ *key_buff+1;
  371.       key_buff++;
  372.     }
  373.     key++;
  374.   }
  375.   else
  376.   {
  377.     diff_flag=0;
  378.     key_end=end= key+keyseg->base.length;
  379.   }
  380.  
  381.   start=key;
  382.   if (key_buff)
  383.     while (key < end && *key == *key_buff)
  384.     {
  385.       key++; key_buff++;
  386.     }
  387.  
  388.   s_temp->key=key; s_temp->key_length= (uint) (key_end-key);
  389.  
  390.   if (same_length && key == key_end)
  391.   {
  392.     s_temp->ref_length=128;
  393.     length=(int) key_length-(int)(key_end-start); /* Same as prev key */
  394.     if (key_pos)
  395.     {
  396.       s_temp->n_length= *key_pos;
  397.       key_pos=0;                /* Can't combine with next */
  398.     }
  399.   }
  400.   else
  401.   {
  402.     if (start != key)
  403.     {                        /* Starts as prev key */
  404.       s_temp->ref_length= (uint) (key-start)+128;
  405.       length=(int) (1+key_length-(uint) (key-start));
  406.     }
  407.     else
  408.       length=(int) (key_length+ (1-diff_flag));        /* Not packed key */
  409.   }
  410.   s_temp->totlength=(uint) length;
  411.  
  412.   DBUG_PRINT("test",("tot_length: %d  length: %d  uniq_key_length: %d",
  413.              key_length,length,s_temp->key_length));
  414.  
  415.     /* If something after that is not 0 length test if we can combine */
  416.  
  417.   if (key_pos && (n_length= *key_pos))
  418.   {
  419.     key_pos++;
  420.     ref_length=0;
  421.     if (n_length & 128)
  422.     {
  423.       if ((ref_length=n_length & 127))
  424.     if (diff_flag)
  425.       n_length= *key_pos++;            /* Length of key-part */
  426.     else
  427.       n_length=keyseg->base.length - ref_length;
  428.     }
  429.     else
  430.       if (*start == *key_pos && diff_flag && start != key_end)
  431.     length++;                /* One new pos for ref.len */
  432.  
  433.     DBUG_PRINT("test",("length: %d  key_pos: %lx",length,key_pos));
  434.     if (n_length != 128)
  435.     {                        /* Not same key after */
  436.       key=start+ref_length;
  437.       while (n_length > 0 && key < key_end && *key == *key_pos)
  438.       {
  439.     key++; key_pos++;
  440.     ref_length++;
  441.     n_length--;
  442.     length--;                /* We gained one char */
  443.       }
  444.  
  445.       if (n_length == 0 && diff_flag)
  446.       {
  447.     n_length=128;                /* Same as prev key */
  448.     length--;                /* We don't need key-length */
  449.       }
  450.       else if (ref_length)
  451.     s_temp->n_ref_length=ref_length | 128;
  452.     }
  453.     s_temp->n_length=n_length;
  454.   }
  455.   return (uint) length;
  456. } /* _nisam_get_pack_key_length */
  457.  
  458. #else
  459.  
  460. uint
  461. _nisam_get_pack_key_length(N_KEYDEF *keyinfo,
  462.             uint nod_flag,  /* If nod: Length of nod-pointer */
  463.             uchar *key_pos, /* Position to pos after key in buff */
  464.             uchar *key_buff,/* Last key before current key */
  465.             uchar *key,    /* Current key */
  466.             S_PARAM *s_temp/* How next key will be packed */
  467.             )
  468. {
  469.   reg1 N_KEYSEG *keyseg;
  470.   int length;
  471.   uint key_length,ref_length,n_length,diff_flag,same_length,org_key_length=0;
  472.   uchar *start,*end,*key_end;
  473.  
  474.   s_temp->key=key;
  475.   if (!(keyinfo->base.flag & HA_PACK_KEY))
  476.     return (s_temp->totlength=_nisam_keylength(keyinfo,key)+nod_flag);
  477.   s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
  478.  
  479.   same_length=0; keyseg=keyinfo->seg;
  480.   key_length=_nisam_keylength(keyinfo,key)+nod_flag;
  481.   s_temp->prev_key=key_buff;
  482.  
  483.   if (keyseg->base.flag & HA_SPACE_PACK)
  484.   {
  485.     diff_flag=1;
  486.     end=key_end= key+ *key+1;
  487.     if (key_buff)
  488.     {
  489.       org_key_length= (uint) *key_buff;
  490.       if (*key == *key_buff && *key)
  491.     same_length=1;            /* Don't use key-pack if length == 0 */
  492.       else if (*key > *key_buff)
  493.     end=key+ org_key_length+1;
  494.       key_buff++;
  495.     }
  496.     key++;
  497.   }
  498.   else
  499.   {
  500.     diff_flag=0;
  501.     key_end=end= key+(org_key_length=keyseg->base.length);
  502.   }
  503.  
  504.   start=key;
  505.   if (key_buff)
  506.     while (key < end && *key == *key_buff)
  507.     {
  508.       key++; key_buff++;
  509.     }
  510.  
  511.   s_temp->key=key; s_temp->key_length= (uint) (key_end-key);
  512.  
  513.   if (same_length && key == key_end)
  514.   {
  515.     s_temp->ref_length=128;
  516.     length=(int) key_length-(int)(key_end-start); /* Same as prev key */
  517.     if (key_pos)
  518.     {                        /* Can't combine with next */
  519.       s_temp->n_length= *key_pos;        /* Needed by _nisam_store_key */
  520.       key_pos=0;
  521.     }
  522.   }
  523.   else
  524.   {
  525.     if (start != key)
  526.     {                        /* Starts as prev key */
  527.       s_temp->ref_length= (uint) (key-start)+128;
  528.       length=(int) (1+key_length-(uint) (key-start));
  529.     }
  530.     else
  531.       length=(int) (key_length+ (1-diff_flag));        /* Not packed key */
  532.   }
  533.   s_temp->totlength=(uint) length;
  534.   s_temp->prev_length=0;
  535.   DBUG_PRINT("test",("tot_length: %d  length: %d  uniq_key_length: %d",
  536.              key_length,length,s_temp->key_length));
  537.  
  538.     /* If something after that is not 0 length test if we can combine */
  539.  
  540.   if (key_pos && (n_length= *key_pos++))
  541.   {
  542.     if (n_length == 128)
  543.     {
  544.       /*
  545.     We put a different key between two identical keys
  546.     Extend next key to have same prefix as this key
  547.       */
  548.       if (s_temp->ref_length)
  549.       {                    /* make next key longer */
  550.     s_temp->part_of_prev_key= s_temp->ref_length;
  551.     s_temp->prev_length=      org_key_length - (s_temp->ref_length-128);
  552.     s_temp->n_length=       s_temp->prev_length;
  553.     s_temp->prev_key+=        diff_flag + (s_temp->ref_length - 128);
  554.     length+=          s_temp->prev_length+diff_flag;
  555.       }
  556.       else
  557.       {                        /* Can't use prev key */
  558.     s_temp->part_of_prev_key=0;
  559.     s_temp->prev_length= org_key_length;
  560.     s_temp->n_length=    org_key_length;
  561.     s_temp->prev_key+=   diff_flag;        /* To start of key */
  562.     length+=         org_key_length;
  563.       }
  564.       return (uint) length;
  565.     }
  566.  
  567.     if (n_length & 128)
  568.     {
  569.       ref_length=n_length & 127;
  570.       if (diff_flag)                /* If SPACE_PACK */
  571.     n_length= *key_pos++;            /* Length of key-part */
  572.       else
  573.     n_length=keyseg->base.length - ref_length;
  574.  
  575.       /* Test if new keys has fewer characters that match the previous key */
  576.       if (!s_temp->ref_length)
  577.       {                        /* Can't use prev key */
  578.     s_temp->part_of_prev_key=    0;
  579.     s_temp->prev_length=         ref_length;
  580.     s_temp->n_length=        n_length+ref_length;
  581.     s_temp->prev_key+=        diff_flag;    /* To start of key */
  582.     return (uint) length+ref_length-diff_flag;
  583.       }
  584.       if (ref_length+128 > s_temp->ref_length)
  585.       {
  586.     /* We must copy characters from the original key to the next key */
  587.     s_temp->part_of_prev_key= s_temp->ref_length;
  588.     s_temp->prev_length=      ref_length+128 - s_temp->ref_length;
  589.     s_temp->n_length=      n_length + s_temp->prev_length;
  590.     s_temp->prev_key+=       diff_flag + s_temp->ref_length -128;
  591.     return (uint) length + s_temp->prev_length;
  592.       }
  593.     }
  594.     else
  595.     {
  596.       ref_length=0;
  597.       if (*start == *key_pos && diff_flag && start != key_end)
  598.     length++;                /* One new pos for ref.len */
  599.     }
  600.     DBUG_PRINT("test",("length: %d  key_pos: %lx",length,key_pos));
  601.  
  602.     key=start+ref_length;
  603.     while (n_length > 0 && key < key_end && *key == *key_pos)
  604.     {
  605.       key++; key_pos++;
  606.       ref_length++;
  607.       n_length--;
  608.       length--;                /* We gained one char */
  609.     }
  610.  
  611.     if (n_length == 0 && diff_flag)
  612.     {
  613.       n_length=128;                /* Same as prev key */
  614.       length--;                /* We don't need key-length */
  615.     }
  616.     else if (ref_length)
  617.       s_temp->n_ref_length=ref_length | 128;
  618.     s_temp->n_length=n_length;
  619.   }
  620.   return (uint) length;
  621. } /* _nisam_get_pack_key_length */
  622. #endif
  623.  
  624.  
  625.     /* store a key in page-buffert */
  626.  
  627. void _nisam_store_key(N_KEYDEF *keyinfo, register uchar *key_pos,
  628.            register S_PARAM *s_temp)
  629. {
  630.   uint length;
  631.   uchar *start;
  632.  
  633.   if (! (keyinfo->base.flag & HA_PACK_KEY))
  634.   {
  635.     memcpy((byte*) key_pos,(byte*) s_temp->key,(size_t) s_temp->totlength);
  636.     return;
  637.   }
  638.   start=key_pos;
  639.   if ((*key_pos=(uchar) s_temp->ref_length))
  640.     key_pos++;
  641.   if (s_temp->ref_length == 0 ||
  642.       (s_temp->ref_length > 128 &&
  643.        (keyinfo->seg[0].base.flag & HA_SPACE_PACK)))
  644.     *key_pos++= (uchar) s_temp->key_length;
  645.   bmove((byte*) key_pos,(byte*) s_temp->key,
  646.     (length=s_temp->totlength-(uint) (key_pos-start)));
  647.   key_pos+=length;
  648.  
  649.   if (s_temp->prev_length)
  650.   {
  651.     /* Extend next key because new key didn't have same prefix as prev key */
  652.     if (s_temp->part_of_prev_key)
  653.       *key_pos++ = s_temp->part_of_prev_key;
  654.     if (keyinfo->seg[0].base.flag & HA_SPACE_PACK)
  655.       *key_pos++= s_temp->n_length;
  656.     memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
  657.     return;
  658.   }
  659.  
  660.   if ((*key_pos = (uchar) s_temp->n_ref_length))
  661.   {
  662.     if (! (keyinfo->seg[0].base.flag & HA_SPACE_PACK))
  663.       return;                    /* Don't save keylength */
  664.     key_pos++;                    /* Store ref for next key */
  665.   }
  666.   *key_pos = (uchar) s_temp->n_length;
  667.   return;
  668. } /* _nisam_store_key */
  669.  
  670.  
  671.     /* Calculate how to much to move to split a page in two */
  672.     /* Returns pointer and key for get_key() to get mid key */
  673.     /* There is at last 2 keys after pointer in buff */
  674.  
  675. uchar *_nisam_find_half_pos(N_INFO *info, N_KEYDEF *keyinfo, uchar *page, uchar *key)
  676. {
  677.   uint keys,length,key_ref_length,nod_flag;
  678.   uchar *end,*lastpos;
  679.   DBUG_ENTER("_nisam_find_half_pos");
  680.  
  681.   nod_flag=test_if_nod(page);
  682.   key_ref_length=2+nod_flag;
  683.   length=getint(page)-key_ref_length;
  684.   page+=key_ref_length;
  685.   if (!(keyinfo->base.flag & (HA_PACK_KEY | HA_SPACE_PACK_USED)))
  686.   {
  687.     keys=(length/(keyinfo->base.keylength+nod_flag))/2;
  688.     DBUG_RETURN(page+keys*(keyinfo->base.keylength+nod_flag));
  689.   }
  690.  
  691.   end=page+length/2-key_ref_length;        /* This is aprox. half */
  692.   *key='\0';
  693.   do
  694.   {
  695.     lastpos=page;
  696.     VOID((*keyinfo->get_key)(keyinfo,nod_flag,&page,key));
  697.    } while (page < end);
  698.  
  699.    DBUG_PRINT("exit",("returns: %lx  page: %lx  half: %lx",lastpos,page,end));
  700.    DBUG_RETURN(lastpos);
  701. } /* _nisam_find_half_pos */
  702.  
  703.  
  704.     /* Balance page with not packed keys with page on right/left */
  705.     /* returns 0 if balance was done */
  706.  
  707. static int _nisam_balance_page(register N_INFO *info, N_KEYDEF *keyinfo,
  708.                 uchar *key, uchar *curr_buff, uchar *father_buff,
  709.                 uchar *father_key_pos, ulong father_page)
  710. {
  711.   my_bool right;
  712.   uint k_length,father_length,father_keylength,nod_flag,curr_keylength,
  713.        right_length,left_length,new_right_length,new_left_length,extra_length,
  714.        length,keys;
  715.   uchar *pos,*buff,*extra_buff;
  716.   ulong next_page,new_pos;
  717.   byte tmp_part_key[N_MAX_KEY_BUFF];
  718.   DBUG_ENTER("_nisam_balance_page");
  719.  
  720.   k_length=keyinfo->base.keylength;
  721.   father_length=getint(father_buff);
  722.   father_keylength=k_length+info->s->base.key_reflength;
  723.   nod_flag=test_if_nod(curr_buff);
  724.   curr_keylength=k_length+nod_flag;
  725.   info->page_changed=1;
  726.  
  727.   if ((father_key_pos != father_buff+father_length && (info->s->rnd++ & 1)) ||
  728.       father_key_pos == father_buff+2+info->s->base.key_reflength)
  729.   {
  730.     right=1;
  731.     next_page= _nisam_kpos(info->s->base.key_reflength,
  732.             father_key_pos+father_keylength);
  733.     buff=info->buff;
  734.     DBUG_PRINT("test",("use right page: %lu",next_page));
  735.   }
  736.   else
  737.   {
  738.     right=0;
  739.     father_key_pos-=father_keylength;
  740.     next_page= _nisam_kpos(info->s->base.key_reflength,father_key_pos);
  741.                     /* Fix that curr_buff is to left */
  742.     buff=curr_buff; curr_buff=info->buff;
  743.     DBUG_PRINT("test",("use left page: %lu",next_page));
  744.   }                    /* father_key_pos ptr to parting key */
  745.  
  746.   if (!_nisam_fetch_keypage(info,keyinfo,next_page,info->buff,0))
  747.     goto err;
  748.   DBUG_DUMP("next",(byte*) info->buff,getint(info->buff));
  749.  
  750.     /* Test if there is room to share keys */
  751.  
  752.   left_length=getint(curr_buff);
  753.   right_length=getint(buff);
  754.   keys=(left_length+right_length-4-nod_flag*2)/curr_keylength;
  755.  
  756.   if ((right ? right_length : left_length) + curr_keylength <=
  757.       keyinfo->base.block_length)
  758.   {                        /* Merge buffs */
  759.     new_left_length=2+nod_flag+(keys/2)*curr_keylength;
  760.     new_right_length=2+nod_flag+((keys+1)/2)*curr_keylength;
  761.     putint(curr_buff,new_left_length,nod_flag);
  762.     putint(buff,new_right_length,nod_flag);
  763.  
  764.     if (left_length < new_left_length)
  765.     {                        /* Move keys buff -> leaf */
  766.       pos=curr_buff+left_length;
  767.       memcpy((byte*) pos,(byte*) father_key_pos, (size_t) k_length);
  768.       memcpy((byte*) pos+k_length, (byte*) buff+2,
  769.          (size_t) (length=new_left_length - left_length - k_length));
  770.       pos=buff+2+length;
  771.       memcpy((byte*) father_key_pos,(byte*) pos,(size_t) k_length);
  772.       bmove((byte*) buff+2,(byte*) pos+k_length,new_right_length);
  773.     }
  774.     else
  775.     {                        /* Move keys -> buff */
  776.  
  777.       bmove_upp((byte*) buff+new_right_length,(byte*) buff+right_length,
  778.         right_length-2);
  779.       length=new_right_length-right_length-k_length;
  780.       memcpy((byte*) buff+2+length,father_key_pos,(size_t) k_length);
  781.       pos=curr_buff+new_left_length;
  782.       memcpy((byte*) father_key_pos,(byte*) pos,(size_t) k_length);
  783.       memcpy((byte*) buff+2,(byte*) pos+k_length,(size_t) length);
  784.     }
  785.  
  786.     if (_nisam_write_keypage(info,keyinfo,next_page,info->buff) ||
  787.     _nisam_write_keypage(info,keyinfo,father_page,father_buff))
  788.       goto err;
  789.     DBUG_RETURN(0);
  790.   }
  791.  
  792.     /* curr_buff[] and buff[] are full, lets splitt and make new nod */
  793.  
  794.   extra_buff=info->buff+info->s->base.max_block;
  795.   new_left_length=new_right_length=2+nod_flag+(keys+1)/3*curr_keylength;
  796.   if (keys == 5)                /* Too few keys to balance */
  797.     new_left_length-=curr_keylength;
  798.   extra_length=nod_flag+left_length+right_length-new_left_length-new_right_length-curr_keylength;
  799.   DBUG_PRINT("info",("left_length: %d  right_length: %d  new_left_length: %d  new_right_length: %d  extra_length: %d",
  800.              left_length, right_length,
  801.              new_left_length, new_right_length,
  802.              extra_length));
  803.   putint(curr_buff,new_left_length,nod_flag);
  804.   putint(buff,new_right_length,nod_flag);
  805.   putint(extra_buff,extra_length+2,nod_flag);
  806.  
  807.   /* move first largest keys to new page  */
  808.   pos=buff+right_length-extra_length;
  809.   memcpy((byte*) extra_buff+2,pos,(size_t) extra_length);
  810.  
  811.   /* Save new parting key */
  812.   memcpy(tmp_part_key, pos-k_length,k_length);
  813.  
  814.   /* Make place for new keys */
  815.   bmove_upp((byte*) buff+new_right_length,(byte*) pos-k_length,
  816.         right_length-extra_length-k_length-2);
  817.   /* Copy keys from left page */
  818.   pos= curr_buff+new_left_length;
  819.   memcpy((byte*) buff+2,(byte*) pos+k_length,
  820.      (size_t) (length=left_length-new_left_length-k_length));
  821.   /* Copy old parting key */
  822.   memcpy((byte*) buff+2+length,father_key_pos,(size_t) k_length);
  823.  
  824.   /* Move new parting keys up */
  825.   memcpy((byte*) (right ? key : father_key_pos),pos, (size_t) k_length);
  826.   memcpy((byte*) (right ? father_key_pos : key), tmp_part_key, k_length);
  827.  
  828.   if ((new_pos=_nisam_new(info,keyinfo)) == NI_POS_ERROR)
  829.     goto err;
  830.   _nisam_kpointer(info,key+k_length,new_pos);
  831.   if (_nisam_write_keypage(info,keyinfo,(right ? new_pos : next_page),
  832.             info->buff) ||
  833.       _nisam_write_keypage(info,keyinfo,(right ? next_page : new_pos),extra_buff))
  834.     goto err;
  835.  
  836.   DBUG_RETURN(1);                /* Middle key up */
  837.  
  838. err:
  839.   DBUG_RETURN(-1);
  840. } /* _nisam_balance_page */
  841.