/* 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 #else #include #endif #include /* 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)); } 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 keys\n",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 keys\n",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 keys\n",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 */