← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/heap/hp_hash.c

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

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/heap/hp_hash.c
 
1
/* Copyright (C) 2000-2006 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
/* The hash functions used for saveing keys */
 
17
 
 
18
#include "heapdef.h"
 
19
#include <m_ctype.h>
 
20
 
 
21
 
 
22
 
 
23
/*
 
24
  Find out how many rows there is in the given range
 
25
 
 
26
  SYNOPSIS
 
27
    hp_rb_records_in_range()
 
28
    info                HEAP handler
 
29
    inx                 Index to use
 
30
    min_key             Min key. Is = 0 if no min range
 
31
    max_key             Max key. Is = 0 if no max range
 
32
 
 
33
  NOTES
 
34
    min_key.flag can have one of the following values:
 
35
      HA_READ_KEY_EXACT         Include the key in the range
 
36
      HA_READ_AFTER_KEY         Don't include key in range
 
37
 
 
38
    max_key.flag can have one of the following values:
 
39
      HA_READ_BEFORE_KEY        Don't include key in range
 
40
      HA_READ_AFTER_KEY         Include all 'end_key' values in the range
 
41
 
 
42
  RETURN
 
43
   HA_POS_ERROR         Something is wrong with the index tree.
 
44
   0                    There is no matching keys in the given range
 
45
   number > 0           There is approximately 'number' matching rows in
 
46
                        the range.
 
47
*/
 
48
 
 
49
ha_rows hp_rb_records_in_range(HP_INFO *info, int inx,  key_range *min_key,
 
50
                               key_range *max_key)
 
51
{
 
52
  ha_rows start_pos, end_pos;
 
53
  HP_KEYDEF *keyinfo= info->s->keydef + inx;
 
54
  TREE *rb_tree = &keyinfo->rb_tree;
 
55
  heap_rb_param custom_arg;
 
56
  DBUG_ENTER("hp_rb_records_in_range");
 
57
 
 
58
  info->lastinx= inx;
 
59
  custom_arg.keyseg= keyinfo->seg;
 
60
  custom_arg.search_flag= SEARCH_FIND | SEARCH_SAME;
 
61
  if (min_key)
 
62
  {
 
63
    custom_arg.key_length= hp_rb_pack_key(keyinfo, (uchar*) info->recbuf,
 
64
                                          (uchar*) min_key->key,
 
65
                                          min_key->keypart_map);
 
66
    start_pos= tree_record_pos(rb_tree, info->recbuf, min_key->flag,
 
67
                               &custom_arg);
 
68
  }
 
69
  else
 
70
  {
 
71
    start_pos= 0;
 
72
  }
 
73
 
 
74
  if (max_key)
 
75
  {
 
76
    custom_arg.key_length= hp_rb_pack_key(keyinfo, (uchar*) info->recbuf,
 
77
                                          (uchar*) max_key->key,
 
78
                                          max_key->keypart_map);
 
79
    end_pos= tree_record_pos(rb_tree, info->recbuf, max_key->flag,
 
80
                             &custom_arg);
 
81
  }
 
82
  else
 
83
  {
 
84
    end_pos= rb_tree->elements_in_tree + (ha_rows)1;
 
85
  }
 
86
 
 
87
  DBUG_PRINT("info",("start_pos: %lu  end_pos: %lu", (ulong) start_pos,
 
88
                     (ulong) end_pos));
 
89
  if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
 
90
    DBUG_RETURN(HA_POS_ERROR);
 
91
  DBUG_RETURN(end_pos < start_pos ? (ha_rows) 0 :
 
92
              (end_pos == start_pos ? (ha_rows) 1 : end_pos - start_pos));
 
93
}
 
94
 
 
95
 
 
96
        /* Search after a record based on a key */
 
97
        /* Sets info->current_ptr to found record */
 
98
        /* next_flag:  Search=0, next=1, prev =2, same =3 */
 
99
 
 
100
uchar *hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *key,
 
101
                uint nextflag)
 
102
{
 
103
  register HASH_INFO *pos,*prev_ptr;
 
104
  int flag;
 
105
  uint old_nextflag;
 
106
  HP_SHARE *share=info->s;
 
107
  DBUG_ENTER("hp_search");
 
108
  old_nextflag=nextflag;
 
109
  flag=1;
 
110
  prev_ptr=0;
 
111
 
 
112
  if (share->records)
 
113
  {
 
114
    pos=hp_find_hash(&keyinfo->block, hp_mask(hp_hashnr(keyinfo, key),
 
115
                                              share->blength, share->records));
 
116
    do
 
117
    {
 
118
      if (!hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
 
119
      {
 
120
        switch (nextflag) {
 
121
        case 0:                                 /* Search after key */
 
122
          DBUG_PRINT("exit", ("found key at 0x%lx", (long) pos->ptr_to_rec));
 
123
          info->current_hash_ptr=pos;
 
124
          DBUG_RETURN(info->current_ptr= pos->ptr_to_rec);
 
125
        case 1:                                 /* Search next */
 
126
          if (pos->ptr_to_rec == info->current_ptr)
 
127
            nextflag=0;
 
128
          break;
 
129
        case 2:                                 /* Search previous */
 
130
          if (pos->ptr_to_rec == info->current_ptr)
 
131
          {
 
132
            my_errno=HA_ERR_KEY_NOT_FOUND;      /* If gpos == 0 */
 
133
            info->current_hash_ptr=prev_ptr;
 
134
            DBUG_RETURN(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
 
135
          }
 
136
          prev_ptr=pos;                         /* Prev. record found */
 
137
          break;
 
138
        case 3:                                 /* Search same */
 
139
          if (pos->ptr_to_rec == info->current_ptr)
 
140
          {
 
141
            info->current_hash_ptr=pos;
 
142
            DBUG_RETURN(info->current_ptr);
 
143
          }
 
144
        }
 
145
      }
 
146
      if (flag)
 
147
      {
 
148
        flag=0;                                 /* Reset flag */
 
149
        if (hp_find_hash(&keyinfo->block,
 
150
                         hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
 
151
                                  share->blength, share->records)) != pos)
 
152
          break;                                /* Wrong link */
 
153
      }
 
154
    }
 
155
    while ((pos=pos->next_key));
 
156
  }
 
157
  my_errno=HA_ERR_KEY_NOT_FOUND;
 
158
  if (nextflag == 2 && ! info->current_ptr)
 
159
  {
 
160
    /* Do a previous from end */
 
161
    info->current_hash_ptr=prev_ptr;
 
162
    DBUG_RETURN(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
 
163
  }
 
164
 
 
165
  if (old_nextflag && nextflag)
 
166
    my_errno=HA_ERR_RECORD_CHANGED;             /* Didn't find old record */
 
167
  DBUG_PRINT("exit",("Error: %d",my_errno));
 
168
  info->current_hash_ptr=0;  
 
169
  DBUG_RETURN((info->current_ptr= 0));
 
170
}
 
171
 
 
172
 
 
173
/*
 
174
  Search next after last read;  Assumes that the table hasn't changed
 
175
  since last read !
 
176
*/
 
177
 
 
178
uchar *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *key,
 
179
                      HASH_INFO *pos)
 
180
{
 
181
  DBUG_ENTER("hp_search_next");
 
182
 
 
183
  while ((pos= pos->next_key))
 
184
  {
 
185
    if (! hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
 
186
    {
 
187
      info->current_hash_ptr=pos;
 
188
      DBUG_RETURN (info->current_ptr= pos->ptr_to_rec);
 
189
    }
 
190
  }
 
191
  my_errno=HA_ERR_KEY_NOT_FOUND;
 
192
  DBUG_PRINT("exit",("Error: %d",my_errno));
 
193
  info->current_hash_ptr=0;
 
194
  DBUG_RETURN ((info->current_ptr= 0));
 
195
}
 
196
 
 
197
 
 
198
/*
 
199
  Calculate position number for hash value.
 
200
  SYNOPSIS
 
201
    hp_mask()
 
202
      hashnr     Hash value
 
203
      buffmax    Value such that
 
204
                 2^(n-1) < maxlength <= 2^n = buffmax
 
205
      maxlength  
 
206
  
 
207
  RETURN
 
208
    Array index, in [0..maxlength)
 
209
*/
 
210
 
 
211
ulong hp_mask(ulong hashnr, ulong buffmax, ulong maxlength)
 
212
{
 
213
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
 
214
  return (hashnr & ((buffmax >> 1) -1));
 
215
}
 
216
 
 
217
 
 
218
/*
 
219
  Change
 
220
    next_link -> ... -> X -> pos
 
221
  to
 
222
    next_link -> ... -> X -> newlink
 
223
*/
 
224
 
 
225
void hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
 
226
{
 
227
  HASH_INFO *old_link;
 
228
  do
 
229
  {
 
230
    old_link=next_link;
 
231
  }
 
232
  while ((next_link=next_link->next_key) != pos);
 
233
  old_link->next_key=newlink;
 
234
  return;
 
235
}
 
236
 
 
237
#ifndef NEW_HASH_FUNCTION
 
238
 
 
239
        /* Calc hashvalue for a key */
 
240
 
 
241
ulong hp_hashnr(register HP_KEYDEF *keydef, register const uchar *key)
 
242
{
 
243
  /*register*/ 
 
244
  ulong nr=1, nr2=4;
 
245
  HA_KEYSEG *seg,*endseg;
 
246
 
 
247
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
 
248
  {
 
249
    uchar *pos=(uchar*) key;
 
250
    key+=seg->length;
 
251
    if (seg->null_bit)
 
252
    {
 
253
      key++;                                    /* Skip null byte */
 
254
      if (*pos)                                 /* Found null */
 
255
      {
 
256
        nr^= (nr << 1) | 1;
 
257
        /* Add key pack length (2) to key for VARCHAR segments */
 
258
        if (seg->type == HA_KEYTYPE_VARTEXT1)
 
259
          key+= 2;
 
260
        continue;
 
261
      }
 
262
      pos++;
 
263
    }
 
264
    if (seg->type == HA_KEYTYPE_TEXT)
 
265
    {
 
266
       CHARSET_INFO *cs= seg->charset;
 
267
       uint length= seg->length;
 
268
       if (cs->mbmaxlen > 1)
 
269
       {
 
270
         uint char_length;
 
271
         char_length= my_charpos(cs, pos, pos + length, length/cs->mbmaxlen);
 
272
         set_if_smaller(length, char_length);
 
273
       }
 
274
       cs->coll->hash_sort(cs, pos, length, &nr, &nr2);
 
275
    }
 
276
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
 
277
    {
 
278
       CHARSET_INFO *cs= seg->charset;
 
279
       uint pack_length= 2;                     /* Key packing is constant */
 
280
       uint length= uint2korr(pos);
 
281
       if (cs->mbmaxlen > 1)
 
282
       {
 
283
         uint char_length;
 
284
         char_length= my_charpos(cs, pos +pack_length,
 
285
                                 pos +pack_length + length,
 
286
                                 seg->length/cs->mbmaxlen);
 
287
         set_if_smaller(length, char_length);
 
288
       }
 
289
       cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
 
290
       key+= pack_length;
 
291
    }
 
292
    else
 
293
    {
 
294
      for (; pos < (uchar*) key ; pos++)
 
295
      {
 
296
        nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos)) + (nr << 8);
 
297
        nr2+=3;
 
298
      }
 
299
    }
 
300
  }
 
301
  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
 
302
  return((ulong) nr);
 
303
}
 
304
 
 
305
        /* Calc hashvalue for a key in a record */
 
306
 
 
307
ulong hp_rec_hashnr(register HP_KEYDEF *keydef, register const uchar *rec)
 
308
{
 
309
  ulong nr=1, nr2=4;
 
310
  HA_KEYSEG *seg,*endseg;
 
311
 
 
312
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
 
313
  {
 
314
    uchar *pos=(uchar*) rec+seg->start,*end=pos+seg->length;
 
315
    if (seg->null_bit)
 
316
    {
 
317
      if (rec[seg->null_pos] & seg->null_bit)
 
318
      {
 
319
        nr^= (nr << 1) | 1;
 
320
        continue;
 
321
      }
 
322
    }
 
323
    if (seg->type == HA_KEYTYPE_TEXT)
 
324
    {
 
325
      CHARSET_INFO *cs= seg->charset;
 
326
      uint char_length= seg->length;
 
327
      if (cs->mbmaxlen > 1)
 
328
      {
 
329
        char_length= my_charpos(cs, pos, pos + char_length,
 
330
                                char_length / cs->mbmaxlen);
 
331
        set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
 
332
      }
 
333
      cs->coll->hash_sort(cs, pos, char_length, &nr, &nr2);
 
334
    }
 
335
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
 
336
    {
 
337
      CHARSET_INFO *cs= seg->charset;
 
338
      uint pack_length= seg->bit_start;
 
339
      uint length= (pack_length == 1 ? (uint) *(uchar*) pos : uint2korr(pos));
 
340
      if (cs->mbmaxlen > 1)
 
341
      {
 
342
        uint char_length;
 
343
        char_length= my_charpos(cs, pos + pack_length,
 
344
                                pos + pack_length + length,
 
345
                                seg->length/cs->mbmaxlen);
 
346
        set_if_smaller(length, char_length);
 
347
      }
 
348
      cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
 
349
    }
 
350
    else
 
351
    {
 
352
      for (; pos < end ; pos++)
 
353
      {
 
354
        nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos))+ (nr << 8);
 
355
        nr2+=3;
 
356
      }
 
357
    }
 
358
  }
 
359
  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
 
360
  return(nr);
 
361
}
 
362
 
 
363
#else
 
364
 
 
365
/*
 
366
 * Fowler/Noll/Vo hash
 
367
 *
 
368
 * The basis of the hash algorithm was taken from an idea sent by email to the
 
369
 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
 
370
 * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
 
371
 * later improved on their algorithm.
 
372
 *
 
373
 * The magic is in the interesting relationship between the special prime
 
374
 * 16777619 (2^24 + 403) and 2^32 and 2^8.
 
375
 *
 
376
 * This hash produces the fewest collisions of any function that we've seen so
 
377
 * far, and works well on both numbers and strings.
 
378
 */
 
379
 
 
380
ulong hp_hashnr(register HP_KEYDEF *keydef, register const uchar *key)
 
381
{
 
382
  /*
 
383
    Note, if a key consists of a combination of numeric and
 
384
    a text columns, it most likely won't work well.
 
385
    Making text columns work with NEW_HASH_FUNCTION
 
386
    needs also changes in strings/ctype-xxx.c.
 
387
  */
 
388
  ulong nr= 1, nr2= 4;
 
389
  HA_KEYSEG *seg,*endseg;
 
390
 
 
391
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
 
392
  {
 
393
    uchar *pos=(uchar*) key;
 
394
    key+=seg->length;
 
395
    if (seg->null_bit)
 
396
    {
 
397
      key++;
 
398
      if (*pos)
 
399
      {
 
400
        nr^= (nr << 1) | 1;
 
401
        /* Add key pack length (2) to key for VARCHAR segments */
 
402
        if (seg->type == HA_KEYTYPE_VARTEXT1)
 
403
          key+= 2;
 
404
        continue;
 
405
      }
 
406
      pos++;
 
407
    }
 
408
    if (seg->type == HA_KEYTYPE_TEXT)
 
409
    {
 
410
      seg->charset->coll->hash_sort(seg->charset, pos, ((uchar*)key)-pos,
 
411
                                    &nr, &nr2);
 
412
    }
 
413
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
 
414
    {
 
415
      uint pack_length= 2;                      /* Key packing is constant */
 
416
      uint length= uint2korr(pos);
 
417
      seg->charset->coll->hash_sort(seg->charset, pos+pack_length, length,
 
418
                                    &nr, &nr2);
 
419
      key+= pack_length;
 
420
    }
 
421
    else
 
422
    {
 
423
      for ( ; pos < (uchar*) key ; pos++)
 
424
      {
 
425
        nr *=16777619; 
 
426
        nr ^=(uint) *pos;
 
427
      }
 
428
    }
 
429
  }
 
430
  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
 
431
  return(nr);
 
432
}
 
433
 
 
434
        /* Calc hashvalue for a key in a record */
 
435
 
 
436
ulong hp_rec_hashnr(register HP_KEYDEF *keydef, register const uchar *rec)
 
437
{
 
438
  ulong nr= 1, nr2= 4;
 
439
  HA_KEYSEG *seg,*endseg;
 
440
 
 
441
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
 
442
  {
 
443
    uchar *pos=(uchar*) rec+seg->start;
 
444
    if (seg->null_bit)
 
445
    {
 
446
      if (rec[seg->null_pos] & seg->null_bit)
 
447
      {
 
448
        nr^= (nr << 1) | 1;
 
449
        continue;
 
450
      }
 
451
    }
 
452
    if (seg->type == HA_KEYTYPE_TEXT)
 
453
    {
 
454
      uint char_length= seg->length; /* TODO: fix to use my_charpos() */
 
455
      seg->charset->coll->hash_sort(seg->charset, pos, char_length,
 
456
                                    &nr, &nr2);
 
457
    }
 
458
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
 
459
    {
 
460
      uint pack_length= seg->bit_start;
 
461
      uint length= (pack_length == 1 ? (uint) *(uchar*) pos : uint2korr(pos));
 
462
      seg->charset->coll->hash_sort(seg->charset, pos+pack_length,
 
463
                                    length, &nr, &nr2);
 
464
    }
 
465
    else
 
466
    {
 
467
      uchar *end= pos+seg->length;
 
468
      for ( ; pos < end ; pos++)
 
469
      {
 
470
        nr *=16777619; 
 
471
        nr ^=(uint) *pos;
 
472
      }
 
473
    }
 
474
  }
 
475
  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
 
476
  return(nr);
 
477
}
 
478
 
 
479
#endif
 
480
 
 
481
 
 
482
/*
 
483
  Compare keys for two records. Returns 0 if they are identical
 
484
 
 
485
  SYNOPSIS
 
486
    hp_rec_key_cmp()
 
487
    keydef              Key definition
 
488
    rec1                Record to compare
 
489
    rec2                Other record to compare
 
490
    diff_if_only_endspace_difference
 
491
                        Different number of end space is significant    
 
492
 
 
493
  NOTES
 
494
    diff_if_only_endspace_difference is used to allow us to insert
 
495
    'a' and 'a ' when there is an an unique key.
 
496
 
 
497
  RETURN
 
498
    0           Key is identical
 
499
    <> 0        Key differes
 
500
*/
 
501
 
 
502
int hp_rec_key_cmp(HP_KEYDEF *keydef, const uchar *rec1, const uchar *rec2,
 
503
                   my_bool diff_if_only_endspace_difference)
 
504
{
 
505
  HA_KEYSEG *seg,*endseg;
 
506
 
 
507
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
 
508
  {
 
509
    if (seg->null_bit)
 
510
    {
 
511
      if ((rec1[seg->null_pos] & seg->null_bit) !=
 
512
          (rec2[seg->null_pos] & seg->null_bit))
 
513
        return 1;
 
514
      if (rec1[seg->null_pos] & seg->null_bit)
 
515
        continue;
 
516
    }
 
517
    if (seg->type == HA_KEYTYPE_TEXT)
 
518
    {
 
519
      CHARSET_INFO *cs= seg->charset;
 
520
      uint char_length1;
 
521
      uint char_length2;
 
522
      uchar *pos1= (uchar*)rec1 + seg->start;
 
523
      uchar *pos2= (uchar*)rec2 + seg->start;
 
524
      if (cs->mbmaxlen > 1)
 
525
      {
 
526
        uint char_length= seg->length / cs->mbmaxlen;
 
527
        char_length1= my_charpos(cs, pos1, pos1 + seg->length, char_length);
 
528
        set_if_smaller(char_length1, seg->length);
 
529
        char_length2= my_charpos(cs, pos2, pos2 + seg->length, char_length);
 
530
        set_if_smaller(char_length2, seg->length);
 
531
      }
 
532
      else
 
533
      {
 
534
        char_length1= char_length2= seg->length;
 
535
      }
 
536
      if (seg->charset->coll->strnncollsp(seg->charset,
 
537
                                          pos1,char_length1,
 
538
                                          pos2,char_length2, 0))
 
539
        return 1;
 
540
    }
 
541
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
 
542
    {
 
543
      uchar *pos1= (uchar*) rec1 + seg->start;
 
544
      uchar *pos2= (uchar*) rec2 + seg->start;
 
545
      uint char_length1, char_length2;
 
546
      uint pack_length= seg->bit_start;
 
547
      CHARSET_INFO *cs= seg->charset;
 
548
      if (pack_length == 1)
 
549
      {
 
550
        char_length1= (uint) *(uchar*) pos1++;
 
551
        char_length2= (uint) *(uchar*) pos2++;
 
552
      }
 
553
      else
 
554
      {
 
555
        char_length1= uint2korr(pos1);
 
556
        char_length2= uint2korr(pos2);
 
557
        pos1+= 2;
 
558
        pos2+= 2;
 
559
      }
 
560
      if (cs->mbmaxlen > 1)
 
561
      {
 
562
        uint safe_length1= char_length1;
 
563
        uint safe_length2= char_length2;
 
564
        uint char_length= seg->length / cs->mbmaxlen;
 
565
        char_length1= my_charpos(cs, pos1, pos1 + char_length1, char_length);
 
566
        set_if_smaller(char_length1, safe_length1);
 
567
        char_length2= my_charpos(cs, pos2, pos2 + char_length2, char_length);
 
568
        set_if_smaller(char_length2, safe_length2);
 
569
      }
 
570
 
 
571
      if (cs->coll->strnncollsp(seg->charset,
 
572
                                pos1, char_length1,
 
573
                                pos2, char_length2,
 
574
                                seg->flag & HA_END_SPACE_ARE_EQUAL ?
 
575
                                0 : diff_if_only_endspace_difference))
 
576
        return 1;
 
577
    }
 
578
    else
 
579
    {
 
580
      if (bcmp(rec1+seg->start,rec2+seg->start,seg->length))
 
581
        return 1;
 
582
    }
 
583
  }
 
584
  return 0;
 
585
}
 
586
 
 
587
        /* Compare a key in a record to a whole key */
 
588
 
 
589
int hp_key_cmp(HP_KEYDEF *keydef, const uchar *rec, const uchar *key)
 
590
{
 
591
  HA_KEYSEG *seg,*endseg;
 
592
 
 
593
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ;
 
594
       seg < endseg ;
 
595
       key+= (seg++)->length)
 
596
  {
 
597
    if (seg->null_bit)
 
598
    {
 
599
      int found_null=test(rec[seg->null_pos] & seg->null_bit);
 
600
      if (found_null != (int) *key++)
 
601
        return 1;
 
602
      if (found_null)
 
603
      {
 
604
        /* Add key pack length (2) to key for VARCHAR segments */
 
605
        if (seg->type == HA_KEYTYPE_VARTEXT1)
 
606
          key+= 2;
 
607
        continue;
 
608
      }
 
609
    }
 
610
    if (seg->type == HA_KEYTYPE_TEXT)
 
611
    {
 
612
      CHARSET_INFO *cs= seg->charset;
 
613
      uint char_length_key;
 
614
      uint char_length_rec;
 
615
      uchar *pos= (uchar*) rec + seg->start;
 
616
      if (cs->mbmaxlen > 1)
 
617
      {
 
618
        uint char_length= seg->length / cs->mbmaxlen;
 
619
        char_length_key= my_charpos(cs, key, key + seg->length, char_length);
 
620
        set_if_smaller(char_length_key, seg->length);
 
621
        char_length_rec= my_charpos(cs, pos, pos + seg->length, char_length);
 
622
        set_if_smaller(char_length_rec, seg->length);
 
623
      }
 
624
      else
 
625
      {
 
626
        char_length_key= seg->length;
 
627
        char_length_rec= seg->length;
 
628
      }
 
629
      
 
630
      if (seg->charset->coll->strnncollsp(seg->charset,
 
631
                                          (uchar*) pos, char_length_rec,
 
632
                                          (uchar*) key, char_length_key, 0))
 
633
        return 1;
 
634
    }
 
635
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
 
636
    {
 
637
      uchar *pos= (uchar*) rec + seg->start;
 
638
      CHARSET_INFO *cs= seg->charset;
 
639
      uint pack_length= seg->bit_start;
 
640
      uint char_length_rec= (pack_length == 1 ? (uint) *(uchar*) pos :
 
641
                             uint2korr(pos));
 
642
      /* Key segments are always packed with 2 bytes */
 
643
      uint char_length_key= uint2korr(key);
 
644
      pos+= pack_length;
 
645
      key+= 2;                                  /* skip key pack length */
 
646
      if (cs->mbmaxlen > 1)
 
647
      {
 
648
        uint char_length1, char_length2;
 
649
        char_length1= char_length2= seg->length / cs->mbmaxlen; 
 
650
        char_length1= my_charpos(cs, key, key + char_length_key, char_length1);
 
651
        set_if_smaller(char_length_key, char_length1);
 
652
        char_length2= my_charpos(cs, pos, pos + char_length_rec, char_length2);
 
653
        set_if_smaller(char_length_rec, char_length2);
 
654
      }
 
655
 
 
656
      if (cs->coll->strnncollsp(seg->charset,
 
657
                                (uchar*) pos, char_length_rec,
 
658
                                (uchar*) key, char_length_key, 0))
 
659
        return 1;
 
660
    }
 
661
    else
 
662
    {
 
663
      if (bcmp(rec+seg->start,key,seg->length))
 
664
        return 1;
 
665
    }
 
666
  }
 
667
  return 0;
 
668
}
 
669
 
 
670
 
 
671
        /* Copy a key from a record to a keybuffer */
 
672
 
 
673
void hp_make_key(HP_KEYDEF *keydef, uchar *key, const uchar *rec)
 
674
{
 
675
  HA_KEYSEG *seg,*endseg;
 
676
 
 
677
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
 
678
  {
 
679
    CHARSET_INFO *cs= seg->charset;
 
680
    uint char_length= seg->length;
 
681
    uchar *pos= (uchar*) rec + seg->start;
 
682
    if (seg->null_bit)
 
683
      *key++= test(rec[seg->null_pos] & seg->null_bit);
 
684
    if (cs->mbmaxlen > 1)
 
685
    {
 
686
      char_length= my_charpos(cs, pos, pos + seg->length,
 
687
                              char_length / cs->mbmaxlen);
 
688
      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
 
689
    }
 
690
    if (seg->type == HA_KEYTYPE_VARTEXT1)
 
691
      char_length+= seg->bit_start;             /* Copy also length */
 
692
    memcpy(key,rec+seg->start,(size_t) char_length);
 
693
    key+= char_length;
 
694
  }
 
695
}
 
696
 
 
697
#define FIX_LENGTH(cs, pos, length, char_length)                        \
 
698
  do {                                                                  \
 
699
    if (length > char_length)                                           \
 
700
      char_length= my_charpos(cs, pos, pos+length, char_length);        \
 
701
    set_if_smaller(char_length,length);                                 \
 
702
  } while(0)
 
703
 
 
704
 
 
705
uint hp_rb_make_key(HP_KEYDEF *keydef, uchar *key, 
 
706
                    const uchar *rec, uchar *recpos)
 
707
{
 
708
  uchar *start_key= key;
 
709
  HA_KEYSEG *seg, *endseg;
 
710
 
 
711
  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
 
712
  {
 
713
    uint char_length;
 
714
    if (seg->null_bit)
 
715
    {
 
716
      if (!(*key++= 1 - test(rec[seg->null_pos] & seg->null_bit)))
 
717
        continue;
 
718
    }
 
719
    if (seg->flag & HA_SWAP_KEY)
 
720
    {
 
721
      uint length= seg->length;
 
722
      uchar *pos= (uchar*) rec + seg->start;
 
723
      
 
724
#ifdef HAVE_ISNAN
 
725
      if (seg->type == HA_KEYTYPE_FLOAT)
 
726
      {
 
727
        float nr;
 
728
        float4get(nr, pos);
 
729
        if (isnan(nr))
 
730
        {
 
731
          /* Replace NAN with zero */
 
732
          bzero(key, length);
 
733
          key+= length;
 
734
          continue;
 
735
        }
 
736
      }
 
737
      else if (seg->type == HA_KEYTYPE_DOUBLE)
 
738
      {
 
739
        double nr;
 
740
        float8get(nr, pos);
 
741
        if (isnan(nr))
 
742
        {
 
743
          bzero(key, length);
 
744
          key+= length;
 
745
          continue;
 
746
        }
 
747
      }
 
748
#endif
 
749
      pos+= length;
 
750
      while (length--)
 
751
      {
 
752
        *key++= *--pos;
 
753
      }
 
754
      continue;
 
755
    }
 
756
 
 
757
    if (seg->flag & HA_VAR_LENGTH_PART)
 
758
    {
 
759
      uchar *pos=      (uchar*) rec + seg->start;
 
760
      uint length=     seg->length;
 
761
      uint pack_length= seg->bit_start;
 
762
      uint tmp_length= (pack_length == 1 ? (uint) *(uchar*) pos :
 
763
                        uint2korr(pos));
 
764
      CHARSET_INFO *cs= seg->charset;
 
765
      char_length= length/cs->mbmaxlen;
 
766
 
 
767
      pos+= pack_length;                        /* Skip VARCHAR length */
 
768
      set_if_smaller(length,tmp_length);
 
769
      FIX_LENGTH(cs, pos, length, char_length);
 
770
      store_key_length_inc(key,char_length);
 
771
      memcpy((uchar*) key,(uchar*) pos,(size_t) char_length);
 
772
      key+= char_length;
 
773
      continue;
 
774
    }
 
775
 
 
776
    char_length= seg->length;
 
777
    if (seg->charset->mbmaxlen > 1)
 
778
    {
 
779
      char_length= my_charpos(seg->charset, 
 
780
                              rec + seg->start, rec + seg->start + char_length,
 
781
                              char_length / seg->charset->mbmaxlen);
 
782
      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
 
783
      if (char_length < seg->length)
 
784
        seg->charset->cset->fill(seg->charset, (char*) key + char_length,
 
785
                                 seg->length - char_length, ' ');
 
786
    }
 
787
    memcpy(key, rec + seg->start, (size_t) char_length);
 
788
    key+= seg->length;
 
789
  }
 
790
  memcpy(key, &recpos, sizeof(uchar*));
 
791
  return (uint) (key - start_key);
 
792
}
 
793
 
 
794
 
 
795
uint hp_rb_pack_key(HP_KEYDEF *keydef, uchar *key, const uchar *old,
 
796
                    key_part_map keypart_map)
 
797
{
 
798
  HA_KEYSEG *seg, *endseg;
 
799
  uchar *start_key= key;
 
800
 
 
801
  for (seg= keydef->seg, endseg= seg + keydef->keysegs;
 
802
       seg < endseg && keypart_map; old+= seg->length, seg++)
 
803
  {
 
804
    uint char_length;
 
805
    keypart_map>>= 1;
 
806
    if (seg->null_bit)
 
807
    {
 
808
      if (!(*key++= (char) 1 - *old++))
 
809
        continue;
 
810
      }
 
811
    if (seg->flag & HA_SWAP_KEY)
 
812
    {
 
813
      uint length= seg->length;
 
814
      uchar *pos= (uchar*) old + length;
 
815
      
 
816
      while (length--)
 
817
      {
 
818
        *key++= *--pos;
 
819
      }
 
820
      continue;
 
821
    }
 
822
    if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
 
823
    {
 
824
      /* Length of key-part used with heap_rkey() always 2 */
 
825
      uint tmp_length=uint2korr(old);
 
826
      uint length= seg->length;
 
827
      CHARSET_INFO *cs= seg->charset;
 
828
      char_length= length/cs->mbmaxlen;
 
829
 
 
830
      old+= 2;
 
831
      set_if_smaller(length,tmp_length);        /* Safety */
 
832
      FIX_LENGTH(cs, old, length, char_length);
 
833
      store_key_length_inc(key,char_length);
 
834
      memcpy((uchar*) key, old,(size_t) char_length);
 
835
      key+= char_length;
 
836
      continue;
 
837
    }
 
838
    char_length= seg->length;
 
839
    if (seg->charset->mbmaxlen > 1)
 
840
    {
 
841
      char_length= my_charpos(seg->charset, old, old+char_length,
 
842
                              char_length / seg->charset->mbmaxlen);
 
843
      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
 
844
      if (char_length < seg->length)
 
845
        seg->charset->cset->fill(seg->charset, (char*) key + char_length, 
 
846
                                 seg->length - char_length, ' ');
 
847
    }
 
848
    memcpy(key, old, (size_t) char_length);
 
849
    key+= seg->length;
 
850
  }
 
851
  return (uint) (key - start_key);
 
852
}
 
853
 
 
854
 
 
855
uint hp_rb_key_length(HP_KEYDEF *keydef, 
 
856
                      const uchar *key __attribute__((unused)))
 
857
{
 
858
  return keydef->length;
 
859
}
 
860
 
 
861
 
 
862
uint hp_rb_null_key_length(HP_KEYDEF *keydef, const uchar *key)
 
863
{
 
864
  const uchar *start_key= key;
 
865
  HA_KEYSEG *seg, *endseg;
 
866
  
 
867
  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
 
868
  {
 
869
    if (seg->null_bit && !*key++)
 
870
      continue;
 
871
    key+= seg->length;
 
872
  }
 
873
  return (uint) (key - start_key);
 
874
}
 
875
                  
 
876
 
 
877
uint hp_rb_var_key_length(HP_KEYDEF *keydef, const uchar *key)
 
878
{
 
879
  const uchar *start_key= key;
 
880
  HA_KEYSEG *seg, *endseg;
 
881
  
 
882
  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
 
883
  {
 
884
    uint length= seg->length;
 
885
    if (seg->null_bit && !*key++)
 
886
      continue;
 
887
    if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
 
888
    {
 
889
      get_key_length(length, key);
 
890
    }
 
891
    key+= length;
 
892
  }
 
893
  return (uint) (key - start_key);
 
894
}
 
895
 
 
896
 
 
897
/*
 
898
  Test if any of the key parts are NULL.
 
899
  Return:
 
900
    1 if any of the key parts was NULL
 
901
    0 otherwise
 
902
*/
 
903
 
 
904
my_bool hp_if_null_in_key(HP_KEYDEF *keydef, const uchar *record)
 
905
{
 
906
  HA_KEYSEG *seg,*endseg;
 
907
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
 
908
  {
 
909
    if (seg->null_bit && (record[seg->null_pos] & seg->null_bit))
 
910
      return 1;
 
911
  }
 
912
  return 0;
 
913
}
 
914
 
 
915
 
 
916
/*
 
917
  Update auto_increment info
 
918
 
 
919
  SYNOPSIS
 
920
    update_auto_increment()
 
921
    info                        MyISAM handler
 
922
    record                      Row to update
 
923
 
 
924
  IMPLEMENTATION
 
925
    Only replace the auto_increment value if it is higher than the previous
 
926
    one. For signed columns we don't update the auto increment value if it's
 
927
    less than zero.
 
928
*/
 
929
 
 
930
void heap_update_auto_increment(HP_INFO *info, const uchar *record)
 
931
{
 
932
  ulonglong value= 0;                   /* Store unsigned values here */
 
933
  longlong s_value= 0;                  /* Store signed values here */
 
934
 
 
935
  HA_KEYSEG *keyseg= info->s->keydef[info->s->auto_key - 1].seg;
 
936
  const uchar *key=  (uchar*) record + keyseg->start;
 
937
 
 
938
  switch (info->s->auto_key_type) {
 
939
  case HA_KEYTYPE_INT8:
 
940
    s_value= (longlong) *(char*)key;
 
941
    break;
 
942
  case HA_KEYTYPE_BINARY:
 
943
    value=(ulonglong)  *(uchar*) key;
 
944
    break;
 
945
  case HA_KEYTYPE_SHORT_INT:
 
946
    s_value= (longlong) sint2korr(key);
 
947
    break;
 
948
  case HA_KEYTYPE_USHORT_INT:
 
949
    value=(ulonglong) uint2korr(key);
 
950
    break;
 
951
  case HA_KEYTYPE_LONG_INT:
 
952
    s_value= (longlong) sint4korr(key);
 
953
    break;
 
954
  case HA_KEYTYPE_ULONG_INT:
 
955
    value=(ulonglong) uint4korr(key);
 
956
    break;
 
957
  case HA_KEYTYPE_INT24:
 
958
    s_value= (longlong) sint3korr(key);
 
959
    break;
 
960
  case HA_KEYTYPE_UINT24:
 
961
    value=(ulonglong) uint3korr(key);
 
962
    break;
 
963
  case HA_KEYTYPE_FLOAT:                        /* This shouldn't be used */
 
964
  {
 
965
    float f_1;
 
966
    float4get(f_1,key);
 
967
    /* Ignore negative values */
 
968
    value = (f_1 < (float) 0.0) ? 0 : (ulonglong) f_1;
 
969
    break;
 
970
  }
 
971
  case HA_KEYTYPE_DOUBLE:                       /* This shouldn't be used */
 
972
  {
 
973
    double f_1;
 
974
    float8get(f_1,key);
 
975
    /* Ignore negative values */
 
976
    value = (f_1 < 0.0) ? 0 : (ulonglong) f_1;
 
977
    break;
 
978
  }
 
979
  case HA_KEYTYPE_LONGLONG:
 
980
    s_value= sint8korr(key);
 
981
    break;
 
982
  case HA_KEYTYPE_ULONGLONG:
 
983
    value= uint8korr(key);
 
984
    break;
 
985
  default:
 
986
    DBUG_ASSERT(0);
 
987
    value=0;                                    /* Error */
 
988
    break;
 
989
  }
 
990
 
 
991
  /*
 
992
    The following code works becasue if s_value < 0 then value is 0
 
993
    and if s_value == 0 then value will contain either s_value or the
 
994
    correct value.
 
995
  */
 
996
  set_if_bigger(info->s->auto_increment,
 
997
                (s_value > 0) ? (ulonglong) s_value : value);
 
998
}