1
/* Copyright (C) 2000-2006 MySQL AB
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.
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.
12
You should have received a copy of the GNU General Public License
13
along with this program; if not, write to the Free Software
14
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
/* The hash functions used for saveing keys */
18
#include "heap_priv.h"
20
#include "drizzled/charset_info.h"
21
#include <drizzled/util/test.h>
28
using namespace drizzled;
31
static uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key);
32
static int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key);
35
/* Search after a record based on a key */
36
/* Sets info->current_ptr to found record */
37
/* next_flag: Search=0, next=1, prev =2, same =3 */
39
unsigned char *hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const unsigned char *key,
42
register HASH_INFO *pos,*prev_ptr;
44
uint32_t old_nextflag;
45
HP_SHARE *share=info->getShare();
46
old_nextflag=nextflag;
52
pos=hp_find_hash(&keyinfo->block, hp_mask(hp_hashnr(keyinfo, key),
53
share->blength, share->records));
56
if (!hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
59
case 0: /* Search after key */
60
info->current_hash_ptr=pos;
61
return(info->current_ptr= pos->ptr_to_rec);
62
case 1: /* Search next */
63
if (pos->ptr_to_rec == info->current_ptr)
66
case 2: /* Search previous */
67
if (pos->ptr_to_rec == info->current_ptr)
69
errno=HA_ERR_KEY_NOT_FOUND; /* If gpos == 0 */
70
info->current_hash_ptr=prev_ptr;
71
return(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
73
prev_ptr=pos; /* Prev. record found */
75
case 3: /* Search same */
76
if (pos->ptr_to_rec == info->current_ptr)
78
info->current_hash_ptr=pos;
79
return(info->current_ptr);
85
flag=0; /* Reset flag */
86
if (hp_find_hash(&keyinfo->block,
87
hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
88
share->blength, share->records)) != pos)
89
break; /* Wrong link */
92
while ((pos=pos->next_key));
94
errno=HA_ERR_KEY_NOT_FOUND;
95
if (nextflag == 2 && ! info->current_ptr)
97
/* Do a previous from end */
98
info->current_hash_ptr=prev_ptr;
99
return(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
102
if (old_nextflag && nextflag)
103
errno=HA_ERR_RECORD_CHANGED; /* Didn't find old record */
104
info->current_hash_ptr=0;
105
return((info->current_ptr= 0));
110
Search next after last read; Assumes that the table hasn't changed
114
unsigned char *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const unsigned char *key,
117
while ((pos= pos->next_key))
119
if (! hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
121
info->current_hash_ptr=pos;
122
return (info->current_ptr= pos->ptr_to_rec);
125
errno=HA_ERR_KEY_NOT_FOUND;
126
info->current_hash_ptr=0;
127
return ((info->current_ptr= 0));
132
Calculate position number for hash value.
136
buffmax Value such that
137
2^(n-1) < maxlength <= 2^n = buffmax
141
Array index, in [0..maxlength)
144
uint32_t hp_mask(uint32_t hashnr, uint32_t buffmax, uint32_t maxlength)
146
if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
147
return (hashnr & ((buffmax >> 1) -1));
153
next_link -> ... -> X -> pos
155
next_link -> ... -> X -> newlink
158
void hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
165
while ((next_link=next_link->next_key) != pos);
166
old_link->next_key=newlink;
170
/* Calc hashvalue for a key */
172
static uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key)
175
uint32_t nr=1, nr2=4;
176
HA_KEYSEG *seg,*endseg;
178
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
180
unsigned char *pos=(unsigned char*) key;
184
key++; /* Skip null byte */
185
if (*pos) /* Found null */
188
/* Add key pack length (2) to key for VARCHAR segments */
189
if (seg->type == HA_KEYTYPE_VARTEXT1)
195
if (seg->type == HA_KEYTYPE_TEXT)
197
const CHARSET_INFO * const cs= seg->charset;
198
uint32_t length= seg->length;
199
if (cs->mbmaxlen > 1)
201
uint32_t char_length;
202
char_length= my_charpos(cs, pos, pos + length, length/cs->mbmaxlen);
203
set_if_smaller(length, char_length);
205
cs->coll->hash_sort(cs, pos, length, &nr, &nr2);
207
else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
209
const CHARSET_INFO * const cs= seg->charset;
210
uint32_t pack_length= 2; /* Key packing is constant */
211
uint32_t length= uint2korr(pos);
212
if (cs->mbmaxlen > 1)
214
uint32_t char_length;
215
char_length= my_charpos(cs, pos +pack_length,
216
pos +pack_length + length,
217
seg->length/cs->mbmaxlen);
218
set_if_smaller(length, char_length);
220
cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
225
for (; pos < (unsigned char*) key ; pos++)
227
nr^=(uint32_t) ((((uint) nr & 63)+nr2)*((uint) *pos)) + (nr << 8);
232
return((uint32_t) nr);
235
/* Calc hashvalue for a key in a record */
237
uint32_t hp_rec_hashnr(register HP_KEYDEF *keydef, register const unsigned char *rec)
239
uint32_t nr=1, nr2=4;
240
HA_KEYSEG *seg,*endseg;
242
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
244
unsigned char *pos=(unsigned char*) rec+seg->start,*end=pos+seg->length;
247
if (rec[seg->null_pos] & seg->null_bit)
253
if (seg->type == HA_KEYTYPE_TEXT)
255
const CHARSET_INFO * const cs= seg->charset;
256
uint32_t char_length= seg->length;
257
if (cs->mbmaxlen > 1)
259
char_length= my_charpos(cs, pos, pos + char_length,
260
char_length / cs->mbmaxlen);
261
set_if_smaller(char_length, (uint32_t)seg->length); /* QQ: ok to remove? */
263
cs->coll->hash_sort(cs, pos, char_length, &nr, &nr2);
265
else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
267
const CHARSET_INFO * const cs= seg->charset;
268
uint32_t pack_length= seg->bit_start;
269
uint32_t length= (pack_length == 1 ? (uint) *(unsigned char*) pos : uint2korr(pos));
270
if (cs->mbmaxlen > 1)
272
uint32_t char_length;
273
char_length= my_charpos(cs, pos + pack_length,
274
pos + pack_length + length,
275
seg->length/cs->mbmaxlen);
276
set_if_smaller(length, char_length);
278
cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
282
for (; pos < end ; pos++)
284
nr^=(uint32_t) ((((uint) nr & 63)+nr2)*((uint) *pos))+ (nr << 8);
293
Compare keys for two records. Returns 0 if they are identical
297
keydef Key definition
298
rec1 Record to compare
299
rec2 Other record to compare
300
diff_if_only_endspace_difference
301
Different number of end space is significant
304
diff_if_only_endspace_difference is used to allow us to insert
305
'a' and 'a ' when there is an an unique key.
312
int hp_rec_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec1, const unsigned char *rec2,
313
bool diff_if_only_endspace_difference)
315
HA_KEYSEG *seg,*endseg;
317
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
321
if ((rec1[seg->null_pos] & seg->null_bit) !=
322
(rec2[seg->null_pos] & seg->null_bit))
324
if (rec1[seg->null_pos] & seg->null_bit)
327
if (seg->type == HA_KEYTYPE_TEXT)
329
const CHARSET_INFO * const cs= seg->charset;
330
uint32_t char_length1;
331
uint32_t char_length2;
332
unsigned char *pos1= (unsigned char*)rec1 + seg->start;
333
unsigned char *pos2= (unsigned char*)rec2 + seg->start;
334
if (cs->mbmaxlen > 1)
336
uint32_t char_length= seg->length / cs->mbmaxlen;
337
char_length1= my_charpos(cs, pos1, pos1 + seg->length, char_length);
338
set_if_smaller(char_length1, (uint32_t)seg->length);
339
char_length2= my_charpos(cs, pos2, pos2 + seg->length, char_length);
340
set_if_smaller(char_length2, (uint32_t)seg->length);
344
char_length1= char_length2= seg->length;
346
if (seg->charset->coll->strnncollsp(seg->charset,
348
pos2,char_length2, 0))
351
else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
353
unsigned char *pos1= (unsigned char*) rec1 + seg->start;
354
unsigned char *pos2= (unsigned char*) rec2 + seg->start;
355
uint32_t char_length1, char_length2;
356
uint32_t pack_length= seg->bit_start;
357
const CHARSET_INFO * const cs= seg->charset;
358
if (pack_length == 1)
360
char_length1= (uint) *(unsigned char*) pos1++;
361
char_length2= (uint) *(unsigned char*) pos2++;
365
char_length1= uint2korr(pos1);
366
char_length2= uint2korr(pos2);
370
if (cs->mbmaxlen > 1)
372
uint32_t safe_length1= char_length1;
373
uint32_t safe_length2= char_length2;
374
uint32_t char_length= seg->length / cs->mbmaxlen;
375
char_length1= my_charpos(cs, pos1, pos1 + char_length1, char_length);
376
set_if_smaller(char_length1, safe_length1);
377
char_length2= my_charpos(cs, pos2, pos2 + char_length2, char_length);
378
set_if_smaller(char_length2, safe_length2);
381
if (cs->coll->strnncollsp(seg->charset,
384
seg->flag & HA_END_SPACE_ARE_EQUAL ?
385
0 : diff_if_only_endspace_difference))
390
if (memcmp(rec1+seg->start,rec2+seg->start,seg->length))
397
/* Compare a key in a record to a whole key */
399
static int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key)
401
HA_KEYSEG *seg,*endseg;
403
for (seg=keydef->seg,endseg=seg+keydef->keysegs ;
405
key+= (seg++)->length)
409
int found_null=test(rec[seg->null_pos] & seg->null_bit);
410
if (found_null != (int) *key++)
414
/* Add key pack length (2) to key for VARCHAR segments */
415
if (seg->type == HA_KEYTYPE_VARTEXT1)
420
if (seg->type == HA_KEYTYPE_TEXT)
422
const CHARSET_INFO * const cs= seg->charset;
423
uint32_t char_length_key;
424
uint32_t char_length_rec;
425
unsigned char *pos= (unsigned char*) rec + seg->start;
426
if (cs->mbmaxlen > 1)
428
uint32_t char_length= seg->length / cs->mbmaxlen;
429
char_length_key= my_charpos(cs, key, key + seg->length, char_length);
430
set_if_smaller(char_length_key, (uint32_t)seg->length);
431
char_length_rec= my_charpos(cs, pos, pos + seg->length, char_length);
432
set_if_smaller(char_length_rec, (uint32_t)seg->length);
436
char_length_key= seg->length;
437
char_length_rec= seg->length;
440
if (seg->charset->coll->strnncollsp(seg->charset,
441
(unsigned char*) pos, char_length_rec,
442
(unsigned char*) key, char_length_key, 0))
445
else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
447
unsigned char *pos= (unsigned char*) rec + seg->start;
448
const CHARSET_INFO * const cs= seg->charset;
449
uint32_t pack_length= seg->bit_start;
450
uint32_t char_length_rec= (pack_length == 1 ? (uint) *(unsigned char*) pos :
452
/* Key segments are always packed with 2 bytes */
453
uint32_t char_length_key= uint2korr(key);
455
key+= 2; /* skip key pack length */
456
if (cs->mbmaxlen > 1)
458
uint32_t char_length1, char_length2;
459
char_length1= char_length2= seg->length / cs->mbmaxlen;
460
char_length1= my_charpos(cs, key, key + char_length_key, char_length1);
461
set_if_smaller(char_length_key, char_length1);
462
char_length2= my_charpos(cs, pos, pos + char_length_rec, char_length2);
463
set_if_smaller(char_length_rec, char_length2);
466
if (cs->coll->strnncollsp(seg->charset,
467
(unsigned char*) pos, char_length_rec,
468
(unsigned char*) key, char_length_key, 0))
473
if (memcmp(rec+seg->start,key,seg->length))
481
/* Copy a key from a record to a keybuffer */
483
void hp_make_key(HP_KEYDEF *keydef, unsigned char *key, const unsigned char *rec)
485
HA_KEYSEG *seg,*endseg;
487
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
489
const CHARSET_INFO * const cs= seg->charset;
490
uint32_t char_length= seg->length;
491
unsigned char *pos= (unsigned char*) rec + seg->start;
493
*key++= test(rec[seg->null_pos] & seg->null_bit);
494
if (cs->mbmaxlen > 1)
496
char_length= my_charpos(cs, pos, pos + seg->length,
497
char_length / cs->mbmaxlen);
498
set_if_smaller(char_length, (uint32_t)seg->length); /* QQ: ok to remove? */
500
if (seg->type == HA_KEYTYPE_VARTEXT1)
501
char_length+= seg->bit_start; /* Copy also length */
502
memcpy(key,rec+seg->start,(size_t) char_length);
507
#define FIX_LENGTH(cs, pos, length, char_length) \
509
if (length > char_length) \
510
char_length= my_charpos(cs, pos, pos+length, char_length); \
511
set_if_smaller(char_length,length); \
515
Test if any of the key parts are NULL.
517
1 if any of the key parts was NULL
521
bool hp_if_null_in_key(HP_KEYDEF *keydef, const unsigned char *record)
523
HA_KEYSEG *seg,*endseg;
524
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
526
if (seg->null_bit && (record[seg->null_pos] & seg->null_bit))
534
Update auto_increment info
537
update_auto_increment()
542
Only replace the auto_increment value if it is higher than the previous
543
one. For signed columns we don't update the auto increment value if it's
547
void heap_update_auto_increment(HP_INFO *info, const unsigned char *record)
549
uint64_t value= 0; /* Store unsigned values here */
550
int64_t s_value= 0; /* Store signed values here */
552
HA_KEYSEG *keyseg= info->getShare()->keydef[info->getShare()->auto_key - 1].seg;
553
const unsigned char *key= (unsigned char*) record + keyseg->start;
555
switch (info->getShare()->auto_key_type) {
556
case HA_KEYTYPE_BINARY:
557
value=(uint64_t) *(unsigned char*) key;
559
case HA_KEYTYPE_LONG_INT:
560
s_value= (int64_t) sint4korr(key);
562
case HA_KEYTYPE_ULONG_INT:
563
value=(uint64_t) uint4korr(key);
565
case HA_KEYTYPE_DOUBLE: /* This shouldn't be used */
569
/* Ignore negative values */
570
value = (f_1 < 0.0) ? 0 : (uint64_t) f_1;
573
case HA_KEYTYPE_LONGLONG:
574
s_value= sint8korr(key);
576
case HA_KEYTYPE_ULONGLONG:
577
value= uint8korr(key);
586
The following code works becasue if s_value < 0 then value is 0
587
and if s_value == 0 then value will contain either s_value or the
590
set_if_bigger(info->getShare()->auto_increment,
591
(s_value > 0) ? (uint64_t) s_value : value);