← 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 Aker
  • Date: 2009-03-20 18:52:05 UTC
  • mfrom: (950.1.1 mordred)
  • Revision ID: brian@tangent.org-20090320185205-g7o6kq17r25b6odf
Merge Monty

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/heap/hp_hash.c
11
11
 
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 */
15
15
 
16
16
/* The hash functions used for saveing keys */
17
17
 
18
 
#include "heap_priv.h"
 
18
#include "heapdef.h"
19
19
 
20
 
#include "drizzled/charset_info.h"
 
20
#include <mystrings/m_ctype.h>
21
21
#include <drizzled/util/test.h>
22
22
 
23
 
#include <math.h>
24
23
#include <string.h>
25
24
 
26
 
#include <cassert>
27
 
 
28
 
using namespace drizzled;
29
 
using namespace std;
30
 
 
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);
 
25
/*
 
26
  Find out how many rows there is in the given range
 
27
 
 
28
  SYNOPSIS
 
29
    hp_rb_records_in_range()
 
30
    info                HEAP handler
 
31
    inx                 Index to use
 
32
    min_key             Min key. Is = 0 if no min range
 
33
    max_key             Max key. Is = 0 if no max range
 
34
 
 
35
  NOTES
 
36
    min_key.flag can have one of the following values:
 
37
      HA_READ_KEY_EXACT         Include the key in the range
 
38
      HA_READ_AFTER_KEY         Don't include key in range
 
39
 
 
40
    max_key.flag can have one of the following values:
 
41
      HA_READ_BEFORE_KEY        Don't include key in range
 
42
      HA_READ_AFTER_KEY         Include all 'end_key' values in the range
 
43
 
 
44
  RETURN
 
45
   HA_POS_ERROR         Something is wrong with the index tree.
 
46
   0                    There is no matching keys in the given range
 
47
   number > 0           There is approximately 'number' matching rows in
 
48
                        the range.
 
49
*/
 
50
 
 
51
ha_rows hp_rb_records_in_range(HP_INFO *info, int inx,  key_range *min_key,
 
52
                               key_range *max_key)
 
53
{
 
54
  ha_rows start_pos, end_pos;
 
55
  HP_KEYDEF *keyinfo= info->s->keydef + inx;
 
56
  TREE *rb_tree = &keyinfo->rb_tree;
 
57
  heap_rb_param custom_arg;
 
58
 
 
59
  info->lastinx= inx;
 
60
  custom_arg.keyseg= keyinfo->seg;
 
61
  custom_arg.search_flag= SEARCH_FIND | SEARCH_SAME;
 
62
  if (min_key)
 
63
  {
 
64
    custom_arg.key_length= hp_rb_pack_key(keyinfo, (unsigned char*) info->recbuf,
 
65
                                          (unsigned char*) min_key->key,
 
66
                                          min_key->keypart_map);
 
67
    start_pos= tree_record_pos(rb_tree, info->recbuf, min_key->flag,
 
68
                               &custom_arg);
 
69
  }
 
70
  else
 
71
  {
 
72
    start_pos= 0;
 
73
  }
 
74
 
 
75
  if (max_key)
 
76
  {
 
77
    custom_arg.key_length= hp_rb_pack_key(keyinfo, (unsigned char*) info->recbuf,
 
78
                                          (unsigned char*) max_key->key,
 
79
                                          max_key->keypart_map);
 
80
    end_pos= tree_record_pos(rb_tree, info->recbuf, max_key->flag,
 
81
                             &custom_arg);
 
82
  }
 
83
  else
 
84
  {
 
85
    end_pos= rb_tree->elements_in_tree + (ha_rows)1;
 
86
  }
 
87
 
 
88
  if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
 
89
    return(HA_POS_ERROR);
 
90
  return(end_pos < start_pos ? (ha_rows) 0 :
 
91
              (end_pos == start_pos ? (ha_rows) 1 : end_pos - start_pos));
 
92
}
33
93
 
34
94
 
35
95
        /* Search after a record based on a key */
42
102
  register HASH_INFO *pos,*prev_ptr;
43
103
  int flag;
44
104
  uint32_t old_nextflag;
45
 
  HP_SHARE *share=info->getShare();
 
105
  HP_SHARE *share=info->s;
46
106
  old_nextflag=nextflag;
47
107
  flag=1;
48
108
  prev_ptr=0;
66
126
        case 2:                                 /* Search previous */
67
127
          if (pos->ptr_to_rec == info->current_ptr)
68
128
          {
69
 
            errno=HA_ERR_KEY_NOT_FOUND; /* If gpos == 0 */
 
129
            my_errno=HA_ERR_KEY_NOT_FOUND;      /* If gpos == 0 */
70
130
            info->current_hash_ptr=prev_ptr;
71
131
            return(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
72
132
          }
91
151
    }
92
152
    while ((pos=pos->next_key));
93
153
  }
94
 
  errno=HA_ERR_KEY_NOT_FOUND;
 
154
  my_errno=HA_ERR_KEY_NOT_FOUND;
95
155
  if (nextflag == 2 && ! info->current_ptr)
96
156
  {
97
157
    /* Do a previous from end */
100
160
  }
101
161
 
102
162
  if (old_nextflag && nextflag)
103
 
    errno=HA_ERR_RECORD_CHANGED;                /* Didn't find old record */
 
163
    my_errno=HA_ERR_RECORD_CHANGED;             /* Didn't find old record */
104
164
  info->current_hash_ptr=0;
105
165
  return((info->current_ptr= 0));
106
166
}
122
182
      return (info->current_ptr= pos->ptr_to_rec);
123
183
    }
124
184
  }
125
 
  errno=HA_ERR_KEY_NOT_FOUND;
 
185
  my_errno=HA_ERR_KEY_NOT_FOUND;
126
186
  info->current_hash_ptr=0;
127
187
  return ((info->current_ptr= 0));
128
188
}
167
227
  return;
168
228
}
169
229
 
 
230
#ifndef NEW_HASH_FUNCTION
 
231
 
170
232
        /* Calc hashvalue for a key */
171
233
 
172
 
static uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key)
 
234
uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key)
173
235
{
174
236
  /*register*/
175
237
  uint32_t nr=1, nr2=4;
289
351
  return(nr);
290
352
}
291
353
 
 
354
#else
 
355
 
 
356
/*
 
357
 * Fowler/Noll/Vo hash
 
358
 *
 
359
 * The basis of the hash algorithm was taken from an idea sent by email to the
 
360
 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
 
361
 * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
 
362
 * later improved on their algorithm.
 
363
 *
 
364
 * The magic is in the interesting relationship between the special prime
 
365
 * 16777619 (2^24 + 403) and 2^32 and 2^8.
 
366
 *
 
367
 * This hash produces the fewest collisions of any function that we've seen so
 
368
 * far, and works well on both numbers and strings.
 
369
 */
 
370
 
 
371
uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key)
 
372
{
 
373
  /*
 
374
    Note, if a key consists of a combination of numeric and
 
375
    a text columns, it most likely won't work well.
 
376
    Making text columns work with NEW_HASH_FUNCTION
 
377
    needs also changes in strings/ctype-xxx.c.
 
378
  */
 
379
  uint32_t nr= 1, nr2= 4;
 
380
  HA_KEYSEG *seg,*endseg;
 
381
 
 
382
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
 
383
  {
 
384
    unsigned char *pos=(unsigned char*) key;
 
385
    key+=seg->length;
 
386
    if (seg->null_bit)
 
387
    {
 
388
      key++;
 
389
      if (*pos)
 
390
      {
 
391
        nr^= (nr << 1) | 1;
 
392
        /* Add key pack length (2) to key for VARCHAR segments */
 
393
        if (seg->type == HA_KEYTYPE_VARTEXT1)
 
394
          key+= 2;
 
395
        continue;
 
396
      }
 
397
      pos++;
 
398
    }
 
399
    if (seg->type == HA_KEYTYPE_TEXT)
 
400
    {
 
401
      seg->charset->coll->hash_sort(seg->charset, pos, ((unsigned char*)key)-pos,
 
402
                                    &nr, &nr2);
 
403
    }
 
404
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
 
405
    {
 
406
      uint32_t pack_length= 2;                      /* Key packing is constant */
 
407
      uint32_t length= uint2korr(pos);
 
408
      seg->charset->coll->hash_sort(seg->charset, pos+pack_length, length,
 
409
                                    &nr, &nr2);
 
410
      key+= pack_length;
 
411
    }
 
412
    else
 
413
    {
 
414
      for ( ; pos < (unsigned char*) key ; pos++)
 
415
      {
 
416
        nr *=16777619;
 
417
        nr ^=(uint) *pos;
 
418
      }
 
419
    }
 
420
  }
 
421
  return(nr);
 
422
}
 
423
 
 
424
        /* Calc hashvalue for a key in a record */
 
425
 
 
426
uint32_t hp_rec_hashnr(register HP_KEYDEF *keydef, register const unsigned char *rec)
 
427
{
 
428
  uint32_t nr= 1, nr2= 4;
 
429
  HA_KEYSEG *seg,*endseg;
 
430
 
 
431
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
 
432
  {
 
433
    unsigned char *pos=(unsigned char*) rec+seg->start;
 
434
    if (seg->null_bit)
 
435
    {
 
436
      if (rec[seg->null_pos] & seg->null_bit)
 
437
      {
 
438
        nr^= (nr << 1) | 1;
 
439
        continue;
 
440
      }
 
441
    }
 
442
    if (seg->type == HA_KEYTYPE_TEXT)
 
443
    {
 
444
      uint32_t char_length= seg->length; /* TODO: fix to use my_charpos() */
 
445
      seg->charset->coll->hash_sort(seg->charset, pos, char_length,
 
446
                                    &nr, &nr2);
 
447
    }
 
448
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
 
449
    {
 
450
      uint32_t pack_length= seg->bit_start;
 
451
      uint32_t length= (pack_length == 1 ? (uint) *(unsigned char*) pos : uint2korr(pos));
 
452
      seg->charset->coll->hash_sort(seg->charset, pos+pack_length,
 
453
                                    length, &nr, &nr2);
 
454
    }
 
455
    else
 
456
    {
 
457
      unsigned char *end= pos+seg->length;
 
458
      for ( ; pos < end ; pos++)
 
459
      {
 
460
        nr *=16777619;
 
461
        nr ^=(uint) *pos;
 
462
      }
 
463
    }
 
464
  }
 
465
  return(nr);
 
466
}
 
467
 
 
468
#endif
 
469
 
 
470
 
292
471
/*
293
472
  Compare keys for two records. Returns 0 if they are identical
294
473
 
396
575
 
397
576
        /* Compare a key in a record to a whole key */
398
577
 
399
 
static int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key)
 
578
int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key)
400
579
{
401
580
  HA_KEYSEG *seg,*endseg;
402
581
 
511
690
    set_if_smaller(char_length,length);                                 \
512
691
  } while(0)
513
692
 
 
693
 
 
694
uint32_t hp_rb_make_key(HP_KEYDEF *keydef, unsigned char *key,
 
695
                    const unsigned char *rec, unsigned char *recpos)
 
696
{
 
697
  unsigned char *start_key= key;
 
698
  HA_KEYSEG *seg, *endseg;
 
699
 
 
700
  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
 
701
  {
 
702
    uint32_t char_length;
 
703
    if (seg->null_bit)
 
704
    {
 
705
      if (!(*key++= 1 - test(rec[seg->null_pos] & seg->null_bit)))
 
706
        continue;
 
707
    }
 
708
    if (seg->flag & HA_SWAP_KEY)
 
709
    {
 
710
      uint32_t length= seg->length;
 
711
      unsigned char *pos= (unsigned char*) rec + seg->start;
 
712
 
 
713
#ifdef HAVE_ISNAN
 
714
      if (seg->type == HA_KEYTYPE_FLOAT)
 
715
      {
 
716
        float nr;
 
717
        float4get(nr, pos);
 
718
        if (isnan(nr))
 
719
        {
 
720
          /* Replace NAN with zero */
 
721
          memset(key, 0, length);
 
722
          key+= length;
 
723
          continue;
 
724
        }
 
725
      }
 
726
      else if (seg->type == HA_KEYTYPE_DOUBLE)
 
727
      {
 
728
        double nr;
 
729
        float8get(nr, pos);
 
730
        if (isnan(nr))
 
731
        {
 
732
          memset(key, 0, length);
 
733
          key+= length;
 
734
          continue;
 
735
        }
 
736
      }
 
737
#endif
 
738
      pos+= length;
 
739
      while (length--)
 
740
      {
 
741
        *key++= *--pos;
 
742
      }
 
743
      continue;
 
744
    }
 
745
 
 
746
    if (seg->flag & HA_VAR_LENGTH_PART)
 
747
    {
 
748
      unsigned char *pos=      (unsigned char*) rec + seg->start;
 
749
      uint32_t length=     seg->length;
 
750
      uint32_t pack_length= seg->bit_start;
 
751
      uint32_t tmp_length= (pack_length == 1 ? (uint) *(unsigned char*) pos :
 
752
                        uint2korr(pos));
 
753
      const CHARSET_INFO * const cs= seg->charset;
 
754
      char_length= length/cs->mbmaxlen;
 
755
 
 
756
      pos+= pack_length;                        /* Skip VARCHAR length */
 
757
      set_if_smaller(length,tmp_length);
 
758
      FIX_LENGTH(cs, pos, length, char_length);
 
759
      store_key_length_inc(key,char_length);
 
760
      memcpy(key,pos,(size_t) char_length);
 
761
      key+= char_length;
 
762
      continue;
 
763
    }
 
764
 
 
765
    char_length= seg->length;
 
766
    if (seg->charset->mbmaxlen > 1)
 
767
    {
 
768
      char_length= my_charpos(seg->charset,
 
769
                              rec + seg->start, rec + seg->start + char_length,
 
770
                              char_length / seg->charset->mbmaxlen);
 
771
      set_if_smaller(char_length, (uint32_t)seg->length); /* QQ: ok to remove? */
 
772
      if (char_length < seg->length)
 
773
        seg->charset->cset->fill(seg->charset, (char*) key + char_length,
 
774
                                 seg->length - char_length, ' ');
 
775
    }
 
776
    memcpy(key, rec + seg->start, (size_t) char_length);
 
777
    key+= seg->length;
 
778
  }
 
779
  memcpy(key, &recpos, sizeof(unsigned char*));
 
780
  return (uint32_t) (key - start_key);
 
781
}
 
782
 
 
783
 
 
784
uint32_t hp_rb_pack_key(HP_KEYDEF *keydef, unsigned char *key, const unsigned char *old,
 
785
                    key_part_map keypart_map)
 
786
{
 
787
  HA_KEYSEG *seg, *endseg;
 
788
  unsigned char *start_key= key;
 
789
 
 
790
  for (seg= keydef->seg, endseg= seg + keydef->keysegs;
 
791
       seg < endseg && keypart_map; old+= seg->length, seg++)
 
792
  {
 
793
    uint32_t char_length;
 
794
    keypart_map>>= 1;
 
795
    if (seg->null_bit)
 
796
    {
 
797
      if (!(*key++= (char) 1 - *old++))
 
798
        continue;
 
799
      }
 
800
    if (seg->flag & HA_SWAP_KEY)
 
801
    {
 
802
      uint32_t length= seg->length;
 
803
      unsigned char *pos= (unsigned char*) old + length;
 
804
 
 
805
      while (length--)
 
806
      {
 
807
        *key++= *--pos;
 
808
      }
 
809
      continue;
 
810
    }
 
811
    if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
 
812
    {
 
813
      /* Length of key-part used with heap_rkey() always 2 */
 
814
      uint32_t tmp_length=uint2korr(old);
 
815
      uint32_t length= seg->length;
 
816
      const CHARSET_INFO * const cs= seg->charset;
 
817
      char_length= length/cs->mbmaxlen;
 
818
 
 
819
      old+= 2;
 
820
      set_if_smaller(length,tmp_length);        /* Safety */
 
821
      FIX_LENGTH(cs, old, length, char_length);
 
822
      store_key_length_inc(key,char_length);
 
823
      memcpy(key, old,(size_t) char_length);
 
824
      key+= char_length;
 
825
      continue;
 
826
    }
 
827
    char_length= seg->length;
 
828
    if (seg->charset->mbmaxlen > 1)
 
829
    {
 
830
      char_length= my_charpos(seg->charset, old, old+char_length,
 
831
                              char_length / seg->charset->mbmaxlen);
 
832
      set_if_smaller(char_length, (uint32_t)seg->length); /* QQ: ok to remove? */
 
833
      if (char_length < seg->length)
 
834
        seg->charset->cset->fill(seg->charset, (char*) key + char_length,
 
835
                                 seg->length - char_length, ' ');
 
836
    }
 
837
    memcpy(key, old, (size_t) char_length);
 
838
    key+= seg->length;
 
839
  }
 
840
  return (uint) (key - start_key);
 
841
}
 
842
 
 
843
 
 
844
uint32_t hp_rb_key_length(HP_KEYDEF *keydef, const unsigned char *not_used)
 
845
{
 
846
  (void)not_used;
 
847
  return keydef->length;
 
848
}
 
849
 
 
850
 
 
851
uint32_t hp_rb_null_key_length(HP_KEYDEF *keydef, const unsigned char *key)
 
852
{
 
853
  const unsigned char *start_key= key;
 
854
  HA_KEYSEG *seg, *endseg;
 
855
 
 
856
  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
 
857
  {
 
858
    if (seg->null_bit && !*key++)
 
859
      continue;
 
860
    key+= seg->length;
 
861
  }
 
862
  return (uint) (key - start_key);
 
863
}
 
864
 
 
865
 
 
866
uint32_t hp_rb_var_key_length(HP_KEYDEF *keydef, const unsigned char *key)
 
867
{
 
868
  const unsigned char *start_key= key;
 
869
  HA_KEYSEG *seg, *endseg;
 
870
 
 
871
  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
 
872
  {
 
873
    uint32_t length= seg->length;
 
874
    if (seg->null_bit && !*key++)
 
875
      continue;
 
876
    if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
 
877
    {
 
878
      get_key_length(length, key);
 
879
    }
 
880
    key+= length;
 
881
  }
 
882
  return (uint) (key - start_key);
 
883
}
 
884
 
 
885
 
514
886
/*
515
887
  Test if any of the key parts are NULL.
516
888
  Return:
549
921
  uint64_t value= 0;                    /* Store unsigned values here */
550
922
  int64_t s_value= 0;                   /* Store signed values here */
551
923
 
552
 
  HA_KEYSEG *keyseg= info->getShare()->keydef[info->getShare()->auto_key - 1].seg;
 
924
  HA_KEYSEG *keyseg= info->s->keydef[info->s->auto_key - 1].seg;
553
925
  const unsigned char *key=  (unsigned char*) record + keyseg->start;
554
926
 
555
 
  switch (info->getShare()->auto_key_type) {
 
927
  switch (info->s->auto_key_type) {
 
928
  case HA_KEYTYPE_INT8:
 
929
    s_value= (int64_t) *(char*)key;
 
930
    break;
556
931
  case HA_KEYTYPE_BINARY:
557
932
    value=(uint64_t)  *(unsigned char*) key;
558
933
    break;
 
934
  case HA_KEYTYPE_SHORT_INT:
 
935
    s_value= (int64_t) sint2korr(key);
 
936
    break;
 
937
  case HA_KEYTYPE_USHORT_INT:
 
938
    value=(uint64_t) uint2korr(key);
 
939
    break;
559
940
  case HA_KEYTYPE_LONG_INT:
560
941
    s_value= (int64_t) sint4korr(key);
561
942
    break;
562
943
  case HA_KEYTYPE_ULONG_INT:
563
944
    value=(uint64_t) uint4korr(key);
564
945
    break;
 
946
  case HA_KEYTYPE_INT24:
 
947
    s_value= (int64_t) sint3korr(key);
 
948
    break;
 
949
  case HA_KEYTYPE_UINT24:
 
950
    value=(uint64_t) uint3korr(key);
 
951
    break;
 
952
  case HA_KEYTYPE_FLOAT:                        /* This shouldn't be used */
 
953
  {
 
954
    float f_1;
 
955
    float4get(f_1,key);
 
956
    /* Ignore negative values */
 
957
    value = (f_1 < (float) 0.0) ? 0 : (uint64_t) f_1;
 
958
    break;
 
959
  }
565
960
  case HA_KEYTYPE_DOUBLE:                       /* This shouldn't be used */
566
961
  {
567
962
    double f_1;
587
982
    and if s_value == 0 then value will contain either s_value or the
588
983
    correct value.
589
984
  */
590
 
  set_if_bigger(info->getShare()->auto_increment,
 
985
  set_if_bigger(info->s->auto_increment,
591
986
                (s_value > 0) ? (uint64_t) s_value : value);
592
987
}