12
12
You should have received a copy of the GNU General Public License
13
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 */
14
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
16
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);
19
#include <mystrings/m_ctype.h>
24
Find out how many rows there is in the given range
27
hp_rb_records_in_range()
30
min_key Min key. Is = 0 if no min range
31
max_key Max key. Is = 0 if no max range
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
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
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
49
ha_rows hp_rb_records_in_range(HP_INFO *info, int inx, key_range *min_key,
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;
58
custom_arg.keyseg= keyinfo->seg;
59
custom_arg.search_flag= SEARCH_FIND | SEARCH_SAME;
62
custom_arg.key_length= hp_rb_pack_key(keyinfo, (unsigned char*) info->recbuf,
63
(unsigned char*) min_key->key,
64
min_key->keypart_map);
65
start_pos= tree_record_pos(rb_tree, info->recbuf, min_key->flag,
75
custom_arg.key_length= hp_rb_pack_key(keyinfo, (unsigned char*) info->recbuf,
76
(unsigned char*) max_key->key,
77
max_key->keypart_map);
78
end_pos= tree_record_pos(rb_tree, info->recbuf, max_key->flag,
83
end_pos= rb_tree->elements_in_tree + (ha_rows)1;
86
if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
88
return(end_pos < start_pos ? (ha_rows) 0 :
89
(end_pos == start_pos ? (ha_rows) 1 : end_pos - start_pos));
35
93
/* Search after a record based on a key */
355
* Fowler/Noll/Vo hash
357
* The basis of the hash algorithm was taken from an idea sent by email to the
358
* IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
359
* Glenn Fowler (gsf@research.att.com). Landon Curt Noll (chongo@toad.com)
360
* later improved on their algorithm.
362
* The magic is in the interesting relationship between the special prime
363
* 16777619 (2^24 + 403) and 2^32 and 2^8.
365
* This hash produces the fewest collisions of any function that we've seen so
366
* far, and works well on both numbers and strings.
369
uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key)
372
Note, if a key consists of a combination of numeric and
373
a text columns, it most likely won't work well.
374
Making text columns work with NEW_HASH_FUNCTION
375
needs also changes in strings/ctype-xxx.c.
377
uint32_t nr= 1, nr2= 4;
378
HA_KEYSEG *seg,*endseg;
380
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
382
unsigned char *pos=(unsigned char*) key;
390
/* Add key pack length (2) to key for VARCHAR segments */
391
if (seg->type == HA_KEYTYPE_VARTEXT1)
397
if (seg->type == HA_KEYTYPE_TEXT)
399
seg->charset->coll->hash_sort(seg->charset, pos, ((unsigned char*)key)-pos,
402
else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
404
uint32_t pack_length= 2; /* Key packing is constant */
405
uint32_t length= uint2korr(pos);
406
seg->charset->coll->hash_sort(seg->charset, pos+pack_length, length,
412
for ( ; pos < (unsigned char*) key ; pos++)
422
/* Calc hashvalue for a key in a record */
424
uint32_t hp_rec_hashnr(register HP_KEYDEF *keydef, register const unsigned char *rec)
426
uint32_t nr= 1, nr2= 4;
427
HA_KEYSEG *seg,*endseg;
429
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
431
unsigned char *pos=(unsigned char*) rec+seg->start;
434
if (rec[seg->null_pos] & seg->null_bit)
440
if (seg->type == HA_KEYTYPE_TEXT)
442
uint32_t char_length= seg->length; /* TODO: fix to use my_charpos() */
443
seg->charset->coll->hash_sort(seg->charset, pos, char_length,
446
else if (seg->type == HA_KEYTYPE_VARTEXT1) /* Any VARCHAR segments */
448
uint32_t pack_length= seg->bit_start;
449
uint32_t length= (pack_length == 1 ? (uint) *(unsigned char*) pos : uint2korr(pos));
450
seg->charset->coll->hash_sort(seg->charset, pos+pack_length,
455
unsigned char *end= pos+seg->length;
456
for ( ; pos < end ; pos++)
293
470
Compare keys for two records. Returns 0 if they are identical
428
605
uint32_t char_length= seg->length / cs->mbmaxlen;
429
606
char_length_key= my_charpos(cs, key, key + seg->length, char_length);
430
set_if_smaller(char_length_key, (uint32_t)seg->length);
607
set_if_smaller(char_length_key, seg->length);
431
608
char_length_rec= my_charpos(cs, pos, pos + seg->length, char_length);
432
set_if_smaller(char_length_rec, (uint32_t)seg->length);
609
set_if_smaller(char_length_rec, seg->length);
436
613
char_length_key= seg->length;
437
614
char_length_rec= seg->length;
440
617
if (seg->charset->coll->strnncollsp(seg->charset,
441
618
(unsigned char*) pos, char_length_rec,
442
619
(unsigned char*) key, char_length_key, 0))
511
688
set_if_smaller(char_length,length); \
692
uint32_t hp_rb_make_key(HP_KEYDEF *keydef, unsigned char *key,
693
const unsigned char *rec, unsigned char *recpos)
695
unsigned char *start_key= key;
696
HA_KEYSEG *seg, *endseg;
698
for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
700
uint32_t char_length;
703
if (!(*key++= 1 - test(rec[seg->null_pos] & seg->null_bit)))
706
if (seg->flag & HA_SWAP_KEY)
708
uint32_t length= seg->length;
709
unsigned char *pos= (unsigned char*) rec + seg->start;
712
if (seg->type == HA_KEYTYPE_FLOAT)
718
/* Replace NAN with zero */
719
memset(key, 0, length);
724
else if (seg->type == HA_KEYTYPE_DOUBLE)
730
memset(key, 0, length);
744
if (seg->flag & HA_VAR_LENGTH_PART)
746
unsigned char *pos= (unsigned char*) rec + seg->start;
747
uint32_t length= seg->length;
748
uint32_t pack_length= seg->bit_start;
749
uint32_t tmp_length= (pack_length == 1 ? (uint) *(unsigned char*) pos :
751
const CHARSET_INFO * const cs= seg->charset;
752
char_length= length/cs->mbmaxlen;
754
pos+= pack_length; /* Skip VARCHAR length */
755
set_if_smaller(length,tmp_length);
756
FIX_LENGTH(cs, pos, length, char_length);
757
store_key_length_inc(key,char_length);
758
memcpy(key,pos,(size_t) char_length);
763
char_length= seg->length;
764
if (seg->charset->mbmaxlen > 1)
766
char_length= my_charpos(seg->charset,
767
rec + seg->start, rec + seg->start + char_length,
768
char_length / seg->charset->mbmaxlen);
769
set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
770
if (char_length < seg->length)
771
seg->charset->cset->fill(seg->charset, (char*) key + char_length,
772
seg->length - char_length, ' ');
774
memcpy(key, rec + seg->start, (size_t) char_length);
777
memcpy(key, &recpos, sizeof(unsigned char*));
778
return (uint) (key - start_key);
782
uint32_t hp_rb_pack_key(HP_KEYDEF *keydef, unsigned char *key, const unsigned char *old,
783
key_part_map keypart_map)
785
HA_KEYSEG *seg, *endseg;
786
unsigned char *start_key= key;
788
for (seg= keydef->seg, endseg= seg + keydef->keysegs;
789
seg < endseg && keypart_map; old+= seg->length, seg++)
791
uint32_t char_length;
795
if (!(*key++= (char) 1 - *old++))
798
if (seg->flag & HA_SWAP_KEY)
800
uint32_t length= seg->length;
801
unsigned char *pos= (unsigned char*) old + length;
809
if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
811
/* Length of key-part used with heap_rkey() always 2 */
812
uint32_t tmp_length=uint2korr(old);
813
uint32_t length= seg->length;
814
const CHARSET_INFO * const cs= seg->charset;
815
char_length= length/cs->mbmaxlen;
818
set_if_smaller(length,tmp_length); /* Safety */
819
FIX_LENGTH(cs, old, length, char_length);
820
store_key_length_inc(key,char_length);
821
memcpy(key, old,(size_t) char_length);
825
char_length= seg->length;
826
if (seg->charset->mbmaxlen > 1)
828
char_length= my_charpos(seg->charset, old, old+char_length,
829
char_length / seg->charset->mbmaxlen);
830
set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
831
if (char_length < seg->length)
832
seg->charset->cset->fill(seg->charset, (char*) key + char_length,
833
seg->length - char_length, ' ');
835
memcpy(key, old, (size_t) char_length);
838
return (uint) (key - start_key);
842
uint32_t hp_rb_key_length(HP_KEYDEF *keydef,
843
const unsigned char *key __attribute__((unused)))
845
return keydef->length;
849
uint32_t hp_rb_null_key_length(HP_KEYDEF *keydef, const unsigned char *key)
851
const unsigned char *start_key= key;
852
HA_KEYSEG *seg, *endseg;
854
for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
856
if (seg->null_bit && !*key++)
860
return (uint) (key - start_key);
864
uint32_t hp_rb_var_key_length(HP_KEYDEF *keydef, const unsigned char *key)
866
const unsigned char *start_key= key;
867
HA_KEYSEG *seg, *endseg;
869
for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
871
uint32_t length= seg->length;
872
if (seg->null_bit && !*key++)
874
if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
876
get_key_length(length, key);
880
return (uint) (key - start_key);
515
885
Test if any of the key parts are NULL.
549
919
uint64_t value= 0; /* Store unsigned values here */
550
920
int64_t s_value= 0; /* Store signed values here */
552
HA_KEYSEG *keyseg= info->getShare()->keydef[info->getShare()->auto_key - 1].seg;
922
HA_KEYSEG *keyseg= info->s->keydef[info->s->auto_key - 1].seg;
553
923
const unsigned char *key= (unsigned char*) record + keyseg->start;
555
switch (info->getShare()->auto_key_type) {
925
switch (info->s->auto_key_type) {
926
case HA_KEYTYPE_INT8:
927
s_value= (int64_t) *(char*)key;
556
929
case HA_KEYTYPE_BINARY:
557
930
value=(uint64_t) *(unsigned char*) key;
932
case HA_KEYTYPE_SHORT_INT:
933
s_value= (int64_t) sint2korr(key);
935
case HA_KEYTYPE_USHORT_INT:
936
value=(uint64_t) uint2korr(key);
559
938
case HA_KEYTYPE_LONG_INT:
560
939
s_value= (int64_t) sint4korr(key);
562
941
case HA_KEYTYPE_ULONG_INT:
563
942
value=(uint64_t) uint4korr(key);
944
case HA_KEYTYPE_INT24:
945
s_value= (int64_t) sint3korr(key);
947
case HA_KEYTYPE_UINT24:
948
value=(uint64_t) uint3korr(key);
950
case HA_KEYTYPE_FLOAT: /* This shouldn't be used */
954
/* Ignore negative values */
955
value = (f_1 < (float) 0.0) ? 0 : (uint64_t) f_1;
565
958
case HA_KEYTYPE_DOUBLE: /* This shouldn't be used */