← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/myisam/mi_delete.cc

  • Committer: Padraig O'Sullivan
  • Date: 2009-09-13 01:03:01 UTC
  • mto: (1126.9.2 captain-20090915-01)
  • mto: This revision was merged to the branch mainline in revision 1133.
  • Revision ID: osullivan.padraig@gmail.com-20090913010301-tcvvezipx1124acy
Added calls to the dtrace delete begin/end probes.

Show diffs side-by-side

added added

removed removed

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