home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / myisam / sort.c < prev   
C/C++ Source or Header  |  2000-10-22  |  14KB  |  493 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 "myisamdef.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. #define DISK_BUFFER_SIZE (IO_SIZE*16)
  37.  
  38. typedef struct st_buffpek {
  39.   my_off_t file_pos;            /* position to buffer */
  40.   ha_rows count;            /* keys in buffer */
  41.   uchar *base,*key;            /* Pekare inom sort_key - indexdel */
  42.   uint mem_count;            /* keys left in memory */
  43.   uint max_keys;            /* Max keys in buffert */
  44. } BUFFPEK;
  45.  
  46. extern void print_error _VARARGS((const char *fmt,...));
  47.  
  48.     /* functions defined in this file */
  49.  
  50. static ha_rows NEAR_F find_all_keys(MI_SORT_PARAM *info,uint keys,
  51.                     uchar **sort_keys,
  52.                     BUFFPEK *buffpek,int *maxbuffer,
  53.                     IO_CACHE *tempfile);
  54. static int NEAR_F write_keys(MI_SORT_PARAM *info,uchar * *sort_keys,
  55.                  uint count, BUFFPEK *buffpek,IO_CACHE *tempfile);
  56. static int NEAR_F write_index(MI_SORT_PARAM *info,uchar * *sort_keys,
  57.                   uint count);
  58. static int NEAR_F merge_many_buff(MI_SORT_PARAM *info,uint keys,
  59.                   uchar * *sort_keys,
  60.                   BUFFPEK *buffpek,int *maxbuffer,
  61.                   IO_CACHE *t_file);
  62. static uint NEAR_F read_to_buffer(IO_CACHE *fromfile,BUFFPEK *buffpek,
  63.                   uint sort_length);
  64. static int NEAR_F merge_buffers(MI_SORT_PARAM *info,uint keys,
  65.                 IO_CACHE *from_file, IO_CACHE *to_file,
  66.                 uchar * *sort_keys, BUFFPEK *lastbuff,
  67.                 BUFFPEK *Fb, BUFFPEK *Tb);
  68. static int NEAR_F merge_index(MI_SORT_PARAM *,uint,uchar **,BUFFPEK *, int,
  69.                   IO_CACHE *);
  70. static char **make_char_array(uint fields,uint length,myf my_flag);
  71.  
  72.     /* Creates a index of sorted keys */
  73.     /* Returns 0 if everything went ok */
  74.  
  75. int _create_index_by_sort(MI_SORT_PARAM *info,my_bool no_messages,
  76.               ulong sortbuff_size)
  77. {
  78.   int error,maxbuffer,skr;
  79.   uint memavl,old_memavl,keys,sort_length;
  80.   BUFFPEK *buffpek;
  81.   ha_rows records;
  82.   uchar **sort_keys;
  83.   IO_CACHE tempfile;
  84.   DBUG_ENTER("_create_index_by_sort");
  85.   DBUG_PRINT("enter",("sort_length: %d", info->key_length));
  86.  
  87.   my_b_clear(&tempfile);
  88.   buffpek= (BUFFPEK *) NULL; sort_keys= (uchar **) NULL; error= 1;
  89.   maxbuffer=1;
  90.  
  91.   memavl=max(sortbuff_size,MIN_SORT_MEMORY);
  92.   records=    info->max_records;
  93.   sort_length=    info->key_length;
  94.   LINT_INIT(keys);
  95.  
  96.   while (memavl >= MIN_SORT_MEMORY)
  97.   {
  98.     if ((my_off_t) (records+1)*(sort_length+sizeof(char*)) <=
  99.     (my_off_t) memavl)
  100.       keys= records+1;
  101.     else
  102.       do
  103.       {
  104.     skr=maxbuffer;
  105.     if (memavl < sizeof(BUFFPEK)*(uint) maxbuffer ||
  106.         (keys=(memavl-sizeof(BUFFPEK)*(uint) maxbuffer)/
  107.          (sort_length+sizeof(char*))) <= 1)
  108.     {
  109.       mi_check_print_error(info->sort_info->param,
  110.                    "sort_buffer_size is to small");
  111.       goto err;
  112.     }
  113.       }
  114.       while ((maxbuffer= (int) (records/(keys-1)+1)) != skr);
  115.  
  116.     if ((sort_keys= (uchar **) make_char_array(keys,sort_length,MYF(0))))
  117.     {
  118.       if ((buffpek = (BUFFPEK*) my_malloc((uint) (sizeof(BUFFPEK)*
  119.                           (uint) maxbuffer),
  120.                       MYF(0))))
  121.     break;
  122.       else
  123.     my_free((gptr) sort_keys,MYF(0));
  124.     }
  125.     old_memavl=memavl;
  126.     if ((memavl=memavl/4*3) < MIN_SORT_MEMORY && old_memavl > MIN_SORT_MEMORY)
  127.       memavl=MIN_SORT_MEMORY;
  128.   }
  129.   if (memavl < MIN_SORT_MEMORY)
  130.   {
  131.     mi_check_print_error(info->sort_info->param,"Sort buffer to small"); /* purecov: tested */
  132.     goto err; /* purecov: tested */
  133.   }
  134.   (*info->lock_in_memory)(info->sort_info->param);/* Everything is allocated */
  135.  
  136.   if (!no_messages)
  137.     printf("  - Searching for keys, allocating buffer for %d keys\n",keys);
  138.  
  139.   if ((records=find_all_keys(info,keys,sort_keys,buffpek,&maxbuffer,&tempfile))
  140.       == HA_POS_ERROR)
  141.     goto err; /* purecov: tested */
  142.   if (maxbuffer == 0)
  143.   {
  144.     if (!no_messages)
  145.       printf("  - Dumping %lu keys\n",records);
  146.     if (write_index(info,sort_keys,(uint) records))
  147.       goto err; /* purecov: inspected */
  148.   }
  149.   else
  150.   {
  151.     keys=(keys*(sort_length+sizeof(char*)))/sort_length;
  152.     if (maxbuffer >= MERGEBUFF2)
  153.     {
  154.       if (!no_messages)
  155.     printf("  - Merging %lu keys\n",records); /* purecov: tested */
  156.       if (merge_many_buff(info,keys,sort_keys,buffpek,&maxbuffer,&tempfile))
  157.     goto err; /* purecov: inspected */
  158.     }
  159.     if (flush_io_cache(&tempfile) ||
  160.     reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
  161.       goto err; /* purecov: inspected */
  162.     if (!no_messages)
  163.       puts("  - Last merge and dumping keys"); /* purecov: tested */
  164.     if (merge_index(info,keys,sort_keys,buffpek,maxbuffer,&tempfile))
  165.       goto err; /* purecov: inspected */
  166.   }
  167.   error =0;
  168.  
  169. err:
  170.   if (sort_keys)
  171.     my_free((gptr) sort_keys,MYF(0));
  172.   if (buffpek)
  173.     my_free((gptr) buffpek,MYF(0));
  174.   close_cached_file(&tempfile);
  175.  
  176.   DBUG_RETURN(error ? -1 : 0);
  177. } /* _create_index_by_sort */
  178.  
  179.  
  180.     /* Search after all keys and place them in a temp. file */
  181.  
  182. static ha_rows NEAR_F find_all_keys(MI_SORT_PARAM *info, uint keys,
  183.                     uchar **sort_keys, BUFFPEK *buffpek,
  184.                     int *maxbuffer, IO_CACHE *tempfile)
  185. {
  186.   int error;
  187.   uint idx,indexpos;
  188.   DBUG_ENTER("find_all_keys");
  189.  
  190.   idx=indexpos=error=0;
  191.  
  192.   while (!(error=(*info->key_read)(info->sort_info,sort_keys[idx])))
  193.   {
  194.     if ((uint) ++idx == keys)
  195.     {
  196.       if (indexpos >= (uint) *maxbuffer ||
  197.       write_keys(info,sort_keys,idx-1,buffpek+indexpos,tempfile))
  198.     DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
  199.       memcpy(sort_keys[0],sort_keys[idx-1],(size_t) info->key_length);
  200.       idx=1; indexpos++;
  201.     }
  202.   }
  203.   if (error > 0)
  204.     DBUG_RETURN(HA_POS_ERROR);        /* Aborted by get_key */ /* purecov: inspected */
  205.   if (indexpos)
  206.     if (indexpos >= (uint) *maxbuffer ||
  207.     write_keys(info,sort_keys,idx,buffpek+indexpos,tempfile))
  208.       DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
  209.   *maxbuffer=(int) indexpos;
  210.   DBUG_RETURN(indexpos*(keys-1)+idx);
  211. } /* find_all_keys */
  212.  
  213.  
  214.     /* Write all keys in memory to file for later merge */
  215.  
  216. static int NEAR_F write_keys(MI_SORT_PARAM *info, register uchar **sort_keys,
  217.                  uint count, BUFFPEK *buffpek,
  218.                  IO_CACHE *tempfile)
  219. {
  220.   uchar **end;
  221.   uint sort_length=info->key_length;
  222.   DBUG_ENTER("write_keys");
  223.  
  224.   qsort2((byte*) sort_keys,count,sizeof(byte*),(qsort2_cmp) info->key_cmp,
  225.     info->sort_info);
  226.   if (!my_b_inited(tempfile) &&
  227.       open_cached_file(tempfile, info->tmpdir, "ST", DISK_BUFFER_SIZE,
  228.                info->myf_rw))
  229.     DBUG_RETURN(1); /* purecov: inspected */
  230.   buffpek->file_pos=my_b_tell(tempfile);
  231.   buffpek->count=count;
  232.  
  233.   for (end=sort_keys+count ; sort_keys != end ; sort_keys++)
  234.     if (my_b_write(tempfile,(byte*) *sort_keys,(uint) sort_length))
  235.       DBUG_RETURN(1); /* purecov: inspected */
  236.   DBUG_RETURN(0);
  237. } /* write_keys */
  238.  
  239.  
  240.     /* Write index */
  241.  
  242. static int NEAR_F write_index(MI_SORT_PARAM *info, register uchar **sort_keys,
  243.                   register uint count)
  244. {
  245.   DBUG_ENTER("write_index");
  246.  
  247.   qsort2((gptr) sort_keys,(size_t) count,sizeof(byte*),
  248.     (qsort2_cmp) info->key_cmp,info->sort_info);
  249.   while (count--)
  250.     if ((*info->key_write)(info->sort_info,*sort_keys++))
  251.       DBUG_RETURN(-1); /* purecov: inspected */
  252.   DBUG_RETURN(0);
  253. } /* write_index */
  254.  
  255.  
  256.     /* Merge buffers to make < MERGEBUFF2 buffers */
  257.  
  258. static int NEAR_F merge_many_buff(MI_SORT_PARAM *info, uint keys,
  259.                   uchar **sort_keys, BUFFPEK *buffpek,
  260.                   int *maxbuffer, IO_CACHE *t_file)
  261. {
  262.   register int i;
  263.   IO_CACHE t_file2, *from_file, *to_file, *temp;
  264.   BUFFPEK *lastbuff;
  265.   DBUG_ENTER("merge_many_buff");
  266.  
  267.   if (*maxbuffer < MERGEBUFF2)
  268.     DBUG_RETURN(0);                /* purecov: inspected */
  269.   if (flush_io_cache(t_file) ||
  270.       open_cached_file(&t_file2,info->tmpdir,"ST",DISK_BUFFER_SIZE,
  271.                info->myf_rw))
  272.     DBUG_RETURN(1);                /* purecov: inspected */
  273.  
  274.   from_file= t_file ; to_file= &t_file2;
  275.   while (*maxbuffer >= MERGEBUFF2)
  276.   {
  277.     reinit_io_cache(from_file,READ_CACHE,0L,0,0);
  278.     reinit_io_cache(to_file,WRITE_CACHE,0L,0,0);
  279.     lastbuff=buffpek;
  280.     for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
  281.     {
  282.       if (merge_buffers(info,keys,from_file,to_file,sort_keys,lastbuff++,
  283.             buffpek+i,buffpek+i+MERGEBUFF-1))
  284.     break; /* purecov: inspected */
  285.     }
  286.     if (merge_buffers(info,keys,from_file,to_file,sort_keys,lastbuff++,
  287.               buffpek+i,buffpek+ *maxbuffer))
  288.       break; /* purecov: inspected */
  289.     if (flush_io_cache(to_file))
  290.       break;                    /* purecov: inspected */
  291.     temp=from_file; from_file=to_file; to_file=temp;
  292.     *maxbuffer= (int) (lastbuff-buffpek)-1;
  293.   }
  294.   close_cached_file(to_file);            /* This holds old result */
  295.   if (to_file == t_file)
  296.     *t_file=t_file2;                /* Copy result file */
  297.  
  298.   DBUG_RETURN(*maxbuffer >= MERGEBUFF2);    /* Return 1 if interrupted */
  299. } /* merge_many_buff */
  300.  
  301.  
  302.     /* Read data to buffer */
  303.     /* This returns (uint) -1 if something goes wrong */
  304.  
  305. static uint NEAR_F read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
  306.                   uint sort_length)
  307. {
  308.   register uint count;
  309.   uint length;
  310.  
  311.   if ((count=(uint) min((ha_rows) buffpek->max_keys,buffpek->count)))
  312.   {
  313.     if (my_pread(fromfile->file,(byte*) buffpek->base,
  314.          (length= sort_length*count),buffpek->file_pos,MYF_RW))
  315.       return((uint) -1);            /* purecov: inspected */
  316.     buffpek->key=buffpek->base;
  317.     buffpek->file_pos+= length;            /* New filepos */
  318.     buffpek->count-=    count;
  319.     buffpek->mem_count= count;
  320.   }
  321.   return (count*sort_length);
  322. } /* read_to_buffer */
  323.  
  324.  
  325.     /* Merge buffers to one buffer */
  326.     /* If to_file == 0 then use info->key_write */
  327.  
  328. static int NEAR_F
  329. merge_buffers(MI_SORT_PARAM *info, uint keys, IO_CACHE *from_file, 
  330.           IO_CACHE *to_file, uchar **sort_keys, BUFFPEK *lastbuff,
  331.           BUFFPEK *Fb, BUFFPEK *Tb)
  332. {
  333.   int error;
  334.   uint sort_length,maxcount;
  335.   ha_rows count;
  336.   my_off_t to_start_filepos;
  337.   uchar *strpos;
  338.   BUFFPEK *buffpek,**refpek;
  339.   QUEUE queue;
  340.   DBUG_ENTER("merge_buffers");
  341.  
  342.   count=error=0;
  343.   maxcount=keys/((uint) (Tb-Fb) +1);
  344.   LINT_INIT(to_start_filepos);
  345.   if (to_file)
  346.     to_start_filepos=my_b_tell(to_file);
  347.   strpos=(uchar*) sort_keys;
  348.   sort_length=info->key_length;
  349.  
  350.   if (init_queue(&queue,(uint) (Tb-Fb)+1,offsetof(BUFFPEK,key),0,
  351.          (int (*)(void*, byte *,byte*)) info->key_cmp,
  352.          (void*) info->sort_info))
  353.     DBUG_RETURN(1); /* purecov: inspected */
  354.  
  355.   for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
  356.   {
  357.     count+= buffpek->count;
  358.     buffpek->base= strpos;
  359.     buffpek->max_keys=maxcount;
  360.     strpos+= (uint) (error=(int) read_to_buffer(from_file,buffpek,
  361.                         sort_length));
  362.     if (error == -1)
  363.       goto err; /* purecov: inspected */
  364.     queue_insert(&queue,(void*) buffpek);
  365.   }
  366.  
  367.   while (queue.elements > 1)
  368.   {
  369.     for (;;)
  370.     {
  371.       buffpek=(BUFFPEK*) queue_top(&queue);
  372.       if (to_file)
  373.       {
  374.     if (my_b_write(to_file,(byte*) buffpek->key,(uint) sort_length))
  375.     {
  376.       error=1; goto err; /* purecov: inspected */
  377.     }
  378.       }
  379.       else
  380.       {
  381.     if ((*info->key_write)(info->sort_info,(void*) buffpek->key))
  382.     {
  383.       error=1; goto err; /* purecov: inspected */
  384.     }
  385.       }
  386.       buffpek->key+=sort_length;
  387.       if (! --buffpek->mem_count)
  388.       {
  389.     if (!(error=(int) read_to_buffer(from_file,buffpek,sort_length)))
  390.     {
  391.       uchar *base=buffpek->base;
  392.       uint max_keys=buffpek->max_keys;
  393.  
  394.       VOID(queue_remove(&queue,0));
  395.  
  396.       /* Put room used by buffer to use in other buffer */
  397.       for (refpek= (BUFFPEK**) &queue_top(&queue);
  398.            refpek <= (BUFFPEK**) &queue_end(&queue);
  399.            refpek++)
  400.       {
  401.         buffpek= *refpek;
  402.         if (buffpek->base+buffpek->max_keys*sort_length == base)
  403.         {
  404.           buffpek->max_keys+=max_keys;
  405.           break;
  406.         }
  407.         else if (base+max_keys*sort_length == buffpek->base)
  408.         {
  409.           buffpek->base=base;
  410.           buffpek->max_keys+=max_keys;
  411.           break;
  412.         }
  413.       }
  414.       break;        /* One buffer have been removed */
  415.     }
  416.       }
  417.       else if (error == -1)
  418.     goto err;        /* purecov: inspected */
  419.       queue_replaced(&queue);    /* Top element has been replaced */
  420.     }
  421.   }
  422.   buffpek=(BUFFPEK*) queue_top(&queue);
  423.   buffpek->base=(uchar *) sort_keys;
  424.   buffpek->max_keys=keys;
  425.   do
  426.   {
  427.     if (to_file)
  428.     {
  429.       if (my_b_write(to_file,(byte*) buffpek->key,
  430.              (sort_length*buffpek->mem_count)))
  431.       {
  432.     error=1; goto err; /* purecov: inspected */
  433.       }
  434.     }
  435.     else
  436.     {
  437.       register uchar *end;
  438.       strpos= buffpek->key;
  439.       for (end=strpos+buffpek->mem_count*sort_length;
  440.        strpos != end ;
  441.        strpos+=sort_length)
  442.       {
  443.     if ((*info->key_write)(info->sort_info,(void*) strpos))
  444.     {
  445.       error=1; goto err; /* purecov: inspected */
  446.     }
  447.       }
  448.     }
  449.   }
  450.   while ((error=(int) read_to_buffer(from_file,buffpek,sort_length)) != -1 &&
  451.      error != 0);
  452.  
  453.   lastbuff->count=count;
  454.   if (to_file)
  455.     lastbuff->file_pos=to_start_filepos;
  456. err:
  457.   delete_queue(&queue);
  458.   DBUG_RETURN(error);
  459. } /* merge_buffers */
  460.  
  461.  
  462.     /* Do a merge to output-file (save only positions) */
  463.  
  464. static int NEAR_F
  465. merge_index(MI_SORT_PARAM *info, uint keys, uchar **sort_keys,
  466.         BUFFPEK *buffpek, int maxbuffer, IO_CACHE *tempfile)
  467. {
  468.   DBUG_ENTER("merge_index");
  469.   if (merge_buffers(info,keys,tempfile,(IO_CACHE*) 0,sort_keys,buffpek,buffpek,
  470.             buffpek+maxbuffer))
  471.     DBUG_RETURN(1); /* purecov: inspected */
  472.   DBUG_RETURN(0);
  473. } /* merge_index */
  474.  
  475.  
  476.     /* Make a pointer of arrays to keys */
  477.  
  478. static char **make_char_array(register uint fields, uint length, myf my_flag)
  479. {
  480.   register char **pos;
  481.   char **old_pos,*char_pos;
  482.   DBUG_ENTER("make_char_array");
  483.  
  484.   if ((old_pos= (char**) my_malloc( fields*(length+sizeof(char*)), my_flag)))
  485.   {
  486.     pos=old_pos; char_pos=((char*) (pos+fields)) -length;
  487.     while (fields--)
  488.       *(pos++) = (char_pos+= length);
  489.   }
  490.  
  491.   DBUG_RETURN(old_pos);
  492. } /* make_char_array */
  493.