Drizzled Public API Documentation

mi_search.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 /* key handling functions */
00017 
00018 #include "myisam_priv.h"
00019 #include <drizzled/charset_info.h>
00020 #include <drizzled/internal/m_string.h>
00021 #include <drizzled/util/test.h>
00022 
00023 using namespace drizzled;
00024 
00025 static bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
00026                                 unsigned char *key, unsigned char *keypos,
00027                                 uint32_t *return_key_length);
00028 
00029         /* Check index */
00030 
00031 int _mi_check_index(MI_INFO *info, int inx)
00032 {
00033   if (inx == -1)                        /* Use last index */
00034     inx=info->lastinx;
00035   if (inx < 0 || ! mi_is_key_active(info->s->state.key_map, inx))
00036   {
00037     errno=HA_ERR_WRONG_INDEX;
00038     return -1;
00039   }
00040   if (info->lastinx != inx)             /* Index changed */
00041   {
00042     info->lastinx = inx;
00043     info->page_changed=1;
00044     info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
00045                    HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
00046   }
00047   if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
00048     return(-1);
00049   return(inx);
00050 } /* mi_check_index */
00051 
00052 
00053         /*
00054         ** Search after row by a key
00055         ** Position to row is stored in info->lastpos
00056         ** Return: -1 if not found
00057         **          1 if one should continue search on higher level
00058         */
00059 
00060 int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
00061                unsigned char *key, uint32_t key_len, uint32_t nextflag, register internal::my_off_t pos)
00062 {
00063   bool last_key;
00064   int error,flag;
00065   uint32_t nod_flag;
00066   unsigned char *keypos,*maxpos;
00067   unsigned char lastkey[MI_MAX_KEY_BUFF],*buff;
00068 
00069   if (pos == HA_OFFSET_ERROR)
00070   {
00071     errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
00072     info->lastpos= HA_OFFSET_ERROR;
00073     if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
00074       return(-1);                          /* Not found ; return error */
00075     return(1);                             /* Search at upper levels */
00076   }
00077 
00078   if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
00079                                test(!(nextflag & SEARCH_SAVE_BUFF)))))
00080     goto err;
00081 
00082   flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
00083                               &keypos,lastkey, &last_key);
00084   if (flag == MI_FOUND_WRONG_KEY)
00085     return(-1);
00086   nod_flag=mi_test_if_nod(buff);
00087   maxpos=buff+mi_getint(buff)-1;
00088 
00089   if (flag)
00090   {
00091     if ((error=_mi_search(info,keyinfo,key,key_len,nextflag,
00092                           _mi_kpos(nod_flag,keypos))) <= 0)
00093       return(error);
00094 
00095     if (flag >0)
00096     {
00097       if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
00098           keypos == buff+2+nod_flag)
00099         return(1);                                 /* Bigger than key */
00100     }
00101     else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
00102       return(1);                                   /* Smaller than key */
00103   }
00104   else
00105   {
00106     if ((nextflag & SEARCH_FIND) && nod_flag &&
00107   ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
00108    key_len != USE_WHOLE_KEY))
00109     {
00110       if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
00111                             _mi_kpos(nod_flag,keypos))) >= 0 ||
00112           errno != HA_ERR_KEY_NOT_FOUND)
00113         return(error);
00114       info->last_keypage= HA_OFFSET_ERROR;              /* Buffer not in mem */
00115     }
00116   }
00117   if (pos != info->last_keypage)
00118   {
00119     unsigned char *old_buff=buff;
00120     if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
00121                                  test(!(nextflag & SEARCH_SAVE_BUFF)))))
00122       goto err;
00123     keypos=buff+(keypos-old_buff);
00124     maxpos=buff+(maxpos-old_buff);
00125   }
00126 
00127   if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
00128   {
00129     uint32_t not_used[2];
00130     if (_mi_get_prev_key(info,keyinfo, buff, info->lastkey, keypos,
00131                          &info->lastkey_length))
00132       goto err;
00133     if (!(nextflag & SEARCH_SMALLER) &&
00134         ha_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND,
00135                    not_used))
00136     {
00137       errno=HA_ERR_KEY_NOT_FOUND;                    /* Didn't find key */
00138       goto err;
00139     }
00140   }
00141   else
00142   {
00143     info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey);
00144     if (!info->lastkey_length)
00145       goto err;
00146     memcpy(info->lastkey,lastkey,info->lastkey_length);
00147   }
00148   info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
00149   /* Save position for a possible read next / previous */
00150   info->int_keypos=info->buff+ (keypos-buff);
00151   info->int_maxpos=info->buff+ (maxpos-buff);
00152   info->int_nod_flag=nod_flag;
00153   info->int_keytree_version=keyinfo->version;
00154   info->last_search_keypage=info->last_keypage;
00155   info->page_changed=0;
00156   info->buff_used= (info->buff != buff);        /* If we have to reread buff */
00157 
00158   return(0);
00159 
00160 err:
00161   info->lastpos= HA_OFFSET_ERROR;
00162   info->page_changed=1;
00163   return (-1);
00164 } /* _mi_search */
00165 
00166 
00167         /* Search after key in page-block */
00168         /* If packed key puts smaller or identical key in buff */
00169         /* ret_pos point to where find or bigger key starts */
00170         /* ARGSUSED */
00171 
00172 int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
00173                    unsigned char *key, uint32_t key_len, uint32_t comp_flag, unsigned char **ret_pos,
00174                    unsigned char *buff, bool *last_key)
00175 {
00176   (void)buff;
00177   register int start,mid,end,save_end;
00178   int flag= 0;
00179   uint32_t totlength,nod_flag,not_used[2];
00180 
00181   totlength=keyinfo->keylength+(nod_flag=mi_test_if_nod(page));
00182   start=0; mid=1;
00183   save_end=end=(int) ((mi_getint(page)-2-nod_flag)/totlength-1);
00184   page+=2+nod_flag;
00185 
00186   while (start != end)
00187   {
00188     mid= (start+end)/2;
00189     if ((flag=ha_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
00190                          comp_flag, not_used))
00191         >= 0)
00192       end=mid;
00193     else
00194       start=mid+1;
00195   }
00196   if (mid != start)
00197     flag=ha_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
00198                      comp_flag, not_used);
00199   if (flag < 0)
00200     start++;                    /* point at next, bigger key */
00201   *ret_pos=page+(uint) start*totlength;
00202   *last_key= end == save_end;
00203   return(flag);
00204 } /* _mi_bin_search */
00205 
00206 
00207 /*
00208   Locate a packed key in a key page.
00209 
00210   SYNOPSIS
00211     _mi_seq_search()
00212     info                        Open table information.
00213     keyinfo                     Key definition information.
00214     page                        Key page (beginning).
00215     key                         Search key.
00216     key_len                     Length to use from search key or USE_WHOLE_KEY
00217     comp_flag                   Search flags like SEARCH_SAME etc.
00218     ret_pos             RETURN  Position in key page behind this key.
00219     buff                RETURN  Copy of previous or identical unpacked key.
00220     last_key            RETURN  If key is last in page.
00221 
00222   DESCRIPTION
00223     Used instead of _mi_bin_search() when key is packed.
00224     Puts smaller or identical key in buff.
00225     Key is searched sequentially.
00226 
00227   RETURN
00228     > 0         Key in 'buff' is smaller than search key.
00229     0           Key in 'buff' is identical to search key.
00230     < 0         Not found.
00231 */
00232 
00233 int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
00234                    unsigned char *key, uint32_t key_len, uint32_t comp_flag, unsigned char **ret_pos,
00235                    unsigned char *buff, bool *last_key)
00236 {
00237   int flag= 0;
00238   uint32_t nod_flag,length=0,not_used[2];
00239   unsigned char t_buff[MI_MAX_KEY_BUFF],*end;
00240 
00241   end= page+mi_getint(page);
00242   nod_flag=mi_test_if_nod(page);
00243   page+=2+nod_flag;
00244   *ret_pos=page;
00245   t_buff[0]=0;                                  /* Avoid bugs */
00246   while (page < end)
00247   {
00248     length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
00249     if (length == 0 || page > end)
00250     {
00251       mi_print_error(info->s, HA_ERR_CRASHED);
00252       errno=HA_ERR_CRASHED;
00253       return(MI_FOUND_WRONG_KEY);
00254     }
00255     if ((flag=ha_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
00256                          not_used)) >= 0)
00257       break;
00258     memcpy(buff,t_buff,length);
00259     *ret_pos=page;
00260   }
00261   if (flag == 0)
00262     memcpy(buff,t_buff,length);                 /* Result is first key */
00263   *last_key= page == end;
00264   return(flag);
00265 } /* _mi_seq_search */
00266 
00267 
00268 int _mi_prefix_search(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
00269                       unsigned char *key, uint32_t key_len, uint32_t nextflag, unsigned char **ret_pos,
00270                       unsigned char *buff, bool *last_key)
00271 {
00272   /*
00273     my_flag is raw comparison result to be changed according to
00274     SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
00275     flag is the value returned by ha_key_cmp and as treated as final
00276   */
00277   int flag=0, my_flag=-1;
00278   uint32_t nod_flag, length=0, len, matched, cmplen, kseg_len;
00279   uint32_t prefix_len=0,suffix_len;
00280   int key_len_skip, seg_len_pack=0, key_len_left;
00281   unsigned char *end, *kseg, *vseg;
00282   unsigned char *sort_order=keyinfo->seg->charset->sort_order;
00283   unsigned char tt_buff[MI_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
00284   unsigned char *saved_from=NULL, *saved_to=NULL, *saved_vseg=NULL;
00285   uint32_t  saved_length=0, saved_prefix_len=0;
00286   uint32_t  length_pack;
00287 
00288 
00289   t_buff[0]=0;                                  /* Avoid bugs */
00290   end= page+mi_getint(page);
00291   nod_flag=mi_test_if_nod(page);
00292   page+=2+nod_flag;
00293   *ret_pos=page;
00294   kseg=key;
00295 
00296   get_key_pack_length(kseg_len,length_pack,kseg);
00297   key_len_skip=length_pack+kseg_len;
00298   key_len_left=(int) key_len- (int) key_len_skip;
00299   /* If key_len is 0, then lenght_pack is 1, then key_len_left is -1. */
00300   cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
00301 
00302   /*
00303     Keys are compressed the following way:
00304 
00305     If the max length of first key segment <= 127 bytes the prefix is
00306     1 byte else it's 2 byte
00307 
00308     (prefix) length  The high bit is set if this is a prefix for the prev key.
00309     [suffix length]  Packed length of suffix if the previous was a prefix.
00310     (suffix) data    Key data bytes (past the common prefix or whole segment).
00311     [next-key-seg]   Next key segments (([packed length], data), ...)
00312     pointer          Reference to the data file (last_keyseg->length).
00313   */
00314 
00315   matched=0;  /* how many char's from prefix were alredy matched */
00316   len=0;      /* length of previous key unpacked */
00317 
00318   while (page < end)
00319   {
00320     uint32_t packed= *page & 128;
00321 
00322     vseg=page;
00323     if (keyinfo->seg->length >= 127)
00324     {
00325       suffix_len=mi_uint2korr(vseg) & 32767;
00326       vseg+=2;
00327     }
00328     else
00329       suffix_len= *vseg++ & 127;
00330 
00331     if (packed)
00332     {
00333       if (suffix_len == 0)
00334       {
00335         /* == 0x80 or 0x8000, same key, prefix length == old key length. */
00336         prefix_len=len;
00337       }
00338       else
00339       {
00340         /* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
00341         prefix_len=suffix_len;
00342         get_key_length(suffix_len,vseg);
00343       }
00344     }
00345     else
00346     {
00347       /* Not packed. No prefix used from last key. */
00348       prefix_len=0;
00349     }
00350 
00351     len=prefix_len+suffix_len;
00352     seg_len_pack=get_pack_length(len);
00353     t_buff=tt_buff+3-seg_len_pack;
00354     store_key_length(t_buff,len);
00355 
00356     if (prefix_len > saved_prefix_len)
00357       memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
00358              prefix_len-saved_prefix_len);
00359     saved_vseg=vseg;
00360     saved_prefix_len=prefix_len;
00361 
00362     {
00363       unsigned char *from=vseg+suffix_len;
00364       HA_KEYSEG *keyseg;
00365       uint32_t l;
00366 
00367       for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
00368       {
00369 
00370         if (keyseg->flag & HA_NULL_PART)
00371         {
00372           if (!(*from++))
00373             continue;
00374         }
00375         if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
00376         {
00377           get_key_length(l,from);
00378         }
00379         else
00380           l=keyseg->length;
00381 
00382         from+=l;
00383       }
00384       from+=keyseg->length;
00385       page=from+nod_flag;
00386       length=from-vseg;
00387     }
00388 
00389     if (page > end)
00390     {
00391       mi_print_error(info->s, HA_ERR_CRASHED);
00392       errno=HA_ERR_CRASHED;
00393       return(MI_FOUND_WRONG_KEY);
00394     }
00395 
00396     if (matched >= prefix_len)
00397     {
00398       /* We have to compare. But we can still skip part of the key */
00399       uint32_t  left;
00400       unsigned char *k=kseg+prefix_len;
00401 
00402       /*
00403         If prefix_len > cmplen then we are in the end-space comparison
00404         phase. Do not try to acces the key any more ==> left= 0.
00405       */
00406       left= ((len <= cmplen) ? suffix_len :
00407              ((prefix_len < cmplen) ? cmplen - prefix_len : 0));
00408 
00409       matched=prefix_len+left;
00410 
00411       if (sort_order)
00412       {
00413         for (my_flag=0;left;left--)
00414           if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
00415             break;
00416       }
00417       else
00418       {
00419         for (my_flag=0;left;left--)
00420           if ((my_flag= (int) *vseg++ - (int) *k++))
00421             break;
00422       }
00423 
00424       if (my_flag>0)      /* mismatch */
00425         break;
00426       if (my_flag==0) /* match */
00427       {
00428   /*
00429         **  len cmplen seg_left_len more_segs
00430         **     <                               matched=len; continue search
00431         **     >      =                        prefix ? found : (matched=len; continue search)
00432         **     >      <                 -      ok, found
00433         **     =      <                 -      ok, found
00434         **     =      =                 -      ok, found
00435         **     =      =                 +      next seg
00436         */
00437         if (len < cmplen)
00438         {
00439     if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
00440          keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
00441                keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
00442       my_flag= -1;
00443     else
00444     {
00445       /* We have to compare k and vseg as if they were space extended */
00446       unsigned char *k_end= k+ (cmplen - len);
00447       for ( ; k < k_end && *k == ' '; k++) ;
00448       if (k == k_end)
00449         goto cmp_rest;    /* should never happen */
00450       if (*k < (unsigned char) ' ')
00451       {
00452         my_flag= 1;   /* Compared string is smaller */
00453         break;
00454       }
00455       my_flag= -1;    /* Continue searching */
00456     }
00457         }
00458         else if (len > cmplen)
00459         {
00460     unsigned char *vseg_end;
00461     if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
00462       goto fix_flag;
00463 
00464     /* We have to compare k and vseg as if they were space extended */
00465     for (vseg_end= vseg + (len-cmplen) ;
00466          vseg < vseg_end && *vseg == (unsigned char) ' ';
00467          vseg++, matched++) ;
00468     assert(vseg < vseg_end);
00469 
00470     if (*vseg > (unsigned char) ' ')
00471     {
00472       my_flag= 1;     /* Compared string is smaller */
00473       break;
00474     }
00475     my_flag= -1;      /* Continue searching */
00476         }
00477         else
00478   {
00479       cmp_rest:
00480     if (key_len_left>0)
00481     {
00482       uint32_t not_used[2];
00483       if ((flag = ha_key_cmp(keyinfo->seg+1,vseg,
00484            k, key_len_left, nextflag, not_used)) >= 0)
00485         break;
00486     }
00487     else
00488     {
00489       /*
00490         at this line flag==-1 if the following lines were already
00491         visited and 0 otherwise,  i.e. flag <=0 here always !!!
00492       */
00493   fix_flag:
00494       assert(flag <= 0);
00495       if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
00496         flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
00497       if (flag>=0)
00498         break;
00499     }
00500   }
00501       }
00502       matched-=left;
00503     }
00504     /* else (matched < prefix_len) ---> do nothing. */
00505 
00506     memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
00507     saved_to=buff+saved_length;
00508     saved_from=saved_vseg;
00509     saved_length=length;
00510     *ret_pos=page;
00511   }
00512   if (my_flag)
00513     flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
00514   if (flag == 0)
00515   {
00516     memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
00517     saved_to=buff+saved_length;
00518     saved_from=saved_vseg;
00519     saved_length=length;
00520   }
00521   if (saved_length)
00522     memcpy(saved_to,saved_from,saved_length);
00523 
00524   *last_key= page == end;
00525 
00526   return(flag);
00527 } /* _mi_prefix_search */
00528 
00529 
00530         /* Get pos to a key_block */
00531 
00532 internal::my_off_t _mi_kpos(uint32_t nod_flag, unsigned char *after_key)
00533 {
00534   after_key-=nod_flag;
00535   switch (nod_flag) {
00536 #if SIZEOF_OFF_T > 4
00537   case 7:
00538     return mi_uint7korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
00539   case 6:
00540     return mi_uint6korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
00541   case 5:
00542     return mi_uint5korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
00543 #else
00544   case 7:
00545     after_key++;
00546   case 6:
00547     after_key++;
00548   case 5:
00549     after_key++;
00550 #endif
00551   case 4:
00552     return ((internal::my_off_t) mi_uint4korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
00553   case 3:
00554     return ((internal::my_off_t) mi_uint3korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
00555   case 2:
00556     return (internal::my_off_t) (mi_uint2korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH);
00557   case 1:
00558     return (uint) (*after_key)*MI_MIN_KEY_BLOCK_LENGTH;
00559   case 0:                                       /* At leaf page */
00560   default:                                      /* Impossible */
00561     return(HA_OFFSET_ERROR);
00562   }
00563 } /* _kpos */
00564 
00565 
00566         /* Save pos to a key_block */
00567 
00568 void _mi_kpointer(register MI_INFO *info, register unsigned char *buff, internal::my_off_t pos)
00569 {
00570   pos/=MI_MIN_KEY_BLOCK_LENGTH;
00571   switch (info->s->base.key_reflength) {
00572 #if SIZEOF_OFF_T > 4
00573   case 7: mi_int7store(buff,pos); break;
00574   case 6: mi_int6store(buff,pos); break;
00575   case 5: mi_int5store(buff,pos); break;
00576 #else
00577   case 7: *buff++=0;
00578     /* fall trough */
00579   case 6: *buff++=0;
00580     /* fall trough */
00581   case 5: *buff++=0;
00582     /* fall trough */
00583 #endif
00584   case 4: mi_int4store(buff,pos); break;
00585   case 3: mi_int3store(buff,pos); break;
00586   case 2: mi_int2store(buff,(uint) pos); break;
00587   case 1: buff[0]= (unsigned char) pos; break;
00588   default: abort();                             /* impossible */
00589   }
00590 } /* _mi_kpointer */
00591 
00592 
00593         /* Calc pos to a data-record from a key */
00594 
00595 
00596 internal::my_off_t _mi_dpos(MI_INFO *info, uint32_t nod_flag, unsigned char *after_key)
00597 {
00598   internal::my_off_t pos;
00599   after_key-=(nod_flag + info->s->rec_reflength);
00600   switch (info->s->rec_reflength) {
00601 #if SIZEOF_OFF_T > 4
00602   case 8:  pos= (internal::my_off_t) mi_uint8korr(after_key);  break;
00603   case 7:  pos= (internal::my_off_t) mi_uint7korr(after_key);  break;
00604   case 6:  pos= (internal::my_off_t) mi_uint6korr(after_key);  break;
00605   case 5:  pos= (internal::my_off_t) mi_uint5korr(after_key);  break;
00606 #else
00607   case 8:  pos= (internal::my_off_t) mi_uint4korr(after_key+4);   break;
00608   case 7:  pos= (internal::my_off_t) mi_uint4korr(after_key+3);   break;
00609   case 6:  pos= (internal::my_off_t) mi_uint4korr(after_key+2);   break;
00610   case 5:  pos= (internal::my_off_t) mi_uint4korr(after_key+1);   break;
00611 #endif
00612   case 4:  pos= (internal::my_off_t) mi_uint4korr(after_key);  break;
00613   case 3:  pos= (internal::my_off_t) mi_uint3korr(after_key);  break;
00614   case 2:  pos= (internal::my_off_t) mi_uint2korr(after_key);  break;
00615   default:
00616     pos=0L;                                     /* Shut compiler up */
00617   }
00618   return (info->s->options &
00619           (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
00620             pos*info->s->base.pack_reclength;
00621 }
00622 
00623 
00624 /* Calc position from a record pointer ( in delete link chain ) */
00625 
00626 internal::my_off_t _mi_rec_pos(MYISAM_SHARE *s, unsigned char *ptr)
00627 {
00628   internal::my_off_t pos;
00629   switch (s->rec_reflength) {
00630 #if SIZEOF_OFF_T > 4
00631   case 8:
00632     pos= (internal::my_off_t) mi_uint8korr(ptr);
00633     if (pos == HA_OFFSET_ERROR)
00634       return HA_OFFSET_ERROR;                   /* end of list */
00635     break;
00636   case 7:
00637     pos= (internal::my_off_t) mi_uint7korr(ptr);
00638     if (pos == (((internal::my_off_t) 1) << 56) -1)
00639       return HA_OFFSET_ERROR;                   /* end of list */
00640     break;
00641   case 6:
00642     pos= (internal::my_off_t) mi_uint6korr(ptr);
00643     if (pos == (((internal::my_off_t) 1) << 48) -1)
00644       return HA_OFFSET_ERROR;                   /* end of list */
00645     break;
00646   case 5:
00647     pos= (internal::my_off_t) mi_uint5korr(ptr);
00648     if (pos == (((internal::my_off_t) 1) << 40) -1)
00649       return HA_OFFSET_ERROR;                   /* end of list */
00650     break;
00651 #else
00652   case 8:
00653   case 7:
00654   case 6:
00655   case 5:
00656     ptr+= (s->rec_reflength-4);
00657     /* fall through */
00658 #endif
00659   case 4:
00660     pos= (internal::my_off_t) mi_uint4korr(ptr);
00661     if (pos == (internal::my_off_t) UINT32_MAX)
00662       return  HA_OFFSET_ERROR;
00663     break;
00664   case 3:
00665     pos= (internal::my_off_t) mi_uint3korr(ptr);
00666     if (pos == (internal::my_off_t) (1 << 24) -1)
00667       return HA_OFFSET_ERROR;
00668     break;
00669   case 2:
00670     pos= (internal::my_off_t) mi_uint2korr(ptr);
00671     if (pos == (internal::my_off_t) (1 << 16) -1)
00672       return HA_OFFSET_ERROR;
00673     break;
00674   default: abort();                             /* Impossible */
00675   }
00676   return ((s->options &
00677           (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
00678           pos*s->base.pack_reclength);
00679 }
00680 
00681 
00682         /* save position to record */
00683 
00684 void _mi_dpointer(MI_INFO *info, unsigned char *buff, internal::my_off_t pos)
00685 {
00686   if (!(info->s->options &
00687         (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) &&
00688       pos != HA_OFFSET_ERROR)
00689     pos/=info->s->base.pack_reclength;
00690 
00691   switch (info->s->rec_reflength) {
00692 #if SIZEOF_OFF_T > 4
00693   case 8: mi_int8store(buff,pos); break;
00694   case 7: mi_int7store(buff,pos); break;
00695   case 6: mi_int6store(buff,pos); break;
00696   case 5: mi_int5store(buff,pos); break;
00697 #else
00698   case 8: *buff++=0;
00699     /* fall trough */
00700   case 7: *buff++=0;
00701     /* fall trough */
00702   case 6: *buff++=0;
00703     /* fall trough */
00704   case 5: *buff++=0;
00705     /* fall trough */
00706 #endif
00707   case 4: mi_int4store(buff,pos); break;
00708   case 3: mi_int3store(buff,pos); break;
00709   case 2: mi_int2store(buff,(uint) pos); break;
00710   default: abort();                             /* Impossible */
00711   }
00712 } /* _mi_dpointer */
00713 
00714 
00715         /* Get key from key-block */
00716         /* page points at previous key; its advanced to point at next key */
00717         /* key should contain previous key */
00718         /* Returns length of found key + pointers */
00719         /* nod_flag is a flag if we are on nod */
00720 
00721         /* same as _mi_get_key but used with fixed length keys */
00722 
00723 uint32_t _mi_get_static_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
00724                        register unsigned char **page, register unsigned char *key)
00725 {
00726   memcpy(key, *page, keyinfo->keylength+nod_flag);
00727   *page+=keyinfo->keylength+nod_flag;
00728   return(keyinfo->keylength);
00729 } /* _mi_get_static_key */
00730 
00731 
00732 /*
00733   get key witch is packed against previous key or key with a NULL column.
00734 
00735   SYNOPSIS
00736     _mi_get_pack_key()
00737     keyinfo                     key definition information.
00738     nod_flag                    If nod: Length of node pointer, else zero.
00739     page_pos            RETURN  position in key page behind this key.
00740     key                 IN/OUT  in: prev key, out: unpacked key.
00741 
00742   RETURN
00743     key_length + length of data pointer
00744 */
00745 
00746 uint32_t _mi_get_pack_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
00747                       register unsigned char **page_pos, register unsigned char *key)
00748 {
00749   register HA_KEYSEG *keyseg;
00750   unsigned char *start_key,*page=*page_pos;
00751   uint32_t length;
00752 
00753   start_key=key;
00754   for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
00755   {
00756     if (keyseg->flag & HA_PACK_KEY)
00757     {
00758       /* key with length, packed to previous key */
00759       unsigned char *start=key;
00760       uint32_t packed= *page & 128,tot_length,rest_length;
00761       if (keyseg->length >= 127)
00762       {
00763         length=mi_uint2korr(page) & 32767;
00764         page+=2;
00765       }
00766       else
00767         length= *page++ & 127;
00768 
00769       if (packed)
00770       {
00771   if (length > (uint) keyseg->length)
00772   {
00773           mi_print_error(keyinfo->share, HA_ERR_CRASHED);
00774     errno=HA_ERR_CRASHED;
00775     return 0;       /* Error */
00776   }
00777   if (length == 0)      /* Same key */
00778   {
00779     if (keyseg->flag & HA_NULL_PART)
00780       *key++=1;       /* Can't be NULL */
00781     get_key_length(length,key);
00782     key+= length;       /* Same diff_key as prev */
00783     if (length > keyseg->length)
00784     {
00785             mi_print_error(keyinfo->share, HA_ERR_CRASHED);
00786       errno=HA_ERR_CRASHED;
00787       return 0;
00788     }
00789     continue;
00790   }
00791   if (keyseg->flag & HA_NULL_PART)
00792   {
00793     key++;        /* Skip null marker*/
00794     start++;
00795   }
00796 
00797   get_key_length(rest_length,page);
00798   tot_length=rest_length+length;
00799 
00800   /* If the stored length has changed, we must move the key */
00801   if (tot_length >= 255 && *start != 255)
00802   {
00803     /* length prefix changed from a length of one to a length of 3 */
00804     internal::bmove_upp(key+length+3, key+length+1, length);
00805     *key=255;
00806     mi_int2store(key+1,tot_length);
00807     key+=3+length;
00808   }
00809   else if (tot_length < 255 && *start == 255)
00810   {
00811           memmove(key+1,key+3,length);
00812     *key=tot_length;
00813     key+=1+length;
00814   }
00815   else
00816   {
00817     store_key_length_inc(key,tot_length);
00818     key+=length;
00819   }
00820   memcpy(key,page,rest_length);
00821   page+=rest_length;
00822   key+=rest_length;
00823   continue;
00824       }
00825       else
00826       {
00827         if (keyseg->flag & HA_NULL_PART)
00828         {
00829           if (!length--)                        /* Null part */
00830           {
00831             *key++=0;
00832             continue;
00833           }
00834           *key++=1;                             /* Not null */
00835         }
00836       }
00837       if (length > (uint) keyseg->length)
00838       {
00839         mi_print_error(keyinfo->share, HA_ERR_CRASHED);
00840         errno=HA_ERR_CRASHED;
00841         return 0;                               /* Error */
00842       }
00843       store_key_length_inc(key,length);
00844     }
00845     else
00846     {
00847       if (keyseg->flag & HA_NULL_PART)
00848       {
00849         if (!(*key++ = *page++))
00850           continue;
00851       }
00852       if (keyseg->flag &
00853           (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
00854       {
00855         unsigned char *tmp=page;
00856         get_key_length(length,tmp);
00857         length+=(uint) (tmp-page);
00858       }
00859       else
00860         length=keyseg->length;
00861     }
00862     memcpy(key, page, length);
00863     key+=length;
00864     page+=length;
00865   }
00866   length=keyseg->length+nod_flag;
00867   memmove(key,page,length);
00868   *page_pos= page+length;
00869   return ((uint) (key-start_key)+keyseg->length);
00870 } /* _mi_get_pack_key */
00871 
00872 
00873 
00874 /* key that is packed relatively to previous */
00875 
00876 uint32_t _mi_get_binary_pack_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
00877                              register unsigned char **page_pos, register unsigned char *key)
00878 {
00879   register HA_KEYSEG *keyseg;
00880   unsigned char *start_key,*page,*page_end,*from,*from_end;
00881   uint32_t length,tmp;
00882 
00883   page= *page_pos;
00884   page_end=page+MI_MAX_KEY_BUFF+1;
00885   start_key=key;
00886 
00887   /*
00888     Keys are compressed the following way:
00889 
00890     prefix length    Packed length of prefix common with prev key (1 or 3 bytes)
00891     for each key segment:
00892       [is null]        Null indicator if can be null (1 byte, zero means null)
00893       [length]         Packed length if varlength (1 or 3 bytes)
00894       key segment      'length' bytes of key segment value
00895     pointer          Reference to the data file (last_keyseg->length).
00896 
00897     get_key_length() is a macro. It gets the prefix length from 'page'
00898     and puts it into 'length'. It increments 'page' by 1 or 3, depending
00899     on the packed length of the prefix length.
00900   */
00901   get_key_length(length,page);
00902   if (length)
00903   {
00904     if (length > keyinfo->maxlength)
00905     {
00906       mi_print_error(keyinfo->share, HA_ERR_CRASHED);
00907       errno=HA_ERR_CRASHED;
00908       return(0);                                 /* Wrong key */
00909     }
00910     /* Key is packed against prev key, take prefix from prev key. */
00911     from= key;
00912     from_end= key + length;
00913   }
00914   else
00915   {
00916     /* Key is not packed against prev key, take all from page buffer. */
00917     from= page;
00918     from_end= page_end;
00919   }
00920 
00921   /*
00922     The trouble is that key can be split in two parts:
00923       The first part (prefix) is in from .. from_end - 1.
00924       The second part starts at page.
00925     The split can be at every byte position. So we need to check for
00926     the end of the first part before using every byte.
00927   */
00928   for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
00929   {
00930     if (keyseg->flag & HA_NULL_PART)
00931     {
00932       /* If prefix is used up, switch to rest. */
00933       if (from == from_end) { from=page;  from_end=page_end; }
00934       if (!(*key++ = *from++))
00935         continue;                               /* Null part */
00936     }
00937     if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
00938     {
00939       /* If prefix is used up, switch to rest. */
00940       if (from == from_end) { from=page;  from_end=page_end; }
00941       /* Get length of dynamic length key part */
00942       if ((length= (*key++ = *from++)) == 255)
00943       {
00944         /* If prefix is used up, switch to rest. */
00945         if (from == from_end) { from=page;  from_end=page_end; }
00946         length= (uint) ((*key++ = *from++)) << 8;
00947         /* If prefix is used up, switch to rest. */
00948         if (from == from_end) { from=page;  from_end=page_end; }
00949         length+= (uint) ((*key++ = *from++));
00950       }
00951     }
00952     else
00953       length=keyseg->length;
00954 
00955     if ((tmp=(uint) (from_end-from)) <= length)
00956     {
00957       key+=tmp;                                 /* Use old key */
00958       length-=tmp;
00959       from=page; from_end=page_end;
00960     }
00961     memmove(key, from, length);
00962     key+=length;
00963     from+=length;
00964   }
00965   /*
00966     Last segment (type == 0) contains length of data pointer.
00967     If we have mixed key blocks with data pointer and key block pointer,
00968     we have to copy both.
00969   */
00970   length=keyseg->length+nod_flag;
00971   if ((tmp=(uint) (from_end-from)) <= length)
00972   {
00973     /* Remaining length is less or equal max possible length. */
00974     memcpy(key+tmp,page,length-tmp);            /* Get last part of key */
00975     *page_pos= page+length-tmp;
00976   }
00977   else
00978   {
00979     /*
00980       Remaining length is greater than max possible length.
00981       This can happen only if we switched to the new key bytes already.
00982       'page_end' is calculated with MI_MAX_KEY_BUFF. So it can be far
00983       behind the real end of the key.
00984     */
00985     if (from_end != page_end)
00986     {
00987       mi_print_error(keyinfo->share, HA_ERR_CRASHED);
00988       errno=HA_ERR_CRASHED;
00989       return(0);                                 /* Error */
00990     }
00991     /* Copy data pointer and, if appropriate, key block pointer. */
00992     memcpy(key, from, length);
00993     *page_pos= from+length;
00994   }
00995   return((uint) (key-start_key)+keyseg->length);
00996 }
00997 
00998 
00999         /* Get key at position without knowledge of previous key */
01000         /* Returns pointer to next key */
01001 
01002 unsigned char *_mi_get_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
01003                    unsigned char *key, unsigned char *keypos, uint32_t *return_key_length)
01004 {
01005   uint32_t nod_flag;
01006 
01007   nod_flag=mi_test_if_nod(page);
01008   if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
01009   {
01010     memmove(key,keypos,keyinfo->keylength+nod_flag);
01011     return(keypos+keyinfo->keylength+nod_flag);
01012   }
01013   else
01014   {
01015     page+=2+nod_flag;
01016     key[0]=0;                                   /* safety */
01017     while (page <= keypos)
01018     {
01019       *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
01020       if (*return_key_length == 0)
01021       {
01022         mi_print_error(info->s, HA_ERR_CRASHED);
01023         errno=HA_ERR_CRASHED;
01024         return(0);
01025       }
01026     }
01027   }
01028   return(page);
01029 } /* _mi_get_key */
01030 
01031 
01032         /* Get key at position without knowledge of previous key */
01033         /* Returns 0 if ok */
01034 
01035 static bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
01036                                 unsigned char *key, unsigned char *keypos,
01037                                 uint32_t *return_key_length)
01038 {
01039   uint32_t nod_flag;
01040 
01041   nod_flag=mi_test_if_nod(page);
01042   if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
01043   {
01044     *return_key_length=keyinfo->keylength;
01045     memmove(key, keypos - *return_key_length-nod_flag, *return_key_length);
01046     return(0);
01047   }
01048   else
01049   {
01050     page+=2+nod_flag;
01051     key[0]=0;                                   /* safety */
01052     while (page < keypos)
01053     {
01054       *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
01055       if (*return_key_length == 0)
01056       {
01057         mi_print_error(info->s, HA_ERR_CRASHED);
01058         errno=HA_ERR_CRASHED;
01059         return(1);
01060       }
01061     }
01062   }
01063   return(0);
01064 } /* _mi_get_key */
01065 
01066 
01067 
01068         /* Get last key from key-page */
01069         /* Return pointer to where key starts */
01070 
01071 unsigned char *_mi_get_last_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
01072                         unsigned char *lastkey, unsigned char *endpos, uint32_t *return_key_length)
01073 {
01074   uint32_t nod_flag;
01075   unsigned char *lastpos;
01076 
01077   nod_flag=mi_test_if_nod(page);
01078   if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
01079   {
01080     lastpos=endpos-keyinfo->keylength-nod_flag;
01081     *return_key_length=keyinfo->keylength;
01082     if (lastpos > page)
01083       memmove(lastkey,lastpos,keyinfo->keylength+nod_flag);
01084   }
01085   else
01086   {
01087     lastpos=(page+=2+nod_flag);
01088     lastkey[0]=0;
01089     while (page < endpos)
01090     {
01091       lastpos=page;
01092       *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,lastkey);
01093       if (*return_key_length == 0)
01094       {
01095         mi_print_error(info->s, HA_ERR_CRASHED);
01096         errno=HA_ERR_CRASHED;
01097         return(0);
01098       }
01099     }
01100   }
01101   return(lastpos);
01102 } /* _mi_get_last_key */
01103 
01104 
01105         /* Calculate length of key */
01106 
01107 uint32_t _mi_keylength(MI_KEYDEF *keyinfo, register unsigned char *key)
01108 {
01109   register HA_KEYSEG *keyseg;
01110   unsigned char *start;
01111 
01112   if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
01113     return (keyinfo->keylength);
01114 
01115   start=key;
01116   for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
01117   {
01118     if (keyseg->flag & HA_NULL_PART)
01119       if (!*key++)
01120         continue;
01121     if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
01122     {
01123       uint32_t length;
01124       get_key_length(length,key);
01125       key+=length;
01126     }
01127     else
01128       key+= keyseg->length;
01129   }
01130   return((uint) (key-start)+keyseg->length);
01131 } /* _mi_keylength */
01132 
01133 
01134 /*
01135   Calculate length of part key.
01136 
01137   Used in mi_rkey() to find the key found for the key-part that was used.
01138   This is needed in case of multi-byte character sets where we may search
01139   after '0xDF' but find 'ss'
01140 */
01141 
01142 uint32_t _mi_keylength_part(MI_KEYDEF *keyinfo, register unsigned char *key,
01143       HA_KEYSEG *end)
01144 {
01145   register HA_KEYSEG *keyseg;
01146   unsigned char *start= key;
01147 
01148   for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
01149   {
01150     if (keyseg->flag & HA_NULL_PART)
01151       if (!*key++)
01152         continue;
01153     if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
01154     {
01155       uint32_t length;
01156       get_key_length(length,key);
01157       key+=length;
01158     }
01159     else
01160       key+= keyseg->length;
01161   }
01162   return (uint) (key-start);
01163 }
01164 
01165         /* Move a key */
01166 
01167 unsigned char *_mi_move_key(MI_KEYDEF *keyinfo, unsigned char *to, unsigned char *from)
01168 {
01169   register uint32_t length;
01170   length= _mi_keylength(keyinfo, from);
01171   memcpy(to, from, length);
01172   return to+length;
01173 }
01174 
01175         /* Find next/previous record with same key */
01176         /* This can't be used when database is touched after last read */
01177 
01178 int _mi_search_next(register MI_INFO *info, register MI_KEYDEF *keyinfo,
01179                     unsigned char *key, uint32_t key_length, uint32_t nextflag, internal::my_off_t pos)
01180 {
01181   int error;
01182   uint32_t nod_flag;
01183   unsigned char lastkey[MI_MAX_KEY_BUFF];
01184 
01185   /* Force full read if we are at last key or if we are not on a leaf
01186      and the key tree has changed since we used it last time
01187      Note that even if the key tree has changed since last read, we can use
01188      the last read data from the leaf if we haven't used the buffer for
01189      something else.
01190   */
01191 
01192   if (((nextflag & SEARCH_BIGGER) && info->int_keypos >= info->int_maxpos) ||
01193       info->page_changed ||
01194       (info->int_keytree_version != keyinfo->version &&
01195        (info->int_nod_flag || info->buff_used)))
01196     return(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
01197                            nextflag | SEARCH_SAVE_BUFF, pos));
01198 
01199   if (info->buff_used)
01200   {
01201     if (!_mi_fetch_keypage(info,keyinfo,info->last_search_keypage,
01202                            DFLT_INIT_HITS,info->buff,0))
01203       return(-1);
01204     info->buff_used=0;
01205   }
01206 
01207   /* Last used buffer is in info->buff */
01208   nod_flag=mi_test_if_nod(info->buff);
01209 
01210   if (nextflag & SEARCH_BIGGER)                                 /* Next key */
01211   {
01212     internal::my_off_t tmp_pos=_mi_kpos(nod_flag,info->int_keypos);
01213     if (tmp_pos != HA_OFFSET_ERROR)
01214     {
01215       if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
01216                             nextflag | SEARCH_SAVE_BUFF, tmp_pos)) <=0)
01217         return(error);
01218     }
01219     memcpy(lastkey,key,key_length);
01220     if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,
01221                                                    &info->int_keypos,lastkey)))
01222       return(-1);
01223   }
01224   else                                                  /* Previous key */
01225   {
01226     uint32_t length;
01227     /* Find start of previous key */
01228     info->int_keypos=_mi_get_last_key(info,keyinfo,info->buff,lastkey,
01229                                       info->int_keypos, &length);
01230     if (!info->int_keypos)
01231       return(-1);
01232     if (info->int_keypos == info->buff+2)
01233       return(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
01234                              nextflag | SEARCH_SAVE_BUFF, pos));
01235     if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
01236         nextflag | SEARCH_SAVE_BUFF,
01237                           _mi_kpos(nod_flag,info->int_keypos))) <= 0)
01238       return(error);
01239 
01240     /* QQ: We should be able to optimize away the following call */
01241     if (! _mi_get_last_key(info,keyinfo,info->buff,lastkey,
01242                            info->int_keypos,&info->lastkey_length))
01243       return(-1);
01244   }
01245   memcpy(info->lastkey,lastkey,info->lastkey_length);
01246   info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
01247   return(0);
01248 } /* _mi_search_next */
01249 
01250 
01251         /* Search after position for the first row in an index */
01252         /* This is stored in info->lastpos */
01253 
01254 int _mi_search_first(register MI_INFO *info, register MI_KEYDEF *keyinfo,
01255                      register internal::my_off_t pos)
01256 {
01257   uint32_t nod_flag;
01258   unsigned char *page;
01259 
01260   if (pos == HA_OFFSET_ERROR)
01261   {
01262     errno=HA_ERR_KEY_NOT_FOUND;
01263     info->lastpos= HA_OFFSET_ERROR;
01264     return(-1);
01265   }
01266 
01267   do
01268   {
01269     if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,0))
01270     {
01271       info->lastpos= HA_OFFSET_ERROR;
01272       return(-1);
01273     }
01274     nod_flag=mi_test_if_nod(info->buff);
01275     page=info->buff+2+nod_flag;
01276   } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
01277 
01278   if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,
01279                                                  info->lastkey)))
01280     return(-1);                            /* Crashed */
01281 
01282   info->int_keypos=page; info->int_maxpos=info->buff+mi_getint(info->buff)-1;
01283   info->int_nod_flag=nod_flag;
01284   info->int_keytree_version=keyinfo->version;
01285   info->last_search_keypage=info->last_keypage;
01286   info->page_changed=info->buff_used=0;
01287   info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
01288 
01289   return(0);
01290 } /* _mi_search_first */
01291 
01292 
01293         /* Search after position for the last row in an index */
01294         /* This is stored in info->lastpos */
01295 
01296 int _mi_search_last(register MI_INFO *info, register MI_KEYDEF *keyinfo,
01297                     register internal::my_off_t pos)
01298 {
01299   uint32_t nod_flag;
01300   unsigned char *buff,*page;
01301 
01302   if (pos == HA_OFFSET_ERROR)
01303   {
01304     errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
01305     info->lastpos= HA_OFFSET_ERROR;
01306     return(-1);
01307   }
01308 
01309   buff=info->buff;
01310   do
01311   {
01312     if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,buff,0))
01313     {
01314       info->lastpos= HA_OFFSET_ERROR;
01315       return(-1);
01316     }
01317     page= buff+mi_getint(buff);
01318     nod_flag=mi_test_if_nod(buff);
01319   } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
01320 
01321   if (!_mi_get_last_key(info,keyinfo,buff,info->lastkey,page,
01322                         &info->lastkey_length))
01323     return(-1);
01324   info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
01325   info->int_keypos=info->int_maxpos=page;
01326   info->int_nod_flag=nod_flag;
01327   info->int_keytree_version=keyinfo->version;
01328   info->last_search_keypage=info->last_keypage;
01329   info->page_changed=info->buff_used=0;
01330 
01331   return(0);
01332 } /* _mi_search_last */
01333 
01334 
01335 
01336 /****************************************************************************
01337 **
01338 ** Functions to store and pack a key in a page
01339 **
01340 ** mi_calc_xx_key_length takes the following arguments:
01341 **  nod_flag    If nod: Length of nod-pointer
01342 **  next_key    Position to pos after the new key in buffer
01343 **  org_key     Key that was before the next key in buffer
01344 **  prev_key    Last key before current key
01345 **  key         Key that will be stored
01346 **  s_temp      Information how next key will be packed
01347 ****************************************************************************/
01348 
01349 /* Static length key */
01350 
01351 int
01352 _mi_calc_static_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,
01353                            unsigned char *next_pos,
01354                            unsigned char *org_key,
01355                            unsigned char *prev_key,
01356                            unsigned char *key, MI_KEY_PARAM *s_temp)
01357 {
01358   (void)next_pos;
01359   (void)org_key;
01360   (void)prev_key;
01361   s_temp->key=key;
01362   return (int) (s_temp->totlength=keyinfo->keylength+nod_flag);
01363 }
01364 
01365 /* Variable length key */
01366 
01367 int
01368 _mi_calc_var_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,
01369                         unsigned char *next_pos,
01370                         unsigned char *org_key,
01371                         unsigned char *prev_key,
01372                         unsigned char *key, MI_KEY_PARAM *s_temp)
01373 {
01374   (void)next_pos;
01375   (void)org_key;
01376   (void)prev_key;
01377   s_temp->key=key;
01378   return (int) (s_temp->totlength=_mi_keylength(keyinfo,key)+nod_flag);
01379 }
01380 
01381 /*
01382   length of key with a variable length first segment which is prefix
01383   compressed (myisamchk reports 'packed + stripped')
01384 
01385   Keys are compressed the following way:
01386 
01387   If the max length of first key segment <= 127 bytes the prefix is
01388   1 byte else it's 2 byte
01389 
01390   prefix byte(s) The high bit is set if this is a prefix for the prev key
01391   length         Packed length if the previous was a prefix byte
01392   [length]       data bytes ('length' bytes)
01393   next-key-seg   Next key segments
01394 
01395   If the first segment can have NULL:
01396   The length is 0 for NULLS and 1+length for not null columns.
01397 
01398 */
01399 
01400 int
01401 _mi_calc_var_pack_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,
01402                              unsigned char *next_key,
01403                              unsigned char *org_key,
01404                              unsigned char *prev_key,
01405                              unsigned char *key,
01406                              MI_KEY_PARAM *s_temp)
01407 {
01408   register HA_KEYSEG *keyseg;
01409   int length;
01410   uint32_t key_length,ref_length,org_key_length=0,
01411        length_pack,new_key_length,diff_flag,pack_marker;
01412   unsigned char *start,*end,*key_end,*sort_order;
01413   bool same_length;
01414 
01415   length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
01416   same_length=0; keyseg=keyinfo->seg;
01417   key_length=_mi_keylength(keyinfo,key)+nod_flag;
01418 
01419   sort_order=0;
01420 
01421   /* diff flag contains how many bytes is needed to pack key */
01422   if (keyseg->length >= 127)
01423   {
01424     diff_flag=2;
01425     pack_marker=32768;
01426   }
01427   else
01428   {
01429     diff_flag= 1;
01430     pack_marker=128;
01431   }
01432   s_temp->pack_marker=pack_marker;
01433 
01434   /* Handle the case that the first part have NULL values */
01435   if (keyseg->flag & HA_NULL_PART)
01436   {
01437     if (!*key++)
01438     {
01439       s_temp->key=key;
01440       s_temp->key_length= 0;
01441       s_temp->totlength=key_length-1+diff_flag;
01442       s_temp->next_key_pos=0;                   /* No next key */
01443       return (s_temp->totlength);
01444     }
01445     s_temp->store_not_null=1;
01446     key_length--;                               /* We don't store NULL */
01447     if (prev_key && !*prev_key++)
01448       org_key=prev_key=0;                       /* Can't pack against prev */
01449     else if (org_key)
01450       org_key++;                                /* Skip NULL */
01451   }
01452   else
01453     s_temp->store_not_null=0;
01454   s_temp->prev_key=org_key;
01455 
01456   /* The key part will start with a packed length */
01457 
01458   get_key_pack_length(new_key_length,length_pack,key);
01459   end=key_end= key+ new_key_length;
01460   start=key;
01461 
01462   /* Calc how many characters are identical between this and the prev. key */
01463   if (prev_key)
01464   {
01465     get_key_length(org_key_length,prev_key);
01466     s_temp->prev_key=prev_key;          /* Pointer at data */
01467     /* Don't use key-pack if length == 0 */
01468     if (new_key_length && new_key_length == org_key_length)
01469       same_length=1;
01470     else if (new_key_length > org_key_length)
01471       end=key + org_key_length;
01472 
01473     if (sort_order)                             /* SerG */
01474     {
01475       while (key < end && sort_order[*key] == sort_order[*prev_key])
01476       {
01477         key++; prev_key++;
01478       }
01479     }
01480     else
01481     {
01482       while (key < end && *key == *prev_key)
01483       {
01484         key++; prev_key++;
01485       }
01486     }
01487   }
01488 
01489   s_temp->key=key;
01490   s_temp->key_length= (uint) (key_end-key);
01491 
01492   if (same_length && key == key_end)
01493   {
01494     /* identical variable length key */
01495     s_temp->ref_length= pack_marker;
01496     length=(int) key_length-(int) (key_end-start)-length_pack;
01497     length+= diff_flag;
01498     if (next_key)
01499     {                                           /* Can't combine with next */
01500       s_temp->n_length= *next_key;              /* Needed by _mi_store_key */
01501       next_key=0;
01502     }
01503   }
01504   else
01505   {
01506     if (start != key)
01507     {                                           /* Starts as prev key */
01508       ref_length= (uint) (key-start);
01509       s_temp->ref_length= ref_length + pack_marker;
01510       length= (int) (key_length - ref_length);
01511 
01512       length-= length_pack;
01513       length+= diff_flag;
01514       length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;/* Rest_of_key */
01515     }
01516     else
01517     {
01518       s_temp->key_length+=s_temp->store_not_null;       /* If null */
01519       length= key_length - length_pack+ diff_flag;
01520     }
01521   }
01522   s_temp->totlength=(uint) length;
01523   s_temp->prev_length=0;
01524 
01525         /* If something after that hasn't length=0, test if we can combine */
01526   if ((s_temp->next_key_pos=next_key))
01527   {
01528     uint32_t packed,n_length;
01529 
01530     packed = *next_key & 128;
01531     if (diff_flag == 2)
01532     {
01533       n_length= mi_uint2korr(next_key) & 32767; /* Length of next key */
01534       next_key+=2;
01535     }
01536     else
01537       n_length= *next_key++ & 127;
01538     if (!packed)
01539       n_length-= s_temp->store_not_null;
01540 
01541     if (n_length || packed)             /* Don't pack 0 length keys */
01542     {
01543       uint32_t next_length_pack, new_ref_length=s_temp->ref_length;
01544 
01545       if (packed)
01546       {
01547         /* If first key and next key is packed (only on delete) */
01548         if (!prev_key && org_key)
01549         {
01550           get_key_length(org_key_length,org_key);
01551           key=start;
01552           if (sort_order)                       /* SerG */
01553           {
01554             while (key < end && sort_order[*key] == sort_order[*org_key])
01555             {
01556               key++; org_key++;
01557             }
01558           }
01559           else
01560           {
01561             while (key < end && *key == *org_key)
01562             {
01563               key++; org_key++;
01564             }
01565           }
01566           if ((new_ref_length= (uint) (key - start)))
01567             new_ref_length+=pack_marker;
01568         }
01569 
01570         if (!n_length)
01571         {
01572           /*
01573             We put a different key between two identical variable length keys
01574             Extend next key to have same prefix as this key
01575           */
01576           if (new_ref_length)                   /* prefix of previus key */
01577           {                                     /* make next key longer */
01578             s_temp->part_of_prev_key= new_ref_length;
01579             s_temp->prev_length=          org_key_length -
01580               (new_ref_length-pack_marker);
01581             s_temp->n_ref_length= s_temp->part_of_prev_key;
01582             s_temp->n_length= s_temp->prev_length;
01583             n_length=             get_pack_length(s_temp->prev_length);
01584             s_temp->prev_key+=    (new_ref_length - pack_marker);
01585             length+=              s_temp->prev_length + n_length;
01586           }
01587           else
01588           {                                     /* Can't use prev key */
01589             s_temp->part_of_prev_key=0;
01590             s_temp->prev_length= org_key_length;
01591             s_temp->n_ref_length=s_temp->n_length=  org_key_length;
01592             length+=           org_key_length;
01593           }
01594           return (int) length;
01595         }
01596 
01597         ref_length=n_length;
01598         /* Get information about not packed key suffix */
01599         get_key_pack_length(n_length,next_length_pack,next_key);
01600 
01601         /* Test if new keys has fewer characters that match the previous key */
01602         if (!new_ref_length)
01603         {                                       /* Can't use prev key */
01604           s_temp->part_of_prev_key=     0;
01605           s_temp->prev_length=          ref_length;
01606           s_temp->n_ref_length= s_temp->n_length= n_length+ref_length;
01607           return (int) length+ref_length-next_length_pack;
01608         }
01609         if (ref_length+pack_marker > new_ref_length)
01610         {
01611           uint32_t new_pack_length=new_ref_length-pack_marker;
01612           /* We must copy characters from the original key to the next key */
01613           s_temp->part_of_prev_key= new_ref_length;
01614           s_temp->prev_length=      ref_length - new_pack_length;
01615           s_temp->n_ref_length=s_temp->n_length=n_length + s_temp->prev_length;
01616           s_temp->prev_key+=        new_pack_length;
01617           length-= (next_length_pack - get_pack_length(s_temp->n_length));
01618           return (int) length + s_temp->prev_length;
01619         }
01620       }
01621       else
01622       {
01623         /* Next key wasn't a prefix of previous key */
01624         ref_length=0;
01625         next_length_pack=0;
01626       }
01627 
01628       {
01629         uint32_t tmp_length;
01630         key=(start+=ref_length);
01631         if (key+n_length < key_end)             /* Normalize length based */
01632           key_end=key+n_length;
01633         if (sort_order)                         /* SerG */
01634         {
01635           while (key < key_end && sort_order[*key] ==
01636                  sort_order[*next_key])
01637           {
01638             key++; next_key++;
01639           }
01640         }
01641         else
01642         {
01643           while (key < key_end && *key == *next_key)
01644           {
01645             key++; next_key++;
01646           }
01647         }
01648         if (!(tmp_length=(uint) (key-start)))
01649         {                                       /* Key can't be re-packed */
01650           s_temp->next_key_pos=0;
01651           return length;
01652         }
01653         ref_length+=tmp_length;
01654         n_length-=tmp_length;
01655         length-=tmp_length+next_length_pack;    /* We gained these chars */
01656       }
01657       if (n_length == 0 && ref_length == new_key_length)
01658       {
01659         s_temp->n_ref_length=pack_marker;       /* Same as prev key */
01660       }
01661       else
01662       {
01663         s_temp->n_ref_length=ref_length | pack_marker;
01664         length+= get_pack_length(n_length);
01665         s_temp->n_length=n_length;
01666       }
01667     }
01668   }
01669   return length;
01670 }
01671 
01672 
01673 /* Length of key which is prefix compressed */
01674 
01675 int
01676 _mi_calc_bin_pack_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,unsigned char *next_key,
01677                              unsigned char *org_key, unsigned char *prev_key, unsigned char *key,
01678                              MI_KEY_PARAM *s_temp)
01679 {
01680   uint32_t length,key_length,ref_length;
01681 
01682   s_temp->totlength=key_length=_mi_keylength(keyinfo,key)+nod_flag;
01683 #ifdef HAVE_VALGRIND
01684   s_temp->n_length= s_temp->n_ref_length=0; /* For valgrind */
01685 #endif
01686   s_temp->key=key;
01687   s_temp->prev_key=org_key;
01688   if (prev_key)                                 /* If not first key in block */
01689   {
01690     /* pack key against previous key */
01691     /*
01692       As keys may be identical when running a sort in myisamchk, we
01693       have to guard against the case where keys may be identical
01694     */
01695     unsigned char *end;
01696     end=key+key_length;
01697     for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
01698     s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
01699     length=key_length - ref_length + get_pack_length(ref_length);
01700   }
01701   else
01702   {
01703     /* No previous key */
01704     s_temp->ref_length=ref_length=0;
01705     length=key_length+1;
01706   }
01707   if ((s_temp->next_key_pos=next_key))          /* If another key after */
01708   {
01709     /* pack key against next key */
01710     uint32_t next_length,next_length_pack;
01711     get_key_pack_length(next_length,next_length_pack,next_key);
01712 
01713     /* If first key and next key is packed (only on delete) */
01714     if (!prev_key && org_key && next_length)
01715     {
01716       unsigned char *end;
01717       for (key= s_temp->key, end=key+next_length ;
01718            *key == *org_key && key < end;
01719            key++,org_key++) ;
01720       ref_length= (uint) (key - s_temp->key);
01721     }
01722 
01723     if (next_length > ref_length)
01724     {
01725       /* We put a key with different case between two keys with the same prefix
01726          Extend next key to have same prefix as
01727          this key */
01728       s_temp->n_ref_length= ref_length;
01729       s_temp->prev_length=  next_length-ref_length;
01730       s_temp->prev_key+=    ref_length;
01731       return (int) (length+ s_temp->prev_length - next_length_pack +
01732                     get_pack_length(ref_length));
01733     }
01734     /* Check how many characters are identical to next key */
01735     key= s_temp->key+next_length;
01736     while (*key++ == *next_key++) ;
01737     if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
01738     {
01739       s_temp->next_key_pos=0;
01740       return length;                            /* can't pack next key */
01741     }
01742     s_temp->prev_length=0;
01743     s_temp->n_ref_length=ref_length;
01744     return (int) (length-(ref_length - next_length) - next_length_pack +
01745                   get_pack_length(ref_length));
01746   }
01747   return (int) length;
01748 }
01749 
01750 
01751 /*
01752 ** store a key packed with _mi_calc_xxx_key_length in page-buffert
01753 */
01754 
01755 /* store key without compression */
01756 
01757 void _mi_store_static_key(MI_KEYDEF *keyinfo,
01758                           register unsigned char *key_pos,
01759                           register MI_KEY_PARAM *s_temp)
01760 {
01761   (void)keyinfo;
01762   memcpy(key_pos, s_temp->key, s_temp->totlength);
01763 }
01764 
01765 
01766 /* store variable length key with prefix compression */
01767 
01768 #define store_pack_length(test,pos,length) { \
01769   if (test) { *((pos)++) = (unsigned char) (length); } else \
01770   { *((pos)++) = (unsigned char) ((length) >> 8); *((pos)++) = (unsigned char) (length);  } }
01771 
01772 
01773 void _mi_store_var_pack_key(MI_KEYDEF *keyinfo,
01774                             register unsigned char *key_pos,
01775                             register MI_KEY_PARAM *s_temp)
01776 {
01777   (void)keyinfo;
01778   uint32_t length;
01779   unsigned char *start;
01780 
01781   start=key_pos;
01782 
01783   if (s_temp->ref_length)
01784   {
01785     /* Packed against previous key */
01786     store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
01787     /* If not same key after */
01788     if (s_temp->ref_length != s_temp->pack_marker)
01789       store_key_length_inc(key_pos,s_temp->key_length);
01790   }
01791   else
01792   {
01793     /* Not packed against previous key */
01794     store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
01795   }
01796   assert(key_pos >= start);
01797   length= s_temp->totlength - (key_pos - start);
01798   memmove(key_pos, s_temp->key, length);
01799 
01800   if (!s_temp->next_key_pos)                    /* No following key */
01801     return;
01802   key_pos+=length;
01803 
01804   if (s_temp->prev_length)
01805   {
01806     /* Extend next key because new key didn't have same prefix as prev key */
01807     if (s_temp->part_of_prev_key)
01808     {
01809       store_pack_length(s_temp->pack_marker == 128,key_pos,
01810                         s_temp->part_of_prev_key);
01811       store_key_length_inc(key_pos,s_temp->n_length);
01812     }
01813     else
01814     {
01815       s_temp->n_length+= s_temp->store_not_null;
01816       store_pack_length(s_temp->pack_marker == 128,key_pos,
01817                         s_temp->n_length);
01818     }
01819     memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
01820   }
01821   else if (s_temp->n_ref_length)
01822   {
01823     store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
01824     if (s_temp->n_ref_length == s_temp->pack_marker)
01825       return;                                   /* Identical key */
01826     store_key_length(key_pos,s_temp->n_length);
01827   }
01828   else
01829   {
01830     s_temp->n_length+= s_temp->store_not_null;
01831     store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
01832   }
01833 }
01834 
01835 
01836 /* variable length key with prefix compression */
01837 
01838 void _mi_store_bin_pack_key(MI_KEYDEF *keyinfo,
01839                             register unsigned char *key_pos,
01840                             register MI_KEY_PARAM *s_temp)
01841 {
01842   (void)keyinfo;
01843   assert(s_temp->totlength >= s_temp->ref_length);
01844   store_key_length_inc(key_pos,s_temp->ref_length);
01845   memcpy(key_pos,s_temp->key+s_temp->ref_length,
01846          s_temp->totlength - s_temp->ref_length);
01847 
01848   if (s_temp->next_key_pos)
01849   {
01850     key_pos+=(uint) (s_temp->totlength-s_temp->ref_length);
01851     store_key_length_inc(key_pos,s_temp->n_ref_length);
01852     if (s_temp->prev_length)                    /* If we must extend key */
01853     {
01854       memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
01855     }
01856   }
01857 }