home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / isam / _search.c < prev    next >
C/C++ Source or Header  |  2000-08-31  |  25KB  |  890 lines
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.    
  3.    This program is free software; you can redistribute it and/or modify
  4.    it under the terms of the GNU General Public License as published by
  5.    the Free Software Foundation; either version 2 of the License, or
  6.    (at your option) any later version.
  7.    
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.    GNU General Public License for more details.
  12.    
  13.    You should have received a copy of the GNU General Public License
  14.    along with this program; if not, write to the Free Software
  15.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  16.  
  17. /* S|ker efter positionen f|r en nyckel samt d{rmedh|rande funktioner */
  18.  
  19. #include "isamdef.h"
  20. #include "m_ctype.h"
  21.  
  22. #define CMP(a,b) (a<b ? -1 : a == b ? 0 : 1)
  23.  
  24.     /* Check index */
  25.  
  26. int _nisam_check_index(N_INFO *info, int inx)
  27. {
  28.   if (inx == -1)            /* Use last index */
  29.     inx=info->lastinx;
  30.   if (inx >= (int) info->s->state.keys || inx < 0)
  31.   {
  32.     my_errno=HA_ERR_WRONG_INDEX;
  33.     return -1;
  34.   }
  35.   if (info->lastinx != inx)        /* Index changed */
  36.   {
  37.     info->lastinx = inx;
  38.     info->lastpos = NI_POS_ERROR;
  39.     info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
  40.            HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
  41.   }
  42.   if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
  43.     return(-1);
  44.   return(inx);
  45. } /* ni_check_index */
  46.  
  47.  
  48.     /* S|ker reda p} positionen f|r ett record p} basen av en nyckel */
  49.     /* Positionen l{ggs i info->lastpos */
  50.     /* Returns -1 if not found and 1 if search at upper levels */
  51.  
  52. int _nisam_search(register N_INFO *info, register N_KEYDEF *keyinfo, uchar *key, uint key_len, uint nextflag, register ulong pos)
  53. {
  54.   int error,flag;
  55.   uint nod_flag;
  56.   uchar *keypos,*maxpos;
  57.   uchar lastkey[N_MAX_KEY_BUFF],*buff;
  58.   DBUG_ENTER("_nisam_search");
  59.   DBUG_PRINT("enter",("pos: %ld  nextflag: %d  lastpos: %ld",
  60.               pos,nextflag,info->lastpos));
  61.  
  62.   if (pos == NI_POS_ERROR)
  63.   {
  64.     my_errno=HA_ERR_KEY_NOT_FOUND;            /* Didn't find key */
  65.     info->lastpos= NI_POS_ERROR;
  66.     if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
  67.       DBUG_RETURN(-1);                /* Not found ; return error */
  68.     DBUG_RETURN(1);                /* Search at upper levels */
  69.   }
  70.  
  71.   if (!(buff=_nisam_fetch_keypage(info,keyinfo,pos,info->buff,
  72.                    test(!(nextflag & SEARCH_SAVE_BUFF)))))
  73.     goto err;
  74.   DBUG_DUMP("page",(byte*) buff,getint(buff));
  75.  
  76.   flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
  77.                   &keypos,lastkey);
  78.   nod_flag=test_if_nod(buff);
  79.   maxpos=buff+getint(buff)-1;
  80.  
  81.   if (flag)
  82.   {
  83.     if ((error=_nisam_search(info,keyinfo,key,key_len,nextflag,
  84.               _nisam_kpos(nod_flag,keypos))) <= 0)
  85.       DBUG_RETURN(error);
  86.  
  87.     if (flag >0)
  88.     {
  89.       if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) &&
  90.       keypos == buff+2+nod_flag)
  91.     DBUG_RETURN(1);                    /* Bigger than key */
  92.     }
  93.     else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
  94.       DBUG_RETURN(1);                    /* Smaller than key */
  95.   }
  96.   else
  97.   {
  98.     if (nextflag & SEARCH_FIND && (!(keyinfo->base.flag & HA_NOSAME)
  99.                    || key_len) && nod_flag)
  100.     {
  101.       if ((error=_nisam_search(info,keyinfo,key,key_len,SEARCH_FIND,
  102.                 _nisam_kpos(nod_flag,keypos))) >= 0 ||
  103.       my_errno != HA_ERR_KEY_NOT_FOUND)
  104.     DBUG_RETURN(error);
  105.       info->int_pos= NI_POS_ERROR;        /* Buffer not in memory */
  106.     }
  107.   }
  108.   if (pos != info->int_pos)
  109.   {
  110.     uchar *old_buff=buff;
  111.     if (!(buff=_nisam_fetch_keypage(info,keyinfo,pos,info->buff,
  112.                  test(!(nextflag & SEARCH_SAVE_BUFF)))))
  113.       goto err;
  114.     keypos=buff+(keypos-old_buff);
  115.     maxpos=buff+(maxpos-old_buff);
  116.   }
  117.  
  118.   if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
  119.   {
  120.     keypos=_nisam_get_last_key(info,keyinfo,buff,lastkey,keypos);
  121.     if ((nextflag & SEARCH_LAST) &&
  122.     _nisam_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND))
  123.     {
  124.       my_errno=HA_ERR_KEY_NOT_FOUND;            /* Didn't find key */
  125.       goto err;
  126.     }
  127.   }
  128.  
  129.   VOID((*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey));
  130.   VOID(_nisam_move_key(keyinfo,info->lastkey,lastkey));
  131.   info->lastpos=_nisam_dpos(info,nod_flag,keypos);
  132.   info->int_keypos=info->buff+ (keypos-buff);
  133.   info->int_maxpos=info->buff+ (maxpos-buff);
  134.   info->page_changed=0;
  135.   info->buff_used= (info->buff != buff);
  136.   info->last_search_keypage=info->int_pos;
  137.  
  138.   DBUG_PRINT("exit",("found key at %ld",info->lastpos));
  139.   DBUG_RETURN(0);
  140. err:
  141.   DBUG_PRINT("exit",("Error: %d",my_errno));
  142.   info->lastpos= NI_POS_ERROR;
  143.   DBUG_RETURN (-1);
  144. } /* _nisam_search */
  145.  
  146.  
  147.     /* Search after key in page-block */
  148.     /* If packed key puts smaller or identical key in buff */
  149.     /* ret_pos point to where find or bigger key starts */
  150.     /* ARGSUSED */
  151.  
  152. int _nisam_bin_search(N_INFO *info, register N_KEYDEF *keyinfo, uchar *page,
  153.            uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
  154.            uchar *buff __attribute__((unused)))
  155. {
  156.   reg4 int start,mid,end;
  157.   int flag;
  158.   uint totlength,nod_flag;
  159.   DBUG_ENTER("_nisam_bin_search");
  160.  
  161.   LINT_INIT(flag);
  162.   totlength=keyinfo->base.keylength+(nod_flag=test_if_nod(page));
  163.   start=0; mid=1;
  164.   end= (int) ((getint(page)-2-nod_flag)/totlength-1);
  165.   DBUG_PRINT("test",("getint: %d  end: %d",getint(page),end));
  166.   page+=2+nod_flag;
  167.  
  168.   while (start != end)
  169.   {
  170.     mid= (start+end)/2;
  171.     if ((flag=_nisam_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
  172.               comp_flag))
  173.     >= 0)
  174.       end=mid;
  175.     else
  176.       start=mid+1;
  177.   }
  178.   if (mid != start)
  179.     flag=_nisam_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
  180.              comp_flag);
  181.   if (flag < 0)
  182.     start++;            /* point at next, bigger key */
  183.   *ret_pos=page+(uint) start*totlength;
  184.   DBUG_PRINT("exit",("flag: %d  keypos: %d",flag,start));
  185.   DBUG_RETURN(flag);
  186. } /* _nisam_bin_search */
  187.  
  188.  
  189.     /* Used instead of _nisam_bin_search() when key is packed */
  190.     /* Puts smaller or identical key in buff */
  191.     /* Key is searched sequentially */
  192.  
  193. int _nisam_seq_search(N_INFO *info, register N_KEYDEF *keyinfo, uchar *page, uchar *key, uint key_len, uint comp_flag, uchar **ret_pos, uchar *buff)
  194. {
  195.   int flag;
  196.   uint nod_flag,length;
  197.   uchar t_buff[N_MAX_KEY_BUFF],*end;
  198.   DBUG_ENTER("_nisam_seq_search");
  199.  
  200.   LINT_INIT(flag); LINT_INIT(length);
  201.   end= page+getint(page);
  202.   nod_flag=test_if_nod(page);
  203.   page+=2+nod_flag;
  204.   *ret_pos=page;
  205.   while (page < end)
  206.   {
  207.     length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
  208.     if ((flag=_nisam_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag)) >= 0)
  209.       break;
  210. #ifdef EXTRA_DEBUG
  211.     DBUG_PRINT("loop",("page: %lx  key: '%s'  flag: %d",page,t_buff,flag));
  212. #endif
  213.     memcpy(buff,t_buff,length);
  214.     *ret_pos=page;
  215.   }
  216.   if (flag == 0)
  217.     memcpy(buff,t_buff,length);            /* Result is first key */
  218.   DBUG_PRINT("exit",("flag: %d  ret_pos: %lx",flag,*ret_pos));
  219.   DBUG_RETURN(flag);
  220. } /* _nisam_seq_search */
  221.  
  222.  
  223.     /* Get pos to a key_block */
  224.  
  225. ulong _nisam_kpos(uint nod_flag, uchar *after_key)
  226. {
  227.   after_key-=nod_flag;
  228.   switch (nod_flag) {
  229.   case 3:
  230.     return uint3korr(after_key)*512L;
  231.   case 2:
  232.     return uint2korr(after_key)*512L;
  233.   case 1:
  234.     return (uint) (*after_key)*512L;
  235.   case 0:                    /* At leaf page */
  236.   default:                    /* Impossible */
  237.     return(NI_POS_ERROR);
  238.   }
  239. } /* _kpos */
  240.  
  241.  
  242.     /* Save pos to a key_block */
  243.  
  244. void _nisam_kpointer(register N_INFO *info, register uchar *buff, ulong pos)
  245. {
  246.   pos/=512L;
  247.   switch (info->s->base.key_reflength) {
  248.   case 3: int3store(buff,pos); break;
  249.   case 2: int2store(buff,(uint) pos); break;
  250.   case 1: buff[0]= (uchar) pos; break;
  251.   default: abort();                /* impossible */
  252.   }
  253. } /* _nisam_kpointer */
  254.  
  255.  
  256.     /* Calc pos to a data-record */
  257.  
  258. ulong _nisam_dpos(N_INFO *info, uint nod_flag, uchar *after_key)
  259. {
  260.   ulong pos;
  261.   after_key-=(nod_flag + info->s->rec_reflength);
  262.   switch (info->s->rec_reflength) {
  263.   case 4:
  264.     pos= (ulong) uint4korr(after_key);
  265.     break;
  266.   case 3:
  267.     pos= (ulong) uint3korr(after_key);
  268.     break;
  269.   case 2:
  270.     pos= (ulong) uint2korr(after_key);
  271.     break;
  272.   default:
  273.     pos=0L;            /* Shut compiler up */
  274.   }
  275.   return (info->s->base.options &
  276.       (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
  277.         pos*info->s->base.reclength;
  278. }
  279.  
  280.     /* save pos to record */
  281.  
  282. void _nisam_dpointer(N_INFO *info, uchar *buff, ulong pos)
  283. {
  284.   if (!(info->s->base.options &
  285.     (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)))
  286.     pos/=info->s->base.reclength;
  287.  
  288.   switch (info->s->rec_reflength) {
  289.   case 4: int4store(buff,pos); break;
  290.   case 3: int3store(buff,pos); break;
  291.   case 2: int2store(buff,(uint) pos); break;
  292.   default: abort();            /* Impossible */
  293.   }
  294. } /* _nisam_dpointer */
  295.  
  296.  
  297.     /*
  298.     ** Compare two keys with is bigger
  299.     ** Returns <0, 0, >0 acording to with is bigger
  300.     ** Key_length specifies length of key to use.  Number-keys can't
  301.     ** be splitted
  302.     ** If flag <> SEARCH_FIND compare also position
  303.     */
  304. int _nisam_key_cmp(register N_KEYSEG *keyseg, register uchar *a, register uchar *b, uint key_length, uint nextflag)
  305. {
  306.   reg4 int flag,length_diff;
  307.   int16 s_1,s_2;
  308.   int32    l_1,l_2;
  309.   uint32 u_1,u_2;
  310.   float f_1,f_2;
  311.   double d_1,d_2;
  312.   reg5 uchar *end;
  313.  
  314.   if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST))
  315.       || key_length == 0)
  316.     key_length=N_MAX_KEY_BUFF*2;
  317.  
  318.   for ( ; (int) key_length >0 ; key_length-= (keyseg++)->base.length)
  319.   {
  320.     end= a+ min(keyseg->base.length,key_length);
  321.     switch ((enum ha_base_keytype) keyseg->base.type) {
  322.     case HA_KEYTYPE_TEXT:            /* Ascii; Key is converted */
  323.     case HA_KEYTYPE_BINARY:
  324.       if (keyseg->base.flag & HA_SPACE_PACK)
  325.       {
  326.     uchar *as, *bs;
  327.     int length,b_length;
  328.  
  329.     as=a++; bs=b++;
  330.     length= (length_diff= ((int) *as - (b_length= (int) *bs))) < 0 ?
  331.       (int) *as : b_length;
  332.     end= a+ min(key_length,(uint) length);
  333.  
  334. #ifdef USE_STRCOLL
  335.         if (use_strcoll(default_charset_info)) {
  336.           if (((enum ha_base_keytype) keyseg->base.type) == HA_KEYTYPE_BINARY)
  337.           {
  338.             while (a < end)
  339.               if ((flag= (int) *a++ - (int) *b++))
  340.                 return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  341.           }
  342.           else
  343.           {
  344.             if ((flag = my_strnncoll(default_charset_info,
  345.                      a, (int) (end-a), b, b_length)))
  346.               return (keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag;
  347.             b+= (uint) (end-a);
  348.             a=end;
  349.           }
  350.         }
  351.         else
  352. #endif
  353.     {
  354.           while (a < end)
  355.             if ((flag= (int) *a++ - (int) *b++))
  356.               return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  357.     }
  358.     if (key_length < (uint) keyseg->base.length)
  359.     {                        /* key_part */
  360.       if (length_diff)
  361.       {
  362.         if (length_diff < 0 || (uint) *as <= key_length)
  363.           return ((keyseg->base.flag & HA_REVERSE_SORT) ?
  364.               -length_diff : length_diff);
  365.         for (length= (int) key_length-b_length; length-- > 0 ;)
  366.         {
  367.           if (*a++ != ' ')
  368.         return ((keyseg->base.flag & HA_REVERSE_SORT) ? -1 : 1);
  369.         }
  370.       }
  371.       if (nextflag & SEARCH_NO_FIND)    /* Find record after key */
  372.         return (nextflag & SEARCH_BIGGER) ? -1 : 1;
  373.       return 0;
  374.     }
  375.     else
  376.     {
  377.       if (length_diff)
  378.         return ((keyseg->base.flag & HA_REVERSE_SORT) ?
  379.             -length_diff : length_diff);
  380.     }
  381.     a=as+ (uint) *as+1 ; b= bs+ b_length+1;        /* to next key */
  382.       }
  383.       else
  384.       {
  385. #ifdef USE_STRCOLL
  386.         if (use_strcoll(default_charset_info)) {
  387.           if (((enum ha_base_keytype) keyseg->base.type) == HA_KEYTYPE_BINARY)
  388.           {
  389.             while (a < end)
  390.               if ((flag= (int) *a++ - (int) *b++))
  391.                 return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  392.           }
  393.           else
  394.           {
  395.             if ((flag = my_strnncoll(default_charset_info,
  396.                      a, (int) (end-a), b, (int) (end-a))))
  397.               return (keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag;
  398.             b+= (uint) (end-a);
  399.             a=end;
  400.           }
  401.         }
  402.         else
  403. #endif
  404.     {
  405.           while (a < end)
  406.             if ((flag= (int) *a++ - (int) *b++))
  407.               return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  408.     }
  409.       }
  410.       break;
  411.     case HA_KEYTYPE_INT8:
  412.     {
  413.       int i_1= (int) *((signed char*) a);
  414.       int i_2= (int) *((signed char*) b);
  415.       if ((flag = CMP(i_1,i_2)))
  416.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  417.       a= end;
  418.       b++;
  419.       break;
  420.     }
  421.     case HA_KEYTYPE_SHORT_INT:
  422.       shortget(s_1,a);
  423.       shortget(s_2,b);
  424.       if ((flag = CMP(s_1,s_2)))
  425.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  426.       a=  end;
  427.       b+= 2; /* sizeof(short int); */
  428.       break;
  429.     case HA_KEYTYPE_USHORT_INT:
  430.       {
  431.     uint16 us_1,us_2;
  432.     ushortget(us_1,a);
  433.     ushortget(us_2,b);
  434.     if ((flag = CMP(us_1,us_2)))
  435.       return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  436.     a=  end;
  437.     b+=2; /* sizeof(short int); */
  438.     break;
  439.       }
  440.     case HA_KEYTYPE_LONG_INT:
  441.       longget(l_1,a);
  442.       longget(l_2,b);
  443.       if ((flag = CMP(l_1,l_2)))
  444.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  445.       a=  end;
  446.       b+= 4; /* sizeof(long int); */
  447.       break;
  448.     case HA_KEYTYPE_ULONG_INT:
  449.       ulongget(u_1,a);
  450.       ulongget(u_2,b);
  451.       if ((flag = CMP(u_1,u_2)))
  452.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  453.       a=  end;
  454.       b+= 4; /* sizeof(long int); */
  455.       break;
  456.     case HA_KEYTYPE_INT24:
  457.       l_1=sint3korr(a);
  458.       l_2=sint3korr(b);
  459.       if ((flag = CMP(l_1,l_2)))
  460.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  461.       a=  end;
  462.       b+= 3;
  463.       break;
  464.     case HA_KEYTYPE_UINT24:
  465.       l_1=(long) uint3korr(a);
  466.       l_2=(long) uint3korr(b);
  467.       if ((flag = CMP(l_1,l_2)))
  468.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  469.       a=  end;
  470.       b+= 3;
  471.       break;
  472.     case HA_KEYTYPE_FLOAT:
  473.       bmove((byte*) &f_1,(byte*) a,(int) sizeof(float));
  474.       bmove((byte*) &f_2,(byte*) b,(int) sizeof(float));
  475.       if ((flag = CMP(f_1,f_2)))
  476.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  477.       a=  end;
  478.       b+= sizeof(float);
  479.       break;
  480.     case HA_KEYTYPE_DOUBLE:
  481.       doubleget(d_1,a);
  482.       doubleget(d_2,b);
  483.       if ((flag = CMP(d_1,d_2)))
  484.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  485.       a=  end;
  486.       b+= sizeof(double);
  487.       break;
  488.     case HA_KEYTYPE_NUM:                /* Numeric key */
  489.     {
  490.       int swap_flag=keyseg->base.flag & HA_REVERSE_SORT;
  491.       if (keyseg->base.flag & HA_SPACE_PACK)
  492.       {
  493.     int alength,blength;
  494.  
  495.     if (swap_flag)
  496.       swap(uchar*,a,b);
  497.     alength= *a++; blength= *b++;
  498.     if ((flag=(int) (keyseg->base.length-key_length)) < 0)
  499.       flag=0;
  500.     if (alength != blength+flag)
  501.     {
  502.       if ((alength > blength+flag && *a != '-') ||
  503.           (alength < blength+flag && *b == '-'))
  504.         return 1;
  505.       else
  506.         return -1;
  507.     }
  508.     if (*a == '-' && *b == '-')
  509.     {
  510.       swap_flag=1;
  511.       swap(uchar*,a,b);
  512.     }
  513.     end=a+alength;
  514.     while (a < end)
  515.       if (*a++ !=  *b++)
  516.       {
  517.         a--; b--;
  518.         if (isdigit((char) *a) && isdigit((char) *b))
  519.           return ((int) *a - (int) *b);
  520.         if (*a == '-' || isdigit((char) *b))
  521.           return (-1);
  522.         if (*b == '-' || *b++ == ' ' || isdigit((char) *a))
  523.           return (1);
  524.         if (*a++ == ' ')
  525.           return (-1);
  526.       }
  527.       }
  528.       else
  529.       {
  530.     for ( ; a < end && *a == ' ' && *b == ' ' ; a++, b++) ;
  531.     if (*a == '-' && *b == '-')
  532.       swap_flag=1;
  533.     if (swap_flag)
  534.     {
  535.       end=b+(int) (end-a);
  536.       swap(uchar*,a,b);
  537.     }
  538.     while (a < end)
  539.       if (*a++ != *b++)
  540.       {
  541.         a--; b--;
  542.         if (isdigit((char) *a) && isdigit((char) *b))
  543.           return ((int) *a - (int) *b);
  544.         if (*a == '-' || isdigit((char) *b))
  545.           return (-1);
  546.         if (*b == '-' || *b++ == ' ' || isdigit((char) *a))
  547.           return (1);
  548.         if (*a++ == ' ')
  549.           return -1;
  550.       }
  551.       }
  552.       if (swap_flag)
  553.     swap(uchar*,a,b);
  554.       break;
  555.     }
  556. #ifdef HAVE_LONG_LONG
  557.     case HA_KEYTYPE_LONGLONG:
  558.     {
  559.       longlong ll_a,ll_b;
  560.       longlongget(ll_a,a);
  561.       longlongget(ll_b,b);
  562.       if ((flag = CMP(ll_a,ll_b)))
  563.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  564.       a=  end;
  565.       b+= sizeof(longlong);
  566.       break;
  567.     }
  568.     case HA_KEYTYPE_ULONGLONG:
  569.     {
  570.       ulonglong ll_a,ll_b;
  571.       longlongget(ll_a,a);
  572.       longlongget(ll_b,b);
  573.       if ((flag = CMP(ll_a,ll_b)))
  574.     return ((keyseg->base.flag & HA_REVERSE_SORT) ? -flag : flag);
  575.       a=  end;
  576.       b+= sizeof(ulonglong);
  577.       break;
  578.     }
  579. #endif
  580.     case HA_KEYTYPE_END:            /* Ready */
  581.     case HA_KEYTYPE_VARTEXT:            /* Impossible */
  582.     case HA_KEYTYPE_VARBINARY:            /* Impossible */
  583.       goto end;
  584.     }
  585.   }
  586. end:
  587.   if (!(nextflag & SEARCH_FIND))
  588.   {
  589.     if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST)) /* Find record after key */
  590.       return (nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
  591.     LINT_INIT(l_1); LINT_INIT(l_2);
  592.     switch (keyseg->base.length) {
  593.     case 4:
  594.       u_1= (ulong) uint4korr(a);
  595.       u_2= (ulong) uint4korr(b);
  596.       break;
  597.     case 3:
  598.       u_1= (ulong) uint3korr(a);
  599.       u_2= (ulong) uint3korr(b);
  600.       break;
  601.     case 2:
  602.       u_1= (ulong) uint2korr(a);
  603.       u_2= (ulong) uint2korr(b);
  604.       break;
  605.     default: abort();                /* Impossible */
  606.     }
  607.     flag = CMP(u_1,u_2);
  608.  
  609.     if (nextflag & SEARCH_SAME)
  610.       return (flag);                /* read same */
  611.     if (nextflag & SEARCH_BIGGER)
  612.       return (flag <= 0 ? -1 : 1);        /* read next */
  613.     return (flag < 0 ? -1 : 1);            /* read previous */
  614.   }
  615.   return 0;
  616. } /* _nisam_key_cmp */
  617.  
  618.  
  619.     /* Get key from key-block */
  620.     /* page points at previous key; its advanced to point at next key */
  621.     /* key should contain previous key */
  622.     /* Returns length of found key + pointers */
  623.     /* nod_flag is a flag if we are on nod */
  624.  
  625. uint _nisam_get_key(register N_KEYDEF *keyinfo, uint nod_flag,
  626.          register uchar **page, register uchar *key)
  627. {
  628.   reg1 N_KEYSEG *keyseg;
  629.   uchar *start,*start_key;
  630.   uint length,c_length;
  631.  
  632.   LINT_INIT(start);
  633.   start_key=key; c_length=0;
  634.   for (keyseg=keyinfo->seg ; keyseg->base.type ;keyseg++)
  635.   {
  636.     if (keyseg->base.flag & (HA_SPACE_PACK | HA_PACK_KEY))
  637.     {
  638.       start=key;
  639.       if (keyseg->base.flag & HA_SPACE_PACK)
  640.     key++;
  641.       if ((length= *(*page)++) & 128)
  642.       {
  643.     key+= (c_length=(length & 127));
  644.     if (c_length == 0)    /* Same key */
  645.     {
  646.       key+= *start;        /* Same diff_key as prev */
  647.       length=0;
  648.     }
  649.     else
  650.     {
  651.       if (keyseg->base.flag & HA_SPACE_PACK)
  652.         length= *(*page)++;
  653.       else
  654.         length=keyseg->base.length-length+128; /* Rest of key */
  655.       /* Prevent core dumps if wrong data formats */
  656.       if (length > keyseg->base.length)
  657.         length=0;
  658.     }
  659.       }
  660.     }
  661.     else
  662.       length=keyseg->base.length;
  663.     memcpy((byte*) key,(byte*) *page,(size_t) length); key+=length;
  664.     if (keyseg->base.flag & HA_SPACE_PACK)
  665.       *start= (uchar) ((key-start)-1);
  666.     *page+=length;
  667.   }
  668.   length=keyseg->base.length+nod_flag;
  669.   bmove((byte*) key,(byte*) *page,length);
  670.   *page+=length;
  671.   return((uint) (key-start_key)+keyseg->base.length);
  672. } /* _nisam_get_key */
  673.  
  674.  
  675.     /* same as _nisam_get_key but used with fixed length keys */
  676.  
  677. uint _nisam_get_static_key(register N_KEYDEF *keyinfo, uint nod_flag, register uchar **page, register uchar *key)
  678. {
  679.   memcpy((byte*) key,(byte*) *page,
  680.      (size_t) (keyinfo->base.keylength+nod_flag));
  681.   *page+=keyinfo->base.keylength+nod_flag;
  682.   return(keyinfo->base.keylength);
  683. } /* _nisam_get_static_key */
  684.  
  685.  
  686.     /* Get last key from key-block, starting from keypos */
  687.     /* Return pointer to where keystarts */
  688.  
  689. uchar *_nisam_get_last_key(N_INFO *info, N_KEYDEF *keyinfo, uchar *keypos, uchar *lastkey, uchar *endpos)
  690. {
  691.   uint nod_flag;
  692.   uchar *lastpos;
  693.  
  694.   nod_flag=test_if_nod(keypos);
  695.   if (! (keyinfo->base.flag & (HA_PACK_KEY | HA_SPACE_PACK_USED)))
  696.   {
  697.     lastpos=endpos-keyinfo->base.keylength-nod_flag;
  698.     if (lastpos > keypos)
  699.       bmove((byte*) lastkey,(byte*) lastpos,keyinfo->base.keylength+nod_flag);
  700.   }
  701.   else
  702.   {
  703.     lastpos=0 ; keypos+=2+nod_flag;
  704.     lastkey[0]=0;
  705.     while (keypos < endpos)
  706.     {
  707.       lastpos=keypos;
  708.       VOID(_nisam_get_key(keyinfo,nod_flag,&keypos,lastkey));
  709.     }
  710.   }
  711.   return lastpos;
  712. } /* _nisam_get_last_key */
  713.  
  714.  
  715.     /* Calculate length of key */
  716.  
  717. uint _nisam_keylength(N_KEYDEF *keyinfo, register uchar *key)
  718. {
  719.   reg1 N_KEYSEG *keyseg;
  720.   uchar *start;
  721.  
  722.   if (! (keyinfo->base.flag & HA_SPACE_PACK_USED))
  723.     return (keyinfo->base.keylength);
  724.  
  725.   start=key;
  726.   for (keyseg=keyinfo->seg ; keyseg->base.type ; keyseg++)
  727.   {
  728.     if (keyseg->base.flag & HA_SPACE_PACK)
  729.       key+= *key+1;
  730.     else
  731.       key+= keyseg->base.length;
  732.   }
  733.   return((uint) (key-start)+keyseg->base.length);
  734. } /* _nisam_keylength */
  735.  
  736.  
  737.     /* Move a key */
  738.  
  739. uchar *_nisam_move_key(N_KEYDEF *keyinfo, uchar *to, uchar *from)
  740. {
  741.   reg1 uint length;
  742.   memcpy((byte*) to, (byte*) from,
  743.      (size_t) (length=_nisam_keylength(keyinfo,from)));
  744.   return to+length;
  745. }
  746.  
  747.     /* Find next/previous record with same key */
  748.     /* This can't be used when database is touched after last read */
  749.  
  750. int _nisam_search_next(register N_INFO *info, register N_KEYDEF *keyinfo,
  751.             uchar *key, uint nextflag, ulong pos)
  752. {
  753.   int error;
  754.   uint nod_flag;
  755.   uchar lastkey[N_MAX_KEY_BUFF];
  756.   DBUG_ENTER("_nisam_search_next");
  757.   DBUG_PRINT("enter",("nextflag: %d  lastpos: %d  int_keypos: %lx",
  758.                nextflag,info->lastpos,info->int_keypos));
  759.   DBUG_EXECUTE("key",_nisam_print_key(DBUG_FILE,keyinfo->seg,key););
  760.  
  761.   if ((nextflag & SEARCH_BIGGER && info->int_keypos >= info->int_maxpos) ||
  762.       info->int_pos == NI_POS_ERROR || info->page_changed)
  763.     DBUG_RETURN(_nisam_search(info,keyinfo,key,0,nextflag | SEARCH_SAVE_BUFF,
  764.                pos));
  765.  
  766.   if (info->buff_used)
  767.   {
  768.     if (!_nisam_fetch_keypage(info,keyinfo,info->last_search_keypage,
  769.                   info->buff,0))
  770.     {
  771.       info->lastpos= NI_POS_ERROR;
  772.       DBUG_RETURN(-1);
  773.     }
  774.     info->buff_used=0;
  775.   }
  776.  
  777.   /* Last used buffer is in info->buff */
  778.  
  779.   nod_flag=test_if_nod(info->buff);
  780.   VOID(_nisam_move_key(keyinfo,lastkey,key));
  781.  
  782.   if (nextflag & SEARCH_BIGGER)                    /* Next key */
  783.   {
  784.     ulong tmp_pos=_nisam_kpos(nod_flag,info->int_keypos);
  785.     if (tmp_pos != NI_POS_ERROR)
  786.     {
  787.       if ((error=_nisam_search(info,keyinfo,key,0,nextflag | SEARCH_SAVE_BUFF,
  788.                 tmp_pos)) <=0)
  789.     DBUG_RETURN(error);
  790.     }
  791.     VOID((*keyinfo->get_key)(keyinfo,nod_flag,&info->int_keypos,lastkey));
  792.   }
  793.   else                            /* Previous key */
  794.   {
  795.     info->int_keypos=_nisam_get_last_key(info,keyinfo,info->buff,lastkey,
  796.                       info->int_keypos);
  797.     if (info->int_keypos == info->buff+2)
  798.       DBUG_RETURN(_nisam_search(info,keyinfo,key,0,nextflag | SEARCH_SAVE_BUFF,
  799.                  pos));
  800.     if ((error=_nisam_search(info,keyinfo,key,0,nextflag | SEARCH_SAVE_BUFF,
  801.               _nisam_kpos(nod_flag,info->int_keypos))) <= 0)
  802.       DBUG_RETURN(error);
  803.   }
  804.  
  805.   info->int_keypos=_nisam_get_last_key(info,keyinfo,info->buff,lastkey,
  806.                     info->int_keypos);
  807.   VOID(_nisam_move_key(keyinfo,info->lastkey,lastkey));
  808.   VOID((*keyinfo->get_key)(keyinfo,nod_flag,&info->int_keypos,info->lastkey));
  809.   info->lastpos=_nisam_dpos(info,nod_flag,info->int_keypos);
  810.   DBUG_PRINT("exit",("found key at %d",info->lastpos));
  811.   DBUG_RETURN(0);
  812. } /* _nisam_search_next */
  813.  
  814.  
  815.     /* S|ker reda p} positionen f|r f|rsta recordet i ett index */
  816.     /* Positionen l{ggs i info->lastpos */
  817.  
  818. int _nisam_search_first(register N_INFO *info, register N_KEYDEF *keyinfo, register ulong pos)
  819. {
  820.   uint nod_flag;
  821.   uchar *page;
  822.   DBUG_ENTER("_nisam_search_first");
  823.  
  824.   if (pos == NI_POS_ERROR)
  825.   {
  826.     my_errno=HA_ERR_KEY_NOT_FOUND;
  827.     info->lastpos= NI_POS_ERROR;
  828.     DBUG_RETURN(-1);
  829.   }
  830.  
  831.   do
  832.   {
  833.     if (!_nisam_fetch_keypage(info,keyinfo,pos,info->buff,0))
  834.     {
  835.       info->lastpos= NI_POS_ERROR;
  836.       DBUG_RETURN(-1);
  837.     }
  838.     nod_flag=test_if_nod(info->buff);
  839.     page=info->buff+2+nod_flag;
  840.   } while ((pos=_nisam_kpos(nod_flag,page)) != NI_POS_ERROR);
  841.  
  842.   VOID((*keyinfo->get_key)(keyinfo,nod_flag,&page,info->lastkey));
  843.   info->int_keypos=page; info->int_maxpos=info->buff+getint(info->buff)-1;
  844.   info->lastpos=_nisam_dpos(info,nod_flag,page);
  845.   info->page_changed=info->buff_used=0;
  846.   info->last_search_keypage=info->int_pos;
  847.  
  848.   DBUG_PRINT("exit",("found key at %d",info->lastpos));
  849.   DBUG_RETURN(0);
  850. } /* _nisam_search_first */
  851.  
  852.  
  853.     /* S|ker reda p} positionen f|r sista recordet i ett index */
  854.     /* Positionen l{ggs i info->lastpos */
  855.  
  856. int _nisam_search_last(register N_INFO *info, register N_KEYDEF *keyinfo, register ulong pos)
  857. {
  858.   uint nod_flag;
  859.   uchar *buff,*page;
  860.   DBUG_ENTER("_nisam_search_last");
  861.  
  862.   if (pos == NI_POS_ERROR)
  863.   {
  864.     my_errno=HA_ERR_KEY_NOT_FOUND;            /* Didn't find key */
  865.     info->lastpos= NI_POS_ERROR;
  866.     DBUG_RETURN(-1);
  867.   }
  868.  
  869.   buff=info->buff;
  870.   do
  871.   {
  872.     if (!_nisam_fetch_keypage(info,keyinfo,pos,buff,0))
  873.     {
  874.       info->lastpos= NI_POS_ERROR;
  875.       DBUG_RETURN(-1);
  876.     }
  877.     page= buff+getint(buff);
  878.     nod_flag=test_if_nod(buff);
  879.   } while ((pos=_nisam_kpos(nod_flag,page)) != NI_POS_ERROR);
  880.  
  881.   VOID(_nisam_get_last_key(info,keyinfo,buff,info->lastkey,page));
  882.   info->lastpos=_nisam_dpos(info,nod_flag,page);
  883.   info->int_keypos=info->int_maxpos=page;
  884.   info->page_changed=info->buff_used=0;
  885.   info->last_search_keypage=info->int_pos;
  886.  
  887.   DBUG_PRINT("exit",("found key at %d",info->lastpos));
  888.   DBUG_RETURN(0);
  889. } /* _nisam_search_last */
  890.