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 / sort.c < prev    next >
C/C++ Source or Header  |  2000-08-31  |  15KB  |  559 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.   Creates a index for a database by reading keys, sorting them and outputing
  19.   them in sorted order through SORT_INFO functions.
  20. */
  21.  
  22. #include "isamdef.h"
  23. #if defined(MSDOS) || defined(__WIN__)
  24. #include <fcntl.h>
  25. #else
  26. #include <stddef.h>
  27. #endif
  28. #include <queues.h>
  29.  
  30.     /* static variabels */
  31.  
  32. #define MERGEBUFF 15
  33. #define MERGEBUFF2 31
  34. #define MIN_SORT_MEMORY (4096-MALLOC_OVERHEAD)
  35. #define MYF_RW    MYF(MY_NABP | MY_WME | MY_WAIT_IF_FULL)
  36.  
  37. typedef struct st_buffpek {        /* Struktur om sorteringsbuffrarna */
  38.   my_off_t file_pos;            /* Position var bufferten finns */
  39.   ulong count;                /* Antal nycklar i bufferten */
  40.   uchar *base,*key;            /* Pekare inom sort_key - indexdel */
  41.   uint mem_count;            /* Antal nycklar kvar i minnet */
  42.   uint max_keys;            /* Max keys in buffert */
  43. } BUFFPEK;
  44.  
  45. extern void print_error _VARARGS((const char *fmt,...));
  46.  
  47.     /* functions defined in this file */
  48.  
  49. static ulong NEAR_F find_all_keys(SORT_PARAM *info,uint keys,
  50.                   uchar * *sort_keys,
  51.                   BUFFPEK *buffpek,int *maxbuffer,
  52.                   FILE **tempfile, my_string tempname);
  53. static int NEAR_F write_keys(SORT_PARAM *info,uchar * *sort_keys,
  54.                  uint count, BUFFPEK *buffpek,FILE **tempfile,
  55.                  my_string tempname);
  56. static int NEAR_F write_index(SORT_PARAM *info,uchar * *sort_keys,
  57.                   uint count);
  58. static int NEAR_F merge_many_buff(SORT_PARAM *info,uint keys,
  59.                   uchar * *sort_keys,
  60.                   BUFFPEK *buffpek,int *maxbuffer,
  61.                   FILE * *t_file, my_string tempname);
  62. static uint NEAR_F read_to_buffer(FILE *fromfile,BUFFPEK *buffpek,
  63.                   uint sort_length);
  64. static int NEAR_F merge_buffers(SORT_PARAM *info,uint keys,FILE *from_file,
  65.                 FILE *to_file, uchar * *sort_keys,
  66.                 BUFFPEK *lastbuff,BUFFPEK *Fb,
  67.                 BUFFPEK *Tb);
  68. static int NEAR_F merge_index(SORT_PARAM *,uint,uchar **,BUFFPEK *, int,
  69.                   FILE *);
  70. static char **make_char_array(uint fields,uint length,myf my_flag);
  71. static FILE *opentemp(my_string name);
  72. static void closetemp(char *name,FILE *stream);
  73.  
  74.  
  75.     /* Creates a index of sorted keys */
  76.     /* Returns 0 if everything went ok */
  77.  
  78. int _create_index_by_sort(info,no_messages,sortbuff_size)
  79. SORT_PARAM *info;
  80. pbool      no_messages;
  81. uint      sortbuff_size;
  82. {
  83.   int error,maxbuffer,skr;
  84.   uint memavl,old_memavl,keys,sort_length;
  85.   BUFFPEK *buffpek;
  86.   char tempname[FN_REFLEN];
  87.   ulong records;
  88.   uchar **sort_keys;
  89.   FILE *tempfile;
  90.   DBUG_ENTER("_create_index_by_sort");
  91.  
  92.   tempfile=0; buffpek= (BUFFPEK *) NULL; sort_keys= (uchar **) NULL; error= 1;
  93.   maxbuffer=1;
  94.  
  95.   memavl=max(sortbuff_size,MIN_SORT_MEMORY);
  96.   records=    info->max_records;
  97.   sort_length=    info->key_length;
  98.   LINT_INIT(keys);
  99.  
  100.   while (memavl >= MIN_SORT_MEMORY)
  101.   {
  102.     if ((records+1)*(sort_length+sizeof(char*)) < (ulong) memavl)
  103.       keys= records+1;
  104.     else
  105.       do
  106.       {
  107.     skr=maxbuffer;
  108.     if (memavl < sizeof(BUFFPEK)*(uint) maxbuffer ||
  109.         (keys=(memavl-sizeof(BUFFPEK)*(uint) maxbuffer)/
  110.          (sort_length+sizeof(char*))) <= 1)
  111.     {
  112.       print_error("Sortbuffer to small");
  113.       goto err;
  114.     }
  115.       }
  116.       while ((maxbuffer= (int) (records/(keys-1)+1)) != skr);
  117.  
  118.     if ((sort_keys= (uchar **) make_char_array(keys,sort_length,MYF(0))))
  119.     {
  120.       if ((buffpek = (BUFFPEK*) my_malloc((uint) (sizeof(BUFFPEK)*
  121.                           (uint) maxbuffer),
  122.                       MYF(0))))
  123.     break;
  124.       else
  125.     my_free((gptr) sort_keys,MYF(0));
  126.     }
  127.     old_memavl=memavl;
  128.     if ((memavl=memavl/4*3) < MIN_SORT_MEMORY && old_memavl > MIN_SORT_MEMORY)
  129.       memavl=MIN_SORT_MEMORY;
  130.   }
  131.   if (memavl < MIN_SORT_MEMORY)
  132.   {
  133.     print_error("Sortbuffer to small");
  134.     goto err;
  135.   }
  136.   (*info->lock_in_memory)();            /* Everything is allocated */
  137.  
  138.   if (!no_messages)
  139.     printf("  - Searching for keys, allocating buffer for %d keys\n",keys);
  140.  
  141.   if ((records=find_all_keys(info,keys,sort_keys,buffpek,&maxbuffer,&tempfile,
  142.                  tempname))
  143.        == (ulong) -1)
  144.     goto err;
  145.   if (maxbuffer == 0)
  146.   {
  147.     if (!no_messages)
  148.       printf("  - Dumping %lu keys\n",records);
  149.     if (write_index(info,sort_keys,(uint) records))
  150.       goto err;
  151.   }
  152.   else
  153.   {
  154.     keys=(keys*(sort_length+sizeof(char*)))/sort_length;
  155.     if (maxbuffer >= MERGEBUFF2)
  156.     {
  157.       if (!no_messages)
  158.     printf("  - Merging %lu keys\n",records);
  159.       if (merge_many_buff(info,keys,sort_keys,buffpek,&maxbuffer,&tempfile,
  160.               tempname))
  161.     goto err;
  162.     }
  163.     if (!no_messages)
  164.       puts("  - Last merge and dumping keys");
  165.     if (merge_index(info,keys,sort_keys,buffpek,maxbuffer,tempfile))
  166.       goto err;
  167.   }
  168.   error =0;
  169.  
  170. err:
  171.   if (sort_keys)
  172.     my_free((gptr) sort_keys,MYF(0));
  173.   if (buffpek)
  174.     my_free((gptr) buffpek,MYF(0));
  175.   if (tempfile)
  176.     closetemp(tempname,tempfile);
  177.  
  178.   DBUG_RETURN(error ? -1 : 0);
  179. } /* _create_index_by_sort */
  180.  
  181.  
  182.     /* Search after all keys and place them in a temp. file */
  183.  
  184. static ulong NEAR_F find_all_keys(info,keys,sort_keys,buffpek,maxbuffer,
  185.                  tempfile,tempname)
  186. SORT_PARAM *info;
  187. uint    keys;
  188. uchar    **sort_keys;
  189. BUFFPEK *buffpek;
  190. int    *maxbuffer;
  191. FILE    **tempfile;
  192. my_string    tempname;
  193. {
  194.   int error;
  195.   uint index,indexpos;
  196.   DBUG_ENTER("find_all_keys");
  197.  
  198.   index=indexpos=error=0;
  199.  
  200.   while (!(error=(*info->key_read)(sort_keys[index])))
  201.   {
  202.     if ((uint) ++index == keys)
  203.     {
  204.       if (indexpos >= (uint) *maxbuffer ||
  205.       write_keys(info,sort_keys,index-1,buffpek+indexpos,tempfile,
  206.              tempname))
  207.     DBUG_RETURN(NI_POS_ERROR);
  208.       memcpy(sort_keys[0],sort_keys[index-1],(size_t) info->key_length);
  209.       index=1; indexpos++;
  210.     }
  211.   }
  212.   if (error > 0)
  213.     DBUG_RETURN(NI_POS_ERROR);        /* Aborted by get_key */
  214.   if (indexpos)
  215.     if (indexpos >= (uint) *maxbuffer ||
  216.     write_keys(info,sort_keys,index,buffpek+indexpos,tempfile,tempname))
  217.       DBUG_RETURN(NI_POS_ERROR);
  218.   *maxbuffer=(int) indexpos;
  219.   DBUG_RETURN(indexpos*(keys-1)+index);
  220. } /* find_all_keys */
  221.  
  222.  
  223.     /* Write all keys in memory to file for later merge */
  224.  
  225. static int NEAR_F write_keys(info,sort_keys,count,buffpek,tempfile,tempname)
  226. SORT_PARAM *info;
  227. reg1    uchar **sort_keys;
  228. uint    count;
  229. BUFFPEK *buffpek;
  230. reg2 FILE **tempfile;
  231. my_string    tempname;
  232. {
  233.   DBUG_ENTER("write_keys");
  234.  
  235.   qsort2((byte*) sort_keys,count,sizeof(byte*),(qsort2_cmp) info->key_cmp,
  236.      NullS);
  237.   if (! *tempfile && ! (*tempfile=opentemp(tempname)))
  238.     DBUG_RETURN(1);
  239.   buffpek->file_pos=my_ftell(*tempfile,MYF(0));
  240.   buffpek->count=count;
  241.   while (count--)
  242.     if (my_fwrite(*tempfile,(byte*)*sort_keys++,info->key_length,MYF_RW))
  243.       DBUG_RETURN(1);
  244.   DBUG_RETURN(0);
  245. } /* write_keys */
  246.  
  247.  
  248.     /* Write index */
  249.  
  250. static int NEAR_F write_index(info,sort_keys,count)
  251. SORT_PARAM *info;
  252. reg1 uchar **sort_keys;
  253. reg2 uint count;
  254. {
  255.   DBUG_ENTER("write_index");
  256.  
  257.   qsort2((gptr) sort_keys,(size_t) count,sizeof(byte*),
  258.      (qsort2_cmp) info->key_cmp, NullS);
  259.   while (count--)
  260.     if ((*info->key_write)(*sort_keys++))
  261.       DBUG_RETURN(-1);
  262.   DBUG_RETURN(0);
  263. } /* write_index */
  264.  
  265.  
  266.     /* Merge buffers to make < MERGEBUFF2 buffers */
  267.  
  268. static int NEAR_F merge_many_buff(info,keys,sort_keys,buffpek,maxbuffer,t_file,
  269.                   t_name)
  270. SORT_PARAM *info;
  271. uint    keys;
  272. uchar    **sort_keys;
  273. int    *maxbuffer;
  274. BUFFPEK *buffpek;
  275. FILE    **t_file;
  276. my_string    t_name;
  277. {
  278.   register int i;
  279.   FILE    *from_file,*to_file,*temp;
  280.   FILE    *t_file2;
  281.   char    t_name2[FN_REFLEN];
  282.   BUFFPEK *lastbuff;
  283.   DBUG_ENTER("merge_many_buff");
  284.  
  285.   if (!(t_file2=opentemp(t_name2)))
  286.     DBUG_RETURN(1);
  287.  
  288.   from_file= *t_file ; to_file= t_file2;
  289.   while (*maxbuffer >= MERGEBUFF2)
  290.   {
  291.     lastbuff=buffpek;
  292.     for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
  293.     {
  294.       if (merge_buffers(info,keys,from_file,to_file,sort_keys,lastbuff++,
  295.             buffpek+i,buffpek+i+MERGEBUFF-1))
  296.     break;
  297.     }
  298.     if (merge_buffers(info,keys,from_file,to_file,sort_keys,lastbuff++,
  299.               buffpek+i,buffpek+ *maxbuffer))
  300.       break;
  301.     *maxbuffer= (int) (lastbuff-buffpek)-1;
  302.     temp=from_file; from_file=to_file; to_file=temp;
  303.     VOID(my_fseek(to_file,0L,MY_SEEK_SET,MYF(0)));
  304.   }
  305.   if (to_file == *t_file)
  306.   {
  307.     closetemp(t_name,to_file);
  308.     *t_file=t_file2;
  309.     VOID(strmov(t_name,t_name2));
  310.   }
  311.   else closetemp(t_name2,to_file);
  312.  
  313.   DBUG_RETURN(*maxbuffer >= MERGEBUFF2);    /* Return 1 if interrupted */
  314. } /* merge_many_buff */
  315.  
  316.  
  317.     /* Read data to buffer */
  318.     /* This returns (uint) -1 if something goes wrong */
  319.  
  320. static uint NEAR_F read_to_buffer(fromfile,buffpek,sort_length)
  321. FILE    *fromfile;
  322. BUFFPEK *buffpek;
  323. uint sort_length;
  324. {
  325.   register uint count;
  326.   uint length;
  327.  
  328.   if ((count=(uint) min((ulong) buffpek->max_keys,buffpek->count)))
  329.   {
  330.     VOID(my_fseek(fromfile,buffpek->file_pos,MY_SEEK_SET,MYF(0)));
  331.     if (my_fread(fromfile,(byte*) buffpek->base,
  332.          (length= sort_length*count),MYF_RW))
  333.       return((uint) -1);
  334.     buffpek->key=buffpek->base;
  335.     buffpek->file_pos+= length;            /* New filepos */
  336.     buffpek->count-=    count;
  337.     buffpek->mem_count= count;
  338.   }
  339.   return (count*sort_length);
  340. } /* read_to_buffer */
  341.  
  342.  
  343.     /* Merge buffers to one buffer */
  344.     /* If to_file == 0 then use info->key_write */
  345.  
  346. static int NEAR_F merge_buffers(info,keys,from_file,to_file,sort_keys,lastbuff,
  347.                 Fb,Tb)
  348. SORT_PARAM *info;
  349. uint keys;
  350. FILE    *from_file,*to_file;
  351. uchar    **sort_keys;
  352. BUFFPEK *lastbuff,*Fb,*Tb;
  353. {
  354.   int error;
  355.   uint sort_length,maxcount;
  356.   ulong count;
  357.   my_off_t to_start_filepos;
  358.   uchar *strpos;
  359.   BUFFPEK *buffpek,**refpek;
  360.   QUEUE queue;
  361.   DBUG_ENTER("merge_buffers");
  362.  
  363.   count=error=0;
  364.   maxcount=keys/((uint) (Tb-Fb) +1);
  365.   sort_length=info->key_length;
  366.  
  367.   LINT_INIT(to_start_filepos);
  368.   if (to_file)
  369.     to_start_filepos=my_ftell(to_file,MYF(0));
  370.   strpos=(uchar*) sort_keys;
  371.  
  372.   if (init_queue(&queue,(uint) (Tb-Fb)+1,offsetof(BUFFPEK,key),0,
  373.          (int (*)(void *, byte *,byte *)) info->key_cmp,0))
  374.     DBUG_RETURN(1);
  375.  
  376.   for (buffpek= Fb ; buffpek <= Tb && error != -1 ; buffpek++)
  377.   {
  378.     count+= buffpek->count;
  379.     buffpek->base= strpos;
  380.     buffpek->max_keys=maxcount;
  381.     strpos+= (uint) (error=(int) read_to_buffer(from_file,buffpek,
  382.                         sort_length));
  383.     queue_insert(&queue,(void*) buffpek);
  384.   }
  385.   if (error == -1)
  386.     goto err;
  387.  
  388.   while (queue.elements > 1)
  389.   {
  390.     for (;;)
  391.     {
  392.       buffpek=(BUFFPEK*) queue_top(&queue);
  393.       if (to_file)
  394.       {
  395.     if (my_fwrite(to_file,(byte*) buffpek->key,(uint) sort_length,
  396.               MYF_RW | MY_WAIT_IF_FULL))
  397.     {
  398.       error=1; goto err;
  399.     }
  400.       }
  401.       else
  402.       {
  403.     if ((*info->key_write)((void*) buffpek->key))
  404.     {
  405.       error=1; goto err;
  406.     }
  407.       }
  408.       buffpek->key+=sort_length;
  409.       if (! --buffpek->mem_count)
  410.       {
  411.     if (!(error=(int) read_to_buffer(from_file,buffpek,sort_length)))
  412.     {
  413.       uchar *base=buffpek->base;
  414.       uint max_keys=buffpek->max_keys;
  415.  
  416.       VOID(queue_remove(&queue,0));
  417.  
  418.       /* Put room used by buffer to use in other buffer */
  419.       for (refpek= (BUFFPEK**) &queue_top(&queue);
  420.            refpek <= (BUFFPEK**) &queue_end(&queue);
  421.            refpek++)
  422.       {
  423.         buffpek= *refpek;
  424.         if (buffpek->base+buffpek->max_keys*sort_length == base)
  425.         {
  426.           buffpek->max_keys+=max_keys;
  427.           break;
  428.         }
  429.         else if (base+max_keys*sort_length == buffpek->base)
  430.         {
  431.           buffpek->base=base;
  432.           buffpek->max_keys+=max_keys;
  433.           break;
  434.         }
  435.       }
  436.       break;        /* One buffer have been removed */
  437.     }
  438.       }
  439.       queue_replaced(&queue);    /* Top element has been replaced */
  440.     }
  441.   }
  442.   buffpek=(BUFFPEK*) queue_top(&queue);
  443.   buffpek->base=(uchar *) sort_keys;
  444.   buffpek->max_keys=keys;
  445.   do
  446.   {
  447.     if (to_file)
  448.     {
  449.       if (my_fwrite(to_file,(byte*) buffpek->key,
  450.             (uint) (sort_length*buffpek->mem_count),
  451.             MYF_RW | MY_WAIT_IF_FULL))
  452.       {
  453.     error=1; goto err;
  454.       }
  455.     }
  456.     else
  457.     {
  458.       register uchar *end;
  459.       strpos= buffpek->key;
  460.       for (end=strpos+buffpek->mem_count*sort_length;
  461.        strpos != end ;
  462.        strpos+=sort_length)
  463.       {
  464.     if ((*info->key_write)((void*) strpos))
  465.     {
  466.       error=1; goto err;
  467.     }
  468.       }
  469.     }
  470.   }
  471.   while ((error=(int) read_to_buffer(from_file,buffpek,sort_length)) != -1 &&
  472.      error != 0);
  473.  
  474.   lastbuff->count=count;
  475.   if (to_file)
  476.     lastbuff->file_pos=to_start_filepos;    /* New block starts here */
  477. err:
  478.   delete_queue(&queue);
  479.   DBUG_RETURN(error);
  480. } /* merge_buffers */
  481.  
  482.  
  483.     /* Do a merge to output-file (save only positions) */
  484.  
  485. static int NEAR_F merge_index(info,keys,sort_keys,buffpek,maxbuffer,tempfile)
  486. SORT_PARAM *info;
  487. uint    keys;
  488. uchar    **sort_keys;
  489. BUFFPEK *buffpek;
  490. int    maxbuffer;
  491. FILE    *tempfile;
  492. {
  493.   DBUG_ENTER("merge_index");
  494.   if (merge_buffers(info,keys,tempfile,(FILE*) 0,sort_keys,buffpek,buffpek,
  495.             buffpek+maxbuffer))
  496.     DBUG_RETURN(1);
  497.   DBUG_RETURN(0);
  498. } /* merge_index */
  499.  
  500.  
  501.     /* Make a pointer of arrays to keys */
  502.  
  503. static char **make_char_array(fields,length,my_flag)
  504. register uint fields;
  505. uint length;
  506. myf my_flag;
  507. {
  508.   register char **pos;
  509.   char **old_pos,*char_pos;
  510.   DBUG_ENTER("make_char_array");
  511.  
  512.   if ((old_pos= (char**) my_malloc( fields*(length+sizeof(char*)), my_flag)))
  513.   {
  514.     pos=old_pos; char_pos=((char*) (pos+fields)) -length;
  515.     while (fields--)
  516.       *(pos++) = (char_pos+= length);
  517.   }
  518.  
  519.   DBUG_RETURN(old_pos);
  520. } /* make_char_array */
  521.  
  522.  
  523.     /* |ppnar en tempor{rfil som kommer att raderas efter anv{nding */
  524.  
  525. static FILE *opentemp(name)
  526. my_string name;
  527. {
  528.   FILE *stream;
  529.   reg1 my_string str_pos;
  530.   DBUG_ENTER("opentemp");
  531.  
  532.   if (!(str_pos=my_tempnam(NullS,"ST",MYF(MY_WME))))
  533.     DBUG_RETURN(0);
  534.   VOID(strmov(name,str_pos));
  535.   (*free)(str_pos);                /* Inte via vanliga malloc */
  536.  
  537.   stream=my_fopen(name,(int) (O_RDWR | FILE_BINARY | O_CREAT | O_TEMPORARY),
  538.           MYF(MY_WME));
  539. #if O_TEMPORARY == 0 && !defined(CANT_DELETE_OPEN_FILES)
  540.     VOID(my_delete(name,MYF(MY_WME | ME_NOINPUT)));
  541. #endif
  542.   DBUG_PRINT("exit",("stream: %lx",stream));
  543.   DBUG_RETURN (stream);
  544. } /* opentemp */
  545.  
  546.  
  547. static void closetemp(char *name __attribute__((unused)) ,FILE *stream)
  548. {
  549.   DBUG_ENTER("closetemp");
  550.  
  551.   if (stream)
  552.     VOID(my_fclose(stream,MYF(MY_WME)));
  553. #ifdef CANT_DELETE_OPEN_FILES
  554.   if (name)
  555.     VOID(my_delete(name,MYF(MY_WME)));
  556. #endif
  557.   DBUG_VOID_RETURN;
  558. } /* closetemp */
  559.