00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
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
00030
00031 int _mi_check_index(MI_INFO *info, int inx)
00032 {
00033 if (inx == -1)
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)
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 }
00051
00052
00053
00054
00055
00056
00057
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;
00072 info->lastpos= HA_OFFSET_ERROR;
00073 if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
00074 return(-1);
00075 return(1);
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);
00100 }
00101 else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
00102 return(1);
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;
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;
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
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);
00157
00158 return(0);
00159
00160 err:
00161 info->lastpos= HA_OFFSET_ERROR;
00162 info->page_changed=1;
00163 return (-1);
00164 }
00165
00166
00167
00168
00169
00170
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++;
00201 *ret_pos=page+(uint) start*totlength;
00202 *last_key= end == save_end;
00203 return(flag);
00204 }
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
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;
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);
00263 *last_key= page == end;
00264 return(flag);
00265 }
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
00274
00275
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;
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
00300 cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315 matched=0;
00316 len=0;
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
00336 prefix_len=len;
00337 }
00338 else
00339 {
00340
00341 prefix_len=suffix_len;
00342 get_key_length(suffix_len,vseg);
00343 }
00344 }
00345 else
00346 {
00347
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
00399 uint32_t left;
00400 unsigned char *k=kseg+prefix_len;
00401
00402
00403
00404
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)
00425 break;
00426 if (my_flag==0)
00427 {
00428
00429
00430
00431
00432
00433
00434
00435
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
00446 unsigned char *k_end= k+ (cmplen - len);
00447 for ( ; k < k_end && *k == ' '; k++) ;
00448 if (k == k_end)
00449 goto cmp_rest;
00450 if (*k < (unsigned char) ' ')
00451 {
00452 my_flag= 1;
00453 break;
00454 }
00455 my_flag= -1;
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
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;
00473 break;
00474 }
00475 my_flag= -1;
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
00491
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
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 }
00528
00529
00530
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:
00560 default:
00561 return(HA_OFFSET_ERROR);
00562 }
00563 }
00564
00565
00566
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
00579 case 6: *buff++=0;
00580
00581 case 5: *buff++=0;
00582
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();
00589 }
00590 }
00591
00592
00593
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;
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
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;
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;
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;
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;
00650 break;
00651 #else
00652 case 8:
00653 case 7:
00654 case 6:
00655 case 5:
00656 ptr+= (s->rec_reflength-4);
00657
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();
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
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
00700 case 7: *buff++=0;
00701
00702 case 6: *buff++=0;
00703
00704 case 5: *buff++=0;
00705
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();
00711 }
00712 }
00713
00714
00715
00716
00717
00718
00719
00720
00721
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 }
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739
00740
00741
00742
00743
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
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;
00776 }
00777 if (length == 0)
00778 {
00779 if (keyseg->flag & HA_NULL_PART)
00780 *key++=1;
00781 get_key_length(length,key);
00782 key+= length;
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++;
00794 start++;
00795 }
00796
00797 get_key_length(rest_length,page);
00798 tot_length=rest_length+length;
00799
00800
00801 if (tot_length >= 255 && *start != 255)
00802 {
00803
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--)
00830 {
00831 *key++=0;
00832 continue;
00833 }
00834 *key++=1;
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;
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 }
00871
00872
00873
00874
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
00889
00890
00891
00892
00893
00894
00895
00896
00897
00898
00899
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);
00909 }
00910
00911 from= key;
00912 from_end= key + length;
00913 }
00914 else
00915 {
00916
00917 from= page;
00918 from_end= page_end;
00919 }
00920
00921
00922
00923
00924
00925
00926
00927
00928 for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
00929 {
00930 if (keyseg->flag & HA_NULL_PART)
00931 {
00932
00933 if (from == from_end) { from=page; from_end=page_end; }
00934 if (!(*key++ = *from++))
00935 continue;
00936 }
00937 if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
00938 {
00939
00940 if (from == from_end) { from=page; from_end=page_end; }
00941
00942 if ((length= (*key++ = *from++)) == 255)
00943 {
00944
00945 if (from == from_end) { from=page; from_end=page_end; }
00946 length= (uint) ((*key++ = *from++)) << 8;
00947
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;
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
00967
00968
00969
00970 length=keyseg->length+nod_flag;
00971 if ((tmp=(uint) (from_end-from)) <= length)
00972 {
00973
00974 memcpy(key+tmp,page,length-tmp);
00975 *page_pos= page+length-tmp;
00976 }
00977 else
00978 {
00979
00980
00981
00982
00983
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);
00990 }
00991
00992 memcpy(key, from, length);
00993 *page_pos= from+length;
00994 }
00995 return((uint) (key-start_key)+keyseg->length);
00996 }
00997
00998
00999
01000
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;
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 }
01030
01031
01032
01033
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;
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 }
01065
01066
01067
01068
01069
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 }
01103
01104
01105
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 }
01132
01133
01134
01135
01136
01137
01138
01139
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
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
01176
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
01186
01187
01188
01189
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
01208 nod_flag=mi_test_if_nod(info->buff);
01209
01210 if (nextflag & SEARCH_BIGGER)
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
01225 {
01226 uint32_t length;
01227
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
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 }
01249
01250
01251
01252
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);
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 }
01291
01292
01293
01294
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;
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 }
01333
01334
01335
01336
01337
01338
01339
01340
01341
01342
01343
01344
01345
01346
01347
01348
01349
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
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
01383
01384
01385
01386
01387
01388
01389
01390
01391
01392
01393
01394
01395
01396
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
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
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;
01443 return (s_temp->totlength);
01444 }
01445 s_temp->store_not_null=1;
01446 key_length--;
01447 if (prev_key && !*prev_key++)
01448 org_key=prev_key=0;
01449 else if (org_key)
01450 org_key++;
01451 }
01452 else
01453 s_temp->store_not_null=0;
01454 s_temp->prev_key=org_key;
01455
01456
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
01463 if (prev_key)
01464 {
01465 get_key_length(org_key_length,prev_key);
01466 s_temp->prev_key=prev_key;
01467
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)
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
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 {
01500 s_temp->n_length= *next_key;
01501 next_key=0;
01502 }
01503 }
01504 else
01505 {
01506 if (start != key)
01507 {
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;
01515 }
01516 else
01517 {
01518 s_temp->key_length+=s_temp->store_not_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
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;
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)
01542 {
01543 uint32_t next_length_pack, new_ref_length=s_temp->ref_length;
01544
01545 if (packed)
01546 {
01547
01548 if (!prev_key && org_key)
01549 {
01550 get_key_length(org_key_length,org_key);
01551 key=start;
01552 if (sort_order)
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
01574
01575
01576 if (new_ref_length)
01577 {
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 {
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
01599 get_key_pack_length(n_length,next_length_pack,next_key);
01600
01601
01602 if (!new_ref_length)
01603 {
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
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
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)
01632 key_end=key+n_length;
01633 if (sort_order)
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 {
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;
01656 }
01657 if (n_length == 0 && ref_length == new_key_length)
01658 {
01659 s_temp->n_ref_length=pack_marker;
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
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;
01685 #endif
01686 s_temp->key=key;
01687 s_temp->prev_key=org_key;
01688 if (prev_key)
01689 {
01690
01691
01692
01693
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
01704 s_temp->ref_length=ref_length=0;
01705 length=key_length+1;
01706 }
01707 if ((s_temp->next_key_pos=next_key))
01708 {
01709
01710 uint32_t next_length,next_length_pack;
01711 get_key_pack_length(next_length,next_length_pack,next_key);
01712
01713
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
01726
01727
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
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;
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
01753
01754
01755
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
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
01786 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
01787
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
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)
01801 return;
01802 key_pos+=length;
01803
01804 if (s_temp->prev_length)
01805 {
01806
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;
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
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)
01853 {
01854 memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
01855 }
01856 }
01857 }