← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/myisam/mi_delete.c

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/myisam/mi_delete.c
 
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 "fulltext.h"
 
19
#include "rt_index.h"
 
20
 
 
21
static int d_search(MI_INFO *info,MI_KEYDEF *keyinfo,uint comp_flag,
 
22
                    uchar *key,uint key_length,my_off_t page,uchar *anc_buff);
 
23
static int del(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *key,uchar *anc_buff,
 
24
               my_off_t leaf_page,uchar *leaf_buff,uchar *keypos,
 
25
               my_off_t next_block,uchar *ret_key);
 
26
static int underflow(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *anc_buff,
 
27
                     my_off_t leaf_page,uchar *leaf_buff,uchar *keypos);
 
28
static uint remove_key(MI_KEYDEF *keyinfo,uint nod_flag,uchar *keypos,
 
29
                       uchar *lastkey,uchar *page_end,
 
30
                       my_off_t *next_block);
 
31
static int _mi_ck_real_delete(register MI_INFO *info,MI_KEYDEF *keyinfo,
 
32
                              uchar *key, uint key_length, my_off_t *root);
 
33
 
 
34
 
 
35
int mi_delete(MI_INFO *info,const uchar *record)
 
36
{
 
37
  uint i;
 
38
  uchar *old_key;
 
39
  int save_errno;
 
40
  char lastpos[8];
 
41
 
 
42
  MYISAM_SHARE *share=info->s;
 
43
  DBUG_ENTER("mi_delete");
 
44
 
 
45
        /* Test if record is in datafile */
 
46
 
 
47
  DBUG_EXECUTE_IF("myisam_pretend_crashed_table_on_usage",
 
48
                  mi_print_error(info->s, HA_ERR_CRASHED);
 
49
                  DBUG_RETURN(my_errno= HA_ERR_CRASHED););
 
50
  DBUG_EXECUTE_IF("my_error_test_undefined_error",
 
51
                  mi_print_error(info->s, INT_MAX);
 
52
                  DBUG_RETURN(my_errno= INT_MAX););
 
53
  if (!(info->update & HA_STATE_AKTIV))
 
54
  {
 
55
    DBUG_RETURN(my_errno=HA_ERR_KEY_NOT_FOUND); /* No database read */
 
56
  }
 
57
  if (share->options & HA_OPTION_READ_ONLY_DATA)
 
58
  {
 
59
    DBUG_RETURN(my_errno=EACCES);
 
60
  }
 
61
  if (_mi_readinfo(info,F_WRLCK,1))
 
62
    DBUG_RETURN(my_errno);
 
63
  if (info->s->calc_checksum)
 
64
    info->checksum=(*info->s->calc_checksum)(info,record);
 
65
  if ((*share->compare_record)(info,record))
 
66
    goto err;                           /* Error on read-check */
 
67
 
 
68
  if (_mi_mark_file_changed(info))
 
69
    goto err;
 
70
 
 
71
        /* Remove all keys from the .ISAM file */
 
72
 
 
73
  old_key=info->lastkey2;
 
74
  for (i=0 ; i < share->base.keys ; i++ )
 
75
  {
 
76
    if (mi_is_key_active(info->s->state.key_map, i))
 
77
    {
 
78
      info->s->keyinfo[i].version++;
 
79
      if (info->s->keyinfo[i].flag & HA_FULLTEXT )
 
80
      {
 
81
        if (_mi_ft_del(info,i, old_key,record,info->lastpos))
 
82
          goto err;
 
83
      }
 
84
      else
 
85
      {
 
86
        if (info->s->keyinfo[i].ck_delete(info,i,old_key,
 
87
                _mi_make_key(info,i,old_key,record,info->lastpos)))
 
88
          goto err;
 
89
      }
 
90
      /* The above changed info->lastkey2. Inform mi_rnext_same(). */
 
91
      info->update&= ~HA_STATE_RNEXT_SAME;
 
92
    }
 
93
  }
 
94
 
 
95
  if ((*share->delete_record)(info))
 
96
    goto err;                           /* Remove record from database */
 
97
  info->state->checksum-=info->checksum;
 
98
 
 
99
  info->update= HA_STATE_CHANGED+HA_STATE_DELETED+HA_STATE_ROW_CHANGED;
 
100
  info->state->records--;
 
101
 
 
102
  mi_sizestore(lastpos,info->lastpos);
 
103
  myisam_log_command(MI_LOG_DELETE,info,(uchar*) lastpos,sizeof(lastpos),0);
 
104
  VOID(_mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE));
 
105
  allow_break();                        /* Allow SIGHUP & SIGINT */
 
106
  if (info->invalidator != 0)
 
107
  {
 
108
    DBUG_PRINT("info", ("invalidator... '%s' (delete)", info->filename));
 
109
    (*info->invalidator)(info->filename);
 
110
    info->invalidator=0;
 
111
  }
 
112
  DBUG_RETURN(0);
 
113
 
 
114
err:
 
115
  save_errno=my_errno;
 
116
  mi_sizestore(lastpos,info->lastpos);
 
117
  myisam_log_command(MI_LOG_DELETE,info,(uchar*) lastpos, sizeof(lastpos),0);
 
118
  if (save_errno != HA_ERR_RECORD_CHANGED)
 
119
  {
 
120
    mi_print_error(info->s, HA_ERR_CRASHED);
 
121
    mi_mark_crashed(info);              /* mark table crashed */
 
122
  }
 
123
  VOID(_mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE));
 
124
  info->update|=HA_STATE_WRITTEN;       /* Buffer changed */
 
125
  allow_break();                        /* Allow SIGHUP & SIGINT */
 
126
  my_errno=save_errno;
 
127
  if (save_errno == HA_ERR_KEY_NOT_FOUND)
 
128
  {
 
129
    mi_print_error(info->s, HA_ERR_CRASHED);
 
130
    my_errno=HA_ERR_CRASHED;
 
131
  }
 
132
 
 
133
  DBUG_RETURN(my_errno);
 
134
} /* mi_delete */
 
135
 
 
136
 
 
137
        /* Remove a key from the btree index */
 
138
 
 
139
int _mi_ck_delete(register MI_INFO *info, uint keynr, uchar *key,
 
140
                  uint key_length)
 
141
{
 
142
  return _mi_ck_real_delete(info, info->s->keyinfo+keynr, key, key_length,
 
143
                            &info->s->state.key_root[keynr]);
 
144
} /* _mi_ck_delete */
 
145
 
 
146
 
 
147
static int _mi_ck_real_delete(register MI_INFO *info, MI_KEYDEF *keyinfo,
 
148
                              uchar *key, uint key_length, my_off_t *root)
 
149
{
 
150
  int error;
 
151
  uint nod_flag;
 
152
  my_off_t old_root;
 
153
  uchar *root_buff;
 
154
  DBUG_ENTER("_mi_ck_real_delete");
 
155
 
 
156
  if ((old_root=*root) == HA_OFFSET_ERROR)
 
157
  {
 
158
    mi_print_error(info->s, HA_ERR_CRASHED);
 
159
    DBUG_RETURN(my_errno=HA_ERR_CRASHED);
 
160
  }
 
161
  if (!(root_buff= (uchar*) my_alloca((uint) keyinfo->block_length+
 
162
                                      MI_MAX_KEY_BUFF*2)))
 
163
  {
 
164
    DBUG_PRINT("error",("Couldn't allocate memory"));
 
165
    DBUG_RETURN(my_errno=ENOMEM);
 
166
  }
 
167
  DBUG_PRINT("info",("root_page: %ld", (long) old_root));
 
168
  if (!_mi_fetch_keypage(info,keyinfo,old_root,DFLT_INIT_HITS,root_buff,0))
 
169
  {
 
170
    error= -1;
 
171
    goto err;
 
172
  }
 
173
  if ((error=d_search(info,keyinfo,
 
174
                      (keyinfo->flag & HA_FULLTEXT ? SEARCH_FIND | SEARCH_UPDATE
 
175
                                                   : SEARCH_SAME),
 
176
                       key,key_length,old_root,root_buff)) >0)
 
177
  {
 
178
    if (error == 2)
 
179
    {
 
180
      DBUG_PRINT("test",("Enlarging of root when deleting"));
 
181
      error=_mi_enlarge_root(info,keyinfo,key,root);
 
182
    }
 
183
    else /* error == 1 */
 
184
    {
 
185
      if (mi_getint(root_buff) <= (nod_flag=mi_test_if_nod(root_buff))+3)
 
186
      {
 
187
        error=0;
 
188
        if (nod_flag)
 
189
          *root=_mi_kpos(nod_flag,root_buff+2+nod_flag);
 
190
        else
 
191
          *root=HA_OFFSET_ERROR;
 
192
        if (_mi_dispose(info,keyinfo,old_root,DFLT_INIT_HITS))
 
193
          error= -1;
 
194
      }
 
195
      else
 
196
        error=_mi_write_keypage(info,keyinfo,old_root,
 
197
                                DFLT_INIT_HITS,root_buff);
 
198
    }
 
199
  }
 
200
err:
 
201
  my_afree((uchar*) root_buff);
 
202
  DBUG_PRINT("exit",("Return: %d",error));
 
203
  DBUG_RETURN(error);
 
204
} /* _mi_ck_real_delete */
 
205
 
 
206
 
 
207
        /*
 
208
        ** Remove key below key root
 
209
        ** Return values:
 
210
        ** 1 if there are less buffers;  In this case anc_buff is not saved
 
211
        ** 2 if there are more buffers
 
212
        ** -1 on errors
 
213
        */
 
214
 
 
215
static int d_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 
216
                    uint comp_flag, uchar *key, uint key_length,
 
217
                    my_off_t page, uchar *anc_buff)
 
218
{
 
219
  int flag,ret_value,save_flag;
 
220
  uint length,nod_flag,search_key_length;
 
221
  my_bool last_key;
 
222
  uchar *leaf_buff,*keypos;
 
223
  my_off_t leaf_page= 0, next_block;
 
224
  uchar lastkey[MI_MAX_KEY_BUFF];
 
225
  DBUG_ENTER("d_search");
 
226
  DBUG_DUMP("page",(uchar*) anc_buff,mi_getint(anc_buff));
 
227
 
 
228
  search_key_length= (comp_flag & SEARCH_FIND) ? key_length : USE_WHOLE_KEY;
 
229
  flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key, search_key_length,
 
230
                              comp_flag, &keypos, lastkey, &last_key);
 
231
  if (flag == MI_FOUND_WRONG_KEY)
 
232
  {
 
233
    DBUG_PRINT("error",("Found wrong key"));
 
234
    DBUG_RETURN(-1);
 
235
  }
 
236
  nod_flag=mi_test_if_nod(anc_buff);
 
237
 
 
238
  if (!flag && keyinfo->flag & HA_FULLTEXT)
 
239
  {
 
240
    uint off;
 
241
    int  subkeys;
 
242
 
 
243
    get_key_full_length_rdonly(off, lastkey);
 
244
    subkeys=ft_sintXkorr(lastkey+off);
 
245
    DBUG_ASSERT(info->ft1_to_ft2==0 || subkeys >=0);
 
246
    comp_flag=SEARCH_SAME;
 
247
    if (subkeys >= 0)
 
248
    {
 
249
      /* normal word, one-level tree structure */
 
250
      if (info->ft1_to_ft2)
 
251
      {
 
252
        /* we're in ft1->ft2 conversion mode. Saving key data */
 
253
        insert_dynamic(info->ft1_to_ft2, (lastkey+off));
 
254
      }
 
255
      else
 
256
      {
 
257
        /* we need exact match only if not in ft1->ft2 conversion mode */
 
258
        flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key,USE_WHOLE_KEY,
 
259
                                    comp_flag, &keypos, lastkey, &last_key);
 
260
      }
 
261
      /* fall through to normal delete */
 
262
    }
 
263
    else
 
264
    {
 
265
      /* popular word. two-level tree. going down */
 
266
      uint tmp_key_length;
 
267
      my_off_t root;
 
268
      uchar *kpos=keypos;
 
269
 
 
270
      if (!(tmp_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&kpos,lastkey)))
 
271
      {
 
272
        mi_print_error(info->s, HA_ERR_CRASHED);
 
273
        my_errno= HA_ERR_CRASHED;
 
274
        DBUG_RETURN(-1);
 
275
      }
 
276
      root=_mi_dpos(info,nod_flag,kpos);
 
277
      if (subkeys == -1)
 
278
      {
 
279
        /* the last entry in sub-tree */
 
280
        if (_mi_dispose(info, keyinfo, root,DFLT_INIT_HITS))
 
281
          DBUG_RETURN(-1);
 
282
        /* fall through to normal delete */
 
283
      }
 
284
      else
 
285
      {
 
286
        keyinfo=&info->s->ft2_keyinfo;
 
287
        kpos-=keyinfo->keylength+nod_flag; /* we'll modify key entry 'in vivo' */
 
288
        get_key_full_length_rdonly(off, key);
 
289
        key+=off;
 
290
        ret_value=_mi_ck_real_delete(info, &info->s->ft2_keyinfo,
 
291
            key, HA_FT_WLEN, &root);
 
292
        _mi_dpointer(info, kpos+HA_FT_WLEN, root);
 
293
        subkeys++;
 
294
        ft_intXstore(kpos, subkeys);
 
295
        if (!ret_value)
 
296
          ret_value=_mi_write_keypage(info,keyinfo,page,
 
297
                                      DFLT_INIT_HITS,anc_buff);
 
298
        DBUG_PRINT("exit",("Return: %d",ret_value));
 
299
        DBUG_RETURN(ret_value);
 
300
      }
 
301
    }
 
302
  }
 
303
  leaf_buff= 0;
 
304
  if (nod_flag)
 
305
  {
 
306
    leaf_page=_mi_kpos(nod_flag,keypos);
 
307
    if (!(leaf_buff= (uchar*) my_alloca((uint) keyinfo->block_length+
 
308
                                        MI_MAX_KEY_BUFF*2)))
 
309
    {
 
310
      DBUG_PRINT("error",("Couldn't allocate memory"));
 
311
      my_errno=ENOMEM;
 
312
      DBUG_PRINT("exit",("Return: %d",-1));
 
313
      DBUG_RETURN(-1);
 
314
    }
 
315
    if (!_mi_fetch_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff,0))
 
316
      goto err;
 
317
  }
 
318
 
 
319
  if (flag != 0)
 
320
  {
 
321
    if (!nod_flag)
 
322
    {
 
323
      DBUG_PRINT("error",("Didn't find key"));
 
324
      mi_print_error(info->s, HA_ERR_CRASHED);
 
325
      my_errno=HA_ERR_CRASHED;          /* This should newer happend */
 
326
      goto err;
 
327
    }
 
328
    save_flag=0;
 
329
    ret_value=d_search(info,keyinfo,comp_flag,key,key_length,
 
330
                       leaf_page,leaf_buff);
 
331
  }
 
332
  else
 
333
  {                                             /* Found key */
 
334
    uint tmp;
 
335
    length=mi_getint(anc_buff);
 
336
    if (!(tmp= remove_key(keyinfo,nod_flag,keypos,lastkey,anc_buff+length,
 
337
                          &next_block)))
 
338
      goto err;
 
339
 
 
340
    length-= tmp;
 
341
 
 
342
    mi_putint(anc_buff,length,nod_flag);
 
343
    if (!nod_flag)
 
344
    {                                           /* On leaf page */
 
345
      if (_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,anc_buff))
 
346
      {
 
347
        DBUG_PRINT("exit",("Return: %d",-1));
 
348
        DBUG_RETURN(-1);
 
349
      }
 
350
      /* Page will be update later if we return 1 */
 
351
      DBUG_RETURN(test(length <= (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
 
352
                                  (uint) keyinfo->underflow_block_length)));
 
353
    }
 
354
    save_flag=1;
 
355
    ret_value=del(info,keyinfo,key,anc_buff,leaf_page,leaf_buff,keypos,
 
356
                  next_block,lastkey);
 
357
  }
 
358
  if (ret_value >0)
 
359
  {
 
360
    save_flag=1;
 
361
    if (ret_value == 1)
 
362
      ret_value= underflow(info,keyinfo,anc_buff,leaf_page,leaf_buff,keypos);
 
363
    else
 
364
    {                           /* This happens only with packed keys */
 
365
      DBUG_PRINT("test",("Enlarging of key when deleting"));
 
366
      if (!_mi_get_last_key(info,keyinfo,anc_buff,lastkey,keypos,&length))
 
367
      {
 
368
        goto err;
 
369
      }
 
370
      ret_value=_mi_insert(info,keyinfo,key,anc_buff,keypos,lastkey,
 
371
                           (uchar*) 0,(uchar*) 0,(my_off_t) 0,(my_bool) 0);
 
372
    }
 
373
  }
 
374
  if (ret_value == 0 && mi_getint(anc_buff) > keyinfo->block_length)
 
375
  {
 
376
    save_flag=1;
 
377
    ret_value=_mi_split_page(info,keyinfo,key,anc_buff,lastkey,0) | 2;
 
378
  }
 
379
  if (save_flag && ret_value != 1)
 
380
    ret_value|=_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,anc_buff);
 
381
  else
 
382
  {
 
383
    DBUG_DUMP("page",(uchar*) anc_buff,mi_getint(anc_buff));
 
384
  }
 
385
  my_afree((uchar*) leaf_buff);
 
386
  DBUG_PRINT("exit",("Return: %d",ret_value));
 
387
  DBUG_RETURN(ret_value);
 
388
 
 
389
err:
 
390
  my_afree((uchar*) leaf_buff);
 
391
  DBUG_PRINT("exit",("Error: %d",my_errno));
 
392
  DBUG_RETURN (-1);
 
393
} /* d_search */
 
394
 
 
395
 
 
396
        /* Remove a key that has a page-reference */
 
397
 
 
398
static int del(register MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *key,
 
399
               uchar *anc_buff, my_off_t leaf_page, uchar *leaf_buff,
 
400
               uchar *keypos,           /* Pos to where deleted key was */
 
401
               my_off_t next_block,
 
402
               uchar *ret_key)          /* key before keypos in anc_buff */
 
403
{
 
404
  int ret_value,length;
 
405
  uint a_length,nod_flag,tmp;
 
406
  my_off_t next_page;
 
407
  uchar keybuff[MI_MAX_KEY_BUFF],*endpos,*next_buff,*key_start, *prev_key;
 
408
  MYISAM_SHARE *share=info->s;
 
409
  MI_KEY_PARAM s_temp;
 
410
  DBUG_ENTER("del");
 
411
  DBUG_PRINT("enter",("leaf_page: %ld  keypos: 0x%lx", (long) leaf_page,
 
412
                      (ulong) keypos));
 
413
  DBUG_DUMP("leaf_buff",(uchar*) leaf_buff,mi_getint(leaf_buff));
 
414
 
 
415
  endpos=leaf_buff+mi_getint(leaf_buff);
 
416
  if (!(key_start=_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
 
417
                                   &tmp)))
 
418
    DBUG_RETURN(-1);
 
419
 
 
420
  if ((nod_flag=mi_test_if_nod(leaf_buff)))
 
421
  {
 
422
    next_page= _mi_kpos(nod_flag,endpos);
 
423
    if (!(next_buff= (uchar*) my_alloca((uint) keyinfo->block_length+
 
424
                                        MI_MAX_KEY_BUFF*2)))
 
425
      DBUG_RETURN(-1);
 
426
    if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,next_buff,0))
 
427
      ret_value= -1;
 
428
    else
 
429
    {
 
430
      DBUG_DUMP("next_page",(uchar*) next_buff,mi_getint(next_buff));
 
431
      if ((ret_value=del(info,keyinfo,key,anc_buff,next_page,next_buff,
 
432
                         keypos,next_block,ret_key)) >0)
 
433
      {
 
434
        endpos=leaf_buff+mi_getint(leaf_buff);
 
435
        if (ret_value == 1)
 
436
        {
 
437
          ret_value=underflow(info,keyinfo,leaf_buff,next_page,
 
438
                              next_buff,endpos);
 
439
          if (ret_value == 0 && mi_getint(leaf_buff) > keyinfo->block_length)
 
440
          {
 
441
            ret_value=_mi_split_page(info,keyinfo,key,leaf_buff,ret_key,0) | 2;
 
442
          }
 
443
        }
 
444
        else
 
445
        {
 
446
          DBUG_PRINT("test",("Inserting of key when deleting"));
 
447
          if (!_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
 
448
                                &tmp))
 
449
            goto err;
 
450
          ret_value=_mi_insert(info,keyinfo,key,leaf_buff,endpos,keybuff,
 
451
                               (uchar*) 0,(uchar*) 0,(my_off_t) 0,0);
 
452
        }
 
453
      }
 
454
      if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
 
455
        goto err;
 
456
    }
 
457
    my_afree((uchar*) next_buff);
 
458
    DBUG_RETURN(ret_value);
 
459
  }
 
460
 
 
461
        /* Remove last key from leaf page */
 
462
 
 
463
  mi_putint(leaf_buff,key_start-leaf_buff,nod_flag);
 
464
  if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
 
465
    goto err;
 
466
 
 
467
        /* Place last key in ancestor page on deleted key position */
 
468
 
 
469
  a_length=mi_getint(anc_buff);
 
470
  endpos=anc_buff+a_length;
 
471
  if (keypos != anc_buff+2+share->base.key_reflength &&
 
472
      !_mi_get_last_key(info,keyinfo,anc_buff,ret_key,keypos,&tmp))
 
473
    goto err;
 
474
  prev_key=(keypos == anc_buff+2+share->base.key_reflength ?
 
475
            0 : ret_key);
 
476
  length=(*keyinfo->pack_key)(keyinfo,share->base.key_reflength,
 
477
                              keypos == endpos ? (uchar*) 0 : keypos,
 
478
                              prev_key, prev_key,
 
479
                              keybuff,&s_temp);
 
480
  if (length > 0)
 
481
    bmove_upp((uchar*) endpos+length,(uchar*) endpos,(uint) (endpos-keypos));
 
482
  else
 
483
    bmove(keypos,keypos-length, (int) (endpos-keypos)+length);
 
484
  (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
 
485
  /* Save pointer to next leaf */
 
486
  if (!(*keyinfo->get_key)(keyinfo,share->base.key_reflength,&keypos,ret_key))
 
487
    goto err;
 
488
  _mi_kpointer(info,keypos - share->base.key_reflength,next_block);
 
489
  mi_putint(anc_buff,a_length+length,share->base.key_reflength);
 
490
 
 
491
  DBUG_RETURN( mi_getint(leaf_buff) <=
 
492
               (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
 
493
                (uint) keyinfo->underflow_block_length));
 
494
err:
 
495
  DBUG_RETURN(-1);
 
496
} /* del */
 
497
 
 
498
 
 
499
        /* Balances adjacent pages if underflow occours */
 
500
 
 
501
static int underflow(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 
502
                     uchar *anc_buff,
 
503
                     my_off_t leaf_page,/* Ancestor page and underflow page */
 
504
                     uchar *leaf_buff,
 
505
                     uchar *keypos)     /* Position to pos after key */
 
506
{
 
507
  int t_length;
 
508
  uint length,anc_length,buff_length,leaf_length,p_length,s_length,nod_flag,
 
509
       key_reflength,key_length;
 
510
  my_off_t next_page;
 
511
  uchar anc_key[MI_MAX_KEY_BUFF],leaf_key[MI_MAX_KEY_BUFF],
 
512
        *buff,*endpos,*next_keypos,*anc_pos,*half_pos,*temp_pos,*prev_key,
 
513
        *after_key;
 
514
  MI_KEY_PARAM s_temp;
 
515
  MYISAM_SHARE *share=info->s;
 
516
  DBUG_ENTER("underflow");
 
517
  DBUG_PRINT("enter",("leaf_page: %ld  keypos: 0x%lx",(long) leaf_page,
 
518
                      (ulong) keypos));
 
519
  DBUG_DUMP("anc_buff",(uchar*) anc_buff,mi_getint(anc_buff));
 
520
  DBUG_DUMP("leaf_buff",(uchar*) leaf_buff,mi_getint(leaf_buff));
 
521
 
 
522
  buff=info->buff;
 
523
  info->buff_used=1;
 
524
  next_keypos=keypos;
 
525
  nod_flag=mi_test_if_nod(leaf_buff);
 
526
  p_length=nod_flag+2;
 
527
  anc_length=mi_getint(anc_buff);
 
528
  leaf_length=mi_getint(leaf_buff);
 
529
  key_reflength=share->base.key_reflength;
 
530
  if (info->s->keyinfo+info->lastinx == keyinfo)
 
531
    info->page_changed=1;
 
532
 
 
533
  if ((keypos < anc_buff+anc_length && (info->state->records & 1)) ||
 
534
      keypos == anc_buff+2+key_reflength)
 
535
  {                                     /* Use page right of anc-page */
 
536
    DBUG_PRINT("test",("use right page"));
 
537
 
 
538
    if (keyinfo->flag & HA_BINARY_PACK_KEY)
 
539
    {
 
540
      if (!(next_keypos=_mi_get_key(info, keyinfo,
 
541
                                    anc_buff, buff, keypos, &length)))
 
542
        goto err;
 
543
    }
 
544
    else
 
545
    {
 
546
      /* Got to end of found key */
 
547
      buff[0]=buff[1]=0;        /* Avoid length error check if packed key */
 
548
      if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
 
549
                               buff))
 
550
      goto err;
 
551
    }
 
552
    next_page= _mi_kpos(key_reflength,next_keypos);
 
553
    if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff,0))
 
554
      goto err;
 
555
    buff_length=mi_getint(buff);
 
556
    DBUG_DUMP("next",(uchar*) buff,buff_length);
 
557
 
 
558
    /* find keys to make a big key-page */
 
559
    bmove((uchar*) next_keypos-key_reflength,(uchar*) buff+2,
 
560
          key_reflength);
 
561
    if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_key,next_keypos,&length)
 
562
        || !_mi_get_last_key(info,keyinfo,leaf_buff,leaf_key,
 
563
                             leaf_buff+leaf_length,&length))
 
564
      goto err;
 
565
 
 
566
    /* merge pages and put parting key from anc_buff between */
 
567
    prev_key=(leaf_length == p_length ? (uchar*) 0 : leaf_key);
 
568
    t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,buff+p_length,
 
569
                                  prev_key, prev_key,
 
570
                                  anc_key, &s_temp);
 
571
    length=buff_length-p_length;
 
572
    endpos=buff+length+leaf_length+t_length;
 
573
    /* buff will always be larger than before !*/
 
574
    bmove_upp((uchar*) endpos, (uchar*) buff+buff_length,length);
 
575
    memcpy((uchar*) buff, (uchar*) leaf_buff,(size_t) leaf_length);
 
576
    (*keyinfo->store_key)(keyinfo,buff+leaf_length,&s_temp);
 
577
    buff_length=(uint) (endpos-buff);
 
578
    mi_putint(buff,buff_length,nod_flag);
 
579
 
 
580
    /* remove key from anc_buff */
 
581
 
 
582
    if (!(s_length=remove_key(keyinfo,key_reflength,keypos,anc_key,
 
583
                              anc_buff+anc_length,(my_off_t *) 0)))
 
584
      goto err;
 
585
 
 
586
    anc_length-=s_length;
 
587
    mi_putint(anc_buff,anc_length,key_reflength);
 
588
 
 
589
    if (buff_length <= keyinfo->block_length)
 
590
    {                                           /* Keys in one page */
 
591
      memcpy((uchar*) leaf_buff,(uchar*) buff,(size_t) buff_length);
 
592
      if (_mi_dispose(info,keyinfo,next_page,DFLT_INIT_HITS))
 
593
       goto err;
 
594
    }
 
595
    else
 
596
    {                                           /* Page is full */
 
597
      endpos=anc_buff+anc_length;
 
598
      DBUG_PRINT("test",("anc_buff: 0x%lx  endpos: 0x%lx",
 
599
                         (long) anc_buff, (long) endpos));
 
600
      if (keypos != anc_buff+2+key_reflength &&
 
601
          !_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length))
 
602
        goto err;
 
603
      if (!(half_pos=_mi_find_half_pos(nod_flag, keyinfo, buff, leaf_key,
 
604
                                       &key_length, &after_key)))
 
605
        goto err;
 
606
      length=(uint) (half_pos-buff);
 
607
      memcpy((uchar*) leaf_buff,(uchar*) buff,(size_t) length);
 
608
      mi_putint(leaf_buff,length,nod_flag);
 
609
 
 
610
      /* Correct new keypointer to leaf_page */
 
611
      half_pos=after_key;
 
612
      _mi_kpointer(info,leaf_key+key_length,next_page);
 
613
      /* Save key in anc_buff */
 
614
      prev_key=(keypos == anc_buff+2+key_reflength ? (uchar*) 0 : anc_key),
 
615
      t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
 
616
                                    (keypos == endpos ? (uchar*) 0 :
 
617
                                     keypos),
 
618
                                    prev_key, prev_key,
 
619
                                    leaf_key, &s_temp);
 
620
      if (t_length >= 0)
 
621
        bmove_upp((uchar*) endpos+t_length,(uchar*) endpos,
 
622
                  (uint) (endpos-keypos));
 
623
      else
 
624
        bmove(keypos,keypos-t_length,(uint) (endpos-keypos)+t_length);
 
625
      (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
 
626
      mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
 
627
 
 
628
        /* Store key first in new page */
 
629
      if (nod_flag)
 
630
        bmove((uchar*) buff+2,(uchar*) half_pos-nod_flag,(size_t) nod_flag);
 
631
      if (!(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key))
 
632
        goto err;
 
633
      t_length=(int) (*keyinfo->pack_key)(keyinfo, nod_flag, (uchar*) 0,
 
634
                                          (uchar*) 0, (uchar *) 0,
 
635
                                          leaf_key, &s_temp);
 
636
      /* t_length will always be > 0 for a new page !*/
 
637
      length=(uint) ((buff+mi_getint(buff))-half_pos);
 
638
      bmove((uchar*) buff+p_length+t_length,(uchar*) half_pos,(size_t) length);
 
639
      (*keyinfo->store_key)(keyinfo,buff+p_length,&s_temp);
 
640
      mi_putint(buff,length+t_length+p_length,nod_flag);
 
641
 
 
642
      if (_mi_write_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff))
 
643
        goto err;
 
644
    }
 
645
    if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
 
646
      goto err;
 
647
    DBUG_RETURN(anc_length <= ((info->quick_mode ? MI_MIN_BLOCK_LENGTH :
 
648
                                (uint) keyinfo->underflow_block_length)));
 
649
  }
 
650
 
 
651
  DBUG_PRINT("test",("use left page"));
 
652
 
 
653
  keypos=_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length);
 
654
  if (!keypos)
 
655
    goto err;
 
656
  next_page= _mi_kpos(key_reflength,keypos);
 
657
  if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff,0))
 
658
      goto err;
 
659
  buff_length=mi_getint(buff);
 
660
  endpos=buff+buff_length;
 
661
  DBUG_DUMP("prev",(uchar*) buff,buff_length);
 
662
 
 
663
  /* find keys to make a big key-page */
 
664
  bmove((uchar*) next_keypos - key_reflength,(uchar*) leaf_buff+2,
 
665
        key_reflength);
 
666
  next_keypos=keypos;
 
667
  if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
 
668
                           anc_key))
 
669
    goto err;
 
670
  if (!_mi_get_last_key(info,keyinfo,buff,leaf_key,endpos,&length))
 
671
    goto err;
 
672
 
 
673
  /* merge pages and put parting key from anc_buff between */
 
674
  prev_key=(leaf_length == p_length ? (uchar*) 0 : leaf_key);
 
675
  t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,
 
676
                                (leaf_length == p_length ?
 
677
                                 (uchar*) 0 : leaf_buff+p_length),
 
678
                                prev_key, prev_key,
 
679
                                anc_key, &s_temp);
 
680
  if (t_length >= 0)
 
681
    bmove((uchar*) endpos+t_length,(uchar*) leaf_buff+p_length,
 
682
            (size_t) (leaf_length-p_length));
 
683
  else                                          /* We gained space */
 
684
    bmove((uchar*) endpos,(uchar*) leaf_buff+((int) p_length-t_length),
 
685
          (size_t) (leaf_length-p_length+t_length));
 
686
 
 
687
  (*keyinfo->store_key)(keyinfo,endpos,&s_temp);
 
688
  buff_length=buff_length+leaf_length-p_length+t_length;
 
689
  mi_putint(buff,buff_length,nod_flag);
 
690
 
 
691
  /* remove key from anc_buff */
 
692
  if (!(s_length= remove_key(keyinfo,key_reflength,keypos,anc_key,
 
693
                             anc_buff+anc_length,(my_off_t *) 0)))
 
694
    goto err;
 
695
 
 
696
  anc_length-=s_length;
 
697
  mi_putint(anc_buff,anc_length,key_reflength);
 
698
 
 
699
  if (buff_length <= keyinfo->block_length)
 
700
  {                                             /* Keys in one page */
 
701
    if (_mi_dispose(info,keyinfo,leaf_page,DFLT_INIT_HITS))
 
702
      goto err;
 
703
  }
 
704
  else
 
705
  {                                             /* Page is full */
 
706
    if (keypos == anc_buff+2+key_reflength)
 
707
      anc_pos=0;                                /* First key */
 
708
    else if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_pos=anc_key,keypos,
 
709
                               &length))
 
710
      goto err;
 
711
    endpos=_mi_find_half_pos(nod_flag,keyinfo,buff,leaf_key,
 
712
                             &key_length, &half_pos);
 
713
    if (!endpos)
 
714
      goto err;
 
715
    _mi_kpointer(info,leaf_key+key_length,leaf_page);
 
716
    /* Save key in anc_buff */
 
717
    DBUG_DUMP("anc_buff",(uchar*) anc_buff,anc_length);
 
718
    DBUG_DUMP("key_to_anc",(uchar*) leaf_key,key_length);
 
719
 
 
720
    temp_pos=anc_buff+anc_length;
 
721
    t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
 
722
                                  keypos == temp_pos ? (uchar*) 0
 
723
                                  : keypos,
 
724
                                  anc_pos, anc_pos,
 
725
                                  leaf_key,&s_temp);
 
726
    if (t_length > 0)
 
727
      bmove_upp((uchar*) temp_pos+t_length,(uchar*) temp_pos,
 
728
                (uint) (temp_pos-keypos));
 
729
    else
 
730
      bmove(keypos,keypos-t_length,(uint) (temp_pos-keypos)+t_length);
 
731
    (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
 
732
    mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
 
733
 
 
734
    /* Store first key on new page */
 
735
    if (nod_flag)
 
736
      bmove((uchar*) leaf_buff+2,(uchar*) half_pos-nod_flag,(size_t) nod_flag);
 
737
    if (!(length=(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key)))
 
738
      goto err;
 
739
    DBUG_DUMP("key_to_leaf",(uchar*) leaf_key,length);
 
740
    t_length=(*keyinfo->pack_key)(keyinfo,nod_flag, (uchar*) 0,
 
741
                                  (uchar*) 0, (uchar*) 0, leaf_key, &s_temp);
 
742
    length=(uint) ((buff+buff_length)-half_pos);
 
743
    DBUG_PRINT("info",("t_length: %d  length: %d",t_length,(int) length));
 
744
    bmove((uchar*) leaf_buff+p_length+t_length,(uchar*) half_pos,
 
745
          (size_t) length);
 
746
    (*keyinfo->store_key)(keyinfo,leaf_buff+p_length,&s_temp);
 
747
    mi_putint(leaf_buff,length+t_length+p_length,nod_flag);
 
748
    if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
 
749
      goto err;
 
750
    mi_putint(buff,endpos-buff,nod_flag);
 
751
  }
 
752
  if (_mi_write_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff))
 
753
    goto err;
 
754
  DBUG_RETURN(anc_length <= (uint) keyinfo->block_length/2);
 
755
 
 
756
err:
 
757
  DBUG_RETURN(-1);
 
758
} /* underflow */
 
759
 
 
760
 
 
761
        /*
 
762
          remove a key from packed buffert
 
763
          The current code doesn't handle the case that the next key may be
 
764
          packed better against the previous key if there is a case difference
 
765
          returns how many chars was removed or 0 on error
 
766
        */
 
767
 
 
768
static uint remove_key(MI_KEYDEF *keyinfo, uint nod_flag,
 
769
                       uchar *keypos,   /* Where key starts */
 
770
                       uchar *lastkey,  /* key to be removed */
 
771
                       uchar *page_end, /* End of page */
 
772
                       my_off_t *next_block)    /* ptr to next block */
 
773
{
 
774
  int s_length;
 
775
  uchar *start;
 
776
  DBUG_ENTER("remove_key");
 
777
  DBUG_PRINT("enter",("keypos: 0x%lx  page_end: 0x%lx",(long) keypos, (long) page_end));
 
778
 
 
779
  start=keypos;
 
780
  if (!(keyinfo->flag &
 
781
        (HA_PACK_KEY | HA_SPACE_PACK_USED | HA_VAR_LENGTH_KEY |
 
782
         HA_BINARY_PACK_KEY)))
 
783
  {
 
784
    s_length=(int) (keyinfo->keylength+nod_flag);
 
785
    if (next_block && nod_flag)
 
786
      *next_block= _mi_kpos(nod_flag,keypos+s_length);
 
787
  }
 
788
  else
 
789
  {                                      /* Let keypos point at next key */
 
790
    /* Calculate length of key */
 
791
    if (!(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey))
 
792
      DBUG_RETURN(0);                           /* Error */
 
793
 
 
794
    if (next_block && nod_flag)
 
795
      *next_block= _mi_kpos(nod_flag,keypos);
 
796
    s_length=(int) (keypos-start);
 
797
    if (keypos != page_end)
 
798
    {
 
799
      if (keyinfo->flag & HA_BINARY_PACK_KEY)
 
800
      {
 
801
        uchar *old_key=start;
 
802
        uint next_length,prev_length,prev_pack_length;
 
803
        get_key_length(next_length,keypos);
 
804
        get_key_pack_length(prev_length,prev_pack_length,old_key);
 
805
        if (next_length > prev_length)
 
806
        {
 
807
          /* We have to copy data from the current key to the next key */
 
808
          bmove_upp(keypos, (lastkey+next_length),
 
809
                    (next_length-prev_length));
 
810
          keypos-=(next_length-prev_length)+prev_pack_length;
 
811
          store_key_length(keypos,prev_length);
 
812
          s_length=(int) (keypos-start);
 
813
        }
 
814
      }
 
815
      else
 
816
      {
 
817
        /* Check if a variable length first key part */
 
818
        if ((keyinfo->seg->flag & HA_PACK_KEY) && *keypos & 128)
 
819
        {
 
820
          /* Next key is packed against the current one */
 
821
          uint next_length,prev_length,prev_pack_length,lastkey_length,
 
822
            rest_length;
 
823
          if (keyinfo->seg[0].length >= 127)
 
824
          {
 
825
            if (!(prev_length=mi_uint2korr(start) & 32767))
 
826
              goto end;
 
827
            next_length=mi_uint2korr(keypos) & 32767;
 
828
            keypos+=2;
 
829
            prev_pack_length=2;
 
830
          }
 
831
          else
 
832
          {
 
833
            if (!(prev_length= *start & 127))
 
834
              goto end;                         /* Same key as previous*/
 
835
            next_length= *keypos & 127;
 
836
            keypos++;
 
837
            prev_pack_length=1;
 
838
          }
 
839
          if (!(*start & 128))
 
840
            prev_length=0;                      /* prev key not packed */
 
841
          if (keyinfo->seg[0].flag & HA_NULL_PART)
 
842
            lastkey++;                          /* Skip null marker */
 
843
          get_key_length(lastkey_length,lastkey);
 
844
          if (!next_length)                     /* Same key after */
 
845
          {
 
846
            next_length=lastkey_length;
 
847
            rest_length=0;
 
848
          }
 
849
          else
 
850
            get_key_length(rest_length,keypos);
 
851
 
 
852
          if (next_length >= prev_length)
 
853
          {             /* Key after is based on deleted key */
 
854
            uint pack_length,tmp;
 
855
            bmove_upp(keypos, (lastkey+next_length),
 
856
                      tmp=(next_length-prev_length));
 
857
            rest_length+=tmp;
 
858
            pack_length= prev_length ? get_pack_length(rest_length): 0;
 
859
            keypos-=tmp+pack_length+prev_pack_length;
 
860
            s_length=(int) (keypos-start);
 
861
            if (prev_length)                    /* Pack against prev key */
 
862
            {
 
863
              *keypos++= start[0];
 
864
              if (prev_pack_length == 2)
 
865
                *keypos++= start[1];
 
866
              store_key_length(keypos,rest_length);
 
867
            }
 
868
            else
 
869
            {
 
870
              /* Next key is not packed anymore */
 
871
              if (keyinfo->seg[0].flag & HA_NULL_PART)
 
872
              {
 
873
                rest_length++;                  /* Mark not null */
 
874
              }
 
875
              if (prev_pack_length == 2)
 
876
              {
 
877
                mi_int2store(keypos,rest_length);
 
878
              }
 
879
              else
 
880
                *keypos= rest_length;
 
881
            }
 
882
          }
 
883
        }
 
884
      }
 
885
    }
 
886
  }
 
887
  end:
 
888
  bmove((uchar*) start,(uchar*) start+s_length,
 
889
        (uint) (page_end-start-s_length));
 
890
  DBUG_RETURN((uint) s_length);
 
891
} /* remove_key */