← Back to branch summary

~ubuntu-branches/ubuntu/trusty/drizzle/trusty

« back to all changes in this revision

Viewing changes to plugin/myisam/mi_search.cc

  • Committer: Bazaar Package Importer
  • Author(s): Monty Taylor
  • Date: 2010-03-18 12:12:31 UTC
  • Revision ID: james.westby@ubuntu.com-20100318121231-k6g1xe6cshbwa0f8
Tags: upstream-2010.03.1347
Import upstream version 2010.03.1347

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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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;
 
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_purify
 
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
}