filesort.cc 48.4 KB
Newer Older
Marc Alff's avatar
Marc Alff committed
1
/* Copyright (C) 2000-2006 MySQL AB, 2008-2009 Sun Microsystems, Inc
unknown's avatar
unknown committed
2

unknown's avatar
unknown committed
3 4
   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
unknown's avatar
unknown committed
5
   the Free Software Foundation; version 2 of the License.
unknown's avatar
unknown committed
6

unknown's avatar
unknown committed
7 8 9 10
   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.
unknown's avatar
unknown committed
11

unknown's avatar
unknown committed
12 13 14 15 16
   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 */


unknown's avatar
unknown committed
17 18 19 20 21 22
/**
  @file

  @brief
  Sorts a database
*/
unknown's avatar
unknown committed
23

24 25 26
#include "sql_priv.h"
#include "filesort.h"
#include "unireg.h"                      // REQUIRED by other includes
unknown's avatar
unknown committed
27 28 29 30
#ifdef HAVE_STDDEF_H
#include <stddef.h>			/* for macro offsetof */
#endif
#include <m_ctype.h>
31
#include "sql_sort.h"
32
#include "probes_mysql.h"
33 34
#include "sql_test.h"                           // TEST_filesort
#include "opt_range.h"                          // SQL_SELECT
35

unknown's avatar
unknown committed
36
#ifndef THREAD
unknown's avatar
unknown committed
37
#define SKIP_DBUG_IN_FILESORT
unknown's avatar
unknown committed
38 39
#endif

unknown's avatar
unknown committed
40
/// How to write record_ref.
unknown's avatar
unknown committed
41
#define WRITE_REF(file,from) \
42
if (my_b_write((file),(uchar*) (from),param->ref_length)) \
unknown's avatar
unknown committed
43 44 45 46
  DBUG_RETURN(1);

	/* functions defined in this file */

47 48
static char **make_char_array(char **old_pos, register uint fields,
                              uint length, myf my_flag);
49 50
static uchar *read_buffpek_from_file(IO_CACHE *buffer_file, uint count,
                                     uchar *buf);
unknown's avatar
unknown committed
51
static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
52
			     uchar * *sort_keys, IO_CACHE *buffer_file,
unknown's avatar
unknown committed
53 54
			     IO_CACHE *tempfile,IO_CACHE *indexfile);
static int write_keys(SORTPARAM *param,uchar * *sort_keys,
55
		      uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
56
static void make_sortkey(SORTPARAM *param,uchar *to, uchar *ref_pos);
57
static void register_used_fields(SORTPARAM *param);
58
static int merge_index(SORTPARAM *param,uchar *sort_buffer,
unknown's avatar
unknown committed
59 60 61
		       BUFFPEK *buffpek,
		       uint maxbuffer,IO_CACHE *tempfile,
		       IO_CACHE *outfile);
62 63
static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count, 
                       FILESORT_INFO *table_sort);
64 65
static uint suffix_length(ulong string_length);
static uint sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length,
66
		       bool *multi_byte_charset);
unknown's avatar
unknown committed
67 68 69
static SORT_ADDON_FIELD *get_addon_fields(THD *thd, Field **ptabfield,
                                          uint sortlength, uint *plength);
static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
70
                                uchar *buff);
unknown's avatar
unknown committed
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
/**
  Sort a table.
  Creates a set of pointers that can be used to read the rows
  in sorted order. This should be done with the functions
  in records.cc.

  Before calling filesort, one must have done
  table->file->info(HA_STATUS_VARIABLE)

  The result set is stored in table->io_cache or
  table->record_pointers.

  @param thd           Current thread
  @param table		Table to sort
  @param sortorder	How to sort the table
  @param s_length	Number of elements in sortorder
  @param select		condition to apply to the rows
  @param max_rows	Return only this many rows
  @param sort_positions	Set to 1 if we want to force sorting by position
90
			(Needed by UPDATE/INSERT or ALTER TABLE)
unknown's avatar
unknown committed
91
  @param examined_rows	Store number of examined rows here
92

unknown's avatar
unknown committed
93 94 95
  @todo
    check why we do this (param.keys--)
  @note
96 97 98
    If we sort by position (like if sort_positions is 1) filesort() will
    call table->prepare_for_position().

unknown's avatar
unknown committed
99
  @retval
100
    HA_POS_ERROR	Error
unknown's avatar
unknown committed
101 102 103
  @retval
    \#			Number of rows
  @retval
104 105
    examined_rows	will be set to number of examined rows
*/
106

107
ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
108 109
		 SQL_SELECT *select, ha_rows max_rows,
                 bool sort_positions, ha_rows *examined_rows)
unknown's avatar
unknown committed
110 111
{
  int error;
unknown's avatar
unknown committed
112
  ulong memavl, min_sort_memory;
unknown's avatar
unknown committed
113
  uint maxbuffer;
unknown's avatar
unknown committed
114
  BUFFPEK *buffpek;
unknown's avatar
unknown committed
115
  ha_rows records= HA_POS_ERROR;
unknown's avatar
unknown committed
116
  uchar **sort_keys= 0;
117
  IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile; 
unknown's avatar
unknown committed
118
  SORTPARAM param;
119
  bool multi_byte_charset;
120 121
  DBUG_ENTER("filesort");
  DBUG_EXECUTE("info",TEST_filesort(sortorder,s_length););
unknown's avatar
unknown committed
122
#ifdef SKIP_DBUG_IN_FILESORT
unknown's avatar
unknown committed
123 124
  DBUG_PUSH("");		/* No DBUG here */
#endif
125
  FILESORT_INFO table_sort;
unknown's avatar
unknown committed
126 127
  TABLE_LIST *tab= table->pos_in_table_list;
  Item_subselect *subselect= tab ? tab->containing_subselect() : 0;
128

129
  MYSQL_FILESORT_START(table->s->db.str, table->s->table_name.str);
130

131 132 133 134 135 136
  /*
   Release InnoDB's adaptive hash index latch (if holding) before
   running a sort.
  */
  ha_release_temporary_latches(thd);

137
  /* 
138 139 140
    Don't use table->sort in filesort as it is also used by 
    QUICK_INDEX_MERGE_SELECT. Work with a copy and put it back at the end 
    when index_merge select has finished with it.
141 142 143
  */
  memcpy(&table_sort, &table->sort, sizeof(FILESORT_INFO));
  table->sort.io_cache= NULL;
144
  
145
  outfile= table_sort.io_cache;
unknown's avatar
unknown committed
146
  my_b_clear(&tempfile);
147 148 149
  my_b_clear(&buffpek_pointers);
  buffpek=0;
  error= 1;
150
  bzero((char*) &param,sizeof(param));
151
  param.sort_length= sortlength(thd, sortorder, s_length, &multi_byte_charset);
152 153
  /* filesort cannot handle zero-length records. */
  DBUG_ASSERT(param.sort_length);
154
  param.ref_length= table->file->ref_length;
unknown's avatar
unknown committed
155 156
  param.addon_field= 0;
  param.addon_length= 0;
157 158
  if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
      !table->fulltext_searched && !sort_positions)
unknown's avatar
unknown committed
159 160 161 162 163 164 165 166 167
  {
    /* 
      Get the descriptors of all fields whose values are appended 
      to sorted fields and get its total length in param.spack_length.
    */
    param.addon_field= get_addon_fields(thd, table->field, 
                                        param.sort_length,
                                        &param.addon_length);
  }
168 169 170 171 172

  table_sort.addon_buf= 0;
  table_sort.addon_length= param.addon_length;
  table_sort.addon_field= param.addon_field;
  table_sort.unpack= unpack_addon_fields;
unknown's avatar
unknown committed
173 174 175
  if (param.addon_field)
  {
    param.res_length= param.addon_length;
176
    if (!(table_sort.addon_buf= (uchar *) my_malloc(param.addon_length,
unknown's avatar
unknown committed
177 178 179 180 181 182 183 184 185 186 187 188 189
                                                    MYF(MY_WME))))
      goto err;
  }
  else
  {
    param.res_length= param.ref_length;
    /* 
      The reference to the record is considered 
      as an additional sorted field
    */
    param.sort_length+= param.ref_length;
  }
  param.rec_length= param.sort_length+param.addon_length;
unknown's avatar
unknown committed
190
  param.max_rows= max_rows;
unknown's avatar
unknown committed
191

192 193
  if (select && select->quick)
  {
194
    status_var_increment(thd->status_var.filesort_range_count);
195 196 197
  }
  else
  {
198
    status_var_increment(thd->status_var.filesort_scan_count);
199
  }
unknown's avatar
unknown committed
200
#ifdef CAN_TRUST_RANGE
201
  if (select && select->quick && select->quick->records > 0L)
unknown's avatar
unknown committed
202 203
  {
    records=min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
204
		table->file->stats.records)+EXTRA_RECORDS;
unknown's avatar
unknown committed
205 206 207
    selected_records_file=0;
  }
  else
208
#endif
unknown's avatar
unknown committed
209
  {
unknown's avatar
unknown committed
210 211 212 213 214 215 216
    records= table->file->estimate_rows_upper_bound();
    /*
      If number of records is not known, use as much of sort buffer 
      as possible. 
    */
    if (records == HA_POS_ERROR)
      records--;  // we use 'records+1' below.
unknown's avatar
unknown committed
217 218 219
    selected_records_file= 0;
  }

220
  if (multi_byte_charset &&
221
      !(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME))))
unknown's avatar
unknown committed
222 223
    goto err;

224
  memavl= thd->variables.sortbuff_size;
unknown's avatar
unknown committed
225 226
  min_sort_memory= max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
  while (memavl >= min_sort_memory)
unknown's avatar
unknown committed
227
  {
228
    ulong old_memavl;
unknown's avatar
unknown committed
229
    ulong keys= memavl/(param.rec_length+sizeof(char*));
230
    param.keys=(uint) min(records+1, keys);
231 232 233
    if ((table_sort.sort_keys=
	 (uchar **) make_char_array((char **) table_sort.sort_keys,
                                    param.keys, param.rec_length, MYF(0))))
234
      break;
unknown's avatar
unknown committed
235
    old_memavl=memavl;
unknown's avatar
unknown committed
236
    if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
unknown's avatar
unknown committed
237
      memavl= min_sort_memory;
unknown's avatar
unknown committed
238
  }
unknown's avatar
unknown committed
239
  sort_keys= table_sort.sort_keys;
unknown's avatar
unknown committed
240
  if (memavl < min_sort_memory)
unknown's avatar
unknown committed
241
  {
242
    my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
unknown's avatar
unknown committed
243 244
    goto err;
  }
245 246 247 248
  if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
		       DISK_BUFFER_SIZE, MYF(MY_WME)))
    goto err;

249
  param.keys--;  			/* TODO: check why we do this */
250
  param.sort_form= table;
unknown's avatar
unknown committed
251
  param.end=(param.local_sortorder=sortorder)+s_length;
252
  if ((records=find_all_keys(&param,select,sort_keys, &buffpek_pointers,
unknown's avatar
unknown committed
253 254 255
			     &tempfile, selected_records_file)) ==
      HA_POS_ERROR)
    goto err;
unknown's avatar
unknown committed
256
  maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
257

258
  if (maxbuffer == 0)			// The whole set is in memory
unknown's avatar
unknown committed
259
  {
260
    if (save_index(&param,sort_keys,(uint) records, &table_sort))
unknown's avatar
unknown committed
261 262 263 264
      goto err;
  }
  else
  {
unknown's avatar
unknown committed
265 266
    if (table_sort.buffpek && table_sort.buffpek_len < maxbuffer)
    {
267
      my_free(table_sort.buffpek);
unknown's avatar
unknown committed
268 269
      table_sort.buffpek= 0;
    }
270
    if (!(table_sort.buffpek=
271
          (uchar *) read_buffpek_from_file(&buffpek_pointers, maxbuffer,
unknown's avatar
unknown committed
272
                                 table_sort.buffpek)))
273
      goto err;
unknown's avatar
unknown committed
274 275
    buffpek= (BUFFPEK *) table_sort.buffpek;
    table_sort.buffpek_len= maxbuffer;
276
    close_cached_file(&buffpek_pointers);
unknown's avatar
unknown committed
277 278 279 280 281
	/* Open cached file if it isn't open */
    if (! my_b_inited(outfile) &&
	open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
			  MYF(MY_WME)))
      goto err;
282 283
    if (reinit_io_cache(outfile,WRITE_CACHE,0L,0,0))
      goto err;
unknown's avatar
unknown committed
284

285 286 287 288
    /*
      Use also the space previously used by string pointers in sort_buffer
      for temporary key storage.
    */
unknown's avatar
unknown committed
289 290
    param.keys=((param.keys*(param.rec_length+sizeof(char*))) /
		param.rec_length-1);
291
    maxbuffer--;				// Offset from 0
292 293
    if (merge_many_buff(&param,(uchar*) sort_keys,buffpek,&maxbuffer,
			&tempfile))
unknown's avatar
unknown committed
294 295 296 297
      goto err;
    if (flush_io_cache(&tempfile) ||
	reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
      goto err;
298 299
    if (merge_index(&param,(uchar*) sort_keys,buffpek,maxbuffer,&tempfile,
		    outfile))
unknown's avatar
unknown committed
300 301 302 303 304 305 306
      goto err;
  }
  if (records > param.max_rows)
    records=param.max_rows;
  error =0;

 err:
307
  my_free(param.tmp_buffer);
unknown's avatar
unknown committed
308 309
  if (!subselect || !subselect->is_uncacheable())
  {
310
    my_free(sort_keys);
unknown's avatar
unknown committed
311
    table_sort.sort_keys= 0;
312
    my_free(buffpek);
unknown's avatar
unknown committed
313 314 315
    table_sort.buffpek= 0;
    table_sort.buffpek_len= 0;
  }
unknown's avatar
unknown committed
316
  close_cached_file(&tempfile);
317
  close_cached_file(&buffpek_pointers);
unknown's avatar
unknown committed
318 319 320 321 322 323 324 325 326 327 328 329 330
  if (my_b_inited(outfile))
  {
    if (flush_io_cache(outfile))
      error=1;
    {
      my_off_t save_pos=outfile->pos_in_file;
      /* For following reads */
      if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
	error=1;
      outfile->end_of_file=save_pos;
    }
  }
  if (error)
unknown's avatar
unknown committed
331 332
    my_message(ER_FILSORT_ABORT, ER(ER_FILSORT_ABORT),
               MYF(ME_ERROR+ME_WAITTANG));
333
  else
334 335
    statistic_add(thd->status_var.filesort_rows,
		  (ulong) records, &LOCK_status);
336
  *examined_rows= param.examined_rows;
unknown's avatar
unknown committed
337
#ifdef SKIP_DBUG_IN_FILESORT
unknown's avatar
unknown committed
338 339
  DBUG_POP();			/* Ok to DBUG */
#endif
340
  memcpy(&table->sort, &table_sort, sizeof(FILESORT_INFO));
unknown's avatar
unknown committed
341
  DBUG_PRINT("exit",("records: %ld", (long) records));
342
  MYSQL_FILESORT_DONE(error, records);
unknown's avatar
unknown committed
343 344 345 346
  DBUG_RETURN(error ? HA_POS_ERROR : records);
} /* filesort */


unknown's avatar
unknown committed
347
void filesort_free_buffers(TABLE *table, bool full)
unknown's avatar
unknown committed
348
{
349 350 351
  my_free(table->sort.record_pointers);
  table->sort.record_pointers= NULL;

unknown's avatar
unknown committed
352 353
  if (full)
  {
354 355 356 357
    my_free(table->sort.sort_keys);
    table->sort.sort_keys= NULL;
    my_free(table->sort.buffpek);
    table->sort.buffpek= NULL;
358
    table->sort.buffpek_len= 0;
unknown's avatar
unknown committed
359
  }
360 361 362 363 364

  my_free(table->sort.addon_buf);
  my_free(table->sort.addon_field);
  table->sort.addon_buf= NULL;
  table->sort.addon_field= NULL;
unknown's avatar
unknown committed
365 366
}

unknown's avatar
unknown committed
367
/** Make a array of string pointers. */
unknown's avatar
unknown committed
368

369 370
static char **make_char_array(char **old_pos, register uint fields,
                              uint length, myf my_flag)
unknown's avatar
unknown committed
371 372
{
  register char **pos;
373
  char *char_pos;
unknown's avatar
unknown committed
374 375
  DBUG_ENTER("make_char_array");

376 377 378
  if (old_pos ||
      (old_pos= (char**) my_malloc((uint) fields*(length+sizeof(char*)),
				   my_flag)))
unknown's avatar
unknown committed
379 380 381 382 383 384 385 386 387
  {
    pos=old_pos; char_pos=((char*) (pos+fields)) -length;
    while (fields--) *(pos++) = (char_pos+= length);
  }

  DBUG_RETURN(old_pos);
} /* make_char_array */


unknown's avatar
unknown committed
388
/** Read 'count' number of buffer pointers into memory. */
389

390 391
static uchar *read_buffpek_from_file(IO_CACHE *buffpek_pointers, uint count,
                                     uchar *buf)
392
{
393
  ulong length= sizeof(BUFFPEK)*count;
394
  uchar *tmp= buf;
395
  DBUG_ENTER("read_buffpek_from_file");
396
  if (count > UINT_MAX/sizeof(BUFFPEK))
397
    return 0; /* sizeof(BUFFPEK)*count will overflow */
398
  if (!tmp)
399
    tmp= (uchar *)my_malloc(length, MYF(MY_WME));
400 401 402
  if (tmp)
  {
    if (reinit_io_cache(buffpek_pointers,READ_CACHE,0L,0,0) ||
403
	my_b_read(buffpek_pointers, (uchar*) tmp, length))
404
    {
405
      my_free(tmp);
406
      tmp=0;
unknown's avatar
unknown committed
407
    }
408 409
  }
  DBUG_RETURN(tmp);
unknown's avatar
unknown committed
410
}
411

412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461
#ifndef DBUG_OFF
/*
  Print a text, SQL-like record representation into dbug trace.

  Note: this function is a work in progress: at the moment
   - column read bitmap is ignored (can print garbage for unused columns)
   - there is no quoting
*/
static void dbug_print_record(TABLE *table, bool print_rowid)
{
  char buff[1024];
  Field **pfield;
  String tmp(buff,sizeof(buff),&my_charset_bin);
  DBUG_LOCK_FILE;
  
  fprintf(DBUG_FILE, "record (");
  for (pfield= table->field; *pfield ; pfield++)
    fprintf(DBUG_FILE, "%s%s", (*pfield)->field_name, (pfield[1])? ", ":"");
  fprintf(DBUG_FILE, ") = ");

  fprintf(DBUG_FILE, "(");
  for (pfield= table->field; *pfield ; pfield++)
  {
    Field *field=  *pfield;

    if (field->is_null())
      fwrite("NULL", sizeof(char), 4, DBUG_FILE);
   
    if (field->type() == MYSQL_TYPE_BIT)
      (void) field->val_int_as_str(&tmp, 1);
    else
      field->val_str(&tmp);

    fwrite(tmp.ptr(),sizeof(char),tmp.length(),DBUG_FILE);
    if (pfield[1])
      fwrite(", ", sizeof(char), 2, DBUG_FILE);
  }
  fprintf(DBUG_FILE, ")");
  if (print_rowid)
  {
    fprintf(DBUG_FILE, " rowid ");
    for (uint i=0; i < table->file->ref_length; i++)
    {
      fprintf(DBUG_FILE, "%x", (uchar)table->file->ref[i]);
    }
  }
  fprintf(DBUG_FILE, "\n");
  DBUG_UNLOCK_FILE;
}
#endif 
462

unknown's avatar
unknown committed
463
/**
unknown's avatar
unknown committed
464
  Search after sort_keys and write them into tempfile.
unknown's avatar
unknown committed
465 466 467 468 469 470 471 472 473 474 475
  All produced sequences are guaranteed to be non-empty.

  @param param             Sorting parameter
  @param select            Use this to get source data
  @param sort_keys         Array of pointers to sort key + addon buffers.
  @param buffpek_pointers  File to write BUFFPEKs describing sorted segments
                           in tempfile.
  @param tempfile          File to write sorted sequences of sortkeys to.
  @param indexfile         If !NULL, use it for source data (contains rowids)

  @note
unknown's avatar
unknown committed
476
    Basic idea:
unknown's avatar
unknown committed
477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494
    @verbatim
     while (get_next_sortkey())
     {
       if (no free space in sort_keys buffers)
       {
         sort sort_keys buffer;
         dump sorted sequence to 'tempfile';
         dump BUFFPEK describing sequence location into 'buffpek_pointers';
       }
       put sort key into 'sort_keys';
     }
     if (sort_keys has some elements && dumped at least once)
       sort-dump-dump as above;
     else
       don't sort, leave sort_keys array to be sorted by caller.
  @endverbatim

  @retval
unknown's avatar
unknown committed
495
    Number of records written on success.
unknown's avatar
unknown committed
496
  @retval
unknown's avatar
unknown committed
497 498
    HA_POS_ERROR on error.
*/
unknown's avatar
unknown committed
499 500 501

static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select,
			     uchar **sort_keys,
502
			     IO_CACHE *buffpek_pointers,
unknown's avatar
unknown committed
503 504 505 506
			     IO_CACHE *tempfile, IO_CACHE *indexfile)
{
  int error,flag,quick_select;
  uint idx,indexpos,ref_length;
507
  uchar *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
unknown's avatar
unknown committed
508 509
  my_off_t record;
  TABLE *sort_form;
unknown's avatar
unknown committed
510
  THD *thd= current_thd;
511
  volatile THD::killed_state *killed= &thd->killed;
unknown's avatar
unknown committed
512
  handler *file;
513
  MY_BITMAP *save_read_set, *save_write_set;
514
  bool skip_record;
unknown's avatar
unknown committed
515
  DBUG_ENTER("find_all_keys");
516 517 518
  DBUG_PRINT("info",("using: %s",
                     (select ? select->quick ? "ranges" : "where":
                      "every row")));
unknown's avatar
unknown committed
519 520 521 522 523 524 525 526 527

  idx=indexpos=0;
  error=quick_select=0;
  sort_form=param->sort_form;
  file=sort_form->file;
  ref_length=param->ref_length;
  ref_pos= ref_buff;
  quick_select=select && select->quick;
  record=0;
528
  flag= ((!indexfile && file->ha_table_flags() & HA_REC_NOT_IN_SEQ)
unknown's avatar
unknown committed
529 530 531 532 533 534
	 || quick_select);
  if (indexfile || flag)
    ref_pos= &file->ref[0];
  next_pos=ref_pos;
  if (! indexfile && ! quick_select)
  {
535
    next_pos=(uchar*) 0;			/* Find records in sequence */
536
    file->ha_rnd_init(1);
unknown's avatar
unknown committed
537 538
    file->extra_opt(HA_EXTRA_CACHE,
		    current_thd->variables.read_buff_size);
unknown's avatar
unknown committed
539 540
  }

541 542 543 544 545 546
  if (quick_select)
  {
    if (select->quick->reset())
      DBUG_RETURN(HA_POS_ERROR);
  }

547 548 549 550 551 552 553 554
  /* Remember original bitmaps */
  save_read_set=  sort_form->read_set;
  save_write_set= sort_form->write_set;
  /* Set up temporary column read map for columns used by sort */
  bitmap_clear_all(&sort_form->tmp_set);
  /* Temporary set for register_used_fields and register_field_in_read_map */
  sort_form->read_set= &sort_form->tmp_set;
  register_used_fields(param);
555
  if (select && select->cond)
556
    select->cond->walk(&Item::register_field_in_read_map, 1,
557
                       (uchar*) sort_form);
558 559
  sort_form->column_bitmaps_set(&sort_form->tmp_set, &sort_form->tmp_set);

unknown's avatar
unknown committed
560 561 562 563
  for (;;)
  {
    if (quick_select)
    {
564
      if ((error= select->quick->get_next()))
565
        break;
unknown's avatar
unknown committed
566
      file->position(sort_form->record[0]);
567
      DBUG_EXECUTE_IF("debug_filesort", dbug_print_record(sort_form, TRUE););
unknown's avatar
unknown committed
568 569 570 571 572
    }
    else					/* Not quick-select */
    {
      if (indexfile)
      {
573
	if (my_b_read(indexfile,(uchar*) ref_pos,ref_length)) /* purecov: deadcode */
unknown's avatar
unknown committed
574 575 576 577 578 579 580 581 582 583 584
	{
	  error= my_errno ? my_errno : -1;		/* Abort */
	  break;
	}
	error=file->rnd_pos(sort_form->record[0],next_pos);
      }
      else
      {
	error=file->rnd_next(sort_form->record[0]);
	if (!flag)
	{
unknown's avatar
unknown committed
585
	  my_store_ptr(ref_pos,ref_length,record); // Position to row
586
	  record+= sort_form->s->db_record_offset;
unknown's avatar
unknown committed
587
	}
unknown's avatar
unknown committed
588
	else if (!error)
unknown's avatar
unknown committed
589
	  file->position(sort_form->record[0]);
unknown's avatar
unknown committed
590 591 592 593
      }
      if (error && error != HA_ERR_RECORD_DELETED)
	break;
    }
594

unknown's avatar
unknown committed
595 596
    if (*killed)
    {
597
      DBUG_PRINT("info",("Sort killed by user"));
598 599 600 601 602
      if (!indexfile && !quick_select)
      {
        (void) file->extra(HA_EXTRA_NO_CACHE);
        file->ha_rnd_end();
      }
unknown's avatar
unknown committed
603 604
      DBUG_RETURN(HA_POS_ERROR);		/* purecov: inspected */
    }
605 606
    if (error == 0)
      param->examined_rows++;
607 608
    if (!error && (!select ||
                   (!select->skip_record(thd, &skip_record) && !skip_record)))
unknown's avatar
unknown committed
609 610 611
    {
      if (idx == param->keys)
      {
612 613
	if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
	  DBUG_RETURN(HA_POS_ERROR);
614 615
	idx=0;
	indexpos++;
unknown's avatar
unknown committed
616 617 618
      }
      make_sortkey(param,sort_keys[idx++],ref_pos);
    }
unknown's avatar
unknown committed
619 620
    else
      file->unlock_row();
unknown's avatar
unknown committed
621
    /* It does not make sense to read more keys in case of a fatal error */
622
    if (thd->is_error())
623
      break;
unknown's avatar
unknown committed
624
  }
625
  if (!quick_select)
626 627
  {
    (void) file->extra(HA_EXTRA_NO_CACHE);	/* End cacheing of records */
unknown's avatar
unknown committed
628 629
    if (!next_pos)
      file->ha_rnd_end();
630 631
  }

632
  if (thd->is_error())
633 634
    DBUG_RETURN(HA_POS_ERROR);
  
635 636 637
  /* Signal we should use orignal column read and write maps */
  sort_form->column_bitmaps_set(save_read_set, save_write_set);

unknown's avatar
unknown committed
638 639 640 641 642 643
  DBUG_PRINT("test",("error: %d  indexpos: %d",error,indexpos));
  if (error != HA_ERR_END_OF_FILE)
  {
    file->print_error(error,MYF(ME_ERROR | ME_WAITTANG)); /* purecov: inspected */
    DBUG_RETURN(HA_POS_ERROR);			/* purecov: inspected */
  }
644
  if (indexpos && idx &&
645 646
      write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
    DBUG_RETURN(HA_POS_ERROR);			/* purecov: inspected */
unknown's avatar
unknown committed
647
  DBUG_RETURN(my_b_inited(tempfile) ?
unknown's avatar
unknown committed
648
	      (ha_rows) (my_b_tell(tempfile)/param->rec_length) :
unknown's avatar
unknown committed
649 650 651 652
	      idx);
} /* find_all_keys */


unknown's avatar
unknown committed
653 654
/**
  @details
unknown's avatar
unknown committed
655
  Sort the buffer and write:
unknown's avatar
unknown committed
656 657 658 659 660 661 662 663 664 665 666 667 668 669
  -# the sorted sequence to tempfile
  -# a BUFFPEK describing the sorted sequence position to buffpek_pointers

    (was: Skriver en buffert med nycklar till filen)

  @param param             Sort parameters
  @param sort_keys         Array of pointers to keys to sort
  @param count             Number of elements in sort_keys array
  @param buffpek_pointers  One 'BUFFPEK' struct will be written into this file.
                           The BUFFPEK::{file_pos, count} will indicate where
                           the sorted data was stored.
  @param tempfile          The sorted sequence will be written into this file.

  @retval
unknown's avatar
unknown committed
670
    0 OK
unknown's avatar
unknown committed
671
  @retval
unknown's avatar
unknown committed
672 673
    1 Error
*/
unknown's avatar
unknown committed
674

unknown's avatar
unknown committed
675 676
static int
write_keys(SORTPARAM *param, register uchar **sort_keys, uint count,
unknown's avatar
unknown committed
677
           IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
unknown's avatar
unknown committed
678
{
679
  size_t sort_length, rec_length;
unknown's avatar
unknown committed
680
  uchar **end;
681
  BUFFPEK buffpek;
unknown's avatar
unknown committed
682 683
  DBUG_ENTER("write_keys");

unknown's avatar
unknown committed
684 685
  sort_length= param->sort_length;
  rec_length= param->rec_length;
unknown's avatar
unknown committed
686 687 688
#ifdef MC68000
  quicksort(sort_keys,count,sort_length);
#else
689
  my_string_ptr_sort((uchar*) sort_keys, (uint) count, sort_length);
unknown's avatar
unknown committed
690 691
#endif
  if (!my_b_inited(tempfile) &&
unknown's avatar
unknown committed
692 693
      open_cached_file(tempfile, mysql_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
                       MYF(MY_WME)))
694
    goto err;                                   /* purecov: inspected */
695
  /* check we won't have more buffpeks than we can possibly keep in memory */
696
  if (my_b_tell(buffpek_pointers) + sizeof(BUFFPEK) > (ulonglong)UINT_MAX)
697
    goto err;
unknown's avatar
unknown committed
698
  buffpek.file_pos= my_b_tell(tempfile);
unknown's avatar
unknown committed
699
  if ((ha_rows) count > param->max_rows)
700
    count=(uint) param->max_rows;               /* purecov: inspected */
701
  buffpek.count=(ha_rows) count;
unknown's avatar
unknown committed
702
  for (end=sort_keys+count ; sort_keys != end ; sort_keys++)
703
    if (my_b_write(tempfile, (uchar*) *sort_keys, (uint) rec_length))
704
      goto err;
705
  if (my_b_write(buffpek_pointers, (uchar*) &buffpek, sizeof(buffpek)))
706
    goto err;
unknown's avatar
unknown committed
707
  DBUG_RETURN(0);
708 709 710

err:
  DBUG_RETURN(1);
unknown's avatar
unknown committed
711 712 713
} /* write_keys */


unknown's avatar
unknown committed
714 715
/**
  Store length as suffix in high-byte-first order.
716 717 718 719 720 721 722 723 724 725 726 727 728
*/

static inline void store_length(uchar *to, uint length, uint pack_length)
{
  switch (pack_length) {
  case 1:
    *to= (uchar) length;
    break;
  case 2:
    mi_int2store(to, length);
    break;
  case 3:
    mi_int3store(to, length);
729
    break;
730 731 732 733 734 735 736
  default:
    mi_int4store(to, length);
    break;
  }
}


unknown's avatar
unknown committed
737
/** Make a sort-key from record. */
unknown's avatar
unknown committed
738 739

static void make_sortkey(register SORTPARAM *param,
740
			 register uchar *to, uchar *ref_pos)
unknown's avatar
unknown committed
741 742 743 744 745 746 747 748 749
{
  reg3 Field *field;
  reg1 SORT_FIELD *sort_field;
  reg5 uint length;

  for (sort_field=param->local_sortorder ;
       sort_field != param->end ;
       sort_field++)
  {
unknown's avatar
unknown committed
750
    bool maybe_null=0;
unknown's avatar
unknown committed
751 752 753 754 755 756
    if ((field=sort_field->field))
    {						// Field
      if (field->maybe_null())
      {
	if (field->is_null())
	{
unknown's avatar
unknown committed
757 758 759 760
	  if (sort_field->reverse)
	    bfill(to,sort_field->length+1,(char) 255);
	  else
	    bzero((char*) to,sort_field->length+1);
unknown's avatar
unknown committed
761 762 763 764 765 766
	  to+= sort_field->length+1;
	  continue;
	}
	else
	  *to++=1;
      }
767
      field->sort_string(to, sort_field->length);
unknown's avatar
unknown committed
768 769 770 771
    }
    else
    {						// Item
      Item *item=sort_field->item;
772
      maybe_null= item->maybe_null;
unknown's avatar
unknown committed
773 774
      switch (sort_field->result_type) {
      case STRING_RESULT:
775
      {
unknown's avatar
unknown committed
776 777 778 779 780 781 782 783 784 785 786 787 788 789 790
        CHARSET_INFO *cs=item->collation.collation;
        char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 : ' ');
        int diff;
        uint sort_field_length;

        if (maybe_null)
          *to++=1;
        /* All item->str() to use some extra byte for end null.. */
        String tmp((char*) to,sort_field->length+4,cs);
        String *res= item->str_result(&tmp);
        if (!res)
        {
          if (maybe_null)
            bzero((char*) to-1,sort_field->length+1);
          else
unknown's avatar
unknown committed
791
          {
792 793 794 795 796 797 798
            /* purecov: begin deadcode */
            /*
              This should only happen during extreme conditions if we run out
              of memory or have an item marked not null when it can be null.
              This code is here mainly to avoid a hard crash in this case.
            */
            DBUG_ASSERT(0);
unknown's avatar
unknown committed
799 800 801
            DBUG_PRINT("warning",
                       ("Got null on something that shouldn't be null"));
            bzero((char*) to,sort_field->length);	// Avoid crash
802
            /* purecov: end */
unknown's avatar
unknown committed
803
          }
unknown's avatar
unknown committed
804 805 806 807 808 809 810
          break;
        }
        length= res->length();
        sort_field_length= sort_field->length - sort_field->suffix_length;
        diff=(int) (sort_field_length - length);
        if (diff < 0)
        {
811
          diff=0;
unknown's avatar
unknown committed
812 813 814 815 816 817 818 819 820 821 822 823 824
          length= sort_field_length;
        }
        if (sort_field->suffix_length)
        {
          /* Store length last in result_string */
          store_length(to + sort_field_length, length,
                       sort_field->suffix_length);
        }
        if (sort_field->need_strxnfrm)
        {
          char *from=(char*) res->ptr();
          uint tmp_length;
          if ((uchar*) from == to)
unknown's avatar
unknown committed
825
          {
unknown's avatar
unknown committed
826 827 828
            set_if_smaller(length,sort_field->length);
            memcpy(param->tmp_buffer,from,length);
            from=param->tmp_buffer;
unknown's avatar
unknown committed
829
          }
unknown's avatar
unknown committed
830 831 832 833 834 835 836 837 838 839
          tmp_length= my_strnxfrm(cs,to,sort_field->length,
                                  (uchar*) from, length);
          DBUG_ASSERT(tmp_length == sort_field->length);
        }
        else
        {
          my_strnxfrm(cs,(uchar*)to,length,(const uchar*)res->ptr(),length);
          cs->cset->fill(cs, (char *)to+length,diff,fill_char);
        }
        break;
840
      }
unknown's avatar
unknown committed
841 842
      case INT_RESULT:
	{
843 844
          longlong value= item->val_int_result();
          if (maybe_null)
845
          {
unknown's avatar
unknown committed
846
	    *to++=1;				/* purecov: inspected */
847 848 849 850 851 852 853 854 855 856 857 858 859
            if (item->null_value)
            {
              if (maybe_null)
                bzero((char*) to-1,sort_field->length+1);
              else
              {
                DBUG_PRINT("warning",
                           ("Got null on something that shouldn't be null"));
                bzero((char*) to,sort_field->length);
              }
              break;
            }
          }
unknown's avatar
unknown committed
860 861 862 863 864 865 866 867
#if SIZEOF_LONG_LONG > 4
	  to[7]= (uchar) value;
	  to[6]= (uchar) (value >> 8);
	  to[5]= (uchar) (value >> 16);
	  to[4]= (uchar) (value >> 24);
	  to[3]= (uchar) (value >> 32);
	  to[2]= (uchar) (value >> 40);
	  to[1]= (uchar) (value >> 48);
unknown's avatar
unknown committed
868 869 870 871
          if (item->unsigned_flag)                    /* Fix sign */
            to[0]= (uchar) (value >> 56);
          else
            to[0]= (uchar) (value >> 56) ^ 128;	/* Reverse signbit */
unknown's avatar
unknown committed
872 873 874 875
#else
	  to[3]= (uchar) value;
	  to[2]= (uchar) (value >> 8);
	  to[1]= (uchar) (value >> 16);
unknown's avatar
unknown committed
876 877 878 879
          if (item->unsigned_flag)                    /* Fix sign */
            to[0]= (uchar) (value >> 24);
          else
            to[0]= (uchar) (value >> 24) ^ 128;	/* Reverse signbit */
unknown's avatar
unknown committed
880 881 882
#endif
	  break;
	}
unknown's avatar
unknown committed
883 884
      case DECIMAL_RESULT:
        {
885
          my_decimal dec_buf, *dec_val= item->val_decimal_result(&dec_buf);
886 887 888 889 890 891 892 893
          if (maybe_null)
          {
            if (item->null_value)
            { 
              bzero((char*)to, sort_field->length+1);
              to++;
              break;
            }
unknown's avatar
unknown committed
894
            *to++=1;
895
          }
896
          my_decimal2binary(E_DEC_FATAL_ERROR, dec_val, to,
unknown's avatar
unknown committed
897 898 899 900
                            item->max_length - (item->decimals ? 1:0),
                            item->decimals);
         break;
        }
unknown's avatar
unknown committed
901 902
      case REAL_RESULT:
	{
903
          double value= item->val_result();
904 905 906 907 908 909 910 911
	  if (maybe_null)
          {
            if (item->null_value)
            {
              bzero((char*) to,sort_field->length+1);
              to++;
              break;
            }
unknown's avatar
unknown committed
912
	    *to++=1;
913
          }
914
	  change_double_for_sort(value,(uchar*) to);
unknown's avatar
unknown committed
915 916
	  break;
	}
917
      case ROW_RESULT:
unknown's avatar
unknown committed
918
      default: 
unknown's avatar
unknown committed
919 920 921
	// This case should never be choosen
	DBUG_ASSERT(0);
	break;
unknown's avatar
unknown committed
922 923 924 925
      }
    }
    if (sort_field->reverse)
    {							/* Revers key */
unknown's avatar
unknown committed
926 927
      if (maybe_null)
        to[-1]= ~to[-1];
unknown's avatar
unknown committed
928 929 930 931 932 933 934 935 936 937
      length=sort_field->length;
      while (length--)
      {
	*to = (uchar) (~ *to);
	to++;
      }
    }
    else
      to+= sort_field->length;
  }
unknown's avatar
unknown committed
938 939 940 941 942 943 944 945 946 947 948

  if (param->addon_field)
  {
    /* 
      Save field values appended to sorted fields.
      First null bit indicators are appended then field values follow.
      In this implementation we use fixed layout for field values -
      the same for all records.
    */
    SORT_ADDON_FIELD *addonf= param->addon_field;
    uchar *nulls= to;
949
    DBUG_ASSERT(addonf != 0);
unknown's avatar
unknown committed
950 951 952 953 954
    bzero((char *) nulls, addonf->offset);
    to+= addonf->offset;
    for ( ; (field= addonf->field) ; addonf++)
    {
      if (addonf->null_bit && field->is_null())
955
      {
unknown's avatar
unknown committed
956
        nulls[addonf->null_offset]|= addonf->null_bit;
957 958 959 960
#ifdef HAVE_purify
	bzero(to, addonf->length);
#endif
      }
unknown's avatar
unknown committed
961
      else
962 963
      {
#ifdef HAVE_purify
964
        uchar *end= field->pack(to, field->ptr);
965 966 967 968
	uint length= (uint) ((to + addonf->length) - end);
	DBUG_ASSERT((int) length >= 0);
	if (length)
	  bzero(end, length);
969
#else
970
        (void) field->pack(to, field->ptr);
971 972
#endif
      }
unknown's avatar
unknown committed
973 974 975 976 977 978
      to+= addonf->length;
    }
  }
  else
  {
    /* Save filepos last */
979
    memcpy((uchar*) to, ref_pos, (size_t) param->ref_length);
unknown's avatar
unknown committed
980
  }
unknown's avatar
unknown committed
981 982 983
  return;
}

984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007

/*
  Register fields used by sorting in the sorted table's read set
*/

static void register_used_fields(SORTPARAM *param)
{
  reg1 SORT_FIELD *sort_field;
  TABLE *table=param->sort_form;
  MY_BITMAP *bitmap= table->read_set;

  for (sort_field= param->local_sortorder ;
       sort_field != param->end ;
       sort_field++)
  {
    Field *field;
    if ((field= sort_field->field))
    {
      if (field->table == table)
      bitmap_set_bit(bitmap, field->field_index);
    }
    else
    {						// Item
      sort_field->item->walk(&Item::register_field_in_read_map, 1,
1008
                             (uchar *) table);
1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026
    }
  }

  if (param->addon_field)
  {
    SORT_ADDON_FIELD *addonf= param->addon_field;
    Field *field;
    for ( ; (field= addonf->field) ; addonf++)
      bitmap_set_bit(bitmap, field->field_index);
  }
  else
  {
    /* Save filepos last */
    table->prepare_for_position();
  }
}


1027 1028
static bool save_index(SORTPARAM *param, uchar **sort_keys, uint count, 
                       FILESORT_INFO *table_sort)
unknown's avatar
unknown committed
1029
{
unknown's avatar
unknown committed
1030
  uint offset,res_length;
1031
  uchar *to;
unknown's avatar
unknown committed
1032 1033
  DBUG_ENTER("save_index");

1034
  my_string_ptr_sort((uchar*) sort_keys, (uint) count, param->sort_length);
unknown's avatar
unknown committed
1035 1036
  res_length= param->res_length;
  offset= param->rec_length-res_length;
unknown's avatar
unknown committed
1037 1038
  if ((ha_rows) count > param->max_rows)
    count=(uint) param->max_rows;
1039
  if (!(to= table_sort->record_pointers= 
1040
        (uchar*) my_malloc(res_length*count, MYF(MY_WME))))
unknown's avatar
unknown committed
1041 1042
    DBUG_RETURN(1);                 /* purecov: inspected */
  for (uchar **end= sort_keys+count ; sort_keys != end ; sort_keys++)
unknown's avatar
unknown committed
1043
  {
unknown's avatar
unknown committed
1044 1045
    memcpy(to, *sort_keys+offset, res_length);
    to+= res_length;
unknown's avatar
unknown committed
1046 1047 1048 1049 1050
  }
  DBUG_RETURN(0);
}


unknown's avatar
unknown committed
1051
/** Merge buffers to make < MERGEBUFF2 buffers. */
unknown's avatar
unknown committed
1052

1053 1054
int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
		    BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
unknown's avatar
unknown committed
1055
{
1056
  register uint i;
unknown's avatar
unknown committed
1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070
  IO_CACHE t_file2,*from_file,*to_file,*temp;
  BUFFPEK *lastbuff;
  DBUG_ENTER("merge_many_buff");

  if (*maxbuffer < MERGEBUFF2)
    DBUG_RETURN(0);				/* purecov: inspected */
  if (flush_io_cache(t_file) ||
      open_cached_file(&t_file2,mysql_tmpdir,TEMP_PREFIX,DISK_BUFFER_SIZE,
			MYF(MY_WME)))
    DBUG_RETURN(1);				/* purecov: inspected */

  from_file= t_file ; to_file= &t_file2;
  while (*maxbuffer >= MERGEBUFF2)
  {
1071 1072 1073 1074
    if (reinit_io_cache(from_file,READ_CACHE,0L,0,0))
      goto cleanup;
    if (reinit_io_cache(to_file,WRITE_CACHE,0L,0,0))
      goto cleanup;
unknown's avatar
unknown committed
1075
    lastbuff=buffpek;
1076
    for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
unknown's avatar
unknown committed
1077
    {
1078
      if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
unknown's avatar
unknown committed
1079
			buffpek+i,buffpek+i+MERGEBUFF-1,0))
1080
      goto cleanup;
unknown's avatar
unknown committed
1081
    }
1082
    if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
unknown's avatar
unknown committed
1083 1084 1085 1086 1087
		      buffpek+i,buffpek+ *maxbuffer,0))
      break;					/* purecov: inspected */
    if (flush_io_cache(to_file))
      break;					/* purecov: inspected */
    temp=from_file; from_file=to_file; to_file=temp;
1088 1089
    setup_io_cache(from_file);
    setup_io_cache(to_file);
unknown's avatar
unknown committed
1090 1091
    *maxbuffer= (uint) (lastbuff-buffpek)-1;
  }
1092
cleanup:
unknown's avatar
unknown committed
1093 1094
  close_cached_file(to_file);			// This holds old result
  if (to_file == t_file)
1095
  {
unknown's avatar
unknown committed
1096
    *t_file=t_file2;				// Copy result file
1097 1098
    setup_io_cache(t_file);
  }
unknown's avatar
unknown committed
1099 1100 1101 1102 1103

  DBUG_RETURN(*maxbuffer >= MERGEBUFF2);	/* Return 1 if interrupted */
} /* merge_many_buff */


unknown's avatar
unknown committed
1104 1105 1106 1107 1108 1109
/**
  Read data to buffer.

  @retval
    (uint)-1 if something goes wrong
*/
unknown's avatar
unknown committed
1110

1111
uint read_to_buffer(IO_CACHE *fromfile, BUFFPEK *buffpek,
unknown's avatar
unknown committed
1112
		    uint rec_length)
unknown's avatar
unknown committed
1113 1114 1115 1116 1117 1118
{
  register uint count;
  uint length;

  if ((count=(uint) min((ha_rows) buffpek->max_keys,buffpek->count)))
  {
Marc Alff's avatar
Marc Alff committed
1119 1120 1121
    if (mysql_file_pread(fromfile->file, (uchar*) buffpek->base,
                         (length= rec_length*count),
                         buffpek->file_pos, MYF_RW))
unknown's avatar
unknown committed
1122 1123 1124 1125 1126 1127
      return((uint) -1);			/* purecov: inspected */
    buffpek->key=buffpek->base;
    buffpek->file_pos+= length;			/* New filepos */
    buffpek->count-=	count;
    buffpek->mem_count= count;
  }
unknown's avatar
unknown committed
1128
  return (count*rec_length);
unknown's avatar
unknown committed
1129 1130 1131
} /* read_to_buffer */


unknown's avatar
unknown committed
1132 1133 1134 1135 1136 1137 1138 1139 1140
/**
  Put all room used by freed buffer to use in adjacent buffer.

  Note, that we can't simply distribute memory evenly between all buffers,
  because new areas must not overlap with old ones.

  @param[in] queue      list of non-empty buffers, without freed buffer
  @param[in] reuse      empty buffer
  @param[in] key_length key length
1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164
*/

void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint key_length)
{
  uchar *reuse_end= reuse->base + reuse->max_keys * key_length;
  for (uint i= 0; i < queue->elements; ++i)
  {
    BUFFPEK *bp= (BUFFPEK *) queue_element(queue, i);
    if (bp->base + bp->max_keys * key_length == reuse->base)
    {
      bp->max_keys+= reuse->max_keys;
      return;
    }
    else if (bp->base == reuse_end)
    {
      bp->base= reuse->base;
      bp->max_keys+= reuse->max_keys;
      return;
    }
  }
  DBUG_ASSERT(0);
}


unknown's avatar
unknown committed
1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180
/**
  Merge buffers to one buffer.

  @param param        Sort parameter
  @param from_file    File with source data (BUFFPEKs point to this file)
  @param to_file      File to write the sorted result data.
  @param sort_buffer  Buffer for data to store up to MERGEBUFF2 sort keys.
  @param lastbuff     OUT Store here BUFFPEK describing data written to to_file
  @param Fb           First element in source BUFFPEKs array
  @param Tb           Last element in source BUFFPEKs array
  @param flag

  @retval
    0      OK
  @retval
    other  error
unknown's avatar
unknown committed
1181
*/
unknown's avatar
unknown committed
1182

1183
int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
unknown's avatar
unknown committed
1184 1185 1186
                  IO_CACHE *to_file, uchar *sort_buffer,
                  BUFFPEK *lastbuff, BUFFPEK *Fb, BUFFPEK *Tb,
                  int flag)
unknown's avatar
unknown committed
1187 1188
{
  int error;
1189 1190
  uint rec_length,res_length,offset;
  size_t sort_length;
unknown's avatar
unknown committed
1191
  ulong maxcount;
1192
  ha_rows max_rows,org_max_rows;
unknown's avatar
unknown committed
1193 1194
  my_off_t to_start_filepos;
  uchar *strpos;
unknown's avatar
unknown committed
1195
  BUFFPEK *buffpek;
unknown's avatar
unknown committed
1196
  QUEUE queue;
unknown's avatar
unknown committed
1197
  qsort2_cmp cmp;
unknown's avatar
unknown committed
1198
  void *first_cmp_arg;
unknown's avatar
SCRUM  
unknown committed
1199 1200
  volatile THD::killed_state *killed= &current_thd->killed;
  THD::killed_state not_killable;
unknown's avatar
unknown committed
1201 1202
  DBUG_ENTER("merge_buffers");

1203
  status_var_increment(current_thd->status_var.filesort_merge_passes);
1204 1205 1206
  if (param->not_killable)
  {
    killed= &not_killable;
unknown's avatar
unknown committed
1207
    not_killable= THD::NOT_KILLED;
1208
  }
1209

1210
  error=0;
unknown's avatar
unknown committed
1211 1212 1213 1214 1215 1216 1217 1218 1219
  rec_length= param->rec_length;
  res_length= param->res_length;
  sort_length= param->sort_length;
  offset= rec_length-res_length;
  maxcount= (ulong) (param->keys/((uint) (Tb-Fb) +1));
  to_start_filepos= my_b_tell(to_file);
  strpos= (uchar*) sort_buffer;
  org_max_rows=max_rows= param->max_rows;

unknown's avatar
unknown committed
1220 1221 1222
  /* The following will fire if there is not enough space in sort_buffer */
  DBUG_ASSERT(maxcount!=0);
  
unknown's avatar
unknown committed
1223 1224 1225 1226 1227 1228 1229 1230 1231 1232
  if (param->unique_buff)
  {
    cmp= param->compare;
    first_cmp_arg= (void *) &param->cmp_context;
  }
  else
  {
    cmp= get_ptr_compare(sort_length);
    first_cmp_arg= (void*) &sort_length;
  }
unknown's avatar
unknown committed
1233
  if (init_queue(&queue, (uint) (Tb-Fb)+1, offsetof(BUFFPEK,key), 0,
unknown's avatar
unknown committed
1234
                 (queue_compare) cmp, first_cmp_arg))
unknown's avatar
unknown committed
1235
    DBUG_RETURN(1);                                /* purecov: inspected */
unknown's avatar
unknown committed
1236 1237 1238
  for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
  {
    buffpek->base= strpos;
unknown's avatar
unknown committed
1239 1240 1241
    buffpek->max_keys= maxcount;
    strpos+= (uint) (error= (int) read_to_buffer(from_file, buffpek,
                                                                         rec_length));
unknown's avatar
unknown committed
1242 1243
    if (error == -1)
      goto err;					/* purecov: inspected */
unknown's avatar
unknown committed
1244
    buffpek->max_keys= buffpek->mem_count;	// If less data in buffers than expected
1245
    queue_insert(&queue, (uchar*) buffpek);
unknown's avatar
unknown committed
1246 1247
  }

1248 1249 1250 1251 1252 1253 1254 1255 1256 1257
  if (param->unique_buff)
  {
    /* 
       Called by Unique::get()
       Copy the first argument to param->unique_buff for unique removal.
       Store it also in 'to_file'.

       This is safe as we know that there is always more than one element
       in each block to merge (This is guaranteed by the Unique:: algorithm
    */
unknown's avatar
unknown committed
1258 1259
    buffpek= (BUFFPEK*) queue_top(&queue);
    memcpy(param->unique_buff, buffpek->key, rec_length);
1260
    if (my_b_write(to_file, (uchar*) buffpek->key, rec_length))
1261
    {
unknown's avatar
unknown committed
1262
      error=1; goto err;                        /* purecov: inspected */
1263
    }
unknown's avatar
unknown committed
1264
    buffpek->key+= rec_length;
1265
    buffpek->mem_count--;
1266 1267
    if (!--max_rows)
    {
unknown's avatar
unknown committed
1268 1269
      error= 0;                                       /* purecov: inspected */
      goto end;                                       /* purecov: inspected */
1270
    }
unknown's avatar
unknown committed
1271
    queue_replaced(&queue);                        // Top element has been used
1272 1273
  }
  else
unknown's avatar
unknown committed
1274
    cmp= 0;                                        // Not unique
1275

unknown's avatar
unknown committed
1276 1277
  while (queue.elements > 1)
  {
1278 1279
    if (*killed)
    {
unknown's avatar
unknown committed
1280
      error= 1; goto err;                        /* purecov: inspected */
1281
    }
unknown's avatar
unknown committed
1282 1283
    for (;;)
    {
unknown's avatar
unknown committed
1284 1285
      buffpek= (BUFFPEK*) queue_top(&queue);
      if (cmp)                                        // Remove duplicates
1286
      {
unknown's avatar
unknown committed
1287
        if (!(*cmp)(first_cmp_arg, &(param->unique_buff),
unknown's avatar
unknown committed
1288 1289 1290
                    (uchar**) &buffpek->key))
              goto skip_duplicate;
            memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length);
1291
      }
unknown's avatar
unknown committed
1292 1293
      if (flag == 0)
      {
1294
        if (my_b_write(to_file,(uchar*) buffpek->key, rec_length))
unknown's avatar
unknown committed
1295 1296 1297
        {
          error=1; goto err;                        /* purecov: inspected */
        }
unknown's avatar
unknown committed
1298 1299 1300
      }
      else
      {
1301
        if (my_b_write(to_file, (uchar*) buffpek->key+offset, res_length))
unknown's avatar
unknown committed
1302 1303 1304
        {
          error=1; goto err;                        /* purecov: inspected */
        }
unknown's avatar
unknown committed
1305 1306 1307
      }
      if (!--max_rows)
      {
unknown's avatar
unknown committed
1308 1309
        error= 0;                               /* purecov: inspected */
        goto end;                               /* purecov: inspected */
unknown's avatar
unknown committed
1310
      }
1311 1312

    skip_duplicate:
unknown's avatar
unknown committed
1313
      buffpek->key+= rec_length;
unknown's avatar
unknown committed
1314 1315
      if (! --buffpek->mem_count)
      {
unknown's avatar
unknown committed
1316 1317 1318
        if (!(error= (int) read_to_buffer(from_file,buffpek,
                                          rec_length)))
        {
Konstantin Osipov's avatar
Konstantin Osipov committed
1319
          (void) queue_remove(&queue,0);
1320
          reuse_freed_buff(&queue, buffpek, rec_length);
unknown's avatar
unknown committed
1321 1322 1323 1324
          break;                        /* One buffer have been removed */
        }
        else if (error == -1)
          goto err;                        /* purecov: inspected */
unknown's avatar
unknown committed
1325
      }
unknown's avatar
unknown committed
1326
      queue_replaced(&queue);              /* Top element has been replaced */
unknown's avatar
unknown committed
1327 1328
    }
  }
unknown's avatar
unknown committed
1329
  buffpek= (BUFFPEK*) queue_top(&queue);
1330
  buffpek->base= sort_buffer;
unknown's avatar
unknown committed
1331
  buffpek->max_keys= param->keys;
1332 1333 1334 1335 1336 1337 1338

  /*
    As we know all entries in the buffer are unique, we only have to
    check if the first one is the same as the last one we wrote
  */
  if (cmp)
  {
unknown's avatar
unknown committed
1339
    if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (uchar**) &buffpek->key))
1340
    {
unknown's avatar
unknown committed
1341
      buffpek->key+= rec_length;         // Remove duplicate
1342 1343 1344 1345
      --buffpek->mem_count;
    }
  }

unknown's avatar
unknown committed
1346 1347 1348
  do
  {
    if ((ha_rows) buffpek->mem_count > max_rows)
unknown's avatar
unknown committed
1349 1350 1351
    {                                        /* Don't write too many records */
      buffpek->mem_count= (uint) max_rows;
      buffpek->count= 0;                        /* Don't read more */
unknown's avatar
unknown committed
1352
    }
unknown's avatar
unknown committed
1353
    max_rows-= buffpek->mem_count;
unknown's avatar
unknown committed
1354 1355
    if (flag == 0)
    {
1356
      if (my_b_write(to_file,(uchar*) buffpek->key,
unknown's avatar
unknown committed
1357
                     (rec_length*buffpek->mem_count)))
unknown's avatar
unknown committed
1358
      {
unknown's avatar
unknown committed
1359
        error= 1; goto err;                        /* purecov: inspected */
unknown's avatar
unknown committed
1360 1361 1362 1363 1364 1365
      }
    }
    else
    {
      register uchar *end;
      strpos= buffpek->key+offset;
unknown's avatar
unknown committed
1366 1367 1368 1369
      for (end= strpos+buffpek->mem_count*rec_length ;
           strpos != end ;
           strpos+= rec_length)
      {     
1370
        if (my_b_write(to_file, (uchar *) strpos, res_length))
unknown's avatar
unknown committed
1371 1372 1373
        {
          error=1; goto err;                        
        }
unknown's avatar
unknown committed
1374 1375 1376
      }
    }
  }
unknown's avatar
unknown committed
1377 1378
  while ((error=(int) read_to_buffer(from_file,buffpek, rec_length))
         != -1 && error != 0);
unknown's avatar
unknown committed
1379 1380

end:
unknown's avatar
unknown committed
1381 1382
  lastbuff->count= min(org_max_rows-max_rows, param->max_rows);
  lastbuff->file_pos= to_start_filepos;
unknown's avatar
unknown committed
1383 1384 1385 1386 1387 1388 1389 1390
err:
  delete_queue(&queue);
  DBUG_RETURN(error);
} /* merge_buffers */


	/* Do a merge to output-file (save only positions) */

1391
static int merge_index(SORTPARAM *param, uchar *sort_buffer,
unknown's avatar
unknown committed
1392 1393 1394 1395
		       BUFFPEK *buffpek, uint maxbuffer,
		       IO_CACHE *tempfile, IO_CACHE *outfile)
{
  DBUG_ENTER("merge_index");
1396
  if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
unknown's avatar
unknown committed
1397 1398 1399 1400 1401 1402
		    buffpek+maxbuffer,1))
    DBUG_RETURN(1);				/* purecov: inspected */
  DBUG_RETURN(0);
} /* merge_index */


1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415
static uint suffix_length(ulong string_length)
{
  if (string_length < 256)
    return 1;
  if (string_length < 256L*256L)
    return 2;
  if (string_length < 256L*256L*256L)
    return 3;
  return 4;                                     // Can't sort longer than 4G
}



unknown's avatar
unknown committed
1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427
/**
  Calculate length of sort key.

  @param thd			  Thread handler
  @param sortorder		  Order of items to sort
  @param s_length	          Number of items to sort
  @param[out] multi_byte_charset Set to 1 if we are using multi-byte charset
                                 (In which case we have to use strxnfrm())

  @note
    sortorder->length is updated for each sort item.
  @n
1428 1429
    sortorder->need_strxnfrm is set 1 if we have to use strxnfrm

unknown's avatar
unknown committed
1430
  @return
1431 1432
    Total length of sort buffer in bytes
*/
unknown's avatar
unknown committed
1433 1434

static uint
1435 1436
sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length,
           bool *multi_byte_charset)
unknown's avatar
unknown committed
1437 1438
{
  reg2 uint length;
1439
  CHARSET_INFO *cs;
1440
  *multi_byte_charset= 0;
unknown's avatar
unknown committed
1441 1442 1443 1444

  length=0;
  for (; s_length-- ; sortorder++)
  {
1445
    sortorder->need_strxnfrm= 0;
1446
    sortorder->suffix_length= 0;
unknown's avatar
unknown committed
1447 1448
    if (sortorder->field)
    {
1449 1450 1451 1452
      cs= sortorder->field->sort_charset();
      sortorder->length= sortorder->field->sort_length();

      if (use_strnxfrm((cs=sortorder->field->sort_charset())))
unknown's avatar
unknown committed
1453
      {
1454 1455 1456
        sortorder->need_strxnfrm= 1;
        *multi_byte_charset= 1;
        sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
unknown's avatar
unknown committed
1457 1458 1459 1460 1461 1462
      }
      if (sortorder->field->maybe_null())
	length++;				// Place for NULL marker
    }
    else
    {
unknown's avatar
unknown committed
1463 1464 1465 1466
      sortorder->result_type= sortorder->item->result_type();
      if (sortorder->item->result_as_longlong())
        sortorder->result_type= INT_RESULT;
      switch (sortorder->result_type) {
unknown's avatar
unknown committed
1467 1468
      case STRING_RESULT:
	sortorder->length=sortorder->item->max_length;
1469
        set_if_smaller(sortorder->length, thd->variables.max_sort_length);
1470
	if (use_strnxfrm((cs=sortorder->item->collation.collation)))
unknown's avatar
unknown committed
1471
	{ 
1472
          sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
1473 1474
	  sortorder->need_strxnfrm= 1;
	  *multi_byte_charset= 1;
1475
	}
1476 1477 1478 1479 1480 1481
        else if (cs == &my_charset_bin)
        {
          /* Store length last to be able to sort blob/varbinary */
          sortorder->suffix_length= suffix_length(sortorder->length);
          sortorder->length+= sortorder->suffix_length;
        }
unknown's avatar
unknown committed
1482 1483 1484 1485 1486 1487 1488 1489
	break;
      case INT_RESULT:
#if SIZEOF_LONG_LONG > 4
	sortorder->length=8;			// Size of intern longlong
#else
	sortorder->length=4;
#endif
	break;
unknown's avatar
unknown committed
1490 1491 1492 1493 1494 1495
      case DECIMAL_RESULT:
        sortorder->length=
          my_decimal_get_binary_size(sortorder->item->max_length - 
                                     (sortorder->item->decimals ? 1 : 0),
                                     sortorder->item->decimals);
        break;
unknown's avatar
unknown committed
1496 1497 1498
      case REAL_RESULT:
	sortorder->length=sizeof(double);
	break;
1499
      case ROW_RESULT:
unknown's avatar
unknown committed
1500
      default: 
unknown's avatar
unknown committed
1501 1502
	// This case should never be choosen
	DBUG_ASSERT(0);
unknown's avatar
unknown committed
1503
	break;
unknown's avatar
unknown committed
1504 1505 1506 1507
      }
      if (sortorder->item->maybe_null)
	length++;				// Place for NULL marker
    }
unknown's avatar
unknown committed
1508
    set_if_smaller(sortorder->length, thd->variables.max_sort_length);
unknown's avatar
unknown committed
1509 1510 1511 1512 1513 1514 1515 1516
    length+=sortorder->length;
  }
  sortorder->field= (Field*) 0;			// end marker
  DBUG_PRINT("info",("sort_length: %d",length));
  return length;
}


unknown's avatar
unknown committed
1517
/**
unknown's avatar
unknown committed
1518
  Get descriptors of fields appended to sorted fields and
unknown's avatar
unknown committed
1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534
  calculate its total length.

  The function first finds out what fields are used in the result set.
  Then it calculates the length of the buffer to store the values of
  these fields together with the value of sort values. 
  If the calculated length is not greater than max_length_for_sort_data
  the function allocates memory for an array of descriptors containing
  layouts for the values of the non-sorted fields in the buffer and
  fills them.

  @param thd                 Current thread
  @param ptabfield           Array of references to the table fields
  @param sortlength          Total length of sorted fields
  @param[out] plength        Total length of appended fields

  @note
unknown's avatar
unknown committed
1535 1536 1537
    The null bits for the appended values are supposed to be put together
    and stored the buffer just ahead of the value of the first field.

unknown's avatar
unknown committed
1538
  @return
unknown's avatar
unknown committed
1539
    Pointer to the layout descriptors for the appended fields, if any
unknown's avatar
unknown committed
1540 1541
  @retval
    NULL   if we do not store field values with sort data.
unknown's avatar
unknown committed
1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552
*/

static SORT_ADDON_FIELD *
get_addon_fields(THD *thd, Field **ptabfield, uint sortlength, uint *plength)
{
  Field **pfield;
  Field *field;
  SORT_ADDON_FIELD *addonf;
  uint length= 0;
  uint fields= 0;
  uint null_fields= 0;
1553 1554
  MY_BITMAP *read_set= (*ptabfield)->table->read_set;

1555 1556 1557 1558 1559 1560 1561 1562
  /*
    If there is a reference to a field in the query add it
    to the the set of appended fields.
    Note for future refinement:
    This this a too strong condition.
    Actually we need only the fields referred in the
    result set. And for some of them it makes sense to use 
    the values directly from sorted fields.
unknown's avatar
unknown committed
1563 1564
  */
  *plength= 0;
1565

unknown's avatar
unknown committed
1566 1567
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
  {
1568
    if (!bitmap_is_set(read_set, field->field_index))
unknown's avatar
unknown committed
1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590
      continue;
    if (field->flags & BLOB_FLAG)
      return 0;
    length+= field->max_packed_col_length(field->pack_length());
    if (field->maybe_null())
      null_fields++;
    fields++;
  } 
  if (!fields)
    return 0;
  length+= (null_fields+7)/8;

  if (length+sortlength > thd->variables.max_length_for_sort_data ||
      !(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)*
                                               (fields+1), MYF(MY_WME))))
    return 0;

  *plength= length;
  length= (null_fields+7)/8;
  null_fields= 0;
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
  {
1591
    if (!bitmap_is_set(read_set, field->field_index))
unknown's avatar
unknown committed
1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616
      continue;
    addonf->field= field;
    addonf->offset= length;
    if (field->maybe_null())
    {
      addonf->null_offset= null_fields/8;
      addonf->null_bit= 1<<(null_fields & 7);
      null_fields++;
    }
    else
    {
      addonf->null_offset= 0;
      addonf->null_bit= 0;
    }
    addonf->length= field->max_packed_col_length(field->pack_length());
    length+= addonf->length;
    addonf++;
  }
  addonf->field= 0;     // Put end marker
  
  DBUG_PRINT("info",("addon_length: %d",length));
  return (addonf-fields);
}


unknown's avatar
unknown committed
1617 1618
/**
  Copy (unpack) values appended to sorted fields from a buffer back to
unknown's avatar
unknown committed
1619 1620
  their regular positions specified by the Field::ptr pointers.

unknown's avatar
unknown committed
1621 1622
  @param addon_field     Array of descriptors for appended fields
  @param buff            Buffer which to unpack the value from
unknown's avatar
unknown committed
1623

unknown's avatar
unknown committed
1624
  @note
unknown's avatar
unknown committed
1625 1626 1627
    The function is supposed to be used only as a callback function
    when getting field values for the sorted result set.

unknown's avatar
unknown committed
1628
  @return
unknown's avatar
unknown committed
1629 1630 1631 1632
    void.
*/

static void 
1633
unpack_addon_fields(struct st_sort_addon_field *addon_field, uchar *buff)
unknown's avatar
unknown committed
1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645
{
  Field *field;
  SORT_ADDON_FIELD *addonf= addon_field;

  for ( ; (field= addonf->field) ; addonf++)
  {
    if (addonf->null_bit && (addonf->null_bit & buff[addonf->null_offset]))
    {
      field->set_null();
      continue;
    }
    field->set_notnull();
1646
    field->unpack(field->ptr, buff + addonf->offset);
unknown's avatar
unknown committed
1647 1648 1649
  }
}

unknown's avatar
unknown committed
1650 1651 1652 1653 1654 1655 1656
/*
** functions to change a double or float to a sortable string
** The following should work for IEEE
*/

#define DBL_EXP_DIG (sizeof(double)*8-DBL_MANT_DIG)

1657
void change_double_for_sort(double nr,uchar *to)
unknown's avatar
unknown committed
1658 1659 1660 1661 1662 1663 1664 1665 1666 1667
{
  uchar *tmp=(uchar*) to;
  if (nr == 0.0)
  {						/* Change to zero string */
    tmp[0]=(uchar) 128;
    bzero((char*) tmp+1,sizeof(nr)-1);
  }
  else
  {
#ifdef WORDS_BIGENDIAN
1668
    memcpy(tmp, &nr, sizeof(nr));
unknown's avatar
unknown committed
1669 1670 1671
#else
    {
      uchar *ptr= (uchar*) &nr;
1672
#if defined(__FLOAT_WORD_ORDER) && (__FLOAT_WORD_ORDER == __BIG_ENDIAN)
unknown's avatar
unknown committed
1673 1674 1675
      tmp[0]= ptr[3]; tmp[1]=ptr[2]; tmp[2]= ptr[1]; tmp[3]=ptr[0];
      tmp[4]= ptr[7]; tmp[5]=ptr[6]; tmp[6]= ptr[5]; tmp[7]=ptr[4];
#else
unknown's avatar
unknown committed
1676 1677
      tmp[0]= ptr[7]; tmp[1]=ptr[6]; tmp[2]= ptr[5]; tmp[3]=ptr[4];
      tmp[4]= ptr[3]; tmp[5]=ptr[2]; tmp[6]= ptr[1]; tmp[7]=ptr[0];
unknown's avatar
unknown committed
1678
#endif
unknown's avatar
unknown committed
1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696
    }
#endif
    if (tmp[0] & 128)				/* Negative */
    {						/* make complement */
      uint i;
      for (i=0 ; i < sizeof(nr); i++)
	tmp[i]=tmp[i] ^ (uchar) 255;
    }
    else
    {					/* Set high and move exponent one up */
      ushort exp_part=(((ushort) tmp[0] << 8) | (ushort) tmp[1] |
		       (ushort) 32768);
      exp_part+= (ushort) 1 << (16-1-DBL_EXP_DIG);
      tmp[0]= (uchar) (exp_part >> 8);
      tmp[1]= (uchar) exp_part;
    }
  }
}