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 / range.c < prev    next >
C/C++ Source or Header  |  2000-08-31  |  6KB  |  192 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. /*
  18.   Gives a approximated number of how many records there is between two keys.
  19.   Used when optimizing querries.
  20.  */
  21.  
  22. #include "isamdef.h"
  23.  
  24. static ulong _nisam_record_pos(N_INFO *info,const byte *key,uint key_len,
  25.                 enum ha_rkey_function search_flag);
  26. static double _nisam_search_pos(N_INFO *info,N_KEYDEF *keyinfo,uchar *key,
  27.                  uint key_len,uint nextflag,ulong pos);
  28. static uint _nisam_keynr(N_INFO *info,N_KEYDEF *keyinfo,uchar *page,
  29.               uchar *keypos,uint *ret_max_key);
  30.  
  31.  
  32.     /* If start_key = 0 assume read from start */
  33.     /* If end_key = 0 assume read to end */
  34.     /* Returns NI_POS_ERROR on error */
  35.  
  36. ulong nisam_records_in_range(N_INFO *info, int inx, const byte *start_key,
  37.               uint start_key_len,
  38.               enum ha_rkey_function start_search_flag,
  39.               const byte *end_key, uint end_key_len,
  40.               enum ha_rkey_function end_search_flag)
  41. {
  42.   ulong start_pos,end_pos;
  43.   DBUG_ENTER("nisam_records_in_range");
  44.  
  45.   if ((inx = _nisam_check_index(info,inx)) < 0)
  46.     DBUG_RETURN(NI_POS_ERROR);
  47.  
  48. #ifndef NO_LOCKING
  49.   if (_nisam_readinfo(info,F_RDLCK,1))
  50.     DBUG_RETURN(NI_POS_ERROR);
  51. #endif
  52.   info->update&= (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED);
  53.   start_pos= (start_key ?
  54.           _nisam_record_pos(info,start_key,start_key_len,start_search_flag) :
  55.           0L);
  56.   end_pos=   (end_key ?
  57.           _nisam_record_pos(info,end_key,end_key_len,end_search_flag) :
  58.           info->s->state.records+1L);
  59.   VOID(_nisam_writeinfo(info,0));
  60.   if (start_pos == NI_POS_ERROR || end_pos == NI_POS_ERROR)
  61.     DBUG_RETURN(NI_POS_ERROR);
  62.   DBUG_PRINT("info",("records: %ld",end_pos-start_pos));
  63.   DBUG_RETURN(end_pos < start_pos ? 0L :
  64.           (end_pos == start_pos ? 1L : end_pos-start_pos));
  65. }
  66.  
  67.  
  68.     /* Find relative position (in records) for key in index-tree */
  69.  
  70. static ulong _nisam_record_pos(N_INFO *info, const byte *key, uint key_len,
  71.                 enum ha_rkey_function search_flag)
  72. {
  73.   uint inx=(uint) info->lastinx;
  74.   N_KEYDEF *keyinfo=info->s->keyinfo+inx;
  75.   uchar *key_buff;
  76.   double pos;
  77.  
  78.   DBUG_ENTER("_nisam_record_pos");
  79.   DBUG_PRINT("enter",("search_flag: %d",search_flag));
  80.  
  81.   if (key_len >= (keyinfo->base.keylength-info->s->rec_reflength)
  82.       && !(keyinfo->base.flag & HA_SPACE_PACK_USED))
  83.     key_len=USE_HOLE_KEY;
  84.   key_buff=info->lastkey+info->s->base.max_key_length;
  85.   key_len=_nisam_pack_key(info,inx,key_buff,(uchar*) key,key_len);
  86.   DBUG_EXECUTE("key",_nisam_print_key(DBUG_FILE,keyinfo->seg,
  87.                     (uchar*) key_buff););
  88.   pos=_nisam_search_pos(info,keyinfo,key_buff,key_len,
  89.              nisam_read_vec[search_flag] | SEARCH_SAVE_BUFF,
  90.              info->s->state.key_root[inx]);
  91.   if (pos >= 0.0)
  92.   {
  93.     DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->s->state.records)));
  94.     DBUG_RETURN((ulong) (pos*info->s->state.records+0.5));
  95.   }
  96.   DBUG_RETURN(NI_POS_ERROR);
  97. }
  98.  
  99.  
  100.     /* This is a modified version of _nisam_search */
  101.     /* Returns offset for key in indextable (decimal 0.0 <= x <= 1.0) */
  102.  
  103. static double _nisam_search_pos(register N_INFO *info, register N_KEYDEF *keyinfo,
  104.                  uchar *key, uint key_len, uint nextflag,
  105.                  register ulong pos)
  106. {
  107.   int flag;
  108.   uint nod_flag,keynr,max_keynr;
  109.   uchar *keypos,*buff;
  110.   double offset;
  111.   DBUG_ENTER("_nisam_search_pos");
  112.  
  113.   if (pos == NI_POS_ERROR)
  114.     DBUG_RETURN(0.5);
  115.  
  116.   if (!(buff=_nisam_fetch_keypage(info,keyinfo,pos,info->buff,1)))
  117.     goto err;
  118.   flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
  119.                   &keypos,info->lastkey);
  120.   nod_flag=test_if_nod(buff);
  121.   keynr=_nisam_keynr(info,keyinfo,buff,keypos,&max_keynr);
  122.  
  123.   if (flag)
  124.   {
  125.     /*
  126.     ** Didn't found match. keypos points at next (bigger) key
  127.     *  Try to find a smaller, better matching key.
  128.     ** Matches keynr + [0-1]
  129.     */
  130.     if ((offset=_nisam_search_pos(info,keyinfo,key,key_len,nextflag,
  131.                    _nisam_kpos(nod_flag,keypos))) < 0)
  132.       DBUG_RETURN(offset);
  133.   }
  134.   else
  135.   {
  136.     /*
  137.     ** Found match. Keypos points at the start of the found key
  138.     ** Matches keynr+1
  139.     */
  140.     offset=1.0;                    /* Matches keynr+1 */
  141.     if (nextflag & SEARCH_FIND && (!(keyinfo->base.flag & HA_NOSAME)
  142.                    || key_len) && nod_flag)
  143.     {
  144.       /*
  145.       ** There may be identical keys in the tree. Try to match on of those.
  146.       ** Matches keynr + [0-1]
  147.       */
  148.       if ((offset=_nisam_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
  149.                  _nisam_kpos(nod_flag,keypos))) < 0)
  150.     DBUG_RETURN(offset);            /* Read error */
  151.     }
  152.   }
  153.   DBUG_PRINT("info",("keynr: %d  offset: %g  max_keynr: %d  nod: %d  flag: %d",
  154.              keynr,offset,max_keynr,nod_flag,flag));
  155.   DBUG_RETURN((keynr+offset)/(max_keynr+1));
  156. err:
  157.   DBUG_PRINT("exit",("Error: %d",my_errno));
  158.   DBUG_RETURN (-1.0);
  159. }
  160.  
  161.  
  162.     /* Get keynummer of current key and max number of keys in nod */
  163.  
  164. static uint _nisam_keynr(N_INFO *info, register N_KEYDEF *keyinfo, uchar *page, uchar *keypos, uint *ret_max_key)
  165. {
  166.   uint nod_flag,keynr,max_key;
  167.   uchar t_buff[N_MAX_KEY_BUFF],*end;
  168.  
  169.   end= page+getint(page);
  170.   nod_flag=test_if_nod(page);
  171.   page+=2+nod_flag;
  172.  
  173.   if (!(keyinfo->base.flag &
  174.     (HA_PACK_KEY | HA_SPACE_PACK | HA_SPACE_PACK_USED)))
  175.   {
  176.     *ret_max_key= (uint) (end-page)/(keyinfo->base.keylength+nod_flag);
  177.     return (uint) (keypos-page)/(keyinfo->base.keylength+nod_flag);
  178.   }
  179.  
  180.   max_key=keynr=0;
  181.   while (page < end)
  182.   {
  183.     t_buff[0]=0;            /* Don't move packed key */
  184.     VOID((*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff));
  185.     max_key++;
  186.     if (page == keypos)
  187.       keynr=max_key;
  188.   }
  189.   *ret_max_key=max_key;
  190.   return(keynr);
  191. }
  192.