← Back to branch summary

~stewart/drizzle/embedded-innodb-create-select-transaction-arrgh

« back to all changes in this revision

Viewing changes to storage/myisam/mi_search.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_search.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
/* key handling functions */
 
17
 
 
18
#include "fulltext.h"
 
19
#include "m_ctype.h"
 
20
 
 
21
static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
 
22
                                uchar *key, uchar *keypos,
 
23
                                uint *return_key_length);
 
24
 
 
25
        /* Check index */
 
26
 
 
27
int _mi_check_index(MI_INFO *info, int inx)
 
28
{
 
29
  if (inx == -1)                        /* Use last index */
 
30
    inx=info->lastinx;
 
31
  if (inx < 0 || ! mi_is_key_active(info->s->state.key_map, inx))
 
32
  {
 
33
    my_errno=HA_ERR_WRONG_INDEX;
 
34
    return -1;
 
35
  }
 
36
  if (info->lastinx != inx)             /* Index changed */
 
37
  {
 
38
    info->lastinx = inx;
 
39
    info->page_changed=1;
 
40
    info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
 
41
                   HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
 
42
  }
 
43
  if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
 
44
    return(-1);
 
45
  return(inx);
 
46
} /* mi_check_index */
 
47
 
 
48
 
 
49
        /*
 
50
        ** Search after row by a key
 
51
        ** Position to row is stored in info->lastpos
 
52
        ** Return: -1 if not found
 
53
        **          1 if one should continue search on higher level
 
54
        */
 
55
 
 
56
int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 
57
               uchar *key, uint key_len, uint nextflag, register my_off_t pos)
 
58
{
 
59
  my_bool last_key;
 
60
  int error,flag;
 
61
  uint nod_flag;
 
62
  uchar *keypos,*maxpos;
 
63
  uchar lastkey[MI_MAX_KEY_BUFF],*buff;
 
64
  DBUG_ENTER("_mi_search");
 
65
  DBUG_PRINT("enter",("pos: %lu  nextflag: %u  lastpos: %lu",
 
66
                      (ulong) pos, nextflag, (ulong) info->lastpos));
 
67
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_len););
 
68
 
 
69
  if (pos == HA_OFFSET_ERROR)
 
70
  {
 
71
    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
 
72
    info->lastpos= HA_OFFSET_ERROR;
 
73
    if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
 
74
      DBUG_RETURN(-1);                          /* Not found ; return error */
 
75
    DBUG_RETURN(1);                             /* Search at upper levels */
 
76
  }
 
77
 
 
78
  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
 
79
                               test(!(nextflag & SEARCH_SAVE_BUFF)))))
 
80
    goto err;
 
81
  DBUG_DUMP("page",(uchar*) buff,mi_getint(buff));
 
82
 
 
83
  flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
 
84
                              &keypos,lastkey, &last_key);
 
85
  if (flag == MI_FOUND_WRONG_KEY)
 
86
    DBUG_RETURN(-1);
 
87
  nod_flag=mi_test_if_nod(buff);
 
88
  maxpos=buff+mi_getint(buff)-1;
 
89
 
 
90
  if (flag)
 
91
  {
 
92
    if ((error=_mi_search(info,keyinfo,key,key_len,nextflag,
 
93
                          _mi_kpos(nod_flag,keypos))) <= 0)
 
94
      DBUG_RETURN(error);
 
95
 
 
96
    if (flag >0)
 
97
    {
 
98
      if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
 
99
          keypos == buff+2+nod_flag)
 
100
        DBUG_RETURN(1);                                 /* Bigger than key */
 
101
    }
 
102
    else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
 
103
      DBUG_RETURN(1);                                   /* Smaller than key */
 
104
  }
 
105
  else
 
106
  {
 
107
    if ((nextflag & SEARCH_FIND) && nod_flag &&
 
108
        ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
 
109
         key_len != USE_WHOLE_KEY))
 
110
    {
 
111
      if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
 
112
                            _mi_kpos(nod_flag,keypos))) >= 0 ||
 
113
          my_errno != HA_ERR_KEY_NOT_FOUND)
 
114
        DBUG_RETURN(error);
 
115
      info->last_keypage= HA_OFFSET_ERROR;              /* Buffer not in mem */
 
116
    }
 
117
  }
 
118
  if (pos != info->last_keypage)
 
119
  {
 
120
    uchar *old_buff=buff;
 
121
    if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
 
122
                                 test(!(nextflag & SEARCH_SAVE_BUFF)))))
 
123
      goto err;
 
124
    keypos=buff+(keypos-old_buff);
 
125
    maxpos=buff+(maxpos-old_buff);
 
126
  }
 
127
 
 
128
  if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
 
129
  {
 
130
    uint not_used[2];
 
131
    if (_mi_get_prev_key(info,keyinfo, buff, info->lastkey, keypos,
 
132
                         &info->lastkey_length))
 
133
      goto err;
 
134
    if (!(nextflag & SEARCH_SMALLER) &&
 
135
        ha_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND,
 
136
                   not_used))
 
137
    {
 
138
      my_errno=HA_ERR_KEY_NOT_FOUND;                    /* Didn't find key */
 
139
      goto err;
 
140
    }
 
141
  }
 
142
  else
 
143
  {
 
144
    info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey);
 
145
    if (!info->lastkey_length)
 
146
      goto err;
 
147
    memcpy(info->lastkey,lastkey,info->lastkey_length);
 
148
  }
 
149
  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
 
150
  /* Save position for a possible read next / previous */
 
151
  info->int_keypos=info->buff+ (keypos-buff);
 
152
  info->int_maxpos=info->buff+ (maxpos-buff);
 
153
  info->int_nod_flag=nod_flag;
 
154
  info->int_keytree_version=keyinfo->version;
 
155
  info->last_search_keypage=info->last_keypage;
 
156
  info->page_changed=0;
 
157
  info->buff_used= (info->buff != buff);        /* If we have to reread buff */
 
158
 
 
159
  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
 
160
  DBUG_RETURN(0);
 
161
 
 
162
err:
 
163
  DBUG_PRINT("exit",("Error: %d",my_errno));
 
164
  info->lastpos= HA_OFFSET_ERROR;
 
165
  info->page_changed=1;
 
166
  DBUG_RETURN (-1);
 
167
} /* _mi_search */
 
168
 
 
169
 
 
170
        /* Search after key in page-block */
 
171
        /* If packed key puts smaller or identical key in buff */
 
172
        /* ret_pos point to where find or bigger key starts */
 
173
        /* ARGSUSED */
 
174
 
 
175
int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
 
176
                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
 
177
                   uchar *buff __attribute__((unused)), my_bool *last_key)
 
178
{
 
179
  register int start,mid,end,save_end;
 
180
  int flag;
 
181
  uint totlength,nod_flag,not_used[2];
 
182
  DBUG_ENTER("_mi_bin_search");
 
183
 
 
184
  totlength=keyinfo->keylength+(nod_flag=mi_test_if_nod(page));
 
185
  start=0; mid=1;
 
186
  save_end=end=(int) ((mi_getint(page)-2-nod_flag)/totlength-1);
 
187
  DBUG_PRINT("test",("mi_getint: %d  end: %d",mi_getint(page),end));
 
188
  page+=2+nod_flag;
 
189
 
 
190
  while (start != end)
 
191
  {
 
192
    mid= (start+end)/2;
 
193
    if ((flag=ha_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
 
194
                         comp_flag, not_used))
 
195
        >= 0)
 
196
      end=mid;
 
197
    else
 
198
      start=mid+1;
 
199
  }
 
200
  if (mid != start)
 
201
    flag=ha_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
 
202
                     comp_flag, not_used);
 
203
  if (flag < 0)
 
204
    start++;                    /* point at next, bigger key */
 
205
  *ret_pos=page+(uint) start*totlength;
 
206
  *last_key= end == save_end;
 
207
  DBUG_PRINT("exit",("flag: %d  keypos: %d",flag,start));
 
208
  DBUG_RETURN(flag);
 
209
} /* _mi_bin_search */
 
210
 
 
211
 
 
212
/*
 
213
  Locate a packed key in a key page.
 
214
 
 
215
  SYNOPSIS
 
216
    _mi_seq_search()
 
217
    info                        Open table information.
 
218
    keyinfo                     Key definition information.
 
219
    page                        Key page (beginning).
 
220
    key                         Search key.
 
221
    key_len                     Length to use from search key or USE_WHOLE_KEY
 
222
    comp_flag                   Search flags like SEARCH_SAME etc.
 
223
    ret_pos             RETURN  Position in key page behind this key.
 
224
    buff                RETURN  Copy of previous or identical unpacked key.
 
225
    last_key            RETURN  If key is last in page.
 
226
 
 
227
  DESCRIPTION
 
228
    Used instead of _mi_bin_search() when key is packed.
 
229
    Puts smaller or identical key in buff.
 
230
    Key is searched sequentially.
 
231
 
 
232
  RETURN
 
233
    > 0         Key in 'buff' is smaller than search key.
 
234
    0           Key in 'buff' is identical to search key.
 
235
    < 0         Not found.
 
236
*/
 
237
 
 
238
int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
 
239
                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
 
240
                   uchar *buff, my_bool *last_key)
 
241
{
 
242
  int flag;
 
243
  uint nod_flag,length,not_used[2];
 
244
  uchar t_buff[MI_MAX_KEY_BUFF],*end;
 
245
  DBUG_ENTER("_mi_seq_search");
 
246
 
 
247
  end= page+mi_getint(page);
 
248
  nod_flag=mi_test_if_nod(page);
 
249
  page+=2+nod_flag;
 
250
  *ret_pos=page;
 
251
  t_buff[0]=0;                                  /* Avoid bugs */
 
252
  while (page < end)
 
253
  {
 
254
    length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
 
255
    if (length == 0 || page > end)
 
256
    {
 
257
      mi_print_error(info->s, HA_ERR_CRASHED);
 
258
      my_errno=HA_ERR_CRASHED;
 
259
      DBUG_PRINT("error",
 
260
                 ("Found wrong key:  length: %u  page: 0x%lx  end: 0x%lx",
 
261
                  length, (long) page, (long) end));
 
262
      DBUG_RETURN(MI_FOUND_WRONG_KEY);
 
263
    }
 
264
    if ((flag=ha_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
 
265
                         not_used)) >= 0)
 
266
      break;
 
267
#ifdef EXTRA_DEBUG
 
268
    DBUG_PRINT("loop",("page: 0x%lx  key: '%s'  flag: %d", (long) page, t_buff,
 
269
                       flag));
 
270
#endif
 
271
    memcpy(buff,t_buff,length);
 
272
    *ret_pos=page;
 
273
  }
 
274
  if (flag == 0)
 
275
    memcpy(buff,t_buff,length);                 /* Result is first key */
 
276
  *last_key= page == end;
 
277
  DBUG_PRINT("exit",("flag: %d  ret_pos: 0x%lx", flag, (long) *ret_pos));
 
278
  DBUG_RETURN(flag);
 
279
} /* _mi_seq_search */
 
280
 
 
281
 
 
282
int _mi_prefix_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
 
283
                      uchar *key, uint key_len, uint nextflag, uchar **ret_pos,
 
284
                      uchar *buff, my_bool *last_key)
 
285
{
 
286
  /*
 
287
    my_flag is raw comparison result to be changed according to
 
288
    SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
 
289
    flag is the value returned by ha_key_cmp and as treated as final
 
290
  */
 
291
  int flag=0, my_flag=-1;
 
292
  uint nod_flag, length, len, matched, cmplen, kseg_len;
 
293
  uint prefix_len,suffix_len;
 
294
  int key_len_skip, seg_len_pack, key_len_left;
 
295
  uchar *end, *kseg, *vseg;
 
296
  uchar *sort_order=keyinfo->seg->charset->sort_order;
 
297
  uchar tt_buff[MI_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
 
298
  uchar *saved_from, *saved_to, *saved_vseg;
 
299
  uint  saved_length=0, saved_prefix_len=0;
 
300
  uint  length_pack;
 
301
  DBUG_ENTER("_mi_prefix_search");
 
302
 
 
303
  t_buff[0]=0;                                  /* Avoid bugs */
 
304
  end= page+mi_getint(page);
 
305
  nod_flag=mi_test_if_nod(page);
 
306
  page+=2+nod_flag;
 
307
  *ret_pos=page;
 
308
  kseg=key;
 
309
 
 
310
  get_key_pack_length(kseg_len,length_pack,kseg);
 
311
  key_len_skip=length_pack+kseg_len;
 
312
  key_len_left=(int) key_len- (int) key_len_skip;
 
313
  /* If key_len is 0, then lenght_pack is 1, then key_len_left is -1. */
 
314
  cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
 
315
  DBUG_PRINT("info",("key: '%.*s'",kseg_len,kseg));
 
316
 
 
317
  /*
 
318
    Keys are compressed the following way:
 
319
 
 
320
    If the max length of first key segment <= 127 bytes the prefix is
 
321
    1 byte else it's 2 byte
 
322
 
 
323
    (prefix) length  The high bit is set if this is a prefix for the prev key.
 
324
    [suffix length]  Packed length of suffix if the previous was a prefix.
 
325
    (suffix) data    Key data bytes (past the common prefix or whole segment).
 
326
    [next-key-seg]   Next key segments (([packed length], data), ...)
 
327
    pointer          Reference to the data file (last_keyseg->length).
 
328
  */
 
329
 
 
330
  matched=0;  /* how many char's from prefix were alredy matched */
 
331
  len=0;      /* length of previous key unpacked */
 
332
 
 
333
  while (page < end)
 
334
  {
 
335
    uint packed= *page & 128;
 
336
 
 
337
    vseg=page;
 
338
    if (keyinfo->seg->length >= 127)
 
339
    {
 
340
      suffix_len=mi_uint2korr(vseg) & 32767;
 
341
      vseg+=2;
 
342
    }
 
343
    else
 
344
      suffix_len= *vseg++ & 127;
 
345
 
 
346
    if (packed)
 
347
    {
 
348
      if (suffix_len == 0)
 
349
      {
 
350
        /* == 0x80 or 0x8000, same key, prefix length == old key length. */
 
351
        prefix_len=len;
 
352
      }
 
353
      else
 
354
      {
 
355
        /* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
 
356
        prefix_len=suffix_len;
 
357
        get_key_length(suffix_len,vseg);
 
358
      }
 
359
    }
 
360
    else
 
361
    {
 
362
      /* Not packed. No prefix used from last key. */
 
363
      prefix_len=0;
 
364
    }
 
365
 
 
366
    len=prefix_len+suffix_len;
 
367
    seg_len_pack=get_pack_length(len);
 
368
    t_buff=tt_buff+3-seg_len_pack;
 
369
    store_key_length(t_buff,len);
 
370
 
 
371
    if (prefix_len > saved_prefix_len)
 
372
      memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
 
373
             prefix_len-saved_prefix_len);
 
374
    saved_vseg=vseg;
 
375
    saved_prefix_len=prefix_len;
 
376
 
 
377
    DBUG_PRINT("loop",("page: '%.*s%.*s'",prefix_len,t_buff+seg_len_pack,
 
378
                       suffix_len,vseg));
 
379
    {
 
380
      uchar *from=vseg+suffix_len;
 
381
      HA_KEYSEG *keyseg;
 
382
      uint l;
 
383
 
 
384
      for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
 
385
      {
 
386
 
 
387
        if (keyseg->flag & HA_NULL_PART)
 
388
        {
 
389
          if (!(*from++))
 
390
            continue;
 
391
        }
 
392
        if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
 
393
        {
 
394
          get_key_length(l,from);
 
395
        }
 
396
        else
 
397
          l=keyseg->length;
 
398
 
 
399
        from+=l;
 
400
      }
 
401
      from+=keyseg->length;
 
402
      page=from+nod_flag;
 
403
      length=from-vseg;
 
404
    }
 
405
 
 
406
    if (page > end)
 
407
    {
 
408
      mi_print_error(info->s, HA_ERR_CRASHED);
 
409
      my_errno=HA_ERR_CRASHED;
 
410
      DBUG_PRINT("error",
 
411
                 ("Found wrong key:  length: %u  page: 0x%lx  end: %lx",
 
412
                  length, (long) page, (long) end));
 
413
      DBUG_RETURN(MI_FOUND_WRONG_KEY);
 
414
    }
 
415
 
 
416
    if (matched >= prefix_len)
 
417
    {
 
418
      /* We have to compare. But we can still skip part of the key */
 
419
      uint  left;
 
420
      uchar *k=kseg+prefix_len;
 
421
 
 
422
      /*
 
423
        If prefix_len > cmplen then we are in the end-space comparison
 
424
        phase. Do not try to acces the key any more ==> left= 0.
 
425
      */
 
426
      left= ((len <= cmplen) ? suffix_len :
 
427
             ((prefix_len < cmplen) ? cmplen - prefix_len : 0));
 
428
 
 
429
      matched=prefix_len+left;
 
430
 
 
431
      if (sort_order)
 
432
      {
 
433
        for (my_flag=0;left;left--)
 
434
          if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
 
435
            break;
 
436
      }
 
437
      else
 
438
      {
 
439
        for (my_flag=0;left;left--)
 
440
          if ((my_flag= (int) *vseg++ - (int) *k++))
 
441
            break;
 
442
      }
 
443
 
 
444
      if (my_flag>0)      /* mismatch */
 
445
        break;
 
446
      if (my_flag==0) /* match */
 
447
      {
 
448
        /*
 
449
        **  len cmplen seg_left_len more_segs
 
450
        **     <                               matched=len; continue search
 
451
        **     >      =                        prefix ? found : (matched=len; continue search)
 
452
        **     >      <                 -      ok, found
 
453
        **     =      <                 -      ok, found
 
454
        **     =      =                 -      ok, found
 
455
        **     =      =                 +      next seg
 
456
        */
 
457
        if (len < cmplen)
 
458
        {
 
459
          if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
 
460
               keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
 
461
               keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
 
462
            my_flag= -1;
 
463
          else
 
464
          {
 
465
            /* We have to compare k and vseg as if they were space extended */
 
466
            uchar *k_end= k+ (cmplen - len);
 
467
            for ( ; k < k_end && *k == ' '; k++) ;
 
468
            if (k == k_end)
 
469
              goto cmp_rest;            /* should never happen */
 
470
            if (*k < (uchar) ' ')
 
471
            {
 
472
              my_flag= 1;               /* Compared string is smaller */
 
473
              break;
 
474
            }
 
475
            my_flag= -1;                /* Continue searching */
 
476
          }
 
477
        }
 
478
        else if (len > cmplen)
 
479
        {
 
480
          uchar *vseg_end;
 
481
          if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
 
482
            goto fix_flag;
 
483
 
 
484
          /* We have to compare k and vseg as if they were space extended */
 
485
          for (vseg_end= vseg + (len-cmplen) ;
 
486
               vseg < vseg_end && *vseg == (uchar) ' ';
 
487
               vseg++, matched++) ;
 
488
          DBUG_ASSERT(vseg < vseg_end);
 
489
 
 
490
          if (*vseg > (uchar) ' ')
 
491
          {
 
492
            my_flag= 1;                 /* Compared string is smaller */
 
493
            break;
 
494
          }
 
495
          my_flag= -1;                  /* Continue searching */
 
496
        }
 
497
        else
 
498
        {
 
499
      cmp_rest:
 
500
          if (key_len_left>0)
 
501
          {
 
502
            uint not_used[2];
 
503
            if ((flag = ha_key_cmp(keyinfo->seg+1,vseg,
 
504
                                   k, key_len_left, nextflag, not_used)) >= 0)
 
505
              break;
 
506
          }
 
507
          else
 
508
          {
 
509
            /*
 
510
              at this line flag==-1 if the following lines were already
 
511
              visited and 0 otherwise,  i.e. flag <=0 here always !!!
 
512
            */
 
513
        fix_flag:
 
514
            DBUG_ASSERT(flag <= 0);
 
515
            if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
 
516
              flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
 
517
            if (flag>=0)
 
518
              break;
 
519
          }
 
520
        }
 
521
      }
 
522
      matched-=left;
 
523
    }
 
524
    /* else (matched < prefix_len) ---> do nothing. */
 
525
 
 
526
    memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
 
527
    saved_to=buff+saved_length;
 
528
    saved_from=saved_vseg;
 
529
    saved_length=length;
 
530
    *ret_pos=page;
 
531
  }
 
532
  if (my_flag)
 
533
    flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
 
534
  if (flag == 0)
 
535
  {
 
536
    memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
 
537
    saved_to=buff+saved_length;
 
538
    saved_from=saved_vseg;
 
539
    saved_length=length;
 
540
  }
 
541
  if (saved_length)
 
542
    memcpy(saved_to,saved_from,saved_length);
 
543
 
 
544
  *last_key= page == end;
 
545
 
 
546
  DBUG_PRINT("exit",("flag: %d  ret_pos: 0x%lx", flag, (long) *ret_pos));
 
547
  DBUG_RETURN(flag);
 
548
} /* _mi_prefix_search */
 
549
 
 
550
 
 
551
        /* Get pos to a key_block */
 
552
 
 
553
my_off_t _mi_kpos(uint nod_flag, uchar *after_key)
 
554
{
 
555
  after_key-=nod_flag;
 
556
  switch (nod_flag) {
 
557
#if SIZEOF_OFF_T > 4
 
558
  case 7:
 
559
    return mi_uint7korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
 
560
  case 6:
 
561
    return mi_uint6korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
 
562
  case 5:
 
563
    return mi_uint5korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
 
564
#else
 
565
  case 7:
 
566
    after_key++;
 
567
  case 6:
 
568
    after_key++;
 
569
  case 5:
 
570
    after_key++;
 
571
#endif
 
572
  case 4:
 
573
    return ((my_off_t) mi_uint4korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
 
574
  case 3:
 
575
    return ((my_off_t) mi_uint3korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
 
576
  case 2:
 
577
    return (my_off_t) (mi_uint2korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH);
 
578
  case 1:
 
579
    return (uint) (*after_key)*MI_MIN_KEY_BLOCK_LENGTH;
 
580
  case 0:                                       /* At leaf page */
 
581
  default:                                      /* Impossible */
 
582
    return(HA_OFFSET_ERROR);
 
583
  }
 
584
} /* _kpos */
 
585
 
 
586
 
 
587
        /* Save pos to a key_block */
 
588
 
 
589
void _mi_kpointer(register MI_INFO *info, register uchar *buff, my_off_t pos)
 
590
{
 
591
  pos/=MI_MIN_KEY_BLOCK_LENGTH;
 
592
  switch (info->s->base.key_reflength) {
 
593
#if SIZEOF_OFF_T > 4
 
594
  case 7: mi_int7store(buff,pos); break;
 
595
  case 6: mi_int6store(buff,pos); break;
 
596
  case 5: mi_int5store(buff,pos); break;
 
597
#else
 
598
  case 7: *buff++=0;
 
599
    /* fall trough */
 
600
  case 6: *buff++=0;
 
601
    /* fall trough */
 
602
  case 5: *buff++=0;
 
603
    /* fall trough */
 
604
#endif
 
605
  case 4: mi_int4store(buff,pos); break;
 
606
  case 3: mi_int3store(buff,pos); break;
 
607
  case 2: mi_int2store(buff,(uint) pos); break;
 
608
  case 1: buff[0]= (uchar) pos; break;
 
609
  default: abort();                             /* impossible */
 
610
  }
 
611
} /* _mi_kpointer */
 
612
 
 
613
 
 
614
        /* Calc pos to a data-record from a key */
 
615
 
 
616
 
 
617
my_off_t _mi_dpos(MI_INFO *info, uint nod_flag, uchar *after_key)
 
618
{
 
619
  my_off_t pos;
 
620
  after_key-=(nod_flag + info->s->rec_reflength);
 
621
  switch (info->s->rec_reflength) {
 
622
#if SIZEOF_OFF_T > 4
 
623
  case 8:  pos= (my_off_t) mi_uint8korr(after_key);  break;
 
624
  case 7:  pos= (my_off_t) mi_uint7korr(after_key);  break;
 
625
  case 6:  pos= (my_off_t) mi_uint6korr(after_key);  break;
 
626
  case 5:  pos= (my_off_t) mi_uint5korr(after_key);  break;
 
627
#else
 
628
  case 8:  pos= (my_off_t) mi_uint4korr(after_key+4);   break;
 
629
  case 7:  pos= (my_off_t) mi_uint4korr(after_key+3);   break;
 
630
  case 6:  pos= (my_off_t) mi_uint4korr(after_key+2);   break;
 
631
  case 5:  pos= (my_off_t) mi_uint4korr(after_key+1);   break;
 
632
#endif
 
633
  case 4:  pos= (my_off_t) mi_uint4korr(after_key);  break;
 
634
  case 3:  pos= (my_off_t) mi_uint3korr(after_key);  break;
 
635
  case 2:  pos= (my_off_t) mi_uint2korr(after_key);  break;
 
636
  default:
 
637
    pos=0L;                                     /* Shut compiler up */
 
638
  }
 
639
  return (info->s->options &
 
640
          (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
 
641
            pos*info->s->base.pack_reclength;
 
642
}
 
643
 
 
644
 
 
645
/* Calc position from a record pointer ( in delete link chain ) */
 
646
 
 
647
my_off_t _mi_rec_pos(MYISAM_SHARE *s, uchar *ptr)
 
648
{
 
649
  my_off_t pos;
 
650
  switch (s->rec_reflength) {
 
651
#if SIZEOF_OFF_T > 4
 
652
  case 8:
 
653
    pos= (my_off_t) mi_uint8korr(ptr);
 
654
    if (pos == HA_OFFSET_ERROR)
 
655
      return HA_OFFSET_ERROR;                   /* end of list */
 
656
    break;
 
657
  case 7:
 
658
    pos= (my_off_t) mi_uint7korr(ptr);
 
659
    if (pos == (((my_off_t) 1) << 56) -1)
 
660
      return HA_OFFSET_ERROR;                   /* end of list */
 
661
    break;
 
662
  case 6:
 
663
    pos= (my_off_t) mi_uint6korr(ptr);
 
664
    if (pos == (((my_off_t) 1) << 48) -1)
 
665
      return HA_OFFSET_ERROR;                   /* end of list */
 
666
    break;
 
667
  case 5:
 
668
    pos= (my_off_t) mi_uint5korr(ptr);
 
669
    if (pos == (((my_off_t) 1) << 40) -1)
 
670
      return HA_OFFSET_ERROR;                   /* end of list */
 
671
    break;
 
672
#else
 
673
  case 8:
 
674
  case 7:
 
675
  case 6:
 
676
  case 5:
 
677
    ptr+= (s->rec_reflength-4);
 
678
    /* fall through */
 
679
#endif
 
680
  case 4:
 
681
    pos= (my_off_t) mi_uint4korr(ptr);
 
682
    if (pos == (my_off_t) (uint32) ~0L)
 
683
      return  HA_OFFSET_ERROR;
 
684
    break;
 
685
  case 3:
 
686
    pos= (my_off_t) mi_uint3korr(ptr);
 
687
    if (pos == (my_off_t) (1 << 24) -1)
 
688
      return HA_OFFSET_ERROR;
 
689
    break;
 
690
  case 2:
 
691
    pos= (my_off_t) mi_uint2korr(ptr);
 
692
    if (pos == (my_off_t) (1 << 16) -1)
 
693
      return HA_OFFSET_ERROR;
 
694
    break;
 
695
  default: abort();                             /* Impossible */
 
696
  }
 
697
  return ((s->options &
 
698
          (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
 
699
          pos*s->base.pack_reclength);
 
700
}
 
701
 
 
702
 
 
703
        /* save position to record */
 
704
 
 
705
void _mi_dpointer(MI_INFO *info, uchar *buff, my_off_t pos)
 
706
{
 
707
  if (!(info->s->options &
 
708
        (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) &&
 
709
      pos != HA_OFFSET_ERROR)
 
710
    pos/=info->s->base.pack_reclength;
 
711
 
 
712
  switch (info->s->rec_reflength) {
 
713
#if SIZEOF_OFF_T > 4
 
714
  case 8: mi_int8store(buff,pos); break;
 
715
  case 7: mi_int7store(buff,pos); break;
 
716
  case 6: mi_int6store(buff,pos); break;
 
717
  case 5: mi_int5store(buff,pos); break;
 
718
#else
 
719
  case 8: *buff++=0;
 
720
    /* fall trough */
 
721
  case 7: *buff++=0;
 
722
    /* fall trough */
 
723
  case 6: *buff++=0;
 
724
    /* fall trough */
 
725
  case 5: *buff++=0;
 
726
    /* fall trough */
 
727
#endif
 
728
  case 4: mi_int4store(buff,pos); break;
 
729
  case 3: mi_int3store(buff,pos); break;
 
730
  case 2: mi_int2store(buff,(uint) pos); break;
 
731
  default: abort();                             /* Impossible */
 
732
  }
 
733
} /* _mi_dpointer */
 
734
 
 
735
 
 
736
        /* Get key from key-block */
 
737
        /* page points at previous key; its advanced to point at next key */
 
738
        /* key should contain previous key */
 
739
        /* Returns length of found key + pointers */
 
740
        /* nod_flag is a flag if we are on nod */
 
741
 
 
742
        /* same as _mi_get_key but used with fixed length keys */
 
743
 
 
744
uint _mi_get_static_key(register MI_KEYDEF *keyinfo, uint nod_flag,
 
745
                       register uchar **page, register uchar *key)
 
746
{
 
747
  memcpy((uchar*) key,(uchar*) *page,
 
748
         (size_t) (keyinfo->keylength+nod_flag));
 
749
  *page+=keyinfo->keylength+nod_flag;
 
750
  return(keyinfo->keylength);
 
751
} /* _mi_get_static_key */
 
752
 
 
753
 
 
754
/*
 
755
  get key witch is packed against previous key or key with a NULL column.
 
756
 
 
757
  SYNOPSIS
 
758
    _mi_get_pack_key()
 
759
    keyinfo                     key definition information.
 
760
    nod_flag                    If nod: Length of node pointer, else zero.
 
761
    page_pos            RETURN  position in key page behind this key.
 
762
    key                 IN/OUT  in: prev key, out: unpacked key.
 
763
 
 
764
  RETURN
 
765
    key_length + length of data pointer
 
766
*/
 
767
 
 
768
uint _mi_get_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
 
769
                      register uchar **page_pos, register uchar *key)
 
770
{
 
771
  register HA_KEYSEG *keyseg;
 
772
  uchar *start_key,*page=*page_pos;
 
773
  uint length;
 
774
 
 
775
  start_key=key;
 
776
  for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
 
777
  {
 
778
    if (keyseg->flag & HA_PACK_KEY)
 
779
    {
 
780
      /* key with length, packed to previous key */
 
781
      uchar *start=key;
 
782
      uint packed= *page & 128,tot_length,rest_length;
 
783
      if (keyseg->length >= 127)
 
784
      {
 
785
        length=mi_uint2korr(page) & 32767;
 
786
        page+=2;
 
787
      }
 
788
      else
 
789
        length= *page++ & 127;
 
790
 
 
791
      if (packed)
 
792
      {
 
793
        if (length > (uint) keyseg->length)
 
794
        {
 
795
          mi_print_error(keyinfo->share, HA_ERR_CRASHED);
 
796
          my_errno=HA_ERR_CRASHED;
 
797
          return 0;                             /* Error */
 
798
        }
 
799
        if (length == 0)                        /* Same key */
 
800
        {
 
801
          if (keyseg->flag & HA_NULL_PART)
 
802
            *key++=1;                           /* Can't be NULL */
 
803
          get_key_length(length,key);
 
804
          key+= length;                         /* Same diff_key as prev */
 
805
          if (length > keyseg->length)
 
806
          {
 
807
            DBUG_PRINT("error",
 
808
                       ("Found too long null packed key: %u of %u at 0x%lx",
 
809
                        length, keyseg->length, (long) *page_pos));
 
810
            DBUG_DUMP("key",(uchar*) *page_pos,16);
 
811
            mi_print_error(keyinfo->share, HA_ERR_CRASHED);
 
812
            my_errno=HA_ERR_CRASHED;
 
813
            return 0;
 
814
          }
 
815
          continue;
 
816
        }
 
817
        if (keyseg->flag & HA_NULL_PART)
 
818
        {
 
819
          key++;                                /* Skip null marker*/
 
820
          start++;
 
821
        }
 
822
 
 
823
        get_key_length(rest_length,page);
 
824
        tot_length=rest_length+length;
 
825
 
 
826
        /* If the stored length has changed, we must move the key */
 
827
        if (tot_length >= 255 && *start != 255)
 
828
        {
 
829
          /* length prefix changed from a length of one to a length of 3 */
 
830
          bmove_upp(key+length+3, key+length+1, length);
 
831
          *key=255;
 
832
          mi_int2store(key+1,tot_length);
 
833
          key+=3+length;
 
834
        }
 
835
        else if (tot_length < 255 && *start == 255)
 
836
        {
 
837
          bmove(key+1,key+3,length);
 
838
          *key=tot_length;
 
839
          key+=1+length;
 
840
        }
 
841
        else
 
842
        {
 
843
          store_key_length_inc(key,tot_length);
 
844
          key+=length;
 
845
        }
 
846
        memcpy(key,page,rest_length);
 
847
        page+=rest_length;
 
848
        key+=rest_length;
 
849
        continue;
 
850
      }
 
851
      else
 
852
      {
 
853
        if (keyseg->flag & HA_NULL_PART)
 
854
        {
 
855
          if (!length--)                        /* Null part */
 
856
          {
 
857
            *key++=0;
 
858
            continue;
 
859
          }
 
860
          *key++=1;                             /* Not null */
 
861
        }
 
862
      }
 
863
      if (length > (uint) keyseg->length)
 
864
      {
 
865
        DBUG_PRINT("error",("Found too long packed key: %u of %u at 0x%lx",
 
866
                            length, keyseg->length, (long) *page_pos));
 
867
        DBUG_DUMP("key",(uchar*) *page_pos,16);
 
868
        mi_print_error(keyinfo->share, HA_ERR_CRASHED);
 
869
        my_errno=HA_ERR_CRASHED;
 
870
        return 0;                               /* Error */
 
871
      }
 
872
      store_key_length_inc(key,length);
 
873
    }
 
874
    else
 
875
    {
 
876
      if (keyseg->flag & HA_NULL_PART)
 
877
      {
 
878
        if (!(*key++ = *page++))
 
879
          continue;
 
880
      }
 
881
      if (keyseg->flag &
 
882
          (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
 
883
      {
 
884
        uchar *tmp=page;
 
885
        get_key_length(length,tmp);
 
886
        length+=(uint) (tmp-page);
 
887
      }
 
888
      else
 
889
        length=keyseg->length;
 
890
    }
 
891
    memcpy((uchar*) key,(uchar*) page,(size_t) length);
 
892
    key+=length;
 
893
    page+=length;
 
894
  }
 
895
  length=keyseg->length+nod_flag;
 
896
  bmove((uchar*) key,(uchar*) page,length);
 
897
  *page_pos= page+length;
 
898
  return ((uint) (key-start_key)+keyseg->length);
 
899
} /* _mi_get_pack_key */
 
900
 
 
901
 
 
902
 
 
903
/* key that is packed relatively to previous */
 
904
 
 
905
uint _mi_get_binary_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
 
906
                             register uchar **page_pos, register uchar *key)
 
907
{
 
908
  register HA_KEYSEG *keyseg;
 
909
  uchar *start_key,*page,*page_end,*from,*from_end;
 
910
  uint length,tmp;
 
911
  DBUG_ENTER("_mi_get_binary_pack_key");
 
912
 
 
913
  page= *page_pos;
 
914
  page_end=page+MI_MAX_KEY_BUFF+1;
 
915
  start_key=key;
 
916
 
 
917
  /*
 
918
    Keys are compressed the following way:
 
919
 
 
920
    prefix length    Packed length of prefix common with prev key (1 or 3 bytes)
 
921
    for each key segment:
 
922
      [is null]        Null indicator if can be null (1 byte, zero means null)
 
923
      [length]         Packed length if varlength (1 or 3 bytes)
 
924
      key segment      'length' bytes of key segment value
 
925
    pointer          Reference to the data file (last_keyseg->length).
 
926
 
 
927
    get_key_length() is a macro. It gets the prefix length from 'page'
 
928
    and puts it into 'length'. It increments 'page' by 1 or 3, depending
 
929
    on the packed length of the prefix length.
 
930
  */
 
931
  get_key_length(length,page);
 
932
  if (length)
 
933
  {
 
934
    if (length > keyinfo->maxlength)
 
935
    {
 
936
      DBUG_PRINT("error",
 
937
                 ("Found too long binary packed key: %u of %u at 0x%lx",
 
938
                  length, keyinfo->maxlength, (long) *page_pos));
 
939
      DBUG_DUMP("key",(uchar*) *page_pos,16);
 
940
      mi_print_error(keyinfo->share, HA_ERR_CRASHED);
 
941
      my_errno=HA_ERR_CRASHED;
 
942
      DBUG_RETURN(0);                                 /* Wrong key */
 
943
    }
 
944
    /* Key is packed against prev key, take prefix from prev key. */
 
945
    from= key;
 
946
    from_end= key + length;
 
947
  }
 
948
  else
 
949
  {
 
950
    /* Key is not packed against prev key, take all from page buffer. */
 
951
    from= page;
 
952
    from_end= page_end;
 
953
  }
 
954
 
 
955
  /*
 
956
    The trouble is that key can be split in two parts:
 
957
      The first part (prefix) is in from .. from_end - 1.
 
958
      The second part starts at page.
 
959
    The split can be at every byte position. So we need to check for
 
960
    the end of the first part before using every byte.
 
961
  */
 
962
  for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
 
963
  {
 
964
    if (keyseg->flag & HA_NULL_PART)
 
965
    {
 
966
      /* If prefix is used up, switch to rest. */
 
967
      if (from == from_end) { from=page;  from_end=page_end; }
 
968
      if (!(*key++ = *from++))
 
969
        continue;                               /* Null part */
 
970
    }
 
971
    if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
 
972
    {
 
973
      /* If prefix is used up, switch to rest. */
 
974
      if (from == from_end) { from=page;  from_end=page_end; }
 
975
      /* Get length of dynamic length key part */
 
976
      if ((length= (*key++ = *from++)) == 255)
 
977
      {
 
978
        /* If prefix is used up, switch to rest. */
 
979
        if (from == from_end) { from=page;  from_end=page_end; }
 
980
        length= (uint) ((*key++ = *from++)) << 8;
 
981
        /* If prefix is used up, switch to rest. */
 
982
        if (from == from_end) { from=page;  from_end=page_end; }
 
983
        length+= (uint) ((*key++ = *from++));
 
984
      }
 
985
    }
 
986
    else
 
987
      length=keyseg->length;
 
988
 
 
989
    if ((tmp=(uint) (from_end-from)) <= length)
 
990
    {
 
991
      key+=tmp;                                 /* Use old key */
 
992
      length-=tmp;
 
993
      from=page; from_end=page_end;
 
994
    }
 
995
    DBUG_PRINT("info",("key: 0x%lx  from: 0x%lx  length: %u",
 
996
                       (long) key, (long) from, length));
 
997
    memmove((uchar*) key, (uchar*) from, (size_t) length);
 
998
    key+=length;
 
999
    from+=length;
 
1000
  }
 
1001
  /*
 
1002
    Last segment (type == 0) contains length of data pointer.
 
1003
    If we have mixed key blocks with data pointer and key block pointer,
 
1004
    we have to copy both.
 
1005
  */
 
1006
  length=keyseg->length+nod_flag;
 
1007
  if ((tmp=(uint) (from_end-from)) <= length)
 
1008
  {
 
1009
    /* Remaining length is less or equal max possible length. */
 
1010
    memcpy(key+tmp,page,length-tmp);            /* Get last part of key */
 
1011
    *page_pos= page+length-tmp;
 
1012
  }
 
1013
  else
 
1014
  {
 
1015
    /*
 
1016
      Remaining length is greater than max possible length.
 
1017
      This can happen only if we switched to the new key bytes already.
 
1018
      'page_end' is calculated with MI_MAX_KEY_BUFF. So it can be far
 
1019
      behind the real end of the key.
 
1020
    */
 
1021
    if (from_end != page_end)
 
1022
    {
 
1023
      DBUG_PRINT("error",("Error when unpacking key"));
 
1024
      mi_print_error(keyinfo->share, HA_ERR_CRASHED);
 
1025
      my_errno=HA_ERR_CRASHED;
 
1026
      DBUG_RETURN(0);                                 /* Error */
 
1027
    }
 
1028
    /* Copy data pointer and, if appropriate, key block pointer. */
 
1029
    memcpy((uchar*) key,(uchar*) from,(size_t) length);
 
1030
    *page_pos= from+length;
 
1031
  }
 
1032
  DBUG_RETURN((uint) (key-start_key)+keyseg->length);
 
1033
}
 
1034
 
 
1035
 
 
1036
        /* Get key at position without knowledge of previous key */
 
1037
        /* Returns pointer to next key */
 
1038
 
 
1039
uchar *_mi_get_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
 
1040
                   uchar *key, uchar *keypos, uint *return_key_length)
 
1041
{
 
1042
  uint nod_flag;
 
1043
  DBUG_ENTER("_mi_get_key");
 
1044
 
 
1045
  nod_flag=mi_test_if_nod(page);
 
1046
  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
 
1047
  {
 
1048
    bmove((uchar*) key,(uchar*) keypos,keyinfo->keylength+nod_flag);
 
1049
    DBUG_RETURN(keypos+keyinfo->keylength+nod_flag);
 
1050
  }
 
1051
  else
 
1052
  {
 
1053
    page+=2+nod_flag;
 
1054
    key[0]=0;                                   /* safety */
 
1055
    while (page <= keypos)
 
1056
    {
 
1057
      *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
 
1058
      if (*return_key_length == 0)
 
1059
      {
 
1060
        mi_print_error(info->s, HA_ERR_CRASHED);
 
1061
        my_errno=HA_ERR_CRASHED;
 
1062
        DBUG_RETURN(0);
 
1063
      }
 
1064
    }
 
1065
  }
 
1066
  DBUG_PRINT("exit",("page: 0x%lx  length: %u", (long) page,
 
1067
                     *return_key_length));
 
1068
  DBUG_RETURN(page);
 
1069
} /* _mi_get_key */
 
1070
 
 
1071
 
 
1072
        /* Get key at position without knowledge of previous key */
 
1073
        /* Returns 0 if ok */
 
1074
 
 
1075
static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
 
1076
                                uchar *key, uchar *keypos,
 
1077
                                uint *return_key_length)
 
1078
{
 
1079
  uint nod_flag;
 
1080
  DBUG_ENTER("_mi_get_prev_key");
 
1081
 
 
1082
  nod_flag=mi_test_if_nod(page);
 
1083
  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
 
1084
  {
 
1085
    *return_key_length=keyinfo->keylength;
 
1086
    bmove((uchar*) key,(uchar*) keypos- *return_key_length-nod_flag,
 
1087
          *return_key_length);
 
1088
    DBUG_RETURN(0);
 
1089
  }
 
1090
  else
 
1091
  {
 
1092
    page+=2+nod_flag;
 
1093
    key[0]=0;                                   /* safety */
 
1094
    while (page < keypos)
 
1095
    {
 
1096
      *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
 
1097
      if (*return_key_length == 0)
 
1098
      {
 
1099
        mi_print_error(info->s, HA_ERR_CRASHED);
 
1100
        my_errno=HA_ERR_CRASHED;
 
1101
        DBUG_RETURN(1);
 
1102
      }
 
1103
    }
 
1104
  }
 
1105
  DBUG_RETURN(0);
 
1106
} /* _mi_get_key */
 
1107
 
 
1108
 
 
1109
 
 
1110
        /* Get last key from key-page */
 
1111
        /* Return pointer to where key starts */
 
1112
 
 
1113
uchar *_mi_get_last_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
 
1114
                        uchar *lastkey, uchar *endpos, uint *return_key_length)
 
1115
{
 
1116
  uint nod_flag;
 
1117
  uchar *lastpos;
 
1118
  DBUG_ENTER("_mi_get_last_key");
 
1119
  DBUG_PRINT("enter",("page: 0x%lx  endpos: 0x%lx", (long) page,
 
1120
                      (long) endpos));
 
1121
 
 
1122
  nod_flag=mi_test_if_nod(page);
 
1123
  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
 
1124
  {
 
1125
    lastpos=endpos-keyinfo->keylength-nod_flag;
 
1126
    *return_key_length=keyinfo->keylength;
 
1127
    if (lastpos > page)
 
1128
      bmove((uchar*) lastkey,(uchar*) lastpos,keyinfo->keylength+nod_flag);
 
1129
  }
 
1130
  else
 
1131
  {
 
1132
    lastpos=(page+=2+nod_flag);
 
1133
    lastkey[0]=0;
 
1134
    while (page < endpos)
 
1135
    {
 
1136
      lastpos=page;
 
1137
      *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,lastkey);
 
1138
      if (*return_key_length == 0)
 
1139
      {
 
1140
        DBUG_PRINT("error",("Couldn't find last key:  page: 0x%lx",
 
1141
                            (long) page));
 
1142
        mi_print_error(info->s, HA_ERR_CRASHED);
 
1143
        my_errno=HA_ERR_CRASHED;
 
1144
        DBUG_RETURN(0);
 
1145
      }
 
1146
    }
 
1147
  }
 
1148
  DBUG_PRINT("exit",("lastpos: 0x%lx  length: %u", (long) lastpos,
 
1149
                     *return_key_length));
 
1150
  DBUG_RETURN(lastpos);
 
1151
} /* _mi_get_last_key */
 
1152
 
 
1153
 
 
1154
        /* Calculate length of key */
 
1155
 
 
1156
uint _mi_keylength(MI_KEYDEF *keyinfo, register uchar *key)
 
1157
{
 
1158
  register HA_KEYSEG *keyseg;
 
1159
  uchar *start;
 
1160
 
 
1161
  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
 
1162
    return (keyinfo->keylength);
 
1163
 
 
1164
  start=key;
 
1165
  for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
 
1166
  {
 
1167
    if (keyseg->flag & HA_NULL_PART)
 
1168
      if (!*key++)
 
1169
        continue;
 
1170
    if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
 
1171
    {
 
1172
      uint length;
 
1173
      get_key_length(length,key);
 
1174
      key+=length;
 
1175
    }
 
1176
    else
 
1177
      key+= keyseg->length;
 
1178
  }
 
1179
  return((uint) (key-start)+keyseg->length);
 
1180
} /* _mi_keylength */
 
1181
 
 
1182
 
 
1183
/*
 
1184
  Calculate length of part key.
 
1185
 
 
1186
  Used in mi_rkey() to find the key found for the key-part that was used.
 
1187
  This is needed in case of multi-byte character sets where we may search
 
1188
  after '0xDF' but find 'ss'
 
1189
*/
 
1190
 
 
1191
uint _mi_keylength_part(MI_KEYDEF *keyinfo, register uchar *key,
 
1192
                        HA_KEYSEG *end)
 
1193
{
 
1194
  register HA_KEYSEG *keyseg;
 
1195
  uchar *start= key;
 
1196
 
 
1197
  for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
 
1198
  {
 
1199
    if (keyseg->flag & HA_NULL_PART)
 
1200
      if (!*key++)
 
1201
        continue;
 
1202
    if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
 
1203
    {
 
1204
      uint length;
 
1205
      get_key_length(length,key);
 
1206
      key+=length;
 
1207
    }
 
1208
    else
 
1209
      key+= keyseg->length;
 
1210
  }
 
1211
  return (uint) (key-start);
 
1212
}
 
1213
 
 
1214
        /* Move a key */
 
1215
 
 
1216
uchar *_mi_move_key(MI_KEYDEF *keyinfo, uchar *to, uchar *from)
 
1217
{
 
1218
  register uint length;
 
1219
  memcpy((uchar*) to, (uchar*) from,
 
1220
         (size_t) (length=_mi_keylength(keyinfo,from)));
 
1221
  return to+length;
 
1222
}
 
1223
 
 
1224
        /* Find next/previous record with same key */
 
1225
        /* This can't be used when database is touched after last read */
 
1226
 
 
1227
int _mi_search_next(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 
1228
                    uchar *key, uint key_length, uint nextflag, my_off_t pos)
 
1229
{
 
1230
  int error;
 
1231
  uint nod_flag;
 
1232
  uchar lastkey[MI_MAX_KEY_BUFF];
 
1233
  DBUG_ENTER("_mi_search_next");
 
1234
  DBUG_PRINT("enter",("nextflag: %u  lastpos: %lu  int_keypos: %lu",
 
1235
                      nextflag, (ulong) info->lastpos,
 
1236
                      (ulong) info->int_keypos));
 
1237
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_length););
 
1238
 
 
1239
  /* Force full read if we are at last key or if we are not on a leaf
 
1240
     and the key tree has changed since we used it last time
 
1241
     Note that even if the key tree has changed since last read, we can use
 
1242
     the last read data from the leaf if we haven't used the buffer for
 
1243
     something else.
 
1244
  */
 
1245
 
 
1246
  if (((nextflag & SEARCH_BIGGER) && info->int_keypos >= info->int_maxpos) ||
 
1247
      info->page_changed ||
 
1248
      (info->int_keytree_version != keyinfo->version &&
 
1249
       (info->int_nod_flag || info->buff_used)))
 
1250
    DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
 
1251
                           nextflag | SEARCH_SAVE_BUFF, pos));
 
1252
 
 
1253
  if (info->buff_used)
 
1254
  {
 
1255
    if (!_mi_fetch_keypage(info,keyinfo,info->last_search_keypage,
 
1256
                           DFLT_INIT_HITS,info->buff,0))
 
1257
      DBUG_RETURN(-1);
 
1258
    info->buff_used=0;
 
1259
  }
 
1260
 
 
1261
  /* Last used buffer is in info->buff */
 
1262
  nod_flag=mi_test_if_nod(info->buff);
 
1263
 
 
1264
  if (nextflag & SEARCH_BIGGER)                                 /* Next key */
 
1265
  {
 
1266
    my_off_t tmp_pos=_mi_kpos(nod_flag,info->int_keypos);
 
1267
    if (tmp_pos != HA_OFFSET_ERROR)
 
1268
    {
 
1269
      if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
 
1270
                            nextflag | SEARCH_SAVE_BUFF, tmp_pos)) <=0)
 
1271
        DBUG_RETURN(error);
 
1272
    }
 
1273
    memcpy(lastkey,key,key_length);
 
1274
    if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,
 
1275
                                                   &info->int_keypos,lastkey)))
 
1276
      DBUG_RETURN(-1);
 
1277
  }
 
1278
  else                                                  /* Previous key */
 
1279
  {
 
1280
    uint length;
 
1281
    /* Find start of previous key */
 
1282
    info->int_keypos=_mi_get_last_key(info,keyinfo,info->buff,lastkey,
 
1283
                                      info->int_keypos, &length);
 
1284
    if (!info->int_keypos)
 
1285
      DBUG_RETURN(-1);
 
1286
    if (info->int_keypos == info->buff+2)
 
1287
      DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
 
1288
                             nextflag | SEARCH_SAVE_BUFF, pos));
 
1289
    if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
 
1290
                          nextflag | SEARCH_SAVE_BUFF,
 
1291
                          _mi_kpos(nod_flag,info->int_keypos))) <= 0)
 
1292
      DBUG_RETURN(error);
 
1293
 
 
1294
    /* QQ: We should be able to optimize away the following call */
 
1295
    if (! _mi_get_last_key(info,keyinfo,info->buff,lastkey,
 
1296
                           info->int_keypos,&info->lastkey_length))
 
1297
      DBUG_RETURN(-1);
 
1298
  }
 
1299
  memcpy(info->lastkey,lastkey,info->lastkey_length);
 
1300
  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
 
1301
  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
 
1302
  DBUG_RETURN(0);
 
1303
} /* _mi_search_next */
 
1304
 
 
1305
 
 
1306
        /* Search after position for the first row in an index */
 
1307
        /* This is stored in info->lastpos */
 
1308
 
 
1309
int _mi_search_first(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 
1310
                     register my_off_t pos)
 
1311
{
 
1312
  uint nod_flag;
 
1313
  uchar *page;
 
1314
  DBUG_ENTER("_mi_search_first");
 
1315
 
 
1316
  if (pos == HA_OFFSET_ERROR)
 
1317
  {
 
1318
    my_errno=HA_ERR_KEY_NOT_FOUND;
 
1319
    info->lastpos= HA_OFFSET_ERROR;
 
1320
    DBUG_RETURN(-1);
 
1321
  }
 
1322
 
 
1323
  do
 
1324
  {
 
1325
    if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,0))
 
1326
    {
 
1327
      info->lastpos= HA_OFFSET_ERROR;
 
1328
      DBUG_RETURN(-1);
 
1329
    }
 
1330
    nod_flag=mi_test_if_nod(info->buff);
 
1331
    page=info->buff+2+nod_flag;
 
1332
  } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
 
1333
 
 
1334
  if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,
 
1335
                                                 info->lastkey)))
 
1336
    DBUG_RETURN(-1);                            /* Crashed */
 
1337
 
 
1338
  info->int_keypos=page; info->int_maxpos=info->buff+mi_getint(info->buff)-1;
 
1339
  info->int_nod_flag=nod_flag;
 
1340
  info->int_keytree_version=keyinfo->version;
 
1341
  info->last_search_keypage=info->last_keypage;
 
1342
  info->page_changed=info->buff_used=0;
 
1343
  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
 
1344
 
 
1345
  DBUG_PRINT("exit",("found key at %lu", (ulong) info->lastpos));
 
1346
  DBUG_RETURN(0);
 
1347
} /* _mi_search_first */
 
1348
 
 
1349
 
 
1350
        /* Search after position for the last row in an index */
 
1351
        /* This is stored in info->lastpos */
 
1352
 
 
1353
int _mi_search_last(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 
1354
                    register my_off_t pos)
 
1355
{
 
1356
  uint nod_flag;
 
1357
  uchar *buff,*page;
 
1358
  DBUG_ENTER("_mi_search_last");
 
1359
 
 
1360
  if (pos == HA_OFFSET_ERROR)
 
1361
  {
 
1362
    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
 
1363
    info->lastpos= HA_OFFSET_ERROR;
 
1364
    DBUG_RETURN(-1);
 
1365
  }
 
1366
 
 
1367
  buff=info->buff;
 
1368
  do
 
1369
  {
 
1370
    if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,buff,0))
 
1371
    {
 
1372
      info->lastpos= HA_OFFSET_ERROR;
 
1373
      DBUG_RETURN(-1);
 
1374
    }
 
1375
    page= buff+mi_getint(buff);
 
1376
    nod_flag=mi_test_if_nod(buff);
 
1377
  } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
 
1378
 
 
1379
  if (!_mi_get_last_key(info,keyinfo,buff,info->lastkey,page,
 
1380
                        &info->lastkey_length))
 
1381
    DBUG_RETURN(-1);
 
1382
  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
 
1383
  info->int_keypos=info->int_maxpos=page;
 
1384
  info->int_nod_flag=nod_flag;
 
1385
  info->int_keytree_version=keyinfo->version;
 
1386
  info->last_search_keypage=info->last_keypage;
 
1387
  info->page_changed=info->buff_used=0;
 
1388
 
 
1389
  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
 
1390
  DBUG_RETURN(0);
 
1391
} /* _mi_search_last */
 
1392
 
 
1393
 
 
1394
 
 
1395
/****************************************************************************
 
1396
**
 
1397
** Functions to store and pack a key in a page
 
1398
**
 
1399
** mi_calc_xx_key_length takes the following arguments:
 
1400
**  nod_flag    If nod: Length of nod-pointer
 
1401
**  next_key    Position to pos after the new key in buffer
 
1402
**  org_key     Key that was before the next key in buffer
 
1403
**  prev_key    Last key before current key
 
1404
**  key         Key that will be stored
 
1405
**  s_temp      Information how next key will be packed
 
1406
****************************************************************************/
 
1407
 
 
1408
/* Static length key */
 
1409
 
 
1410
int
 
1411
_mi_calc_static_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
 
1412
                           uchar *next_pos  __attribute__((unused)),
 
1413
                           uchar *org_key  __attribute__((unused)),
 
1414
                           uchar *prev_key __attribute__((unused)),
 
1415
                           uchar *key, MI_KEY_PARAM *s_temp)
 
1416
{
 
1417
  s_temp->key=key;
 
1418
  return (int) (s_temp->totlength=keyinfo->keylength+nod_flag);
 
1419
}
 
1420
 
 
1421
/* Variable length key */
 
1422
 
 
1423
int
 
1424
_mi_calc_var_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
 
1425
                        uchar *next_pos  __attribute__((unused)),
 
1426
                        uchar *org_key  __attribute__((unused)),
 
1427
                        uchar *prev_key __attribute__((unused)),
 
1428
                        uchar *key, MI_KEY_PARAM *s_temp)
 
1429
{
 
1430
  s_temp->key=key;
 
1431
  return (int) (s_temp->totlength=_mi_keylength(keyinfo,key)+nod_flag);
 
1432
}
 
1433
 
 
1434
/*
 
1435
  length of key with a variable length first segment which is prefix
 
1436
  compressed (myisamchk reports 'packed + stripped')
 
1437
 
 
1438
  Keys are compressed the following way:
 
1439
 
 
1440
  If the max length of first key segment <= 127 bytes the prefix is
 
1441
  1 byte else it's 2 byte
 
1442
 
 
1443
  prefix byte(s) The high bit is set if this is a prefix for the prev key
 
1444
  length         Packed length if the previous was a prefix byte
 
1445
  [length]       data bytes ('length' bytes)
 
1446
  next-key-seg   Next key segments
 
1447
 
 
1448
  If the first segment can have NULL:
 
1449
  The length is 0 for NULLS and 1+length for not null columns.
 
1450
 
 
1451
*/
 
1452
 
 
1453
int
 
1454
_mi_calc_var_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
 
1455
                             uchar *org_key, uchar *prev_key, uchar *key,
 
1456
                             MI_KEY_PARAM *s_temp)
 
1457
{
 
1458
  register HA_KEYSEG *keyseg;
 
1459
  int length;
 
1460
  uint key_length,ref_length,org_key_length=0,
 
1461
       length_pack,new_key_length,diff_flag,pack_marker;
 
1462
  uchar *start,*end,*key_end,*sort_order;
 
1463
  my_bool same_length;
 
1464
 
 
1465
  length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
 
1466
  same_length=0; keyseg=keyinfo->seg;
 
1467
  key_length=_mi_keylength(keyinfo,key)+nod_flag;
 
1468
 
 
1469
  sort_order=0;
 
1470
  if ((keyinfo->flag & HA_FULLTEXT) &&
 
1471
      ((keyseg->type == HA_KEYTYPE_TEXT) ||
 
1472
       (keyseg->type == HA_KEYTYPE_VARTEXT1) ||
 
1473
       (keyseg->type == HA_KEYTYPE_VARTEXT2)) &&
 
1474
      !use_strnxfrm(keyseg->charset))
 
1475
    sort_order=keyseg->charset->sort_order;
 
1476
 
 
1477
  /* diff flag contains how many bytes is needed to pack key */
 
1478
  if (keyseg->length >= 127)
 
1479
  {
 
1480
    diff_flag=2;
 
1481
    pack_marker=32768;
 
1482
  }
 
1483
  else
 
1484
  {
 
1485
    diff_flag= 1;
 
1486
    pack_marker=128;
 
1487
  }
 
1488
  s_temp->pack_marker=pack_marker;
 
1489
 
 
1490
  /* Handle the case that the first part have NULL values */
 
1491
  if (keyseg->flag & HA_NULL_PART)
 
1492
  {
 
1493
    if (!*key++)
 
1494
    {
 
1495
      s_temp->key=key;
 
1496
      s_temp->key_length= 0;
 
1497
      s_temp->totlength=key_length-1+diff_flag;
 
1498
      s_temp->next_key_pos=0;                   /* No next key */
 
1499
      return (s_temp->totlength);
 
1500
    }
 
1501
    s_temp->store_not_null=1;
 
1502
    key_length--;                               /* We don't store NULL */
 
1503
    if (prev_key && !*prev_key++)
 
1504
      org_key=prev_key=0;                       /* Can't pack against prev */
 
1505
    else if (org_key)
 
1506
      org_key++;                                /* Skip NULL */
 
1507
  }
 
1508
  else
 
1509
    s_temp->store_not_null=0;
 
1510
  s_temp->prev_key=org_key;
 
1511
 
 
1512
  /* The key part will start with a packed length */
 
1513
 
 
1514
  get_key_pack_length(new_key_length,length_pack,key);
 
1515
  end=key_end= key+ new_key_length;
 
1516
  start=key;
 
1517
 
 
1518
  /* Calc how many characters are identical between this and the prev. key */
 
1519
  if (prev_key)
 
1520
  {
 
1521
    get_key_length(org_key_length,prev_key);
 
1522
    s_temp->prev_key=prev_key;          /* Pointer at data */
 
1523
    /* Don't use key-pack if length == 0 */
 
1524
    if (new_key_length && new_key_length == org_key_length)
 
1525
      same_length=1;
 
1526
    else if (new_key_length > org_key_length)
 
1527
      end=key + org_key_length;
 
1528
 
 
1529
    if (sort_order)                             /* SerG */
 
1530
    {
 
1531
      while (key < end && sort_order[*key] == sort_order[*prev_key])
 
1532
      {
 
1533
        key++; prev_key++;
 
1534
      }
 
1535
    }
 
1536
    else
 
1537
    {
 
1538
      while (key < end && *key == *prev_key)
 
1539
      {
 
1540
        key++; prev_key++;
 
1541
      }
 
1542
    }
 
1543
  }
 
1544
 
 
1545
  s_temp->key=key;
 
1546
  s_temp->key_length= (uint) (key_end-key);
 
1547
 
 
1548
  if (same_length && key == key_end)
 
1549
  {
 
1550
    /* identical variable length key */
 
1551
    s_temp->ref_length= pack_marker;
 
1552
    length=(int) key_length-(int) (key_end-start)-length_pack;
 
1553
    length+= diff_flag;
 
1554
    if (next_key)
 
1555
    {                                           /* Can't combine with next */
 
1556
      s_temp->n_length= *next_key;              /* Needed by _mi_store_key */
 
1557
      next_key=0;
 
1558
    }
 
1559
  }
 
1560
  else
 
1561
  {
 
1562
    if (start != key)
 
1563
    {                                           /* Starts as prev key */
 
1564
      ref_length= (uint) (key-start);
 
1565
      s_temp->ref_length= ref_length + pack_marker;
 
1566
      length= (int) (key_length - ref_length);
 
1567
 
 
1568
      length-= length_pack;
 
1569
      length+= diff_flag;
 
1570
      length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;/* Rest_of_key */
 
1571
    }
 
1572
    else
 
1573
    {
 
1574
      s_temp->key_length+=s_temp->store_not_null;       /* If null */
 
1575
      length= key_length - length_pack+ diff_flag;
 
1576
    }
 
1577
  }
 
1578
  s_temp->totlength=(uint) length;
 
1579
  s_temp->prev_length=0;
 
1580
  DBUG_PRINT("test",("tot_length: %u  length: %d  uniq_key_length: %u",
 
1581
                     key_length, length, s_temp->key_length));
 
1582
 
 
1583
        /* If something after that hasn't length=0, test if we can combine */
 
1584
  if ((s_temp->next_key_pos=next_key))
 
1585
  {
 
1586
    uint packed,n_length;
 
1587
 
 
1588
    packed = *next_key & 128;
 
1589
    if (diff_flag == 2)
 
1590
    {
 
1591
      n_length= mi_uint2korr(next_key) & 32767; /* Length of next key */
 
1592
      next_key+=2;
 
1593
    }
 
1594
    else
 
1595
      n_length= *next_key++ & 127;
 
1596
    if (!packed)
 
1597
      n_length-= s_temp->store_not_null;
 
1598
 
 
1599
    if (n_length || packed)             /* Don't pack 0 length keys */
 
1600
    {
 
1601
      uint next_length_pack, new_ref_length=s_temp->ref_length;
 
1602
 
 
1603
      if (packed)
 
1604
      {
 
1605
        /* If first key and next key is packed (only on delete) */
 
1606
        if (!prev_key && org_key)
 
1607
        {
 
1608
          get_key_length(org_key_length,org_key);
 
1609
          key=start;
 
1610
          if (sort_order)                       /* SerG */
 
1611
          {
 
1612
            while (key < end && sort_order[*key] == sort_order[*org_key])
 
1613
            {
 
1614
              key++; org_key++;
 
1615
            }
 
1616
          }
 
1617
          else
 
1618
          {
 
1619
            while (key < end && *key == *org_key)
 
1620
            {
 
1621
              key++; org_key++;
 
1622
            }
 
1623
          }
 
1624
          if ((new_ref_length= (uint) (key - start)))
 
1625
            new_ref_length+=pack_marker;
 
1626
        }
 
1627
 
 
1628
        if (!n_length)
 
1629
        {
 
1630
          /*
 
1631
            We put a different key between two identical variable length keys
 
1632
            Extend next key to have same prefix as this key
 
1633
          */
 
1634
          if (new_ref_length)                   /* prefix of previus key */
 
1635
          {                                     /* make next key longer */
 
1636
            s_temp->part_of_prev_key= new_ref_length;
 
1637
            s_temp->prev_length=          org_key_length -
 
1638
              (new_ref_length-pack_marker);
 
1639
            s_temp->n_ref_length= s_temp->part_of_prev_key;
 
1640
            s_temp->n_length= s_temp->prev_length;
 
1641
            n_length=             get_pack_length(s_temp->prev_length);
 
1642
            s_temp->prev_key+=    (new_ref_length - pack_marker);
 
1643
            length+=              s_temp->prev_length + n_length;
 
1644
          }
 
1645
          else
 
1646
          {                                     /* Can't use prev key */
 
1647
            s_temp->part_of_prev_key=0;
 
1648
            s_temp->prev_length= org_key_length;
 
1649
            s_temp->n_ref_length=s_temp->n_length=  org_key_length;
 
1650
            length+=           org_key_length;
 
1651
          }
 
1652
          return (int) length;
 
1653
        }
 
1654
 
 
1655
        ref_length=n_length;
 
1656
        /* Get information about not packed key suffix */
 
1657
        get_key_pack_length(n_length,next_length_pack,next_key);
 
1658
 
 
1659
        /* Test if new keys has fewer characters that match the previous key */
 
1660
        if (!new_ref_length)
 
1661
        {                                       /* Can't use prev key */
 
1662
          s_temp->part_of_prev_key=     0;
 
1663
          s_temp->prev_length=          ref_length;
 
1664
          s_temp->n_ref_length= s_temp->n_length= n_length+ref_length;
 
1665
          return (int) length+ref_length-next_length_pack;
 
1666
        }
 
1667
        if (ref_length+pack_marker > new_ref_length)
 
1668
        {
 
1669
          uint new_pack_length=new_ref_length-pack_marker;
 
1670
          /* We must copy characters from the original key to the next key */
 
1671
          s_temp->part_of_prev_key= new_ref_length;
 
1672
          s_temp->prev_length=      ref_length - new_pack_length;
 
1673
          s_temp->n_ref_length=s_temp->n_length=n_length + s_temp->prev_length;
 
1674
          s_temp->prev_key+=        new_pack_length;
 
1675
          length-= (next_length_pack - get_pack_length(s_temp->n_length));
 
1676
          return (int) length + s_temp->prev_length;
 
1677
        }
 
1678
      }
 
1679
      else
 
1680
      {
 
1681
        /* Next key wasn't a prefix of previous key */
 
1682
        ref_length=0;
 
1683
        next_length_pack=0;
 
1684
      }
 
1685
      DBUG_PRINT("test",("length: %d  next_key: 0x%lx", length,
 
1686
                         (long) next_key));
 
1687
 
 
1688
      {
 
1689
        uint tmp_length;
 
1690
        key=(start+=ref_length);
 
1691
        if (key+n_length < key_end)             /* Normalize length based */
 
1692
          key_end=key+n_length;
 
1693
        if (sort_order)                         /* SerG */
 
1694
        {
 
1695
          while (key < key_end && sort_order[*key] ==
 
1696
                 sort_order[*next_key])
 
1697
          {
 
1698
            key++; next_key++;
 
1699
          }
 
1700
        }
 
1701
        else
 
1702
        {
 
1703
          while (key < key_end && *key == *next_key)
 
1704
          {
 
1705
            key++; next_key++;
 
1706
          }
 
1707
        }
 
1708
        if (!(tmp_length=(uint) (key-start)))
 
1709
        {                                       /* Key can't be re-packed */
 
1710
          s_temp->next_key_pos=0;
 
1711
          return length;
 
1712
        }
 
1713
        ref_length+=tmp_length;
 
1714
        n_length-=tmp_length;
 
1715
        length-=tmp_length+next_length_pack;    /* We gained these chars */
 
1716
      }
 
1717
      if (n_length == 0 && ref_length == new_key_length)
 
1718
      {
 
1719
        s_temp->n_ref_length=pack_marker;       /* Same as prev key */
 
1720
      }
 
1721
      else
 
1722
      {
 
1723
        s_temp->n_ref_length=ref_length | pack_marker;
 
1724
        length+= get_pack_length(n_length);
 
1725
        s_temp->n_length=n_length;
 
1726
      }
 
1727
    }
 
1728
  }
 
1729
  return length;
 
1730
}
 
1731
 
 
1732
 
 
1733
/* Length of key which is prefix compressed */
 
1734
 
 
1735
int
 
1736
_mi_calc_bin_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
 
1737
                             uchar *org_key, uchar *prev_key, uchar *key,
 
1738
                             MI_KEY_PARAM *s_temp)
 
1739
{
 
1740
  uint length,key_length,ref_length;
 
1741
 
 
1742
  s_temp->totlength=key_length=_mi_keylength(keyinfo,key)+nod_flag;
 
1743
#ifdef HAVE_purify
 
1744
  s_temp->n_length= s_temp->n_ref_length=0;     /* For valgrind */
 
1745
#endif
 
1746
  s_temp->key=key;
 
1747
  s_temp->prev_key=org_key;
 
1748
  if (prev_key)                                 /* If not first key in block */
 
1749
  {
 
1750
    /* pack key against previous key */
 
1751
    /*
 
1752
      As keys may be identical when running a sort in myisamchk, we
 
1753
      have to guard against the case where keys may be identical
 
1754
    */
 
1755
    uchar *end;
 
1756
    end=key+key_length;
 
1757
    for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
 
1758
    s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
 
1759
    length=key_length - ref_length + get_pack_length(ref_length);
 
1760
  }
 
1761
  else
 
1762
  {
 
1763
    /* No previous key */
 
1764
    s_temp->ref_length=ref_length=0;
 
1765
    length=key_length+1;
 
1766
  }
 
1767
  if ((s_temp->next_key_pos=next_key))          /* If another key after */
 
1768
  {
 
1769
    /* pack key against next key */
 
1770
    uint next_length,next_length_pack;
 
1771
    get_key_pack_length(next_length,next_length_pack,next_key);
 
1772
 
 
1773
    /* If first key and next key is packed (only on delete) */
 
1774
    if (!prev_key && org_key && next_length)
 
1775
    {
 
1776
      uchar *end;
 
1777
      for (key= s_temp->key, end=key+next_length ;
 
1778
           *key == *org_key && key < end;
 
1779
           key++,org_key++) ;
 
1780
      ref_length= (uint) (key - s_temp->key);
 
1781
    }
 
1782
 
 
1783
    if (next_length > ref_length)
 
1784
    {
 
1785
      /* We put a key with different case between two keys with the same prefix
 
1786
         Extend next key to have same prefix as
 
1787
         this key */
 
1788
      s_temp->n_ref_length= ref_length;
 
1789
      s_temp->prev_length=  next_length-ref_length;
 
1790
      s_temp->prev_key+=    ref_length;
 
1791
      return (int) (length+ s_temp->prev_length - next_length_pack +
 
1792
                    get_pack_length(ref_length));
 
1793
    }
 
1794
    /* Check how many characters are identical to next key */
 
1795
    key= s_temp->key+next_length;
 
1796
    while (*key++ == *next_key++) ;
 
1797
    if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
 
1798
    {
 
1799
      s_temp->next_key_pos=0;
 
1800
      return length;                            /* can't pack next key */
 
1801
    }
 
1802
    s_temp->prev_length=0;
 
1803
    s_temp->n_ref_length=ref_length;
 
1804
    return (int) (length-(ref_length - next_length) - next_length_pack +
 
1805
                  get_pack_length(ref_length));
 
1806
  }
 
1807
  return (int) length;
 
1808
}
 
1809
 
 
1810
 
 
1811
/*
 
1812
** store a key packed with _mi_calc_xxx_key_length in page-buffert
 
1813
*/
 
1814
 
 
1815
/* store key without compression */
 
1816
 
 
1817
void _mi_store_static_key(MI_KEYDEF *keyinfo __attribute__((unused)),
 
1818
                          register uchar *key_pos,
 
1819
                          register MI_KEY_PARAM *s_temp)
 
1820
{
 
1821
  memcpy((uchar*) key_pos,(uchar*) s_temp->key,(size_t) s_temp->totlength);
 
1822
}
 
1823
 
 
1824
 
 
1825
/* store variable length key with prefix compression */
 
1826
 
 
1827
#define store_pack_length(test,pos,length) { \
 
1828
  if (test) { *((pos)++) = (uchar) (length); } else \
 
1829
  { *((pos)++) = (uchar) ((length) >> 8); *((pos)++) = (uchar) (length);  } }
 
1830
 
 
1831
 
 
1832
void _mi_store_var_pack_key(MI_KEYDEF *keyinfo  __attribute__((unused)),
 
1833
                            register uchar *key_pos,
 
1834
                            register MI_KEY_PARAM *s_temp)
 
1835
{
 
1836
  uint length;
 
1837
  uchar *start;
 
1838
 
 
1839
  start=key_pos;
 
1840
 
 
1841
  if (s_temp->ref_length)
 
1842
  {
 
1843
    /* Packed against previous key */
 
1844
    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
 
1845
    /* If not same key after */
 
1846
    if (s_temp->ref_length != s_temp->pack_marker)
 
1847
      store_key_length_inc(key_pos,s_temp->key_length);
 
1848
  }
 
1849
  else
 
1850
  {
 
1851
    /* Not packed against previous key */
 
1852
    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
 
1853
  }
 
1854
  bmove((uchar*) key_pos,(uchar*) s_temp->key,
 
1855
        (length=s_temp->totlength-(uint) (key_pos-start)));
 
1856
 
 
1857
  if (!s_temp->next_key_pos)                    /* No following key */
 
1858
    return;
 
1859
  key_pos+=length;
 
1860
 
 
1861
  if (s_temp->prev_length)
 
1862
  {
 
1863
    /* Extend next key because new key didn't have same prefix as prev key */
 
1864
    if (s_temp->part_of_prev_key)
 
1865
    {
 
1866
      store_pack_length(s_temp->pack_marker == 128,key_pos,
 
1867
                        s_temp->part_of_prev_key);
 
1868
      store_key_length_inc(key_pos,s_temp->n_length);
 
1869
    }
 
1870
    else
 
1871
    {
 
1872
      s_temp->n_length+= s_temp->store_not_null;
 
1873
      store_pack_length(s_temp->pack_marker == 128,key_pos,
 
1874
                        s_temp->n_length);
 
1875
    }
 
1876
    memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
 
1877
  }
 
1878
  else if (s_temp->n_ref_length)
 
1879
  {
 
1880
    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
 
1881
    if (s_temp->n_ref_length == s_temp->pack_marker)
 
1882
      return;                                   /* Identical key */
 
1883
    store_key_length(key_pos,s_temp->n_length);
 
1884
  }
 
1885
  else
 
1886
  {
 
1887
    s_temp->n_length+= s_temp->store_not_null;
 
1888
    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
 
1889
  }
 
1890
}
 
1891
 
 
1892
 
 
1893
/* variable length key with prefix compression */
 
1894
 
 
1895
void _mi_store_bin_pack_key(MI_KEYDEF *keyinfo  __attribute__((unused)),
 
1896
                            register uchar *key_pos,
 
1897
                            register MI_KEY_PARAM *s_temp)
 
1898
{
 
1899
  store_key_length_inc(key_pos,s_temp->ref_length);
 
1900
  memcpy((char*) key_pos,(char*) s_temp->key+s_temp->ref_length,
 
1901
          (size_t) s_temp->totlength-s_temp->ref_length);
 
1902
 
 
1903
  if (s_temp->next_key_pos)
 
1904
  {
 
1905
    key_pos+=(uint) (s_temp->totlength-s_temp->ref_length);
 
1906
    store_key_length_inc(key_pos,s_temp->n_ref_length);
 
1907
    if (s_temp->prev_length)                    /* If we must extend key */
 
1908
    {
 
1909
      memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
 
1910
    }
 
1911
  }
 
1912
}