sort.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:14k
- /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
- This program is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
- (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
- /*
- Creates a index for a database by reading keys, sorting them and outputing
- them in sorted order through SORT_INFO functions.
- */
- #include "isamdef.h"
- #if defined(MSDOS) || defined(__WIN__)
- #include <fcntl.h>
- #else
- #include <stddef.h>
- #endif
- #include <queues.h>
- /* static variabels */
- #define MERGEBUFF 15
- #define MERGEBUFF2 31
- #define MIN_SORT_MEMORY (4096-MALLOC_OVERHEAD)
- #define MYF_RW MYF(MY_NABP | MY_WME | MY_WAIT_IF_FULL)
- typedef struct st_buffpek { /* Struktur om sorteringsbuffrarna */
- my_off_t file_pos; /* Position var bufferten finns */
- ulong count; /* Antal nycklar i bufferten */
- uchar *base,*key; /* Pekare inom sort_key - indexdel */
- uint mem_count; /* Antal nycklar kvar i minnet */
- uint max_keys; /* Max keys in buffert */
- } BUFFPEK;
- extern void print_error _VARARGS((const char *fmt,...));
- /* functions defined in this file */
- static ulong NEAR_F find_all_keys(SORT_PARAM *info,uint keys,
- uchar * *sort_keys,
- BUFFPEK *buffpek,int *maxbuffer,
- FILE **tempfile, my_string tempname);
- static int NEAR_F write_keys(SORT_PARAM *info,uchar * *sort_keys,
- uint count, BUFFPEK *buffpek,FILE **tempfile,
- my_string tempname);
- static int NEAR_F write_index(SORT_PARAM *info,uchar * *sort_keys,
- uint count);
- static int NEAR_F merge_many_buff(SORT_PARAM *info,uint keys,
- uchar * *sort_keys,
- BUFFPEK *buffpek,int *maxbuffer,
- FILE * *t_file, my_string tempname);
- static uint NEAR_F read_to_buffer(FILE *fromfile,BUFFPEK *buffpek,
- uint sort_length);
- static int NEAR_F merge_buffers(SORT_PARAM *info,uint keys,FILE *from_file,
- FILE *to_file, uchar * *sort_keys,
- BUFFPEK *lastbuff,BUFFPEK *Fb,
- BUFFPEK *Tb);
- static int NEAR_F merge_index(SORT_PARAM *,uint,uchar **,BUFFPEK *, int,
- FILE *);
- static char **make_char_array(uint fields,uint length,myf my_flag);
- static FILE *opentemp(my_string name);
- static void closetemp(char *name,FILE *stream);
- /* Creates a index of sorted keys */
- /* Returns 0 if everything went ok */
- int _create_index_by_sort(info,no_messages,sortbuff_size)
- SORT_PARAM *info;
- pbool no_messages;
- uint sortbuff_size;
- {
- int error,maxbuffer,skr;
- uint memavl,old_memavl,keys,sort_length;
- BUFFPEK *buffpek;
- char tempname[FN_REFLEN];
- ulong records;
- uchar **sort_keys;
- FILE *tempfile;
- DBUG_ENTER("_create_index_by_sort");
- tempfile=0; buffpek= (BUFFPEK *) NULL; sort_keys= (uchar **) NULL; error= 1;
- maxbuffer=1;
- memavl=max(sortbuff_size,MIN_SORT_MEMORY);
- records= info->max_records;
- sort_length= info->key_length;
- LINT_INIT(keys);
- while (memavl >= MIN_SORT_MEMORY)
- {
- if ((records+1)*(sort_length+sizeof(char*)) < (ulong) memavl)
- keys= records+1;
- else
- do
- {
- skr=maxbuffer;
- if (memavl < sizeof(BUFFPEK)*(uint) maxbuffer ||
- (keys=(memavl-sizeof(BUFFPEK)*(uint) maxbuffer)/
- (sort_length+sizeof(char*))) <= 1)
- {
- print_error("Sortbuffer to small");
- goto err;
- }
- }
- while ((maxbuffer= (int) (records/(keys-1)+1)) != skr);
- if ((sort_keys= (uchar **) make_char_array(keys,sort_length,MYF(0))))
- {
- if ((buffpek = (BUFFPEK*) my_malloc((uint) (sizeof(BUFFPEK)*
- (uint) maxbuffer),
- MYF(0))))
- break;
- else
- {
- my_free((gptr) sort_keys,MYF(0));
- sort_keys= 0;
- }
- }
- old_memavl=memavl;
- if ((memavl=memavl/4*3) < MIN_SORT_MEMORY && old_memavl > MIN_SORT_MEMORY)
- memavl=MIN_SORT_MEMORY;
- }
- if (memavl < MIN_SORT_MEMORY)
- {
- print_error("Sortbuffer to small");
- goto err;
- }
- (*info->lock_in_memory)(); /* Everything is allocated */
- if (!no_messages)
- printf(" - Searching for keys, allocating buffer for %d keysn",keys);
- if ((records=find_all_keys(info,keys,sort_keys,buffpek,&maxbuffer,&tempfile,
- tempname))
- == (ulong) -1)
- goto err;
- if (maxbuffer == 0)
- {
- if (!no_messages)
- printf(" - Dumping %lu keysn",records);
- if (write_index(info,sort_keys,(uint) records))
- goto err;
- }
- else
- {
- keys=(keys*(sort_length+sizeof(char*)))/sort_length;
- if (maxbuffer >= MERGEBUFF2)
- {
- if (!no_messages)
- printf(" - Merging %lu keysn",records);
- if (merge_many_buff(info,keys,sort_keys,buffpek,&maxbuffer,&tempfile,
- tempname))
- goto err;
- }
- if (!no_messages)
- puts(" - Last merge and dumping keys");
- if (merge_index(info,keys,sort_keys,buffpek,maxbuffer,tempfile))
- goto err;
- }
- error =0;
- err:
- if (sort_keys)
- my_free((gptr) sort_keys,MYF(0));
- if (buffpek)
- my_free((gptr) buffpek,MYF(0));
- if (tempfile)
- closetemp(tempname,tempfile);
- DBUG_RETURN(error ? -1 : 0);
- } /* _create_index_by_sort */
- /* Search after all keys and place them in a temp. file */
- static ulong NEAR_F find_all_keys(info,keys,sort_keys,buffpek,maxbuffer,
- tempfile,tempname)
- SORT_PARAM *info;
- uint keys;
- uchar **sort_keys;
- BUFFPEK *buffpek;
- int *maxbuffer;
- FILE **tempfile;
- my_string tempname;
- {
- int error;
- uint index,indexpos;
- DBUG_ENTER("find_all_keys");
- index=indexpos=error=0;
- while (!(error=(*info->key_read)(sort_keys[index])))
- {
- if ((uint) ++index == keys)
- {
- if (indexpos >= (uint) *maxbuffer ||
- write_keys(info,sort_keys,index-1,buffpek+indexpos,tempfile,
- tempname))
- DBUG_RETURN(NI_POS_ERROR);
- memcpy(sort_keys[0],sort_keys[index-1],(size_t) info->key_length);
- index=1; indexpos++;
- }
- }
- if (error > 0)
- DBUG_RETURN(NI_POS_ERROR); /* Aborted by get_key */
- if (indexpos)
- if (indexpos >= (uint) *maxbuffer ||
- write_keys(info,sort_keys,index,buffpek+indexpos,tempfile,tempname))
- DBUG_RETURN(NI_POS_ERROR);
- *maxbuffer=(int) indexpos;
- DBUG_RETURN(indexpos*(keys-1)+index);
- } /* find_all_keys */
- /* Write all keys in memory to file for later merge */
- static int NEAR_F write_keys(info,sort_keys,count,buffpek,tempfile,tempname)
- SORT_PARAM *info;
- reg1 uchar **sort_keys;
- uint count;
- BUFFPEK *buffpek;
- reg2 FILE **tempfile;
- my_string tempname;
- {
- DBUG_ENTER("write_keys");
- qsort2((byte*) sort_keys,count,sizeof(byte*),(qsort2_cmp) info->key_cmp,
- NullS);
- if (! *tempfile && ! (*tempfile=opentemp(tempname)))
- DBUG_RETURN(1);
- buffpek->file_pos=my_ftell(*tempfile,MYF(0));
- buffpek->count=count;
- while (count--)
- if (my_fwrite(*tempfile,(byte*)*sort_keys++,info->key_length,MYF_RW))
- DBUG_RETURN(1);
- DBUG_RETURN(0);
- } /* write_keys */
- /* Write index */
- static int NEAR_F write_index(info,sort_keys,count)
- SORT_PARAM *info;
- reg1 uchar **sort_keys;
- reg2 uint count;
- {
- DBUG_ENTER("write_index");
- qsort2((gptr) sort_keys,(size_t) count,sizeof(byte*),
- (qsort2_cmp) info->key_cmp, NullS);
- while (count--)
- if ((*info->key_write)(*sort_keys++))
- DBUG_RETURN(-1);
- DBUG_RETURN(0);
- } /* write_index */
- /* Merge buffers to make < MERGEBUFF2 buffers */
- static int NEAR_F merge_many_buff(info,keys,sort_keys,buffpek,maxbuffer,t_file,
- t_name)
- SORT_PARAM *info;
- uint keys;
- uchar **sort_keys;
- int *maxbuffer;
- BUFFPEK *buffpek;
- FILE **t_file;
- my_string t_name;
- {
- register int i;
- FILE *from_file,*to_file,*temp;
- FILE *t_file2;
- char t_name2[FN_REFLEN];
- BUFFPEK *lastbuff;
- DBUG_ENTER("merge_many_buff");
- if (!(t_file2=opentemp(t_name2)))
- DBUG_RETURN(1);
- from_file= *t_file ; to_file= t_file2;
- while (*maxbuffer >= MERGEBUFF2)
- {
- lastbuff=buffpek;
- for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
- {
- if (merge_buffers(info,keys,from_file,to_file,sort_keys,lastbuff++,
- buffpek+i,buffpek+i+MERGEBUFF-1))
- break;
- }
- if (merge_buffers(info,keys,from_file,to_file,sort_keys,lastbuff++,
- buffpek+i,buffpek+ *maxbuffer))
- break;
- *maxbuffer= (int) (lastbuff-buffpek)-1;
- temp=from_file; from_file=to_file; to_file=temp;
- VOID(my_fseek(to_file,0L,MY_SEEK_SET,MYF(0)));
- }
- if (to_file == *t_file)
- {
- closetemp(t_name,to_file);
- *t_file=t_file2;
- VOID(strmov(t_name,t_name2));
- }
- else closetemp(t_name2,to_file);
- DBUG_RETURN(*maxbuffer >= MERGEBUFF2); /* Return 1 if interrupted */
- } /* merge_many_buff */
- /* Read data to buffer */
- /* This returns (uint) -1 if something goes wrong */
- static uint NEAR_F read_to_buffer(fromfile,buffpek,sort_length)
- FILE *fromfile;
- BUFFPEK *buffpek;
- uint sort_length;
- {
- register uint count;
- uint length;
- if ((count=(uint) min((ulong) buffpek->max_keys,buffpek->count)))
- {
- VOID(my_fseek(fromfile,buffpek->file_pos,MY_SEEK_SET,MYF(0)));
- if (my_fread(fromfile,(byte*) buffpek->base,
- (length= sort_length*count),MYF_RW))
- return((uint) -1);
- buffpek->key=buffpek->base;
- buffpek->file_pos+= length; /* New filepos */
- buffpek->count-= count;
- buffpek->mem_count= count;
- }
- return (count*sort_length);
- } /* read_to_buffer */
- /* Merge buffers to one buffer */
- /* If to_file == 0 then use info->key_write */
- static int NEAR_F merge_buffers(info,keys,from_file,to_file,sort_keys,lastbuff,
- Fb,Tb)
- SORT_PARAM *info;
- uint keys;
- FILE *from_file,*to_file;
- uchar **sort_keys;
- BUFFPEK *lastbuff,*Fb,*Tb;
- {
- int error;
- uint sort_length,maxcount;
- ulong count;
- my_off_t to_start_filepos;
- uchar *strpos;
- BUFFPEK *buffpek,**refpek;
- QUEUE queue;
- DBUG_ENTER("merge_buffers");
- count=error=0;
- maxcount=keys/((uint) (Tb-Fb) +1);
- sort_length=info->key_length;
- LINT_INIT(to_start_filepos);
- if (to_file)
- to_start_filepos=my_ftell(to_file,MYF(0));
- strpos=(uchar*) sort_keys;
- if (init_queue(&queue,(uint) (Tb-Fb)+1,offsetof(BUFFPEK,key),0,
- (int (*)(void *, byte *,byte *)) info->key_cmp,0))
- DBUG_RETURN(1);
- for (buffpek= Fb ; buffpek <= Tb && error != -1 ; buffpek++)
- {
- count+= buffpek->count;
- buffpek->base= strpos;
- buffpek->max_keys=maxcount;
- strpos+= (uint) (error=(int) read_to_buffer(from_file,buffpek,
- sort_length));
- queue_insert(&queue,(void*) buffpek);
- }
- if (error == -1)
- goto err;
- while (queue.elements > 1)
- {
- for (;;)
- {
- buffpek=(BUFFPEK*) queue_top(&queue);
- if (to_file)
- {
- if (my_fwrite(to_file,(byte*) buffpek->key,(uint) sort_length,
- MYF_RW | MY_WAIT_IF_FULL))
- {
- error=1; goto err;
- }
- }
- else
- {
- if ((*info->key_write)((void*) buffpek->key))
- {
- error=1; goto err;
- }
- }
- buffpek->key+=sort_length;
- if (! --buffpek->mem_count)
- {
- if (!(error=(int) read_to_buffer(from_file,buffpek,sort_length)))
- {
- uchar *base=buffpek->base;
- uint max_keys=buffpek->max_keys;
- VOID(queue_remove(&queue,0));
- /* Put room used by buffer to use in other buffer */
- for (refpek= (BUFFPEK**) &queue_top(&queue);
- refpek <= (BUFFPEK**) &queue_end(&queue);
- refpek++)
- {
- buffpek= *refpek;
- if (buffpek->base+buffpek->max_keys*sort_length == base)
- {
- buffpek->max_keys+=max_keys;
- break;
- }
- else if (base+max_keys*sort_length == buffpek->base)
- {
- buffpek->base=base;
- buffpek->max_keys+=max_keys;
- break;
- }
- }
- break; /* One buffer have been removed */
- }
- }
- queue_replaced(&queue); /* Top element has been replaced */
- }
- }
- buffpek=(BUFFPEK*) queue_top(&queue);
- buffpek->base=(uchar *) sort_keys;
- buffpek->max_keys=keys;
- do
- {
- if (to_file)
- {
- if (my_fwrite(to_file,(byte*) buffpek->key,
- (uint) (sort_length*buffpek->mem_count),
- MYF_RW | MY_WAIT_IF_FULL))
- {
- error=1; goto err;
- }
- }
- else
- {
- register uchar *end;
- strpos= buffpek->key;
- for (end=strpos+buffpek->mem_count*sort_length;
- strpos != end ;
- strpos+=sort_length)
- {
- if ((*info->key_write)((void*) strpos))
- {
- error=1; goto err;
- }
- }
- }
- }
- while ((error=(int) read_to_buffer(from_file,buffpek,sort_length)) != -1 &&
- error != 0);
- lastbuff->count=count;
- if (to_file)
- lastbuff->file_pos=to_start_filepos; /* New block starts here */
- err:
- delete_queue(&queue);
- DBUG_RETURN(error);
- } /* merge_buffers */
- /* Do a merge to output-file (save only positions) */
- static int NEAR_F merge_index(info,keys,sort_keys,buffpek,maxbuffer,tempfile)
- SORT_PARAM *info;
- uint keys;
- uchar **sort_keys;
- BUFFPEK *buffpek;
- int maxbuffer;
- FILE *tempfile;
- {
- DBUG_ENTER("merge_index");
- if (merge_buffers(info,keys,tempfile,(FILE*) 0,sort_keys,buffpek,buffpek,
- buffpek+maxbuffer))
- DBUG_RETURN(1);
- DBUG_RETURN(0);
- } /* merge_index */
- /* Make a pointer of arrays to keys */
- static char **make_char_array(fields,length,my_flag)
- register uint fields;
- uint length;
- myf my_flag;
- {
- register char **pos;
- char **old_pos,*char_pos;
- DBUG_ENTER("make_char_array");
- if ((old_pos= (char**) my_malloc( fields*(length+sizeof(char*)), my_flag)))
- {
- pos=old_pos; char_pos=((char*) (pos+fields)) -length;
- while (fields--)
- *(pos++) = (char_pos+= length);
- }
- DBUG_RETURN(old_pos);
- } /* make_char_array */
- /* |ppnar en tempor{rfil som kommer att raderas efter anv{nding */
- static FILE *opentemp(name)
- my_string name;
- {
- FILE *stream;
- reg1 my_string str_pos;
- DBUG_ENTER("opentemp");
- if (!(str_pos=my_tempnam(NullS,"ST",MYF(MY_WME))))
- DBUG_RETURN(0);
- VOID(strmov(name,str_pos));
- (*free)(str_pos); /* Inte via vanliga malloc */
- stream=my_fopen(name,(int) (O_RDWR | FILE_BINARY | O_CREAT | O_TEMPORARY),
- MYF(MY_WME));
- #if O_TEMPORARY == 0 && !defined(CANT_DELETE_OPEN_FILES)
- VOID(my_delete(name,MYF(MY_WME | ME_NOINPUT)));
- #endif
- DBUG_PRINT("exit",("stream: %lx",stream));
- DBUG_RETURN (stream);
- } /* opentemp */
- static void closetemp(char *name __attribute__((unused)) ,FILE *stream)
- {
- DBUG_ENTER("closetemp");
- if (stream)
- VOID(my_fclose(stream,MYF(MY_WME)));
- #ifdef CANT_DELETE_OPEN_FILES
- if (name)
- VOID(my_delete(name,MYF(MY_WME)));
- #endif
- DBUG_VOID_RETURN;
- } /* closetemp */