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

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. /* Sorts a database */
  14. #include "mysql_priv.h"
  15. #ifdef HAVE_STDDEF_H
  16. #include <stddef.h> /* for macro offsetof */
  17. #endif
  18. #include <m_ctype.h>
  19. #include "sql_sort.h"
  20. #ifndef THREAD
  21. #define SKIP_DBUG_IN_FILESORT
  22. #endif
  23. /* How to write record_ref. */
  24. #define WRITE_REF(file,from) 
  25. if (my_b_write((file),(byte*) (from),param->ref_length)) 
  26.   DBUG_RETURN(1);
  27. /* functions defined in this file */
  28. static char **make_char_array(register uint fields, uint length, myf my_flag);
  29. static BUFFPEK *read_buffpek_from_file(IO_CACHE *buffer_file, uint count);
  30. static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
  31.      uchar * *sort_keys, IO_CACHE *buffer_file,
  32.      IO_CACHE *tempfile,IO_CACHE *indexfile);
  33. static int write_keys(SORTPARAM *param,uchar * *sort_keys,
  34.       uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
  35. static void make_sortkey(SORTPARAM *param,uchar *to, byte *ref_pos);
  36. static int merge_index(SORTPARAM *param,uchar *sort_buffer,
  37.        BUFFPEK *buffpek,
  38.        uint maxbuffer,IO_CACHE *tempfile,
  39.        IO_CACHE *outfile);
  40. static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count);
  41. static uint sortlength(SORT_FIELD *sortorder, uint s_length,
  42.        bool *multi_byte_charset);
  43. static SORT_ADDON_FIELD *get_addon_fields(THD *thd, Field **ptabfield,
  44.                                           uint sortlength, uint *plength);
  45. static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
  46.                                 byte *buff);
  47. /*
  48.   Sort a table
  49.   SYNOPSIS
  50.     filesort()
  51.     table Table to sort
  52.     sortorder How to sort the table
  53.     s_length Number of elements in sortorder
  54.     select condition to apply to the rows
  55.     special Not used.
  56. (This could be used to sort the rows pointed on by
  57. select->file)
  58.    examined_rows Store number of examined rows here
  59.   IMPLEMENTATION
  60.     Creates a set of pointers that can be used to read the rows
  61.     in sorted order. This should be done with the functions
  62.     in records.cc
  63.   
  64.   REQUIREMENTS
  65.     Before calling filesort, one must have done
  66.     table->file->info(HA_STATUS_VARIABLE)
  67.   RETURN
  68.     HA_POS_ERROR Error
  69.     # Number of rows
  70.     examined_rows will be set to number of examined rows
  71.     The result set is stored in table->io_cache or
  72.     table->record_pointers
  73. */
  74. ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
  75.  SQL_SELECT *select, ha_rows max_rows, ha_rows *examined_rows)
  76. {
  77.   int error;
  78.   ulong memavl, min_sort_memory;
  79.   uint maxbuffer;
  80.   BUFFPEK *buffpek;
  81.   ha_rows records= HA_POS_ERROR;
  82.   uchar **sort_keys;
  83.   IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile; 
  84.   SORTPARAM param;
  85.   bool multi_byte_charset;
  86.   DBUG_ENTER("filesort");
  87.   DBUG_EXECUTE("info",TEST_filesort(sortorder,s_length););
  88. #ifdef SKIP_DBUG_IN_FILESORT
  89.   DBUG_PUSH(""); /* No DBUG here */
  90. #endif
  91.   outfile= table->sort.io_cache;
  92.   my_b_clear(&tempfile);
  93.   my_b_clear(&buffpek_pointers);
  94.   buffpek=0;
  95.   sort_keys= (uchar **) NULL;
  96.   error= 1;
  97.   bzero((char*) &param,sizeof(param));
  98.   param.sort_length= sortlength(sortorder, s_length, &multi_byte_charset);
  99.   param.ref_length= table->file->ref_length;
  100.   param.addon_field= 0;
  101.   param.addon_length= 0;
  102.   if (!(table->tmp_table || table->fulltext_searched))
  103.   {
  104.     /* 
  105.       Get the descriptors of all fields whose values are appended 
  106.       to sorted fields and get its total length in param.spack_length.
  107.     */
  108.     param.addon_field= get_addon_fields(thd, table->field, 
  109.                                         param.sort_length,
  110.                                         &param.addon_length);
  111.   }
  112.   table->sort.addon_buf= 0;
  113.   table->sort.addon_length= param.addon_length;
  114.   table->sort.addon_field= param.addon_field;
  115.   table->sort.unpack= unpack_addon_fields;
  116.   if (param.addon_field)
  117.   {
  118.     param.res_length= param.addon_length;
  119.     if (!(table->sort.addon_buf= (byte *) my_malloc(param.addon_length,
  120.                                                     MYF(MY_WME))))
  121.       goto err;
  122.   }
  123.   else
  124.   {
  125.     param.res_length= param.ref_length;
  126.     /* 
  127.       The reference to the record is considered 
  128.       as an additional sorted field
  129.     */
  130.     param.sort_length+= param.ref_length;
  131.   }
  132.   param.rec_length= param.sort_length+param.addon_length;
  133.   param.max_rows= max_rows;
  134.   if (select && select->quick)
  135.   {
  136.     statistic_increment(filesort_range_count, &LOCK_status);
  137.   }
  138.   else
  139.   {
  140.     statistic_increment(filesort_scan_count, &LOCK_status);
  141.   }
  142. #ifdef CAN_TRUST_RANGE
  143.   if (select && select->quick && select->quick->records > 0L)
  144.   {
  145.     records=min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
  146. table->file->records)+EXTRA_RECORDS;
  147.     selected_records_file=0;
  148.   }
  149.   else
  150. #endif
  151.   {
  152.     records= table->file->estimate_rows_upper_bound();
  153.     /*
  154.       If number of records is not known, use as much of sort buffer 
  155.       as possible. 
  156.     */
  157.     if (records == HA_POS_ERROR)
  158.       records--;  // we use 'records+1' below.
  159.     selected_records_file= 0;
  160.   }
  161.   if (multi_byte_charset &&
  162.       !(param.tmp_buffer=my_malloc(param.sort_length,MYF(MY_WME))))
  163.     goto err;
  164.   memavl= thd->variables.sortbuff_size;
  165.   min_sort_memory= max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
  166.   while (memavl >= min_sort_memory)
  167.   {
  168.     ulong old_memavl;
  169.     ulong keys= memavl/(param.rec_length+sizeof(char*));
  170.     param.keys=(uint) min(records+1, keys);
  171.     if ((sort_keys= (uchar **) make_char_array(param.keys, param.rec_length,
  172.        MYF(0))))
  173.       break;
  174.     old_memavl=memavl;
  175.     if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
  176.       memavl= min_sort_memory;
  177.   }
  178.   if (memavl < min_sort_memory)
  179.   {
  180.     my_error(ER_OUTOFMEMORY,MYF(ME_ERROR+ME_WAITTANG),
  181.      thd->variables.sortbuff_size);
  182.     goto err;
  183.   }
  184.   if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
  185.        DISK_BUFFER_SIZE, MYF(MY_WME)))
  186.     goto err;
  187.   param.keys--;   /* TODO: check why we do this */
  188.   param.sort_form= table;
  189.   param.end=(param.local_sortorder=sortorder)+s_length;
  190.   if ((records=find_all_keys(&param,select,sort_keys, &buffpek_pointers,
  191.      &tempfile, selected_records_file)) ==
  192.       HA_POS_ERROR)
  193.     goto err;
  194.   maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
  195.   if (maxbuffer == 0) // The whole set is in memory
  196.   {
  197.     if (save_index(&param,sort_keys,(uint) records))
  198.       goto err;
  199.   }
  200.   else
  201.   {
  202.     if (!(buffpek=read_buffpek_from_file(&buffpek_pointers, maxbuffer)))
  203.       goto err;
  204.     close_cached_file(&buffpek_pointers);
  205. /* Open cached file if it isn't open */
  206.     if (! my_b_inited(outfile) &&
  207. open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
  208.   MYF(MY_WME)))
  209.       goto err;
  210.     reinit_io_cache(outfile,WRITE_CACHE,0L,0,0);
  211.     /*
  212.       Use also the space previously used by string pointers in sort_buffer
  213.       for temporary key storage.
  214.     */
  215.     param.keys=((param.keys*(param.rec_length+sizeof(char*))) /
  216. param.rec_length-1);
  217.     maxbuffer--; // Offset from 0
  218.     if (merge_many_buff(&param,(uchar*) sort_keys,buffpek,&maxbuffer,
  219. &tempfile))
  220.       goto err;
  221.     if (flush_io_cache(&tempfile) ||
  222. reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
  223.       goto err;
  224.     if (merge_index(&param,(uchar*) sort_keys,buffpek,maxbuffer,&tempfile,
  225.     outfile))
  226.       goto err;
  227.   }
  228.   if (records > param.max_rows)
  229.     records=param.max_rows;
  230.   error =0;
  231.  err:
  232.   if (param.tmp_buffer)
  233.     x_free(param.tmp_buffer);
  234.   x_free((gptr) sort_keys);
  235.   x_free((gptr) buffpek);
  236.   close_cached_file(&tempfile);
  237.   close_cached_file(&buffpek_pointers);
  238.   if (my_b_inited(outfile))
  239.   {
  240.     if (flush_io_cache(outfile))
  241.       error=1;
  242.     {
  243.       my_off_t save_pos=outfile->pos_in_file;
  244.       /* For following reads */
  245.       if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
  246. error=1;
  247.       outfile->end_of_file=save_pos;
  248.     }
  249.   }
  250.   if (error)
  251.     my_error(ER_FILSORT_ABORT,MYF(ME_ERROR+ME_WAITTANG));
  252.   else
  253.     statistic_add(filesort_rows, (ulong) records, &LOCK_status);
  254.   *examined_rows= param.examined_rows;
  255. #ifdef SKIP_DBUG_IN_FILESORT
  256.   DBUG_POP(); /* Ok to DBUG */
  257. #endif
  258.   DBUG_PRINT("exit",("records: %ld",records));
  259.   DBUG_RETURN(error ? HA_POS_ERROR : records);
  260. } /* filesort */
  261. void filesort_free_buffers(TABLE *table)
  262. {
  263.   if (table->sort.record_pointers)
  264.   {
  265.     my_free((gptr) table->sort.record_pointers,MYF(0));
  266.     table->sort.record_pointers=0;
  267.   }
  268.   if (table->sort.addon_buf)
  269.   {
  270.     my_free((char *) table->sort.addon_buf, MYF(0));
  271.     my_free((char *) table->sort.addon_field, MYF(MY_ALLOW_ZERO_PTR));
  272.     table->sort.addon_buf=0;
  273.     table->sort.addon_field=0;
  274.   }
  275. }
  276. /* Make a array of string pointers */
  277. static char **make_char_array(register uint fields, uint length, myf my_flag)
  278. {
  279.   register char **pos;
  280.   char **old_pos,*char_pos;
  281.   DBUG_ENTER("make_char_array");
  282.   if ((old_pos= (char**) my_malloc((uint) fields*(length+sizeof(char*)),
  283.     my_flag)))
  284.   {
  285.     pos=old_pos; char_pos=((char*) (pos+fields)) -length;
  286.     while (fields--) *(pos++) = (char_pos+= length);
  287.   }
  288.   DBUG_RETURN(old_pos);
  289. } /* make_char_array */
  290. /* Read 'count' number of buffer pointers into memory */
  291. static BUFFPEK *read_buffpek_from_file(IO_CACHE *buffpek_pointers, uint count)
  292. {
  293.   ulong length;
  294.   BUFFPEK *tmp;
  295.   DBUG_ENTER("read_buffpek_from_file");
  296.   tmp=(BUFFPEK*) my_malloc(length=sizeof(BUFFPEK)*count, MYF(MY_WME));
  297.   if (tmp)
  298.   {
  299.     if (reinit_io_cache(buffpek_pointers,READ_CACHE,0L,0,0) ||
  300. my_b_read(buffpek_pointers, (byte*) tmp, length))
  301.     {
  302.       my_free((char*) tmp, MYF(0));
  303.       tmp=0;
  304.     }
  305.   }
  306.   DBUG_RETURN(tmp);
  307. }
  308. /* 
  309.   Search after sort_keys and write them into tempfile.
  310.   SYNOPSIS
  311.     find_all_keys()
  312.       param             Sorting parameter
  313.       select            Use this to get source data
  314.       sort_keys         Array of pointers to sort key + addon buffers.
  315.       buffpek_pointers  File to write BUFFPEKs describing sorted segments
  316.                         in tempfile.
  317.       tempfile          File to write sorted sequences of sortkeys to.
  318.       indexfile         If !NULL, use it for source data (contains rowids)
  319.   
  320.   NOTE
  321.     Basic idea:
  322.       while (get_next_sortkey())
  323.       {
  324.         if (no free space in sort_keys buffers) 
  325.         {
  326.           sort sort_keys buffer;
  327.           dump sorted sequence to 'tempfile';
  328.           dump BUFFPEK describing sequence location into 'buffpek_pointers';
  329.         }
  330.         put sort key into 'sort_keys';
  331.       }
  332.       if (sort_keys has some elements && dumped at least once)
  333.         sort-dump-dump as above;
  334.       else
  335.         don't sort, leave sort_keys array to be sorted by caller.
  336.     
  337.      All produced sequences are guaranteed to be non-empty.
  338.   RETURN
  339.     Number of records written on success.
  340.     HA_POS_ERROR on error.
  341. */
  342. static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select,
  343.      uchar **sort_keys,
  344.      IO_CACHE *buffpek_pointers,
  345.      IO_CACHE *tempfile, IO_CACHE *indexfile)
  346. {
  347.   int error,flag,quick_select;
  348.   uint idx,indexpos,ref_length;
  349.   byte *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
  350.   my_off_t record;
  351.   TABLE *sort_form;
  352.   volatile my_bool *killed= &current_thd->killed;
  353.   handler *file;
  354.   DBUG_ENTER("find_all_keys");
  355.   DBUG_PRINT("info",("using: %s",(select?select->quick?"ranges":"where":"every row")));
  356.   idx=indexpos=0;
  357.   error=quick_select=0;
  358.   sort_form=param->sort_form;
  359.   file=sort_form->file;
  360.   ref_length=param->ref_length;
  361.   ref_pos= ref_buff;
  362.   quick_select=select && select->quick;
  363.   record=0;
  364.   flag= ((!indexfile && file->table_flags() & HA_REC_NOT_IN_SEQ)
  365.  || quick_select);
  366.   if (indexfile || flag)
  367.     ref_pos= &file->ref[0];
  368.   next_pos=ref_pos;
  369.   if (! indexfile && ! quick_select)
  370.   {
  371.     file->reset(); // QQ; Shouldn't be needed
  372.     if (sort_form->key_read) // QQ Can be removed after the reset
  373.       file->extra(HA_EXTRA_KEYREAD); // QQ is removed
  374.     next_pos=(byte*) 0; /* Find records in sequence */
  375.     file->ha_rnd_init(1);
  376.     file->extra_opt(HA_EXTRA_CACHE,
  377.     current_thd->variables.read_buff_size);
  378.   }
  379.   for (;;)
  380.   {
  381.     if (quick_select)
  382.     {
  383.       if ((error=select->quick->get_next()))
  384. break;
  385.       file->position(sort_form->record[0]);
  386.     }
  387.     else /* Not quick-select */
  388.     {
  389.       if (indexfile)
  390.       {
  391. if (my_b_read(indexfile,(byte*) ref_pos,ref_length)) /* purecov: deadcode */
  392. {
  393.   error= my_errno ? my_errno : -1; /* Abort */
  394.   break;
  395. }
  396. error=file->rnd_pos(sort_form->record[0],next_pos);
  397.       }
  398.       else
  399.       {
  400. error=file->rnd_next(sort_form->record[0]);
  401. if (!flag)
  402. {
  403.   ha_store_ptr(ref_pos,ref_length,record); // Position to row
  404.   record+=sort_form->db_record_offset;
  405. }
  406. else if (!error)
  407.   file->position(sort_form->record[0]);
  408.       }
  409.       if (error && error != HA_ERR_RECORD_DELETED)
  410. break;
  411.     }
  412.     if (*killed)
  413.     {
  414.       DBUG_PRINT("info",("Sort killed by user"));
  415.       if (!indexfile && !quick_select)
  416.       {
  417.         (void) file->extra(HA_EXTRA_NO_CACHE);
  418.         file->ha_rnd_end();
  419.       }
  420.       DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
  421.     }
  422.     if (error == 0)
  423.       param->examined_rows++;
  424.     if (error == 0 && (!select || select->skip_record() == 0))
  425.     {
  426.       if (idx == param->keys)
  427.       {
  428. if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
  429.   DBUG_RETURN(HA_POS_ERROR);
  430. idx=0;
  431. indexpos++;
  432.       }
  433.       make_sortkey(param,sort_keys[idx++],ref_pos);
  434.     }
  435.     else
  436.       file->unlock_row();
  437.   }
  438.   (void) file->extra(HA_EXTRA_NO_CACHE); /* End cacheing of records */
  439.   if (!next_pos)
  440.     file->ha_rnd_end();
  441.   DBUG_PRINT("test",("error: %d  indexpos: %d",error,indexpos));
  442.   if (error != HA_ERR_END_OF_FILE)
  443.   {
  444.     file->print_error(error,MYF(ME_ERROR | ME_WAITTANG)); /* purecov: inspected */
  445.     DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
  446.   }
  447.   if (indexpos && idx &&
  448.       write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
  449.     DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
  450.   DBUG_RETURN(my_b_inited(tempfile) ?
  451.       (ha_rows) (my_b_tell(tempfile)/param->rec_length) :
  452.       idx);
  453. } /* find_all_keys */
  454. /*
  455.   Sort the buffer and write:
  456.     1) the sorted sequence to tempfile
  457.     2) a BUFFPEK describing the sorted sequence position to buffpek_pointers
  458.   (was: Skriver en buffert med nycklar till filen)
  459.   SYNOPSIS
  460.     write_keys()
  461.       param             Sort parameters
  462.       sort_keys         Array of pointers to keys to sort
  463.       count             Number of elements in sort_keys array 
  464.       buffpek_pointers  One 'BUFFPEK' struct will be written into this file.
  465.                         The BUFFPEK::{file_pos, count} will indicate where 
  466.                         the sorted data was stored.
  467.       tempfile          The sorted sequence will be written into this file.
  468.     
  469.   RETURN
  470.     0 OK
  471.     1 Error
  472. */
  473. static int
  474. write_keys(SORTPARAM *param, register uchar **sort_keys, uint count,
  475.            IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
  476. {
  477.   uint sort_length, rec_length;
  478.   uchar **end;
  479.   BUFFPEK buffpek;
  480.   DBUG_ENTER("write_keys");
  481.   sort_length= param->sort_length;
  482.   rec_length= param->rec_length;
  483. #ifdef MC68000
  484.   quicksort(sort_keys,count,sort_length);
  485. #else
  486.   my_string_ptr_sort((gptr) sort_keys, (uint) count, sort_length);
  487. #endif
  488.   if (!my_b_inited(tempfile) &&
  489.       open_cached_file(tempfile, mysql_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
  490.                        MYF(MY_WME)))
  491.     goto err;                                        /* purecov: inspected */
  492.   buffpek.file_pos= my_b_tell(tempfile);
  493.   if ((ha_rows) count > param->max_rows)
  494.     count=(uint) param->max_rows;                /* purecov: inspected */
  495.   buffpek.count=(ha_rows) count;
  496.   for (end=sort_keys+count ; sort_keys != end ; sort_keys++)
  497.     if (my_b_write(tempfile, (byte*) *sort_keys, (uint) rec_length))
  498.       goto err;
  499.   if (my_b_write(buffpek_pointers, (byte*) &buffpek, sizeof(buffpek)))
  500.     goto err;
  501.   DBUG_RETURN(0);
  502. err:
  503.   DBUG_RETURN(1);
  504. } /* write_keys */
  505. /* makes a sort-key from record */
  506. static void make_sortkey(register SORTPARAM *param,
  507.  register uchar *to, byte *ref_pos)
  508. {
  509.   reg3 Field *field;
  510.   reg1 SORT_FIELD *sort_field;
  511.   reg5 uint length;
  512.   for (sort_field=param->local_sortorder ;
  513.        sort_field != param->end ;
  514.        sort_field++)
  515.   {
  516.     bool maybe_null=0;
  517.     if ((field=sort_field->field))
  518.     { // Field
  519.       if (field->maybe_null())
  520.       {
  521. if (field->is_null())
  522. {
  523.   if (sort_field->reverse)
  524.     bfill(to,sort_field->length+1,(char) 255);
  525.   else
  526.     bzero((char*) to,sort_field->length+1);
  527.   to+= sort_field->length+1;
  528.   continue;
  529. }
  530. else
  531.   *to++=1;
  532.       }
  533.       field->sort_string((char*) to,sort_field->length);
  534.     }
  535.     else
  536.     { // Item
  537.       Item *item=sort_field->item;
  538.       switch (sort_field->result_type) {
  539.       case STRING_RESULT:
  540. {
  541.           CHARSET_INFO *cs=item->collation.collation;
  542.   char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 : ' ');
  543.   if ((maybe_null=item->maybe_null))
  544.     *to++=1;
  545.   /* All item->str() to use some extra byte for end null.. */
  546.   String tmp((char*) to,sort_field->length+4,cs);
  547.   String *res=item->val_str(&tmp);
  548.   if (!res)
  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); // Avoid crash
  557.     }
  558.     break;
  559.   }
  560.   length=res->length();
  561.   int diff=(int) (sort_field->length-length);
  562.   if (diff < 0)
  563.   {
  564.     diff=0; /* purecov: inspected */
  565.     length=sort_field->length;
  566.   }
  567.           if (sort_field->need_strxnfrm)
  568.           {
  569.     char *from=(char*) res->ptr();
  570.     if ((unsigned char *)from == to)
  571.     {
  572.       set_if_smaller(length,sort_field->length);
  573.       memcpy(param->tmp_buffer,from,length);
  574.       from=param->tmp_buffer;
  575.     }
  576.     uint tmp_length=my_strnxfrm(cs,to,sort_field->length,
  577. (unsigned char *) from, length);
  578.             DBUG_ASSERT(tmp_length == sort_field->length);
  579.           }
  580.           else
  581.           {
  582.              my_strnxfrm(cs,(uchar*)to,length,(const uchar*)res->ptr(),length);
  583.              cs->cset->fill(cs, (char *)to+length,diff,fill_char);
  584.           }
  585.   break;
  586. }
  587.       case INT_RESULT:
  588. {
  589.   longlong value=item->val_int();
  590.   if ((maybe_null=item->maybe_null))
  591.     *to++=1; /* purecov: inspected */
  592.   if (item->null_value)
  593.   {
  594.     if (item->maybe_null)
  595.       bzero((char*) to-1,sort_field->length+1);
  596.     else
  597.     {
  598.       DBUG_PRINT("warning",
  599.  ("Got null on something that shouldn't be null"));
  600.       bzero((char*) to,sort_field->length);
  601.     }
  602.     break;
  603.   }
  604. #if SIZEOF_LONG_LONG > 4
  605.   to[7]= (uchar) value;
  606.   to[6]= (uchar) (value >> 8);
  607.   to[5]= (uchar) (value >> 16);
  608.   to[4]= (uchar) (value >> 24);
  609.   to[3]= (uchar) (value >> 32);
  610.   to[2]= (uchar) (value >> 40);
  611.   to[1]= (uchar) (value >> 48);
  612.           if (item->unsigned_flag)                    /* Fix sign */
  613.             to[0]= (uchar) (value >> 56);
  614.           else
  615.             to[0]= (uchar) (value >> 56) ^ 128; /* Reverse signbit */
  616. #else
  617.   to[3]= (uchar) value;
  618.   to[2]= (uchar) (value >> 8);
  619.   to[1]= (uchar) (value >> 16);
  620.           if (item->unsigned_flag)                    /* Fix sign */
  621.             to[0]= (uchar) (value >> 24);
  622.           else
  623.             to[0]= (uchar) (value >> 24) ^ 128; /* Reverse signbit */
  624. #endif
  625.   break;
  626. }
  627.       case REAL_RESULT:
  628. {
  629.   double value=item->val();
  630.   if ((maybe_null=item->null_value))
  631.   {
  632.     bzero((char*) to,sort_field->length+1);
  633.     to++;
  634.     break;
  635.   }
  636.   if ((maybe_null=item->maybe_null))
  637.     *to++=1;
  638.   change_double_for_sort(value,(byte*) to);
  639.   break;
  640. }
  641.       case ROW_RESULT:
  642.       default: 
  643. // This case should never be choosen
  644. DBUG_ASSERT(0);
  645. break;
  646.       }
  647.     }
  648.     if (sort_field->reverse)
  649.     { /* Revers key */
  650.       if (maybe_null)
  651.         to[-1]= ~to[-1];
  652.       length=sort_field->length;
  653.       while (length--)
  654.       {
  655. *to = (uchar) (~ *to);
  656. to++;
  657.       }
  658.     }
  659.     else
  660.       to+= sort_field->length;
  661.   }
  662.   if (param->addon_field)
  663.   {
  664.     /* 
  665.       Save field values appended to sorted fields.
  666.       First null bit indicators are appended then field values follow.
  667.       In this implementation we use fixed layout for field values -
  668.       the same for all records.
  669.     */
  670.     SORT_ADDON_FIELD *addonf= param->addon_field;
  671.     uchar *nulls= to;
  672.     DBUG_ASSERT(addonf);
  673.     bzero((char *) nulls, addonf->offset);
  674.     to+= addonf->offset;
  675.     for ( ; (field= addonf->field) ; addonf++)
  676.     {
  677.       if (addonf->null_bit && field->is_null())
  678.       {
  679.         nulls[addonf->null_offset]|= addonf->null_bit;
  680. #ifdef HAVE_purify
  681. bzero(to, addonf->length);
  682. #endif
  683.       }
  684.       else
  685.       {
  686.         uchar *end= (uchar*) field->pack((char *) to, field->ptr);
  687. #ifdef HAVE_purify
  688. uint length= (uint) ((to + addonf->length) - end);
  689. DBUG_ASSERT((int) length >= 0);
  690. if (length)
  691.   bzero(end, length);
  692. #endif
  693.       }
  694.       to+= addonf->length;
  695.     }
  696.   }
  697.   else
  698.   {
  699.     /* Save filepos last */
  700.     memcpy((byte*) to, ref_pos, (size_s) param->ref_length);
  701.   }
  702.   return;
  703. }
  704. static bool save_index(SORTPARAM *param, uchar **sort_keys, uint count)
  705. {
  706.   uint offset,res_length;
  707.   byte *to;
  708.   DBUG_ENTER("save_index");
  709.   my_string_ptr_sort((gptr) sort_keys, (uint) count, param->sort_length);
  710.   res_length= param->res_length;
  711.   offset= param->rec_length-res_length;
  712.   if ((ha_rows) count > param->max_rows)
  713.     count=(uint) param->max_rows;
  714.   if (!(to= param->sort_form->sort.record_pointers=
  715.         (byte*) my_malloc(res_length*count, MYF(MY_WME))))
  716.     DBUG_RETURN(1);                 /* purecov: inspected */
  717.   for (uchar **end= sort_keys+count ; sort_keys != end ; sort_keys++)
  718.   {
  719.     memcpy(to, *sort_keys+offset, res_length);
  720.     to+= res_length;
  721.   }
  722.   DBUG_RETURN(0);
  723. }
  724. /* Merge buffers to make < MERGEBUFF2 buffers */
  725. int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
  726.     BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
  727. {
  728.   register int i;
  729.   IO_CACHE t_file2,*from_file,*to_file,*temp;
  730.   BUFFPEK *lastbuff;
  731.   DBUG_ENTER("merge_many_buff");
  732.   if (*maxbuffer < MERGEBUFF2)
  733.     DBUG_RETURN(0); /* purecov: inspected */
  734.   if (flush_io_cache(t_file) ||
  735.       open_cached_file(&t_file2,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
  736. MYF(MY_WME)))
  737.     DBUG_RETURN(1); /* purecov: inspected */
  738.   from_file= t_file ; to_file= &t_file2;
  739.   while (*maxbuffer >= MERGEBUFF2)
  740.   {
  741.     reinit_io_cache(from_file,READ_CACHE,0L,0,0);
  742.     reinit_io_cache(to_file,WRITE_CACHE,0L,0,0);
  743.     lastbuff=buffpek;
  744.     for (i=0 ; i <= (int) *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
  745.     {
  746.       if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
  747. buffpek+i,buffpek+i+MERGEBUFF-1,0))
  748. break; /* purecov: inspected */
  749.     }
  750.     if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
  751.       buffpek+i,buffpek+ *maxbuffer,0))
  752.       break; /* purecov: inspected */
  753.     if (flush_io_cache(to_file))
  754.       break; /* purecov: inspected */
  755.     temp=from_file; from_file=to_file; to_file=temp;
  756.     setup_io_cache(from_file);
  757.     setup_io_cache(to_file);
  758.     *maxbuffer= (uint) (lastbuff-buffpek)-1;
  759.   }
  760.   close_cached_file(to_file); // This holds old result
  761.   if (to_file == t_file)
  762.   {
  763.     *t_file=t_file2; // Copy result file
  764.     setup_io_cache(t_file);
  765.   }
  766.   DBUG_RETURN(*maxbuffer >= MERGEBUFF2); /* Return 1 if interrupted */
  767. } /* merge_many_buff */
  768. /* Read data to buffer */
  769. /* This returns (uint) -1 if something goes wrong */
  770. uint read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
  771.     uint rec_length)
  772. {
  773.   register uint count;
  774.   uint length;
  775.   if ((count=(uint) min((ha_rows) buffpek->max_keys,buffpek->count)))
  776.   {
  777.     if (my_pread(fromfile->file,(byte*) buffpek->base,
  778.  (length= rec_length*count),buffpek->file_pos,MYF_RW))
  779.       return((uint) -1); /* purecov: inspected */
  780.     buffpek->key=buffpek->base;
  781.     buffpek->file_pos+= length; /* New filepos */
  782.     buffpek->count-= count;
  783.     buffpek->mem_count= count;
  784.   }
  785.   return (count*rec_length);
  786. } /* read_to_buffer */
  787. /* 
  788.   Merge buffers to one buffer
  789.   SYNOPSIS
  790.     merge_buffers()
  791.       param        Sort parameter
  792.       from_file    File with source data (BUFFPEKs point to this file)
  793.       to_file      File to write the sorted result data.
  794.       sort_buffer  Buffer for data to store up to MERGEBUFF2 sort keys.
  795.       lastbuff     OUT Store here BUFFPEK describing data written to to_file                   
  796.       Fb           First element in source BUFFPEKs array
  797.       Tb           Last element in source BUFFPEKs array
  798.       flag
  799.   RETURN
  800.     0     - OK
  801.     other - error
  802. */
  803. int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
  804.                   IO_CACHE *to_file, uchar *sort_buffer,
  805.                   BUFFPEK *lastbuff, BUFFPEK *Fb, BUFFPEK *Tb,
  806.                   int flag)
  807. {
  808.   int error;
  809.   uint rec_length,sort_length,res_length,offset;
  810.   ulong maxcount;
  811.   ha_rows max_rows,org_max_rows;
  812.   my_off_t to_start_filepos;
  813.   uchar *strpos;
  814.   BUFFPEK *buffpek,**refpek;
  815.   QUEUE queue;
  816.   qsort2_cmp cmp;
  817.   volatile my_bool *killed= &current_thd->killed;
  818.   my_bool not_killable;
  819.   DBUG_ENTER("merge_buffers");
  820.   statistic_increment(filesort_merge_passes, &LOCK_status);
  821.   if (param->not_killable)
  822.   {
  823.     killed= &not_killable;
  824.     not_killable= 0;
  825.   }
  826.   error=0;
  827.   rec_length= param->rec_length;
  828.   res_length= param->res_length;
  829.   sort_length= param->sort_length;
  830.   offset= rec_length-res_length;
  831.   maxcount= (ulong) (param->keys/((uint) (Tb-Fb) +1));
  832.   to_start_filepos= my_b_tell(to_file);
  833.   strpos= (uchar*) sort_buffer;
  834.   org_max_rows=max_rows= param->max_rows;
  835.   /* The following will fire if there is not enough space in sort_buffer */
  836.   DBUG_ASSERT(maxcount!=0);
  837.   
  838.   if (init_queue(&queue, (uint) (Tb-Fb)+1, offsetof(BUFFPEK,key), 0,
  839.                  (queue_compare) (cmp= get_ptr_compare(sort_length)),
  840.                  (void*) &sort_length))
  841.     DBUG_RETURN(1);                                /* purecov: inspected */
  842.   for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
  843.   {
  844.     buffpek->base= strpos;
  845.     buffpek->max_keys= maxcount;
  846.     strpos+= (uint) (error= (int) read_to_buffer(from_file, buffpek,
  847.                                                                          rec_length));
  848.     if (error == -1)
  849.       goto err; /* purecov: inspected */
  850.     buffpek->max_keys= buffpek->mem_count; // If less data in buffers than expected
  851.     queue_insert(&queue, (byte*) buffpek);
  852.   }
  853.   if (param->unique_buff)
  854.   {
  855.     /* 
  856.        Called by Unique::get()
  857.        Copy the first argument to param->unique_buff for unique removal.
  858.        Store it also in 'to_file'.
  859.        This is safe as we know that there is always more than one element
  860.        in each block to merge (This is guaranteed by the Unique:: algorithm
  861.     */
  862.     buffpek= (BUFFPEK*) queue_top(&queue);
  863.     memcpy(param->unique_buff, buffpek->key, rec_length);
  864.     if (my_b_write(to_file, (byte*) buffpek->key, rec_length))
  865.     {
  866.       error=1; goto err;                        /* purecov: inspected */
  867.     }
  868.     buffpek->key+= rec_length;
  869.     buffpek->mem_count--;
  870.     if (!--max_rows)
  871.     {
  872.       error= 0;                                       /* purecov: inspected */
  873.       goto end;                                       /* purecov: inspected */
  874.     }
  875.     queue_replaced(&queue);                        // Top element has been used
  876.   }
  877.   else
  878.     cmp= 0;                                        // Not unique
  879.   while (queue.elements > 1)
  880.   {
  881.     if (*killed)
  882.     {
  883.       error= 1; goto err;                        /* purecov: inspected */
  884.     }
  885.     for (;;)
  886.     {
  887.       buffpek= (BUFFPEK*) queue_top(&queue);
  888.       if (cmp)                                        // Remove duplicates
  889.       {
  890.         if (!(*cmp)(&sort_length, &(param->unique_buff),
  891.                     (uchar**) &buffpek->key))
  892.               goto skip_duplicate;
  893.             memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length);
  894.       }
  895.       if (flag == 0)
  896.       {
  897.         if (my_b_write(to_file,(byte*) buffpek->key, rec_length))
  898.         {
  899.           error=1; goto err;                        /* purecov: inspected */
  900.         }
  901.       }
  902.       else
  903.       {
  904.         if (my_b_write(to_file, (byte*) buffpek->key+offset, res_length))
  905.         {
  906.           error=1; goto err;                        /* purecov: inspected */
  907.         }
  908.       }
  909.       if (!--max_rows)
  910.       {
  911.         error= 0;                               /* purecov: inspected */
  912.         goto end;                               /* purecov: inspected */
  913.       }
  914.     skip_duplicate:
  915.       buffpek->key+= rec_length;
  916.       if (! --buffpek->mem_count)
  917.       {
  918.         if (!(error= (int) read_to_buffer(from_file,buffpek,
  919.                                           rec_length)))
  920.         {
  921.           uchar *base= buffpek->base;
  922.           ulong max_keys= buffpek->max_keys;
  923.           VOID(queue_remove(&queue,0));
  924.           /* Put room used by buffer to use in other buffer */
  925.           for (refpek= (BUFFPEK**) &queue_top(&queue);
  926.                refpek <= (BUFFPEK**) &queue_end(&queue);
  927.                refpek++)
  928.           {
  929.             buffpek= *refpek;
  930.             if (buffpek->base+buffpek->max_keys*rec_length == base)
  931.             {
  932.               buffpek->max_keys+= max_keys;
  933.               break;
  934.             }
  935.             else if (base+max_keys*rec_length == buffpek->base)
  936.             {
  937.               buffpek->base= base;
  938.               buffpek->max_keys+= max_keys;
  939.               break;
  940.             }
  941.           }
  942.           break;                        /* One buffer have been removed */
  943.         }
  944.         else if (error == -1)
  945.           goto err;                        /* purecov: inspected */
  946.       }
  947.       queue_replaced(&queue);              /* Top element has been replaced */
  948.     }
  949.   }
  950.   buffpek= (BUFFPEK*) queue_top(&queue);
  951.   buffpek->base= sort_buffer;
  952.   buffpek->max_keys= param->keys;
  953.   /*
  954.     As we know all entries in the buffer are unique, we only have to
  955.     check if the first one is the same as the last one we wrote
  956.   */
  957.   if (cmp)
  958.   {
  959.     if (!(*cmp)(&sort_length, &(param->unique_buff), (uchar**) &buffpek->key))
  960.     {
  961.       buffpek->key+= rec_length;         // Remove duplicate
  962.       --buffpek->mem_count;
  963.     }
  964.   }
  965.   do
  966.   {
  967.     if ((ha_rows) buffpek->mem_count > max_rows)
  968.     {                                        /* Don't write too many records */
  969.       buffpek->mem_count= (uint) max_rows;
  970.       buffpek->count= 0;                        /* Don't read more */
  971.     }
  972.     max_rows-= buffpek->mem_count;
  973.     if (flag == 0)
  974.     {
  975.       if (my_b_write(to_file,(byte*) buffpek->key,
  976.                      (rec_length*buffpek->mem_count)))
  977.       {
  978.         error= 1; goto err;                        /* purecov: inspected */
  979.       }
  980.     }
  981.     else
  982.     {
  983.       register uchar *end;
  984.       strpos= buffpek->key+offset;
  985.       for (end= strpos+buffpek->mem_count*rec_length ;
  986.            strpos != end ;
  987.            strpos+= rec_length)
  988.       {     
  989.         if (my_b_write(to_file, (byte *) strpos, res_length))
  990.         {
  991.           error=1; goto err;                        
  992.         }
  993.       }
  994.     }
  995.   }
  996.   while ((error=(int) read_to_buffer(from_file,buffpek, rec_length))
  997.          != -1 && error != 0);
  998. end:
  999.   lastbuff->count= min(org_max_rows-max_rows, param->max_rows);
  1000.   lastbuff->file_pos= to_start_filepos;
  1001. err:
  1002.   delete_queue(&queue);
  1003.   DBUG_RETURN(error);
  1004. } /* merge_buffers */
  1005. /* Do a merge to output-file (save only positions) */
  1006. static int merge_index(SORTPARAM *param, uchar *sort_buffer,
  1007.        BUFFPEK *buffpek, uint maxbuffer,
  1008.        IO_CACHE *tempfile, IO_CACHE *outfile)
  1009. {
  1010.   DBUG_ENTER("merge_index");
  1011.   if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
  1012.     buffpek+maxbuffer,1))
  1013.     DBUG_RETURN(1); /* purecov: inspected */
  1014.   DBUG_RETURN(0);
  1015. } /* merge_index */
  1016. /*
  1017.   Calculate length of sort key
  1018.   SYNOPSIS
  1019.     sortlength()
  1020.     sortorder Order of items to sort
  1021.     uint s_length Number of items to sort
  1022.     multi_byte_charset  (out)
  1023. Set to 1 if we are using multi-byte charset
  1024. (In which case we have to use strxnfrm())
  1025.   NOTES
  1026.     sortorder->length is updated for each sort item
  1027.     sortorder->need_strxnfrm is set 1 if we have to use strxnfrm
  1028.   RETURN
  1029.     Total length of sort buffer in bytes
  1030. */
  1031. static uint
  1032. sortlength(SORT_FIELD *sortorder, uint s_length, bool *multi_byte_charset)
  1033. {
  1034.   reg2 uint length;
  1035.   THD *thd= current_thd;
  1036.   CHARSET_INFO *cs;
  1037.   *multi_byte_charset= 0;
  1038.   length=0;
  1039.   for (; s_length-- ; sortorder++)
  1040.   {
  1041.     sortorder->need_strxnfrm= 0;
  1042.     if (sortorder->field)
  1043.     {
  1044.       if (sortorder->field->type() == FIELD_TYPE_BLOB)
  1045. sortorder->length= thd->variables.max_sort_length;
  1046.       else
  1047.       {
  1048. sortorder->length=sortorder->field->pack_length();
  1049. if (use_strnxfrm((cs=sortorder->field->sort_charset())))
  1050. {
  1051.   sortorder->need_strxnfrm= 1;
  1052.   *multi_byte_charset= 1;
  1053.   sortorder->length= sortorder->length*cs->strxfrm_multiply;
  1054. }
  1055.       }
  1056.       if (sortorder->field->maybe_null())
  1057. length++; // Place for NULL marker
  1058.     }
  1059.     else
  1060.     {
  1061.       switch ((sortorder->result_type=sortorder->item->result_type())) {
  1062.       case STRING_RESULT:
  1063. sortorder->length=sortorder->item->max_length;
  1064. if (use_strnxfrm((cs=sortorder->item->collation.collation)))
  1065.   sortorder->length= sortorder->length*cs->strxfrm_multiply;
  1066.   sortorder->need_strxnfrm= 1;
  1067.   *multi_byte_charset= 1;
  1068. }
  1069. break;
  1070.       case INT_RESULT:
  1071. #if SIZEOF_LONG_LONG > 4
  1072. sortorder->length=8; // Size of intern longlong
  1073. #else
  1074. sortorder->length=4;
  1075. #endif
  1076. break;
  1077.       case REAL_RESULT:
  1078. sortorder->length=sizeof(double);
  1079. break;
  1080.       case ROW_RESULT:
  1081.       default: 
  1082. // This case should never be choosen
  1083. DBUG_ASSERT(0);
  1084. break;
  1085.       }
  1086.       if (sortorder->item->maybe_null)
  1087. length++; // Place for NULL marker
  1088.     }
  1089.     set_if_smaller(sortorder->length, thd->variables.max_sort_length);
  1090.     length+=sortorder->length;
  1091.   }
  1092.   sortorder->field= (Field*) 0; // end marker
  1093.   DBUG_PRINT("info",("sort_length: %d",length));
  1094.   return length;
  1095. }
  1096. /*
  1097.   Get descriptors of fields appended to sorted fields and
  1098.   calculate its total length
  1099.   SYNOPSIS
  1100.     get_addon_fields()
  1101.     thd                 Current thread
  1102.     ptabfields          Array of references to the table fields
  1103.     sortlength          Total length of sorted fields
  1104.     plength    out:     Total length of appended fields
  1105.   DESCRIPTION
  1106.     The function first finds out what fields are used in the result set.
  1107.     Then it calculates the length of the buffer to store the values of
  1108.     these fields together with the value of sort values. 
  1109.     If the calculated length is not greater than max_length_for_sort_data
  1110.     the function allocates memory for an array of descriptors containing
  1111.     layouts for the values of the non-sorted fields in the buffer and
  1112.     fills them.
  1113.   NOTES
  1114.     The null bits for the appended values are supposed to be put together
  1115.     and stored the buffer just ahead of the value of the first field.
  1116.   RETURN
  1117.     Pointer to the layout descriptors for the appended fields, if any
  1118.     NULL - if we do not store field values with sort data.
  1119. */
  1120. static SORT_ADDON_FIELD *
  1121. get_addon_fields(THD *thd, Field **ptabfield, uint sortlength, uint *plength)
  1122. {
  1123.   Field **pfield;
  1124.   Field *field;
  1125.   SORT_ADDON_FIELD *addonf;
  1126.   uint length= 0;
  1127.   uint fields= 0;
  1128.   uint null_fields= 0;
  1129.   /* 
  1130.      If there is a reference to a field in the query add it
  1131.      to the the set of appended fields.
  1132.      Note for future refinement:
  1133.      This this a too strong condition.
  1134.      Actually we need only the fields referred in the
  1135.      result set. And for some of them it makes sense to use 
  1136.      the values directly from sorted fields.
  1137.   */
  1138.   *plength= 0;
  1139.   /*
  1140.      The following statement is added to avoid sorting in alter_table.
  1141.      The fact is the filter 'field->query_id != thd->query_id'
  1142.      doesn't work for alter table
  1143.   */
  1144.   if (thd->lex->sql_command != SQLCOM_SELECT)
  1145.     return 0;
  1146.   for (pfield= ptabfield; (field= *pfield) ; pfield++)
  1147.   {
  1148.     if (field->query_id != thd->query_id)
  1149.       continue;
  1150.     if (field->flags & BLOB_FLAG)
  1151.       return 0;
  1152.     length+= field->max_packed_col_length(field->pack_length());
  1153.     if (field->maybe_null())
  1154.       null_fields++;
  1155.     fields++;
  1156.   } 
  1157.   if (!fields)
  1158.     return 0;
  1159.   length+= (null_fields+7)/8;
  1160.   if (length+sortlength > thd->variables.max_length_for_sort_data ||
  1161.       !(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)*
  1162.                                                (fields+1), MYF(MY_WME))))
  1163.     return 0;
  1164.   *plength= length;
  1165.   length= (null_fields+7)/8;
  1166.   null_fields= 0;
  1167.   for (pfield= ptabfield; (field= *pfield) ; pfield++)
  1168.   {
  1169.     if (field->query_id != thd->query_id)
  1170.       continue;
  1171.     addonf->field= field;
  1172.     addonf->offset= length;
  1173.     if (field->maybe_null())
  1174.     {
  1175.       addonf->null_offset= null_fields/8;
  1176.       addonf->null_bit= 1<<(null_fields & 7);
  1177.       null_fields++;
  1178.     }
  1179.     else
  1180.     {
  1181.       addonf->null_offset= 0;
  1182.       addonf->null_bit= 0;
  1183.     }
  1184.     addonf->length= field->max_packed_col_length(field->pack_length());
  1185.     length+= addonf->length;
  1186.     addonf++;
  1187.   }
  1188.   addonf->field= 0;     // Put end marker
  1189.   
  1190.   DBUG_PRINT("info",("addon_length: %d",length));
  1191.   return (addonf-fields);
  1192. }
  1193. /*
  1194.   Copy (unpack) values appended to sorted fields from a buffer back to 
  1195.   their regular positions specified by the Field::ptr pointers.
  1196.   SYNOPSIS
  1197.     unpack_addon_fields()
  1198.     addon_field     Array of descriptors for appended fields
  1199.     buff            Buffer which to unpack the value from
  1200.   NOTES
  1201.     The function is supposed to be used only as a callback function
  1202.     when getting field values for the sorted result set.
  1203.   RETURN
  1204.     void.
  1205. */
  1206. static void 
  1207. unpack_addon_fields(struct st_sort_addon_field *addon_field, byte *buff)
  1208. {
  1209.   Field *field;
  1210.   SORT_ADDON_FIELD *addonf= addon_field;
  1211.   for ( ; (field= addonf->field) ; addonf++)
  1212.   {
  1213.     if (addonf->null_bit && (addonf->null_bit & buff[addonf->null_offset]))
  1214.     {
  1215.       field->set_null();
  1216.       continue;
  1217.     }
  1218.     field->set_notnull();
  1219.     field->unpack(field->ptr, (char *) buff+addonf->offset);
  1220.   }
  1221. }
  1222. /*
  1223. ** functions to change a double or float to a sortable string
  1224. ** The following should work for IEEE
  1225. */
  1226. #define DBL_EXP_DIG (sizeof(double)*8-DBL_MANT_DIG)
  1227. void change_double_for_sort(double nr,byte *to)
  1228. {
  1229.   uchar *tmp=(uchar*) to;
  1230.   if (nr == 0.0)
  1231.   { /* Change to zero string */
  1232.     tmp[0]=(uchar) 128;
  1233.     bzero((char*) tmp+1,sizeof(nr)-1);
  1234.   }
  1235.   else
  1236.   {
  1237. #ifdef WORDS_BIGENDIAN
  1238.     memcpy_fixed(tmp,&nr,sizeof(nr));
  1239. #else
  1240.     {
  1241.       uchar *ptr= (uchar*) &nr;
  1242. #if defined(__FLOAT_WORD_ORDER) && (__FLOAT_WORD_ORDER == __BIG_ENDIAN)
  1243.       tmp[0]= ptr[3]; tmp[1]=ptr[2]; tmp[2]= ptr[1]; tmp[3]=ptr[0];
  1244.       tmp[4]= ptr[7]; tmp[5]=ptr[6]; tmp[6]= ptr[5]; tmp[7]=ptr[4];
  1245. #else
  1246.       tmp[0]= ptr[7]; tmp[1]=ptr[6]; tmp[2]= ptr[5]; tmp[3]=ptr[4];
  1247.       tmp[4]= ptr[3]; tmp[5]=ptr[2]; tmp[6]= ptr[1]; tmp[7]=ptr[0];
  1248. #endif
  1249.     }
  1250. #endif
  1251.     if (tmp[0] & 128) /* Negative */
  1252.     { /* make complement */
  1253.       uint i;
  1254.       for (i=0 ; i < sizeof(nr); i++)
  1255. tmp[i]=tmp[i] ^ (uchar) 255;
  1256.     }
  1257.     else
  1258.     { /* Set high and move exponent one up */
  1259.       ushort exp_part=(((ushort) tmp[0] << 8) | (ushort) tmp[1] |
  1260.        (ushort) 32768);
  1261.       exp_part+= (ushort) 1 << (16-1-DBL_EXP_DIG);
  1262.       tmp[0]= (uchar) (exp_part >> 8);
  1263.       tmp[1]= (uchar) exp_part;
  1264.     }
  1265.   }
  1266. }