← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/myisam/mi_search.cc

  • Committer: Monty Taylor
  • Date: 2009-04-25 19:24:49 UTC
  • mto: (997.2.5 mordred)
  • mto: This revision was merged to the branch mainline in revision 1003.
  • Revision ID: mordred@inaugust.com-20090425192449-0htujbt2r9jzupn5
Moved heap.

Show diffs side-by-side

added added

removed removed

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