sort.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:14k
源码类别:

MySQL数据库

开发平台:

Visual C++

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