~drizzle-trunk/drizzle/development

/* Copyright (C) 2000-2006 MySQL AB

   This program is free software; you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License

   along with this program; if not, write to the Free Software

   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/* Write a row to a MyISAM table */

#include "fulltext.h"

#include "rt_index.h"

#define MAX_POINTER_LENGTH 8

	/* Functions declared in this file */

static int w_search(MI_INFO *info,MI_KEYDEF *keyinfo,

		    uint comp_flag, uchar *key,

		    uint key_length, my_off_t pos, uchar *father_buff,

		    uchar *father_keypos, my_off_t father_page,

		    my_bool insert_last);

static int _mi_balance_page(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *key,

			    uchar *curr_buff,uchar *father_buff,

			    uchar *father_keypos,my_off_t father_page);

static uchar *_mi_find_last_pos(MI_KEYDEF *keyinfo, uchar *page,

				uchar *key, uint *return_key_length,

				uchar **after_key);

int _mi_ck_write_tree(register MI_INFO *info, uint keynr,uchar *key,

		      uint key_length);

int _mi_ck_write_btree(register MI_INFO *info, uint keynr,uchar *key,

		       uint key_length);

	/* Write new record to database */

int mi_write(MI_INFO *info, uchar *record)

{

  MYISAM_SHARE *share=info->s;

  uint i;

  int save_errno;

  my_off_t filepos;

  uchar *buff;

  my_bool lock_tree= share->concurrent_insert;

  DBUG_ENTER("mi_write");

  DBUG_PRINT("enter",("isam: %d  data: %d",info->s->kfile,info->dfile));

  DBUG_EXECUTE_IF("myisam_pretend_crashed_table_on_usage",

                  mi_print_error(info->s, HA_ERR_CRASHED);

                  DBUG_RETURN(my_errno= HA_ERR_CRASHED););

  if (share->options & HA_OPTION_READ_ONLY_DATA)

  {

    DBUG_RETURN(my_errno=EACCES);

  }

  if (_mi_readinfo(info,F_WRLCK,1))

    DBUG_RETURN(my_errno);

  dont_break();				/* Dont allow SIGHUP or SIGINT */

#if !defined(NO_LOCKING) && defined(USE_RECORD_LOCK)

  if (!info->locked && my_lock(info->dfile,F_WRLCK,0L,F_TO_EOF,

			       MYF(MY_SEEK_NOT_DONE) | info->lock_wait))

    goto err;

#endif

  filepos= ((share->state.dellink != HA_OFFSET_ERROR &&

             !info->append_insert_at_end) ?

	    share->state.dellink :

	    info->state->data_file_length);

  if (share->base.reloc == (ha_rows) 1 &&

      share->base.records == (ha_rows) 1 &&

      info->state->records == (ha_rows) 1)

  {						/* System file */

    my_errno=HA_ERR_RECORD_FILE_FULL;

    goto err2;

  }

  if (info->state->key_file_length >= share->base.margin_key_file_length)

  {

    my_errno=HA_ERR_INDEX_FILE_FULL;

    goto err2;

  }

  if (_mi_mark_file_changed(info))

    goto err2;

  /* Calculate and check all unique constraints */

  for (i=0 ; i < share->state.header.uniques ; i++)

  {

    if (mi_check_unique(info,share->uniqueinfo+i,record,

		     mi_unique_hash(share->uniqueinfo+i,record),

		     HA_OFFSET_ERROR))

      goto err2;

  }

	/* Write all keys to indextree */

  buff=info->lastkey2;

  for (i=0 ; i < share->base.keys ; i++)

  {

    if (mi_is_key_active(share->state.key_map, i))

    {

      my_bool local_lock_tree= (lock_tree &&

                                !(info->bulk_insert &&

                                  is_tree_inited(&info->bulk_insert[i])));

      if (local_lock_tree)

      {

	rw_wrlock(&share->key_root_lock[i]);

	share->keyinfo[i].version++;

      }

      if (share->keyinfo[i].flag & HA_FULLTEXT )

      {

        if (_mi_ft_add(info,i, buff, record, filepos))

        {

	  if (local_lock_tree)

	    rw_unlock(&share->key_root_lock[i]);

          DBUG_PRINT("error",("Got error: %d on write",my_errno));

          goto err;

        }

      }

      else

      {

        if (share->keyinfo[i].ck_insert(info,i,buff,

			_mi_make_key(info,i,buff,record,filepos)))

        {

          if (local_lock_tree)

            rw_unlock(&share->key_root_lock[i]);

          DBUG_PRINT("error",("Got error: %d on write",my_errno));

          goto err;

        }

      }

      /* The above changed info->lastkey2. Inform mi_rnext_same(). */

      info->update&= ~HA_STATE_RNEXT_SAME;

      if (local_lock_tree)

        rw_unlock(&share->key_root_lock[i]);

    }

  }

  if (share->calc_checksum)

    info->checksum=(*share->calc_checksum)(info,record);

  if (!(info->opt_flag & OPT_NO_ROWS))

  {

    if ((*share->write_record)(info,record))

      goto err;

    info->state->checksum+=info->checksum;

  }

  if (share->base.auto_key)

    set_if_bigger(info->s->state.auto_increment,

                  retrieve_auto_increment(info, record));

  info->update= (HA_STATE_CHANGED | HA_STATE_AKTIV | HA_STATE_WRITTEN |

		 HA_STATE_ROW_CHANGED);

  info->state->records++;

  info->lastpos=filepos;

  myisam_log_record(MI_LOG_WRITE,info,record,filepos,0);

  VOID(_mi_writeinfo(info, WRITEINFO_UPDATE_KEYFILE));

  if (info->invalidator != 0)

  {

    DBUG_PRINT("info", ("invalidator... '%s' (update)", info->filename));

    (*info->invalidator)(info->filename);

    info->invalidator=0;

  }

  /*

    Update status of the table. We need to do so after each row write

    for the log tables, as we want the new row to become visible to

    other threads as soon as possible. We don't lock mutex here

    (as it is required by pthread memory visibility rules) as (1) it's

    not critical to use outdated share->is_log_table value (2) locking

    mutex here for every write is too expensive.

  */

  if (share->is_log_table)

    mi_update_status((void*) info);

  allow_break();				/* Allow SIGHUP & SIGINT */

  DBUG_RETURN(0);

err:

  save_errno=my_errno;

  if (my_errno == HA_ERR_FOUND_DUPP_KEY || my_errno == HA_ERR_RECORD_FILE_FULL ||

      my_errno == HA_ERR_NULL_IN_SPATIAL || my_errno == HA_ERR_OUT_OF_MEM)

  {

    if (info->bulk_insert)

    {

      uint j;

      for (j=0 ; j < share->base.keys ; j++)

        mi_flush_bulk_insert(info, j);

    }

    info->errkey= (int) i;

    while ( i-- > 0)

    {

      if (mi_is_key_active(share->state.key_map, i))

      {

	my_bool local_lock_tree= (lock_tree &&

                                  !(info->bulk_insert &&

                                    is_tree_inited(&info->bulk_insert[i])));

	if (local_lock_tree)

	  rw_wrlock(&share->key_root_lock[i]);

	if (share->keyinfo[i].flag & HA_FULLTEXT)

        {

          if (_mi_ft_del(info,i, buff,record,filepos))

	  {

	    if (local_lock_tree)

	      rw_unlock(&share->key_root_lock[i]);

            break;

	  }

        }

        else

	{

	  uint key_length=_mi_make_key(info,i,buff,record,filepos);

	  if (_mi_ck_delete(info,i,buff,key_length))

	  {

	    if (local_lock_tree)

	      rw_unlock(&share->key_root_lock[i]);

	    break;

	  }

	}

	if (local_lock_tree)

	  rw_unlock(&share->key_root_lock[i]);

      }

    }

  }

  else

  {

    mi_print_error(info->s, HA_ERR_CRASHED);

    mi_mark_crashed(info);

  }

  info->update= (HA_STATE_CHANGED | HA_STATE_WRITTEN | HA_STATE_ROW_CHANGED);

  my_errno=save_errno;

err2:

  save_errno=my_errno;

  myisam_log_record(MI_LOG_WRITE,info,record,filepos,my_errno);

  VOID(_mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE));

  allow_break();			/* Allow SIGHUP & SIGINT */

  DBUG_RETURN(my_errno=save_errno);

} /* mi_write */

	/* Write one key to btree */

int _mi_ck_write(MI_INFO *info, uint keynr, uchar *key, uint key_length)

{

  DBUG_ENTER("_mi_ck_write");

  if (info->bulk_insert && is_tree_inited(&info->bulk_insert[keynr]))

  {

    DBUG_RETURN(_mi_ck_write_tree(info, keynr, key, key_length));

  }

  else

  {

    DBUG_RETURN(_mi_ck_write_btree(info, keynr, key, key_length));

  }

} /* _mi_ck_write */

/**********************************************************************

 *                Normal insert code                                  *

 **********************************************************************/

int _mi_ck_write_btree(register MI_INFO *info, uint keynr, uchar *key,

		       uint key_length)

{

  int error;

  uint comp_flag;

  MI_KEYDEF *keyinfo=info->s->keyinfo+keynr;

  my_off_t  *root=&info->s->state.key_root[keynr];

  DBUG_ENTER("_mi_ck_write_btree");

  if (keyinfo->flag & HA_SORT_ALLOWS_SAME)

    comp_flag=SEARCH_BIGGER;			/* Put after same key */

  else if (keyinfo->flag & (HA_NOSAME|HA_FULLTEXT))

  {

    comp_flag=SEARCH_FIND | SEARCH_UPDATE;	/* No duplicates */

    if (keyinfo->flag & HA_NULL_ARE_EQUAL)

      comp_flag|= SEARCH_NULL_ARE_EQUAL;

  }

  else

    comp_flag=SEARCH_SAME;			/* Keys in rec-pos order */

  error=_mi_ck_real_write_btree(info, keyinfo, key, key_length,

                                root, comp_flag);

  if (info->ft1_to_ft2)

  {

    if (!error)

      error= _mi_ft_convert_to_ft2(info, keynr, key);

    delete_dynamic(info->ft1_to_ft2);

    my_free((uchar*)info->ft1_to_ft2, MYF(0));

    info->ft1_to_ft2=0;

  }

  DBUG_RETURN(error);

} /* _mi_ck_write_btree */

int _mi_ck_real_write_btree(MI_INFO *info, MI_KEYDEF *keyinfo,

    uchar *key, uint key_length, my_off_t *root, uint comp_flag)

{

  int error;

  DBUG_ENTER("_mi_ck_real_write_btree");

  /* key_length parameter is used only if comp_flag is SEARCH_FIND */

  if (*root == HA_OFFSET_ERROR ||

      (error=w_search(info, keyinfo, comp_flag, key, key_length,

		      *root, (uchar *) 0, (uchar*) 0,

		      (my_off_t) 0, 1)) > 0)

    error=_mi_enlarge_root(info,keyinfo,key,root);

  DBUG_RETURN(error);

} /* _mi_ck_real_write_btree */

	/* Make a new root with key as only pointer */

int _mi_enlarge_root(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,

                     my_off_t *root)

{

  uint t_length,nod_flag;

  MI_KEY_PARAM s_temp;

  MYISAM_SHARE *share=info->s;

  DBUG_ENTER("_mi_enlarge_root");

  nod_flag= (*root != HA_OFFSET_ERROR) ?  share->base.key_reflength : 0;

  _mi_kpointer(info,info->buff+2,*root); /* if nod */

  t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,(uchar*) 0,

				(uchar*) 0, (uchar*) 0, key,&s_temp);

  mi_putint(info->buff,t_length+2+nod_flag,nod_flag);

  (*keyinfo->store_key)(keyinfo,info->buff+2+nod_flag,&s_temp);

  info->buff_used=info->page_changed=1;		/* info->buff is used */

  if ((*root= _mi_new(info,keyinfo,DFLT_INIT_HITS)) == HA_OFFSET_ERROR ||

      _mi_write_keypage(info,keyinfo,*root,DFLT_INIT_HITS,info->buff))

    DBUG_RETURN(-1);

  DBUG_RETURN(0);

} /* _mi_enlarge_root */

	/*

	  Search after a position for a key and store it there

	  Returns -1 = error

		   0  = ok

		   1  = key should be stored in higher tree

	*/

static int w_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,

		    uint comp_flag, uchar *key, uint key_length, my_off_t page,

		    uchar *father_buff, uchar *father_keypos,

		    my_off_t father_page, my_bool insert_last)

{

  int error,flag;

  uint nod_flag, search_key_length;

  uchar *temp_buff,*keypos;

  uchar keybuff[MI_MAX_KEY_BUFF];

  my_bool was_last_key;

  my_off_t next_page, dupp_key_pos;

  DBUG_ENTER("w_search");

  DBUG_PRINT("enter",("page: %ld", (long) page));

  search_key_length= (comp_flag & SEARCH_FIND) ? key_length : USE_WHOLE_KEY;

  if (!(temp_buff= (uchar*) my_alloca((uint) keyinfo->block_length+

				      MI_MAX_KEY_BUFF*2)))

    DBUG_RETURN(-1);

  if (!_mi_fetch_keypage(info,keyinfo,page,DFLT_INIT_HITS,temp_buff,0))

    goto err;

  flag=(*keyinfo->bin_search)(info,keyinfo,temp_buff,key,search_key_length,

			      comp_flag, &keypos, keybuff, &was_last_key);

  nod_flag=mi_test_if_nod(temp_buff);

  if (flag == 0)

  {

    uint tmp_key_length;

	/* get position to record with duplicated key */

    tmp_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,keybuff);

    if (tmp_key_length)

      dupp_key_pos=_mi_dpos(info,0,keybuff+tmp_key_length);

    else

      dupp_key_pos= HA_OFFSET_ERROR;

    if (keyinfo->flag & HA_FULLTEXT)

    {

      uint off;

      int  subkeys;

      get_key_full_length_rdonly(off, keybuff);

      subkeys=ft_sintXkorr(keybuff+off);

      comp_flag=SEARCH_SAME;

      if (subkeys >= 0)

      {

        /* normal word, one-level tree structure */

        flag=(*keyinfo->bin_search)(info, keyinfo, temp_buff, key,

                                    USE_WHOLE_KEY, comp_flag,

                                    &keypos, keybuff, &was_last_key);

      }

      else

      {

        /* popular word. two-level tree. going down */

        my_off_t root=dupp_key_pos;

        keyinfo=&info->s->ft2_keyinfo;

        get_key_full_length_rdonly(off, key);

        key+=off;

        keypos-=keyinfo->keylength+nod_flag; /* we'll modify key entry 'in vivo' */

        error=_mi_ck_real_write_btree(info, keyinfo, key, 0,

                                      &root, comp_flag);

        _mi_dpointer(info, keypos+HA_FT_WLEN, root);

        subkeys--; /* should there be underflow protection ? */

        DBUG_ASSERT(subkeys < 0);

        ft_intXstore(keypos, subkeys);

        if (!error)

          error=_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,temp_buff);

        my_afree((uchar*) temp_buff);

        DBUG_RETURN(error);

      }

    }

    else /* not HA_FULLTEXT, normal HA_NOSAME key */

    {

      info->dupp_key_pos= dupp_key_pos;

      my_afree((uchar*) temp_buff);

      my_errno=HA_ERR_FOUND_DUPP_KEY;

      DBUG_RETURN(-1);

    }

  }

  if (flag == MI_FOUND_WRONG_KEY)

    DBUG_RETURN(-1);

  if (!was_last_key)

    insert_last=0;

  next_page=_mi_kpos(nod_flag,keypos);

  if (next_page == HA_OFFSET_ERROR ||

      (error=w_search(info, keyinfo, comp_flag, key, key_length, next_page,

		      temp_buff, keypos, page, insert_last)) >0)

  {

    error=_mi_insert(info,keyinfo,key,temp_buff,keypos,keybuff,father_buff,

		     father_keypos,father_page, insert_last);

    if (_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,temp_buff))

      goto err;

  }

  my_afree((uchar*) temp_buff);

  DBUG_RETURN(error);

err:

  my_afree((uchar*) temp_buff);

  DBUG_PRINT("exit",("Error: %d",my_errno));

  DBUG_RETURN (-1);

} /* w_search */

/*

  Insert new key.

  SYNOPSIS

    _mi_insert()

    info                        Open table information.

    keyinfo                     Key definition information.

    key                         New key.

    anc_buff                    Key page (beginning).

    key_pos                     Position in key page where to insert.

    key_buff                    Copy of previous key.

    father_buff                 parent key page for balancing.

    father_key_pos              position in parent key page for balancing.

    father_page                 position of parent key page in file.

    insert_last                 If to append at end of page.

  DESCRIPTION

    Insert new key at right of key_pos.

  RETURN

    2           if key contains key to upper level.

    0           OK.

    < 0         Error.

*/

int _mi_insert(register MI_INFO *info, register MI_KEYDEF *keyinfo,

	       uchar *key, uchar *anc_buff, uchar *key_pos, uchar *key_buff,

               uchar *father_buff, uchar *father_key_pos, my_off_t father_page,

	       my_bool insert_last)

{

  uint a_length,nod_flag;

  int t_length;

  uchar *endpos, *prev_key;

  MI_KEY_PARAM s_temp;

  DBUG_ENTER("_mi_insert");

  DBUG_PRINT("enter",("key_pos: 0x%lx", (long) key_pos));

  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,USE_WHOLE_KEY););

  nod_flag=mi_test_if_nod(anc_buff);

  a_length=mi_getint(anc_buff);

  endpos= anc_buff+ a_length;

  prev_key=(key_pos == anc_buff+2+nod_flag ? (uchar*) 0 : key_buff);

  t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,

				(key_pos == endpos ? (uchar*) 0 : key_pos),

				prev_key, prev_key,

				key,&s_temp);

#ifndef DBUG_OFF

  if (key_pos != anc_buff+2+nod_flag && (keyinfo->flag &

					 (HA_BINARY_PACK_KEY | HA_PACK_KEY)))

  {

    DBUG_DUMP("prev_key",(uchar*) key_buff,_mi_keylength(keyinfo,key_buff));

  }

  if (keyinfo->flag & HA_PACK_KEY)

  {

    DBUG_PRINT("test",("t_length: %d  ref_len: %d",

		       t_length,s_temp.ref_length));

    DBUG_PRINT("test",("n_ref_len: %d  n_length: %d  key_pos: 0x%lx",

		       s_temp.n_ref_length,s_temp.n_length, (long) s_temp.key));

  }

#endif

  if (t_length > 0)

  {

    if (t_length >= keyinfo->maxlength*2+MAX_POINTER_LENGTH)

    {

      mi_print_error(info->s, HA_ERR_CRASHED);

      my_errno=HA_ERR_CRASHED;

      DBUG_RETURN(-1);

    }

    bmove_upp((uchar*) endpos+t_length,(uchar*) endpos,(uint) (endpos-key_pos));

  }

  else

  {

    if (-t_length >= keyinfo->maxlength*2+MAX_POINTER_LENGTH)

    {

      mi_print_error(info->s, HA_ERR_CRASHED);

      my_errno=HA_ERR_CRASHED;

      DBUG_RETURN(-1);

    }

    bmove(key_pos,key_pos-t_length,(uint) (endpos-key_pos)+t_length);

  }

  (*keyinfo->store_key)(keyinfo,key_pos,&s_temp);

  a_length+=t_length;

  mi_putint(anc_buff,a_length,nod_flag);

  if (a_length <= keyinfo->block_length)

  {

    if (keyinfo->block_length - a_length < 32 &&

        keyinfo->flag & HA_FULLTEXT && key_pos == endpos &&

        info->s->base.key_reflength <= info->s->base.rec_reflength &&

        info->s->options & (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD))

    {

      /*

        Normal word. One-level tree. Page is almost full.

        Let's consider converting.

        We'll compare 'key' and the first key at anc_buff

       */

      uchar *a=key, *b=anc_buff+2+nod_flag;

      uint alen, blen, ft2len=info->s->ft2_keyinfo.keylength;

      /* the very first key on the page is always unpacked */

      DBUG_ASSERT((*b & 128) == 0);

#if HA_FT_MAXLEN >= 127

      blen= mi_uint2korr(b); b+=2;

#else

      blen= *b++;

#endif

      get_key_length(alen,a);

      DBUG_ASSERT(info->ft1_to_ft2==0);

      if (alen == blen &&

          ha_compare_text(keyinfo->seg->charset, a, alen, b, blen, 0, 0)==0)

      {

        /* yup. converting */

        info->ft1_to_ft2=(DYNAMIC_ARRAY *)

          my_malloc(sizeof(DYNAMIC_ARRAY), MYF(MY_WME));

        my_init_dynamic_array(info->ft1_to_ft2, ft2len, 300, 50);

        /*

          now, adding all keys from the page to dynarray

          if the page is a leaf (if not keys will be deleted later)

        */

        if (!nod_flag)

        {

          /* let's leave the first key on the page, though, because

             we cannot easily dispatch an empty page here */

          b+=blen+ft2len+2;

          for (a=anc_buff+a_length ; b < a ; b+=ft2len+2)

            insert_dynamic(info->ft1_to_ft2, b);

          /* fixing the page's length - it contains only one key now */

          mi_putint(anc_buff,2+blen+ft2len+2,0);

        }

        /* the rest will be done when we're back from recursion */

      }

    }

    DBUG_RETURN(0);				/* There is room on page */

  }

  /* Page is full */

  if (nod_flag)

    insert_last=0;

  if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&

      father_buff && !insert_last)

    DBUG_RETURN(_mi_balance_page(info,keyinfo,key,anc_buff,father_buff,

				 father_key_pos,father_page));

  DBUG_RETURN(_mi_split_page(info,keyinfo,key,anc_buff,key_buff, insert_last));

} /* _mi_insert */

	/* split a full page in two and assign emerging item to key */

int _mi_split_page(register MI_INFO *info, register MI_KEYDEF *keyinfo,

		   uchar *key, uchar *buff, uchar *key_buff,

		   my_bool insert_last_key)

{

  uint length,a_length,key_ref_length,t_length,nod_flag,key_length;

  uchar *key_pos,*pos, *after_key= NULL;

  my_off_t new_pos;

  MI_KEY_PARAM s_temp;

  DBUG_ENTER("mi_split_page");

  DBUG_DUMP("buff",(uchar*) buff,mi_getint(buff));

  if (info->s->keyinfo+info->lastinx == keyinfo)

    info->page_changed=1;			/* Info->buff is used */

  info->buff_used=1;

  nod_flag=mi_test_if_nod(buff);

  key_ref_length=2+nod_flag;

  if (insert_last_key)

    key_pos=_mi_find_last_pos(keyinfo,buff,key_buff, &key_length, &after_key);

  else

    key_pos=_mi_find_half_pos(nod_flag,keyinfo,buff,key_buff, &key_length,

			      &after_key);

  if (!key_pos)

    DBUG_RETURN(-1);

  length=(uint) (key_pos-buff);

  a_length=mi_getint(buff);

  mi_putint(buff,length,nod_flag);

  key_pos=after_key;

  if (nod_flag)

  {

    DBUG_PRINT("test",("Splitting nod"));

    pos=key_pos-nod_flag;

    memcpy((uchar*) info->buff+2,(uchar*) pos,(size_t) nod_flag);

  }

	/* Move middle item to key and pointer to new page */

  if ((new_pos=_mi_new(info,keyinfo,DFLT_INIT_HITS)) == HA_OFFSET_ERROR)

    DBUG_RETURN(-1);

  _mi_kpointer(info,_mi_move_key(keyinfo,key,key_buff),new_pos);

	/* Store new page */

  if (!(*keyinfo->get_key)(keyinfo,nod_flag,&key_pos,key_buff))

    DBUG_RETURN(-1);

  t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,(uchar *) 0,

				(uchar*) 0, (uchar*) 0,

				key_buff, &s_temp);

  length=(uint) ((buff+a_length)-key_pos);

  memcpy((uchar*) info->buff+key_ref_length+t_length,(uchar*) key_pos,

	 (size_t) length);

  (*keyinfo->store_key)(keyinfo,info->buff+key_ref_length,&s_temp);

  mi_putint(info->buff,length+t_length+key_ref_length,nod_flag);

  if (_mi_write_keypage(info,keyinfo,new_pos,DFLT_INIT_HITS,info->buff))

    DBUG_RETURN(-1);

  DBUG_DUMP("key",(uchar*) key,_mi_keylength(keyinfo,key));

  DBUG_RETURN(2);				/* Middle key up */

} /* _mi_split_page */

	/*

	  Calculate how to much to move to split a page in two

	  Returns pointer to start of key.

	  key will contain the key.

	  return_key_length will contain the length of key

	  after_key will contain the position to where the next key starts

	*/

uchar *_mi_find_half_pos(uint nod_flag, MI_KEYDEF *keyinfo, uchar *page,

			 uchar *key, uint *return_key_length,

			 uchar **after_key)

{

  uint keys,length,key_ref_length;

  uchar *end,*lastpos;

  DBUG_ENTER("_mi_find_half_pos");

  key_ref_length=2+nod_flag;

  length=mi_getint(page)-key_ref_length;

  page+=key_ref_length;

  if (!(keyinfo->flag &

	(HA_PACK_KEY | HA_SPACE_PACK_USED | HA_VAR_LENGTH_KEY |

	 HA_BINARY_PACK_KEY)))

  {

    key_ref_length=keyinfo->keylength+nod_flag;

    keys=length/(key_ref_length*2);

    *return_key_length=keyinfo->keylength;

    end=page+keys*key_ref_length;

    *after_key=end+key_ref_length;

    memcpy(key,end,key_ref_length);

    DBUG_RETURN(end);

  }

  end=page+length/2-key_ref_length;		/* This is aprox. half */

  *key='\0';

  do

  {

    lastpos=page;

    if (!(length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key)))

      DBUG_RETURN(0);

  } while (page < end);

  *return_key_length=length;

  *after_key=page;

  DBUG_PRINT("exit",("returns: 0x%lx  page: 0x%lx  half: 0x%lx",

                     (long) lastpos, (long) page, (long) end));

  DBUG_RETURN(lastpos);

} /* _mi_find_half_pos */

	/*

	  Split buffer at last key

	  Returns pointer to the start of the key before the last key

	  key will contain the last key

	*/

static uchar *_mi_find_last_pos(MI_KEYDEF *keyinfo, uchar *page,

				uchar *key, uint *return_key_length,

				uchar **after_key)

{

  uint keys, length, last_length, key_ref_length;

  uchar *end, *lastpos, *prevpos= NULL;