Drizzled Public API Documentation

hp_hash.cc
00001 /* Copyright (C) 2000-2006 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software
00014    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
00015 
00016 /* The hash functions used for saveing keys */
00017 
00018 #include "heap_priv.h"
00019 
00020 #include <drizzled/charset_info.h>
00021 #include <drizzled/util/test.h>
00022 
00023 #include <math.h>
00024 #include <string.h>
00025 
00026 #include <cassert>
00027 
00028 using namespace drizzled;
00029 using namespace std;
00030 
00031 static uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key);
00032 static int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key);
00033 
00034 
00035   /* Search after a record based on a key */
00036   /* Sets info->current_ptr to found record */
00037   /* next_flag:  Search=0, next=1, prev =2, same =3 */
00038 
00039 unsigned char *hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const unsigned char *key,
00040                 uint32_t nextflag)
00041 {
00042   register HASH_INFO *pos,*prev_ptr;
00043   int flag;
00044   uint32_t old_nextflag;
00045   HP_SHARE *share=info->getShare();
00046   old_nextflag=nextflag;
00047   flag=1;
00048   prev_ptr=0;
00049 
00050   if (share->records)
00051   {
00052     pos=hp_find_hash(&keyinfo->block, hp_mask(hp_hashnr(keyinfo, key),
00053                 share->blength, share->records));
00054     do
00055     {
00056       if (!hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
00057       {
00058   switch (nextflag) {
00059   case 0:         /* Search after key */
00060     info->current_hash_ptr=pos;
00061     return(info->current_ptr= pos->ptr_to_rec);
00062   case 1:         /* Search next */
00063     if (pos->ptr_to_rec == info->current_ptr)
00064       nextflag=0;
00065     break;
00066   case 2:         /* Search previous */
00067     if (pos->ptr_to_rec == info->current_ptr)
00068     {
00069       errno=HA_ERR_KEY_NOT_FOUND; /* If gpos == 0 */
00070       info->current_hash_ptr=prev_ptr;
00071       return(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
00072     }
00073     prev_ptr=pos;       /* Prev. record found */
00074     break;
00075   case 3:         /* Search same */
00076     if (pos->ptr_to_rec == info->current_ptr)
00077     {
00078       info->current_hash_ptr=pos;
00079       return(info->current_ptr);
00080     }
00081   }
00082       }
00083       if (flag)
00084       {
00085   flag=0;         /* Reset flag */
00086   if (hp_find_hash(&keyinfo->block,
00087        hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
00088           share->blength, share->records)) != pos)
00089     break;        /* Wrong link */
00090       }
00091     }
00092     while ((pos=pos->next_key));
00093   }
00094   errno=HA_ERR_KEY_NOT_FOUND;
00095   if (nextflag == 2 && ! info->current_ptr)
00096   {
00097     /* Do a previous from end */
00098     info->current_hash_ptr=prev_ptr;
00099     return(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
00100   }
00101 
00102   if (old_nextflag && nextflag)
00103     errno=HA_ERR_RECORD_CHANGED;    /* Didn't find old record */
00104   info->current_hash_ptr=0;
00105   return((info->current_ptr= 0));
00106 }
00107 
00108 
00109 /*
00110   Search next after last read;  Assumes that the table hasn't changed
00111   since last read !
00112 */
00113 
00114 unsigned char *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const unsigned char *key,
00115           HASH_INFO *pos)
00116 {
00117   while ((pos= pos->next_key))
00118   {
00119     if (! hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
00120     {
00121       info->current_hash_ptr=pos;
00122       return (info->current_ptr= pos->ptr_to_rec);
00123     }
00124   }
00125   errno=HA_ERR_KEY_NOT_FOUND;
00126   info->current_hash_ptr=0;
00127   return ((info->current_ptr= 0));
00128 }
00129 
00130 
00131 /*
00132   Calculate position number for hash value.
00133   SYNOPSIS
00134     hp_mask()
00135       hashnr     Hash value
00136       buffmax    Value such that
00137                  2^(n-1) < maxlength <= 2^n = buffmax
00138       maxlength
00139 
00140   RETURN
00141     Array index, in [0..maxlength)
00142 */
00143 
00144 uint32_t hp_mask(uint32_t hashnr, uint32_t buffmax, uint32_t maxlength)
00145 {
00146   if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
00147   return (hashnr & ((buffmax >> 1) -1));
00148 }
00149 
00150 
00151 /*
00152   Change
00153     next_link -> ... -> X -> pos
00154   to
00155     next_link -> ... -> X -> newlink
00156 */
00157 
00158 void hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
00159 {
00160   HASH_INFO *old_link;
00161   do
00162   {
00163     old_link=next_link;
00164   }
00165   while ((next_link=next_link->next_key) != pos);
00166   old_link->next_key=newlink;
00167   return;
00168 }
00169 
00170   /* Calc hashvalue for a key */
00171 
00172 static uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key)
00173 {
00174   /*register*/
00175   uint32_t nr=1, nr2=4;
00176   HA_KEYSEG *seg,*endseg;
00177 
00178   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
00179   {
00180     unsigned char *pos=(unsigned char*) key;
00181     key+=seg->length;
00182     if (seg->null_bit)
00183     {
00184       key++;          /* Skip null byte */
00185       if (*pos)         /* Found null */
00186       {
00187   nr^= (nr << 1) | 1;
00188   /* Add key pack length (2) to key for VARCHAR segments */
00189         if (seg->type == HA_KEYTYPE_VARTEXT1)
00190           key+= 2;
00191   continue;
00192       }
00193       pos++;
00194     }
00195     if (seg->type == HA_KEYTYPE_TEXT)
00196     {
00197        const CHARSET_INFO * const cs= seg->charset;
00198        uint32_t length= seg->length;
00199        if (cs->mbmaxlen > 1)
00200        {
00201          uint32_t char_length;
00202          char_length= my_charpos(cs, pos, pos + length, length/cs->mbmaxlen);
00203          set_if_smaller(length, char_length);
00204        }
00205        cs->coll->hash_sort(cs, pos, length, &nr, &nr2);
00206     }
00207     else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
00208     {
00209        const CHARSET_INFO * const cs= seg->charset;
00210        uint32_t pack_length= 2;                     /* Key packing is constant */
00211        uint32_t length= uint2korr(pos);
00212        if (cs->mbmaxlen > 1)
00213        {
00214          uint32_t char_length;
00215          char_length= my_charpos(cs, pos +pack_length,
00216                                  pos +pack_length + length,
00217                                  seg->length/cs->mbmaxlen);
00218          set_if_smaller(length, char_length);
00219        }
00220        cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
00221        key+= pack_length;
00222     }
00223     else
00224     {
00225       for (; pos < (unsigned char*) key ; pos++)
00226       {
00227   nr^=(uint32_t) ((((uint) nr & 63)+nr2)*((uint) *pos)) + (nr << 8);
00228   nr2+=3;
00229       }
00230     }
00231   }
00232   return((uint32_t) nr);
00233 }
00234 
00235   /* Calc hashvalue for a key in a record */
00236 
00237 uint32_t hp_rec_hashnr(register HP_KEYDEF *keydef, register const unsigned char *rec)
00238 {
00239   uint32_t nr=1, nr2=4;
00240   HA_KEYSEG *seg,*endseg;
00241 
00242   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
00243   {
00244     unsigned char *pos=(unsigned char*) rec+seg->start,*end=pos+seg->length;
00245     if (seg->null_bit)
00246     {
00247       if (rec[seg->null_pos] & seg->null_bit)
00248       {
00249   nr^= (nr << 1) | 1;
00250   continue;
00251       }
00252     }
00253     if (seg->type == HA_KEYTYPE_TEXT)
00254     {
00255       const CHARSET_INFO * const cs= seg->charset;
00256       uint32_t char_length= seg->length;
00257       if (cs->mbmaxlen > 1)
00258       {
00259         char_length= my_charpos(cs, pos, pos + char_length,
00260                                 char_length / cs->mbmaxlen);
00261         set_if_smaller(char_length, (uint32_t)seg->length); /* QQ: ok to remove? */
00262       }
00263       cs->coll->hash_sort(cs, pos, char_length, &nr, &nr2);
00264     }
00265     else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
00266     {
00267       const CHARSET_INFO * const cs= seg->charset;
00268       uint32_t pack_length= seg->bit_start;
00269       uint32_t length= (pack_length == 1 ? (uint) *(unsigned char*) pos : uint2korr(pos));
00270       if (cs->mbmaxlen > 1)
00271       {
00272         uint32_t char_length;
00273         char_length= my_charpos(cs, pos + pack_length,
00274                                 pos + pack_length + length,
00275                                 seg->length/cs->mbmaxlen);
00276         set_if_smaller(length, char_length);
00277       }
00278       cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
00279     }
00280     else
00281     {
00282       for (; pos < end ; pos++)
00283       {
00284   nr^=(uint32_t) ((((uint) nr & 63)+nr2)*((uint) *pos))+ (nr << 8);
00285   nr2+=3;
00286       }
00287     }
00288   }
00289   return(nr);
00290 }
00291 
00292 /*
00293   Compare keys for two records. Returns 0 if they are identical
00294 
00295   SYNOPSIS
00296     hp_rec_key_cmp()
00297     keydef    Key definition
00298     rec1    Record to compare
00299     rec2    Other record to compare
00300     diff_if_only_endspace_difference
00301       Different number of end space is significant
00302 
00303   NOTES
00304     diff_if_only_endspace_difference is used to allow us to insert
00305     'a' and 'a ' when there is an an unique key.
00306 
00307   RETURN
00308     0   Key is identical
00309     <> 0  Key differes
00310 */
00311 
00312 int hp_rec_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec1, const unsigned char *rec2,
00313                    bool diff_if_only_endspace_difference)
00314 {
00315   HA_KEYSEG *seg,*endseg;
00316 
00317   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
00318   {
00319     if (seg->null_bit)
00320     {
00321       if ((rec1[seg->null_pos] & seg->null_bit) !=
00322     (rec2[seg->null_pos] & seg->null_bit))
00323   return 1;
00324       if (rec1[seg->null_pos] & seg->null_bit)
00325   continue;
00326     }
00327     if (seg->type == HA_KEYTYPE_TEXT)
00328     {
00329       const CHARSET_INFO * const cs= seg->charset;
00330       uint32_t char_length1;
00331       uint32_t char_length2;
00332       unsigned char *pos1= (unsigned char*)rec1 + seg->start;
00333       unsigned char *pos2= (unsigned char*)rec2 + seg->start;
00334       if (cs->mbmaxlen > 1)
00335       {
00336         uint32_t char_length= seg->length / cs->mbmaxlen;
00337         char_length1= my_charpos(cs, pos1, pos1 + seg->length, char_length);
00338         set_if_smaller(char_length1, (uint32_t)seg->length);
00339         char_length2= my_charpos(cs, pos2, pos2 + seg->length, char_length);
00340         set_if_smaller(char_length2, (uint32_t)seg->length);
00341       }
00342       else
00343       {
00344         char_length1= char_length2= seg->length;
00345       }
00346       if (seg->charset->coll->strnncollsp(seg->charset,
00347                   pos1,char_length1,
00348             pos2,char_length2, 0))
00349   return 1;
00350     }
00351     else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
00352     {
00353       unsigned char *pos1= (unsigned char*) rec1 + seg->start;
00354       unsigned char *pos2= (unsigned char*) rec2 + seg->start;
00355       uint32_t char_length1, char_length2;
00356       uint32_t pack_length= seg->bit_start;
00357       const CHARSET_INFO * const cs= seg->charset;
00358       if (pack_length == 1)
00359       {
00360         char_length1= (uint) *(unsigned char*) pos1++;
00361         char_length2= (uint) *(unsigned char*) pos2++;
00362       }
00363       else
00364       {
00365         char_length1= uint2korr(pos1);
00366         char_length2= uint2korr(pos2);
00367         pos1+= 2;
00368         pos2+= 2;
00369       }
00370       if (cs->mbmaxlen > 1)
00371       {
00372         uint32_t safe_length1= char_length1;
00373         uint32_t safe_length2= char_length2;
00374         uint32_t char_length= seg->length / cs->mbmaxlen;
00375         char_length1= my_charpos(cs, pos1, pos1 + char_length1, char_length);
00376         set_if_smaller(char_length1, safe_length1);
00377         char_length2= my_charpos(cs, pos2, pos2 + char_length2, char_length);
00378         set_if_smaller(char_length2, safe_length2);
00379       }
00380 
00381       if (cs->coll->strnncollsp(seg->charset,
00382                                 pos1, char_length1,
00383                                 pos2, char_length2,
00384                                 seg->flag & HA_END_SPACE_ARE_EQUAL ?
00385                                 0 : diff_if_only_endspace_difference))
00386   return 1;
00387     }
00388     else
00389     {
00390       if (memcmp(rec1+seg->start,rec2+seg->start,seg->length))
00391   return 1;
00392     }
00393   }
00394   return 0;
00395 }
00396 
00397   /* Compare a key in a record to a whole key */
00398 
00399 static int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key)
00400 {
00401   HA_KEYSEG *seg,*endseg;
00402 
00403   for (seg=keydef->seg,endseg=seg+keydef->keysegs ;
00404        seg < endseg ;
00405        key+= (seg++)->length)
00406   {
00407     if (seg->null_bit)
00408     {
00409       int found_null=test(rec[seg->null_pos] & seg->null_bit);
00410       if (found_null != (int) *key++)
00411   return 1;
00412       if (found_null)
00413       {
00414         /* Add key pack length (2) to key for VARCHAR segments */
00415         if (seg->type == HA_KEYTYPE_VARTEXT1)
00416           key+= 2;
00417   continue;
00418       }
00419     }
00420     if (seg->type == HA_KEYTYPE_TEXT)
00421     {
00422       const CHARSET_INFO * const cs= seg->charset;
00423       uint32_t char_length_key;
00424       uint32_t char_length_rec;
00425       unsigned char *pos= (unsigned char*) rec + seg->start;
00426       if (cs->mbmaxlen > 1)
00427       {
00428         uint32_t char_length= seg->length / cs->mbmaxlen;
00429         char_length_key= my_charpos(cs, key, key + seg->length, char_length);
00430         set_if_smaller(char_length_key, (uint32_t)seg->length);
00431         char_length_rec= my_charpos(cs, pos, pos + seg->length, char_length);
00432         set_if_smaller(char_length_rec, (uint32_t)seg->length);
00433       }
00434       else
00435       {
00436         char_length_key= seg->length;
00437         char_length_rec= seg->length;
00438       }
00439 
00440       if (seg->charset->coll->strnncollsp(seg->charset,
00441             (unsigned char*) pos, char_length_rec,
00442             (unsigned char*) key, char_length_key, 0))
00443   return 1;
00444     }
00445     else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
00446     {
00447       unsigned char *pos= (unsigned char*) rec + seg->start;
00448       const CHARSET_INFO * const cs= seg->charset;
00449       uint32_t pack_length= seg->bit_start;
00450       uint32_t char_length_rec= (pack_length == 1 ? (uint) *(unsigned char*) pos :
00451                              uint2korr(pos));
00452       /* Key segments are always packed with 2 bytes */
00453       uint32_t char_length_key= uint2korr(key);
00454       pos+= pack_length;
00455       key+= 2;                                  /* skip key pack length */
00456       if (cs->mbmaxlen > 1)
00457       {
00458         uint32_t char_length1, char_length2;
00459         char_length1= char_length2= seg->length / cs->mbmaxlen;
00460         char_length1= my_charpos(cs, key, key + char_length_key, char_length1);
00461         set_if_smaller(char_length_key, char_length1);
00462         char_length2= my_charpos(cs, pos, pos + char_length_rec, char_length2);
00463         set_if_smaller(char_length_rec, char_length2);
00464       }
00465 
00466       if (cs->coll->strnncollsp(seg->charset,
00467                                 (unsigned char*) pos, char_length_rec,
00468                                 (unsigned char*) key, char_length_key, 0))
00469   return 1;
00470     }
00471     else
00472     {
00473       if (memcmp(rec+seg->start,key,seg->length))
00474   return 1;
00475     }
00476   }
00477   return 0;
00478 }
00479 
00480 
00481   /* Copy a key from a record to a keybuffer */
00482 
00483 void hp_make_key(HP_KEYDEF *keydef, unsigned char *key, const unsigned char *rec)
00484 {
00485   HA_KEYSEG *seg,*endseg;
00486 
00487   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
00488   {
00489     const CHARSET_INFO * const cs= seg->charset;
00490     uint32_t char_length= seg->length;
00491     unsigned char *pos= (unsigned char*) rec + seg->start;
00492     if (seg->null_bit)
00493       *key++= test(rec[seg->null_pos] & seg->null_bit);
00494     if (cs->mbmaxlen > 1)
00495     {
00496       char_length= my_charpos(cs, pos, pos + seg->length,
00497                               char_length / cs->mbmaxlen);
00498       set_if_smaller(char_length, (uint32_t)seg->length); /* QQ: ok to remove? */
00499     }
00500     if (seg->type == HA_KEYTYPE_VARTEXT1)
00501       char_length+= seg->bit_start;             /* Copy also length */
00502     memcpy(key,rec+seg->start,(size_t) char_length);
00503     key+= char_length;
00504   }
00505 }
00506 
00507 #define FIX_LENGTH(cs, pos, length, char_length)                        \
00508   do {                                                                  \
00509     if (length > char_length)                                           \
00510       char_length= my_charpos(cs, pos, pos+length, char_length);        \
00511     set_if_smaller(char_length,length);                                 \
00512   } while(0)
00513 
00514 /*
00515   Test if any of the key parts are NULL.
00516   Return:
00517     1 if any of the key parts was NULL
00518     0 otherwise
00519 */
00520 
00521 bool hp_if_null_in_key(HP_KEYDEF *keydef, const unsigned char *record)
00522 {
00523   HA_KEYSEG *seg,*endseg;
00524   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
00525   {
00526     if (seg->null_bit && (record[seg->null_pos] & seg->null_bit))
00527       return 1;
00528   }
00529   return 0;
00530 }
00531 
00532 
00533 /*
00534   Update auto_increment info
00535 
00536   SYNOPSIS
00537     update_auto_increment()
00538     info      MyISAM handler
00539     record      Row to update
00540 
00541   IMPLEMENTATION
00542     Only replace the auto_increment value if it is higher than the previous
00543     one. For signed columns we don't update the auto increment value if it's
00544     less than zero.
00545 */
00546 
00547 void heap_update_auto_increment(HP_INFO *info, const unsigned char *record)
00548 {
00549   uint64_t value= 0;      /* Store unsigned values here */
00550   int64_t s_value= 0;     /* Store signed values here */
00551 
00552   HA_KEYSEG *keyseg= info->getShare()->keydef[info->getShare()->auto_key - 1].seg;
00553   const unsigned char *key=  (unsigned char*) record + keyseg->start;
00554 
00555   switch (info->getShare()->auto_key_type) {
00556   case HA_KEYTYPE_BINARY:
00557     value=(uint64_t)  *(unsigned char*) key;
00558     break;
00559   case HA_KEYTYPE_LONG_INT:
00560     s_value= (int64_t) sint4korr(key);
00561     break;
00562   case HA_KEYTYPE_ULONG_INT:
00563     value=(uint64_t) uint4korr(key);
00564     break;
00565   case HA_KEYTYPE_DOUBLE:                       /* This shouldn't be used */
00566   {
00567     double f_1;
00568     float8get(f_1,key);
00569     /* Ignore negative values */
00570     value = (f_1 < 0.0) ? 0 : (uint64_t) f_1;
00571     break;
00572   }
00573   case HA_KEYTYPE_LONGLONG:
00574     s_value= sint8korr(key);
00575     break;
00576   case HA_KEYTYPE_ULONGLONG:
00577     value= uint8korr(key);
00578     break;
00579   default:
00580     assert(0);
00581     value=0;                                    /* Error */
00582     break;
00583   }
00584 
00585   /*
00586     The following code works becasue if s_value < 0 then value is 0
00587     and if s_value == 0 then value will contain either s_value or the
00588     correct value.
00589   */
00590   set_if_bigger(info->getShare()->auto_increment,
00591                 (s_value > 0) ? (uint64_t) s_value : value);
00592 }