home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / sql / filesort.cpp < prev    next >
C/C++ Source or Header  |  2000-11-20  |  27KB  |  963 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. /* Sorts a database */
  19.  
  20. #include "mysql_priv.h"
  21. #ifdef HAVE_STDDEF_H
  22. #include <stddef.h>            /* for macro offsetof */
  23. #endif
  24. #include <m_ctype.h>
  25. #ifndef THREAD
  26. #define SKIPP_DBUG_IN_FILESORT
  27. #endif
  28.     /* static variabels */
  29.  
  30. #define MERGEBUFF  7
  31. #define MERGEBUFF2 15
  32.  
  33.     /* How to write record_ref. */
  34.  
  35. #define WRITE_REF(file,from) \
  36. if (my_b_write((file),(byte*) (from),param->ref_length)) \
  37.   DBUG_RETURN(1);
  38.  
  39. typedef struct st_buffpek {        /* Struktur om sorteringsbuffrarna */
  40.   my_off_t file_pos;            /* Where we are in the sort file */
  41.   uchar *base,*key;            /* key pointers */
  42.   ha_rows count;            /* Number of rows in table */
  43.   ulong mem_count;            /* numbers of keys in memory */
  44.   ulong max_keys;            /* Max keys in buffert */
  45. } BUFFPEK;
  46.  
  47.  
  48. typedef struct st_sort_param {
  49.   uint sort_length;            /* Length of sortarg */
  50.   uint keys;                /* Max antal nycklar / buffert */
  51.   uint ref_length;            /* Length of record ref. */
  52.   ha_rows max_rows;
  53.   TABLE *sort_form;            /* For quicker make_sortkey */
  54.   SORT_FIELD *local_sortorder;
  55.   SORT_FIELD *end;
  56. #ifdef USE_STRCOLL
  57.   char* tmp_buffer;
  58. #endif
  59. } SORTPARAM;
  60.  
  61.     /* functions defined in this file */
  62.  
  63. static char **make_char_array(register uint fields, uint length, myf my_flag);
  64. static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
  65.                  uchar * *sort_keys,
  66.                  BUFFPEK *buffpek,uint *maxbuffer,
  67.                  IO_CACHE *tempfile,IO_CACHE *indexfile);
  68. static int write_keys(SORTPARAM *param,uchar * *sort_keys,
  69.               uint count,BUFFPEK *buffpek,
  70.               IO_CACHE *tempfile);
  71. static void make_sortkey(SORTPARAM *param,uchar *to,
  72.              byte *ref_pos);
  73. static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count);
  74. static int merge_many_buff(SORTPARAM *param,uchar * *sort_keys,
  75.                BUFFPEK *buffpek,
  76.                uint *maxbuffer, IO_CACHE *t_file);
  77. static uint read_to_buffer(IO_CACHE *fromfile,BUFFPEK *buffpek,
  78.                uint sort_length);
  79. static int merge_buffers(SORTPARAM *param,IO_CACHE *from_file,
  80.              IO_CACHE *to_file,uchar * *sort_keys,
  81.              BUFFPEK *lastbuff,BUFFPEK *Fb,
  82.              BUFFPEK *Tb,int flag);
  83. static int merge_index(SORTPARAM *param,uchar * *sort_keys,
  84.                BUFFPEK *buffpek,
  85.                uint maxbuffer,IO_CACHE *tempfile,
  86.                IO_CACHE *outfile);
  87. static uint sortlength(SORT_FIELD *sortorder,uint length);
  88.  
  89.     /* Makes a indexfil of recordnumbers of a sorted database */
  90.     /* outfile is reset before data is written to it, if it wasn't
  91.      open a new file is opened */
  92.  
  93. ha_rows filesort(TABLE **table, SORT_FIELD *sortorder, uint s_length,
  94.          SQL_SELECT *select, ha_rows special, ha_rows max_rows)
  95. {
  96.   int error;
  97.   uint memavl,old_memavl,maxbuffer,skr;
  98.   BUFFPEK *buffpek;
  99.   ha_rows records;
  100.   uchar **sort_keys;
  101.   IO_CACHE tempfile,*selected_records_file,*outfile;
  102.   SORTPARAM param;
  103.   DBUG_ENTER("filesort");
  104.   DBUG_EXECUTE("info",TEST_filesort(table,sortorder,s_length,special););
  105. #ifdef SKIPP_DBUG_IN_FILESORT
  106.   DBUG_PUSH("");        /* No DBUG here */
  107. #endif
  108.  
  109.   outfile= table[0]->io_cache;
  110.   my_b_clear(&tempfile);
  111.   buffpek= (BUFFPEK *) NULL; sort_keys= (uchar **) NULL; error= 1;
  112.   maxbuffer=1;
  113.   param.ref_length= table[0]->file->ref_length;
  114.   param.sort_length=sortlength(sortorder,s_length)+ param.ref_length;
  115.   param.max_rows= max_rows;
  116.  
  117.   if (select && select->quick)
  118.   {
  119.     statistic_increment(filesort_range_count, &LOCK_status);
  120.   }
  121.   else
  122.   {
  123.     statistic_increment(filesort_scan_count, &LOCK_status);
  124.   }
  125.   if (select && my_b_inited(&select->file))
  126.   {
  127.     records=special=select->records;        /* purecov: deadcode */
  128.     selected_records_file= &select->file;    /* purecov: deadcode */
  129.     reinit_io_cache(selected_records_file,READ_CACHE,0L,0,0); /* purecov: deadcode */
  130.   }
  131.   else if (special)
  132.   {
  133.     records=special;                /* purecov: deadcode */
  134.     selected_records_file= outfile;        /* purecov: deadcode */
  135.     reinit_io_cache(selected_records_file,READ_CACHE,0L,0,0); /* purecov: deadcode */
  136.   }
  137. #ifdef CAN_TRUST_RANGE
  138.   else if (select && select->quick && select->quick->records > 0L)
  139.   {
  140.     VOID(ha_info(&table[0]->form,0));    /* Get record-count */
  141.     records=min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
  142.         table[0]->file->records)+EXTRA_RECORDS;
  143.     selected_records_file=0;
  144.   }
  145. #endif
  146.   else
  147.   {
  148.     table[0]->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);/* Get record-count */
  149.     records=table[0]->file->estimate_number_of_rows();
  150.     selected_records_file= 0;
  151.   }
  152.   if (param.sort_length == param.ref_length && records > param.max_rows)
  153.     records=param.max_rows;            /* purecov: inspected */
  154.  
  155. #ifdef USE_STRCOLL
  156.   if (use_strcoll(default_charset_info) &&
  157.       !(param.tmp_buffer=my_malloc(param.sort_length,MYF(MY_WME))))
  158.     goto err;
  159. #endif
  160.  
  161.   memavl=sortbuff_size;
  162.   while (memavl >= MIN_SORT_MEMORY)
  163.   {
  164.     if ((ulonglong) (records+1)*(param.sort_length+sizeof(char*))+sizeof(BUFFPEK)*10 <
  165.     (ulonglong) memavl)
  166.       param.keys=(uint) records+1;
  167.     else
  168.     {
  169.       maxbuffer=1;
  170.       do
  171.       {
  172.     skr=maxbuffer;
  173.     if (memavl < sizeof(BUFFPEK)*maxbuffer)
  174.     {
  175.       my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
  176.       goto err;
  177.     }
  178.     param.keys=(memavl-sizeof(BUFFPEK)*maxbuffer)/
  179.       (param.sort_length+sizeof(char*));
  180.       }
  181.       while ((maxbuffer= (uint) (records/param.keys+1)) != skr);
  182.     }
  183.     if ((sort_keys= (uchar **) make_char_array(param.keys,param.sort_length,
  184.                            MYF(0))))
  185.       if ((buffpek = (BUFFPEK*) my_malloc((uint) sizeof(BUFFPEK)*
  186.                       (maxbuffer+10),
  187.                       MYF(0))))
  188.     break;
  189.       else
  190.     my_free((gptr) sort_keys,MYF(0));
  191.     old_memavl=memavl;
  192.     if ((memavl=memavl/4*3) < MIN_SORT_MEMORY && old_memavl > MIN_SORT_MEMORY)
  193.       memavl=MIN_SORT_MEMORY;
  194.   }
  195.   param.keys--;
  196.   maxbuffer+=10;            /* Some extra range */
  197.  
  198.   if (memavl < MIN_SORT_MEMORY)
  199.   {
  200.     my_error(ER_OUTOFMEMORY,MYF(ME_ERROR+ME_WAITTANG),sortbuff_size);
  201.     goto err;
  202.   }
  203.   param.sort_form= table[0];
  204.   param.end=(param.local_sortorder=sortorder)+s_length;
  205.   if ((records=find_all_keys(¶m,select,sort_keys,buffpek,&maxbuffer,
  206.                  &tempfile, selected_records_file)) ==
  207.       HA_POS_ERROR)
  208.     goto err;
  209.   if (maxbuffer == 0)            // The whole set is in memory
  210.   {
  211.     if (save_index(¶m,sort_keys,(uint) records))
  212.       goto err;
  213.   }
  214.   else
  215.   {
  216.     /* Open cached file if it isn't open */
  217.     if (! my_b_inited(outfile) &&
  218.     open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
  219.               MYF(MY_WME)))
  220.       goto err;
  221.     reinit_io_cache(outfile,WRITE_CACHE,0L,0,0);
  222.  
  223.     param.keys=((param.keys*(param.sort_length+sizeof(char*))) /
  224.         param.sort_length-1);
  225.     if (merge_many_buff(¶m,sort_keys,buffpek,&maxbuffer,&tempfile))
  226.       goto err;
  227.     if (flush_io_cache(&tempfile) ||
  228.     reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
  229.       goto err;
  230.     if (merge_index(¶m,sort_keys,buffpek,maxbuffer,&tempfile,outfile))
  231.       goto err;
  232.   }
  233.   if (records > param.max_rows)
  234.     records=param.max_rows;
  235.   error =0;
  236.  
  237.  err:
  238. #ifdef USE_STRCOLL
  239.   if (use_strcoll(default_charset_info))
  240.     x_free(param.tmp_buffer);
  241. #endif
  242.   x_free((gptr) sort_keys);
  243.   x_free((gptr) buffpek);
  244.   close_cached_file(&tempfile);
  245.   if (my_b_inited(outfile))
  246.   {
  247.     if (flush_io_cache(outfile))
  248.       error=1;
  249.     {
  250.       my_off_t save_pos=outfile->pos_in_file;
  251.       /* For following reads */
  252.       if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
  253.     error=1;
  254.       outfile->end_of_file=save_pos;
  255.     }
  256.   }
  257.   if (error)
  258.     my_error(ER_FILSORT_ABORT,MYF(ME_ERROR+ME_WAITTANG));
  259.   else
  260.     statistic_add(filesort_rows, records, &LOCK_status);
  261.  
  262. #ifdef SKIPP_DBUG_IN_FILESORT
  263.   DBUG_POP();            /* Ok to DBUG */
  264. #endif
  265.   DBUG_PRINT("exit",("records: %ld",records));
  266.   DBUG_RETURN(error ? HA_POS_ERROR : records);
  267. } /* filesort */
  268.  
  269.  
  270.     /* Make a array of string pointers */
  271.  
  272. static char **make_char_array(register uint fields, uint length, myf my_flag)
  273. {
  274.   register char **pos;
  275.   char **old_pos,*char_pos;
  276.   DBUG_ENTER("make_char_array");
  277.  
  278.   if ((old_pos= (char**) my_malloc((uint) fields*(length+sizeof(char*)),
  279.                     my_flag)))
  280.   {
  281.     pos=old_pos; char_pos=((char*) (pos+fields)) -length;
  282.     while (fields--) *(pos++) = (char_pos+= length);
  283.   }
  284.  
  285.   DBUG_RETURN(old_pos);
  286. } /* make_char_array */
  287.  
  288.  
  289.     /* Search after sort_keys and place them in a temp. file */
  290.  
  291. static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select,
  292.                  uchar **sort_keys,
  293.                  BUFFPEK *buffpek, uint *maxbuffer,
  294.                  IO_CACHE *tempfile, IO_CACHE *indexfile)
  295. {
  296.   int error,flag,quick_select;
  297.   uint idx,indexpos,ref_length;
  298.   byte *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
  299.   my_off_t record;
  300.   TABLE *sort_form;
  301.   volatile bool *killed= ¤t_thd->killed;
  302.   handler *file;
  303.   DBUG_ENTER("find_all_keys");
  304.  
  305.   idx=indexpos=0;
  306.   error=quick_select=0;
  307.   sort_form=param->sort_form;
  308.   file=sort_form->file;
  309.   ref_length=param->ref_length;
  310.   ref_pos= ref_buff;
  311.   quick_select=select && select->quick;
  312.   record=0;
  313.   flag= ((!indexfile && file->option_flag() & HA_REC_NOT_IN_SEQ)
  314.      || quick_select);
  315.   if (indexfile || flag)
  316.     ref_pos= &file->ref[0];
  317.   next_pos=ref_pos;
  318.   if (! indexfile && ! quick_select)
  319.   {
  320.     file->reset();            // QQ; Shouldn't be needed
  321.     if (sort_form->key_read)        // QQ Can be removed after the reset
  322.       file->extra(HA_EXTRA_KEYREAD);    // QQ is removed
  323.     next_pos=(byte*) 0;            /* Find records in sequence */
  324.     file->rnd_init();
  325.     file->extra(HA_EXTRA_CACHE);    /* Quicker reads */
  326.   }
  327.  
  328.   if (quick_select)
  329.     error=select->quick->init();
  330.  
  331.   if (!error)
  332.   for (;;)
  333.   {
  334.     if (quick_select)
  335.     {
  336.       if ((error=select->quick->get_next()))
  337.     break;
  338.       file->position(sort_form->record[0]);
  339.     }
  340.     else                    /* Not quick-select */
  341.     {
  342.       if (indexfile)
  343.       {
  344.     if (my_b_read(indexfile,(byte*) ref_pos,ref_length)) /* purecov: deadcode */
  345.     {
  346.       error= my_errno ? my_errno : -1;        /* Abort */
  347.       break;
  348.     }
  349.     if (TEST_IF_LASTREF(ref_pos,ref_length))
  350.     {
  351.       error=HA_ERR_END_OF_FILE;
  352.       break;
  353.     }
  354.     error=file->rnd_pos(sort_form->record[0],next_pos);
  355.       }
  356.       else
  357.       {
  358.     error=file->rnd_next(sort_form->record[0]);
  359.     if (!flag)
  360.     {
  361.       ha_store_ptr(ref_pos,ref_length,record); // Position to row
  362.       record+=sort_form->db_record_offset;
  363.     }
  364.     else
  365.       file->position(sort_form->record[0]);
  366.       }
  367.       if (error && error != HA_ERR_RECORD_DELETED)
  368.     break;
  369.     }
  370.     if (*killed)
  371.     {
  372.       DBUG_PRINT("info",("Sort killed by user"));
  373.       (void) file->extra(HA_EXTRA_NO_CACHE);
  374.       file->rnd_end();
  375.       DBUG_RETURN(HA_POS_ERROR);        /* purecov: inspected */
  376.     }
  377.     if (error == 0 && (!select || select->skipp_record() == 0))
  378.     {
  379.       if (idx == param->keys)
  380.       {
  381.     if (indexpos >= *maxbuffer ||
  382.         write_keys(param,sort_keys,idx,buffpek+indexpos,tempfile))
  383.           DBUG_RETURN(HA_POS_ERROR);
  384.     idx=0; indexpos++;
  385.     if (param->ref_length == param->sort_length &&
  386.         my_b_tell(tempfile)/param->sort_length >= param->max_rows)
  387.     {
  388.       error=HA_ERR_END_OF_FILE;
  389.       break;            /* Found enough records */
  390.     }
  391.       }
  392.       make_sortkey(param,sort_keys[idx++],ref_pos);
  393.     }
  394.   }
  395.   (void) file->extra(HA_EXTRA_NO_CACHE);    /* End cacheing of records */
  396.   file->rnd_end();
  397.   DBUG_PRINT("test",("error: %d  indexpos: %d",error,indexpos));
  398.   if (error != HA_ERR_END_OF_FILE)
  399.   {
  400.     file->print_error(error,MYF(ME_ERROR | ME_WAITTANG)); /* purecov: inspected */
  401.     DBUG_RETURN(HA_POS_ERROR);            /* purecov: inspected */
  402.   }
  403.   if (indexpos)
  404.     if (indexpos >= *maxbuffer ||
  405.     write_keys(param,sort_keys,idx,buffpek+indexpos,tempfile))
  406.       DBUG_RETURN(HA_POS_ERROR);        /* purecov: inspected */
  407.   *maxbuffer=indexpos;
  408.   DBUG_RETURN(my_b_inited(tempfile) ?
  409.           (ha_rows) (my_b_tell(tempfile)/param->sort_length) :
  410.           idx);
  411. } /* find_all_keys */
  412.  
  413.  
  414.     /* Skriver en buffert med nycklar till filen */
  415.  
  416. static int write_keys(SORTPARAM *param, register uchar **sort_keys, uint count,
  417.               BUFFPEK *buffpek, IO_CACHE *tempfile)
  418. {
  419.   uint sort_length;
  420.   DBUG_ENTER("write_keys");
  421.  
  422.   sort_length=param->sort_length;
  423. #ifdef MC68000
  424.   quicksort(sort_keys,count,sort_length);
  425. #else
  426.   my_string_ptr_sort((gptr) sort_keys,(uint) count,sort_length);
  427. #endif
  428.   if (!my_b_inited(tempfile) &&
  429.       open_cached_file(tempfile,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
  430.             MYF(MY_WME)))
  431.     DBUG_RETURN(1);                /* purecov: inspected */
  432.   buffpek->file_pos=my_b_tell(tempfile);
  433.   if ((ha_rows) count > param->max_rows)
  434.     count=(uint) param->max_rows;        /* purecov: inspected */
  435.   buffpek->count=(ha_rows) count;
  436.   for (uchar **end=sort_keys+count ; sort_keys != end ; sort_keys++)
  437.     if (my_b_write(tempfile,(byte*) *sort_keys,(uint) sort_length))
  438.       DBUG_RETURN(1);
  439.   DBUG_RETURN(0);
  440. } /* write_keys */
  441.  
  442.  
  443.     /* makes a sort-key from record */
  444.  
  445. static void make_sortkey(register SORTPARAM *param,
  446.              register uchar *to, byte *ref_pos)
  447. {
  448.   reg3 Field *field;
  449.   reg1 SORT_FIELD *sort_field;
  450.   reg5 uint length;
  451.  
  452.   for (sort_field=param->local_sortorder ;
  453.        sort_field != param->end ;
  454.        sort_field++)
  455.   {
  456.     if ((field=sort_field->field))
  457.     {                        // Field
  458.       if (field->maybe_null())
  459.       {
  460.     if (field->is_null())
  461.     {
  462.       if (sort_field->reverse)
  463.         bfill(to,sort_field->length+1,(char) 255);
  464.       else
  465.         bzero((char*) to,sort_field->length+1);
  466.       to+= sort_field->length+1;
  467.       continue;
  468.     }
  469.     else
  470.       *to++=1;
  471.       }
  472.       field->sort_string((char*) to,sort_field->length);
  473.     }
  474.     else
  475.     {                        // Item
  476.       Item *item=sort_field->item;
  477.       switch (sort_field->result_type) {
  478.       case STRING_RESULT:
  479.     {
  480.       if (item->maybe_null)
  481.         *to++=1;
  482.       /* All item->str() to use some extra byte for end null.. */
  483.       String tmp((char*) to,sort_field->length+4);
  484.       String *res=item->val_str(&tmp);
  485.       if (!res)
  486.       {
  487.         if (item->maybe_null)
  488.           bzero((char*) to-1,sort_field->length+1);
  489.         else
  490.         {
  491.           DBUG_PRINT("warning",
  492.              ("Got null on something that shouldn't be null"));
  493.           bzero((char*) to,sort_field->length);    // Avoid crash
  494.         }
  495.         break;
  496.       }
  497.       length=res->length();
  498.       int diff=(int) (sort_field->length-length);
  499.       if (diff < 0)
  500.       {
  501.         diff=0;                /* purecov: inspected */
  502.         length=sort_field->length;
  503.       }
  504. #ifdef USE_STRCOLL
  505.           if (use_strcoll(default_charset_info))
  506.           {
  507.             if (item->binary)
  508.             {
  509.               if (res->ptr() != (char*) to)
  510.                 memcpy(to,res->ptr(),length);
  511.               bzero((char*) to+length,diff);
  512.             }
  513.             else
  514.             {
  515.               char *from=(char*) res->ptr();
  516.               if ((unsigned char *)from == to)
  517.               {
  518.                 set_if_smaller(length,sort_field->length);
  519.                 memcpy(param->tmp_buffer,from,length);
  520.                 from=param->tmp_buffer;
  521.               }
  522.               uint tmp_length=my_strnxfrm(default_charset_info,
  523.                                           to,(unsigned char *) from,
  524.                                           sort_field->length,
  525.                                           length);
  526.               if (tmp_length < sort_field->length)
  527.                 bzero((char*) to+tmp_length,sort_field->length-tmp_length);
  528.             }
  529.           }
  530.           else
  531.           {
  532. #endif
  533.             if (res->ptr() != (char*) to)
  534.               memcpy(to,res->ptr(),length);
  535.             bzero((char *)to+length,diff);
  536.             if (!item->binary)
  537.               case_sort((char*) to,length);
  538. #ifdef USE_STRCOLL
  539.           }
  540. #endif
  541.       break;
  542.     }
  543.       case INT_RESULT:
  544.     {
  545.       longlong value=item->val_int();
  546.       if (item->maybe_null)
  547.         *to++=1;                /* purecov: inspected */
  548.       if (item->null_value)
  549.       {
  550.         if (item->maybe_null)
  551.           bzero((char*) to-1,sort_field->length+1);
  552.         else
  553.         {
  554.           DBUG_PRINT("warning",
  555.              ("Got null on something that shouldn't be null"));
  556.           bzero((char*) to,sort_field->length);
  557.         }
  558.         break;
  559.       }
  560. #if SIZEOF_LONG_LONG > 4
  561.       to[7]= (uchar) value;
  562.       to[6]= (uchar) (value >> 8);
  563.       to[5]= (uchar) (value >> 16);
  564.       to[4]= (uchar) (value >> 24);
  565.       to[3]= (uchar) (value >> 32);
  566.       to[2]= (uchar) (value >> 40);
  567.       to[1]= (uchar) (value >> 48);
  568.       to[0]= (uchar) (value >> 56) ^ 128;    // Fix sign
  569. #else
  570.       to[3]= (uchar) value;
  571.       to[2]= (uchar) (value >> 8);
  572.       to[1]= (uchar) (value >> 16);
  573.       to[0]= (uchar) (value >> 24) ^ 128;    // Fix sign
  574. #endif
  575.       break;
  576.     }
  577.       case REAL_RESULT:
  578.     {
  579.       double value=item->val();
  580.       if (item->null_value)
  581.       {
  582.         bzero((char*) to,sort_field->length+1);
  583.         to++;
  584.         break;
  585.       }
  586.       if (item->maybe_null)
  587.         *to++=1;
  588.       change_double_for_sort(value,(byte*) to);
  589.       break;
  590.     }
  591.       }
  592.     }
  593.     if (sort_field->reverse)
  594.     {                            /* Revers key */
  595.       length=sort_field->length;
  596.       while (length--)
  597.       {
  598.     *to = (uchar) (~ *to);
  599.     to++;
  600.       }
  601.     }
  602.     else
  603.       to+= sort_field->length;
  604.   }
  605.   memcpy((byte*) to,ref_pos,(size_s) param->ref_length);/* Save filepos last */
  606.   return;
  607. }
  608.  
  609.  
  610. static bool save_index(SORTPARAM *param, uchar **sort_keys, uint count)
  611. {
  612.   uint offset,ref_length;
  613.   byte *to;
  614.   DBUG_ENTER("save_index");
  615.  
  616.   my_string_ptr_sort((gptr) sort_keys,(uint) count,param->sort_length);
  617.   ref_length=param->ref_length;
  618.   offset=param->sort_length-ref_length;
  619.   if ((ha_rows) count > param->max_rows)
  620.     count=(uint) param->max_rows;
  621.   if (!(to=param->sort_form->record_pointers=
  622.     (byte*) my_malloc(ref_length*count,MYF(MY_WME))))
  623.     DBUG_RETURN(1);                /* purecov: inspected */
  624.   for (uchar **end=sort_keys+count ; sort_keys != end ; sort_keys++)
  625.   {
  626.     memcpy(to,*sort_keys+offset,ref_length);
  627.     to+=ref_length;
  628.   }
  629.   DBUG_RETURN(0);
  630. }
  631.  
  632.  
  633.     /* Merge buffers to make < MERGEBUFF2 buffers */
  634.  
  635. static int merge_many_buff(SORTPARAM *param, uchar **sort_keys,
  636.                BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
  637. {
  638.   register int i;
  639.   IO_CACHE t_file2,*from_file,*to_file,*temp;
  640.   BUFFPEK *lastbuff;
  641.   DBUG_ENTER("merge_many_buff");
  642.  
  643.   if (*maxbuffer < MERGEBUFF2)
  644.     DBUG_RETURN(0);                /* purecov: inspected */
  645.   if (flush_io_cache(t_file) ||
  646.       open_cached_file(&t_file2,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
  647.             MYF(MY_WME)))
  648.     DBUG_RETURN(1);                /* purecov: inspected */
  649.  
  650.   from_file= t_file ; to_file= &t_file2;
  651.   while (*maxbuffer >= MERGEBUFF2)
  652.   {
  653.     reinit_io_cache(from_file,READ_CACHE,0L,0,0);
  654.     reinit_io_cache(to_file,WRITE_CACHE,0L,0,0);
  655.     lastbuff=buffpek;
  656.     for (i=0 ; i <= (int) *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
  657.     {
  658.       if (merge_buffers(param,from_file,to_file,sort_keys,lastbuff++,
  659.             buffpek+i,buffpek+i+MERGEBUFF-1,0))
  660.     break;                    /* purecov: inspected */
  661.     }
  662.     if (merge_buffers(param,from_file,to_file,sort_keys,lastbuff++,
  663.               buffpek+i,buffpek+ *maxbuffer,0))
  664.       break;                    /* purecov: inspected */
  665.     if (flush_io_cache(to_file))
  666.       break;                    /* purecov: inspected */
  667.     temp=from_file; from_file=to_file; to_file=temp;
  668.     *maxbuffer= (uint) (lastbuff-buffpek)-1;
  669.   }
  670.   close_cached_file(to_file);            // This holds old result
  671.   if (to_file == t_file)
  672.     *t_file=t_file2;                // Copy result file
  673.  
  674.   DBUG_RETURN(*maxbuffer >= MERGEBUFF2);    /* Return 1 if interrupted */
  675. } /* merge_many_buff */
  676.  
  677.  
  678.     /* Read data to buffer */
  679.     /* This returns (uint) -1 if something goes wrong */
  680.  
  681. static uint read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
  682.                uint sort_length)
  683. {
  684.   register uint count;
  685.   uint length;
  686.  
  687.   if ((count=(uint) min((ha_rows) buffpek->max_keys,buffpek->count)))
  688.   {
  689.     if (my_pread(fromfile->file,(byte*) buffpek->base,
  690.          (length= sort_length*count),buffpek->file_pos,MYF_RW))
  691.       return((uint) -1);            /* purecov: inspected */
  692.     buffpek->key=buffpek->base;
  693.     buffpek->file_pos+= length;            /* New filepos */
  694.     buffpek->count-=    count;
  695.     buffpek->mem_count= count;
  696.   }
  697.   return (count*sort_length);
  698. } /* read_to_buffer */
  699.  
  700.  
  701.     /* Merge buffers to one buffer */
  702.  
  703. static int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
  704.              IO_CACHE *to_file, uchar **sort_keys,
  705.              BUFFPEK *lastbuff, BUFFPEK *Fb, BUFFPEK *Tb,
  706.              int flag)
  707. {
  708.   int error;
  709.   uint sort_length,offset;
  710.   ulong maxcount;
  711.   ha_rows count,max_rows;
  712.   my_off_t to_start_filepos;
  713.   uchar *strpos;
  714.   BUFFPEK *buffpek,**refpek;
  715.   QUEUE queue;
  716.   volatile bool *killed= ¤t_thd->killed;
  717.   DBUG_ENTER("merge_buffers");
  718.  
  719.   statistic_increment(filesort_merge_passes, &LOCK_status);
  720.  
  721.   count=error=0;
  722.   offset=param->sort_length-param->ref_length;
  723.   maxcount=(ulong) (param->keys/((uint) (Tb-Fb) +1));
  724.   to_start_filepos=my_b_tell(to_file);
  725.   strpos=(uchar*) sort_keys;
  726.   sort_length=param->sort_length;
  727.   max_rows=param->max_rows;
  728.  
  729.   if (init_queue(&queue,(uint) (Tb-Fb)+1,offsetof(BUFFPEK,key),0,
  730.          (int (*) (void *, byte *,byte*))
  731.          get_ptr_compare(sort_length),(void*) &sort_length))
  732.     DBUG_RETURN(1);                /* purecov: inspected */
  733.   for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
  734.   {
  735.     count+= buffpek->count;
  736.     buffpek->base= strpos;
  737.     buffpek->max_keys=maxcount;
  738.     strpos+= (uint) (error=(int) read_to_buffer(from_file,buffpek,
  739.                         sort_length));
  740.     if (error == -1)
  741.       goto err;                    /* purecov: inspected */
  742.     queue_insert(&queue,(byte*) buffpek);
  743.   }
  744.  
  745.   while (queue.elements > 1)
  746.   {
  747.     if (*killed)
  748.     {
  749.       error=1; goto err;            /* purecov: inspected */
  750.     }
  751.     for (;;)
  752.     {
  753.       buffpek=(BUFFPEK*) queue_top(&queue);
  754.       if (flag == 0)
  755.       {
  756.     if (my_b_write(to_file,(byte*) buffpek->key, sort_length))
  757.     {
  758.       error=1; goto err;            /* purecov: inspected */
  759.     }
  760.       }
  761.       else
  762.       {
  763.     WRITE_REF(to_file,(byte*) buffpek->key+offset);
  764.       }
  765.       if (!--max_rows)
  766.       {
  767.     error=0;                /* purecov: inspected */
  768.     goto end;                /* purecov: inspected */
  769.       }
  770.       buffpek->key+=sort_length;
  771.       if (! --buffpek->mem_count)
  772.       {
  773.     if (!(error=(int) read_to_buffer(from_file,buffpek,
  774.                      sort_length)))
  775.     {
  776.       uchar *base=buffpek->base;
  777.       ulong max_keys=buffpek->max_keys;
  778.  
  779.       VOID(queue_remove(&queue,0));
  780.  
  781.       /* Put room used by buffer to use in other buffer */
  782.       for (refpek= (BUFFPEK**) &queue_top(&queue);
  783.            refpek <= (BUFFPEK**) &queue_end(&queue);
  784.            refpek++)
  785.       {
  786.         buffpek= *refpek;
  787.         if (buffpek->base+buffpek->max_keys*sort_length == base)
  788.         {
  789.           buffpek->max_keys+=max_keys;
  790.           break;
  791.         }
  792.         else if (base+max_keys*sort_length == buffpek->base)
  793.         {
  794.           buffpek->base=base;
  795.           buffpek->max_keys+=max_keys;
  796.           break;
  797.         }
  798.       }
  799.       break;            /* One buffer have been removed */
  800.     }
  801.     else if (error == -1)
  802.       goto err;                /* purecov: inspected */
  803.       }
  804.       queue_replaced(&queue);        /* Top element has been replaced */
  805.     }
  806.   }
  807.   buffpek=(BUFFPEK*) queue_top(&queue);
  808.   buffpek->base=(uchar *) sort_keys;
  809.   buffpek->max_keys=param->keys;
  810.   do
  811.   {
  812.     if ((ha_rows) buffpek->mem_count > max_rows)
  813.     {                    /* Don't write too many records */
  814.       buffpek->mem_count=(uint) max_rows;
  815.       buffpek->count=0;            /* Don't read more */
  816.     }
  817.     if (flag == 0)
  818.     {
  819.       if (my_b_write(to_file,(byte*) buffpek->key,
  820.              (sort_length*buffpek->mem_count)))
  821.       {
  822.     error=1; goto err;            /* purecov: inspected */
  823.       }
  824.     }
  825.     else
  826.     {
  827.       register uchar *end;
  828.       strpos= buffpek->key+offset;
  829.       for (end=strpos+buffpek->mem_count*sort_length;
  830.        strpos != end ;
  831.        strpos+=sort_length)
  832.       {
  833.     WRITE_REF(to_file,strpos);
  834.       }
  835.     }
  836.   }
  837.   while ((error=(int) read_to_buffer(from_file,buffpek,sort_length))
  838.      != -1 && error != 0);
  839.  
  840. end:
  841.   lastbuff->count=min(count,param->max_rows);
  842.   lastbuff->file_pos=to_start_filepos;
  843. err:
  844.   delete_queue(&queue);
  845.   DBUG_RETURN(error);
  846. } /* merge_buffers */
  847.  
  848.  
  849.     /* Do a merge to output-file (save only positions) */
  850.  
  851. static int merge_index(SORTPARAM *param, uchar **sort_keys,
  852.                BUFFPEK *buffpek, uint maxbuffer,
  853.                IO_CACHE *tempfile, IO_CACHE *outfile)
  854. {
  855.   DBUG_ENTER("merge_index");
  856.   if (merge_buffers(param,tempfile,outfile,sort_keys,buffpek,buffpek,
  857.             buffpek+maxbuffer,1))
  858.     DBUG_RETURN(1);                /* purecov: inspected */
  859.   DBUG_RETURN(0);
  860. } /* merge_index */
  861.  
  862.  
  863.     /* Calculate length of sort key */
  864.  
  865. static uint
  866. sortlength(SORT_FIELD *sortorder, uint s_length)
  867. {
  868.   reg2 uint length;
  869.  
  870.   length=0;
  871.   for (; s_length-- ; sortorder++)
  872.   {
  873.     if (sortorder->field)
  874.     {
  875.       if (sortorder->field->type() == FIELD_TYPE_BLOB)
  876.     sortorder->length=max_item_sort_length;
  877.       else
  878.       {
  879.     sortorder->length=sortorder->field->pack_length();
  880. #ifdef USE_STRCOLL
  881.     if (use_strcoll(default_charset_info) && !sortorder->field->binary())
  882.       sortorder->length= sortorder->length*MY_STRXFRM_MULTIPLY;
  883. #endif
  884.       }
  885.       if (sortorder->field->maybe_null())
  886.     length++;                // Place for NULL marker
  887.     }
  888.     else
  889.     {
  890.       switch ((sortorder->result_type=sortorder->item->result_type())) {
  891.       case STRING_RESULT:
  892.     sortorder->length=sortorder->item->max_length;
  893. #ifdef USE_STRCOLL
  894.     if (use_strcoll(default_charset_info) && !sortorder->item->binary)
  895.       sortorder->length= sortorder->length*MY_STRXFRM_MULTIPLY;
  896. #endif
  897.     break;
  898.       case INT_RESULT:
  899. #if SIZEOF_LONG_LONG > 4
  900.     sortorder->length=8;            // Size of intern longlong
  901. #else
  902.     sortorder->length=4;
  903. #endif
  904.     break;
  905.       case REAL_RESULT:
  906.     sortorder->length=sizeof(double);
  907.     break;
  908.       }
  909.       if (sortorder->item->maybe_null)
  910.     length++;                // Place for NULL marker
  911.     }
  912.     set_if_smaller(sortorder->length,max_item_sort_length);
  913.     length+=sortorder->length;
  914.   }
  915.   sortorder->field= (Field*) 0;            // end marker
  916.   DBUG_PRINT("info",("sort_length: %d",length));
  917.   return length;
  918. }
  919.  
  920.  
  921. /*
  922. ** functions to change a double or float to a sortable string
  923. ** The following should work for IEEE
  924. */
  925.  
  926. #define DBL_EXP_DIG (sizeof(double)*8-DBL_MANT_DIG)
  927.  
  928. void change_double_for_sort(double nr,byte *to)
  929. {
  930.   uchar *tmp=(uchar*) to;
  931.   if (nr == 0.0)
  932.   {                        /* Change to zero string */
  933.     tmp[0]=(uchar) 128;
  934.     bzero((char*) tmp+1,sizeof(nr)-1);
  935.   }
  936.   else
  937.   {
  938. #ifdef WORDS_BIGENDIAN
  939.     memcpy_fixed(tmp,&nr,sizeof(nr));
  940. #else
  941.     {
  942.       uchar *ptr= (uchar*) &nr;
  943.       tmp[0]= ptr[7]; tmp[1]=ptr[6]; tmp[2]= ptr[5]; tmp[3]=ptr[4];
  944.       tmp[4]= ptr[3]; tmp[5]=ptr[2]; tmp[6]= ptr[1]; tmp[7]=ptr[0];
  945.     }
  946. #endif
  947.     if (tmp[0] & 128)                /* Negative */
  948.     {                        /* make complement */
  949.       uint i;
  950.       for (i=0 ; i < sizeof(nr); i++)
  951.     tmp[i]=tmp[i] ^ (uchar) 255;
  952.     }
  953.     else
  954.     {                    /* Set high and move exponent one up */
  955.       ushort exp_part=(((ushort) tmp[0] << 8) | (ushort) tmp[1] |
  956.                (ushort) 32768);
  957.       exp_part+= (ushort) 1 << (16-1-DBL_EXP_DIG);
  958.       tmp[0]= (uchar) (exp_part >> 8);
  959.       tmp[1]= (uchar) exp_part;
  960.     }
  961.   }
  962. }
  963.