filesort.cc 48.1 KB
Newer Older
unknown's avatar
unknown committed
1
/* Copyright (C) 2000-2006 MySQL AB  
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 27 28

#include "mysql_priv.h"
#ifdef HAVE_STDDEF_H
#include <stddef.h>			/* for macro offsetof */
#endif
#include <m_ctype.h>
29 30
#include "sql_sort.h"

unknown's avatar
unknown committed
31
#ifndef THREAD
unknown's avatar
unknown committed
32
#define SKIP_DBUG_IN_FILESORT
unknown's avatar
unknown committed
33 34
#endif

unknown's avatar
unknown committed
35
/// How to write record_ref.
unknown's avatar
unknown committed
36
#define WRITE_REF(file,from) \
37
if (my_b_write((file),(uchar*) (from),param->ref_length)) \
unknown's avatar
unknown committed
38 39 40 41
  DBUG_RETURN(1);

	/* functions defined in this file */

42 43
static char **make_char_array(char **old_pos, register uint fields,
                              uint length, myf my_flag);
44 45
static uchar *read_buffpek_from_file(IO_CACHE *buffer_file, uint count,
                                     uchar *buf);
unknown's avatar
unknown committed
46
static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
47
			     uchar * *sort_keys, IO_CACHE *buffer_file,
unknown's avatar
unknown committed
48 49
			     IO_CACHE *tempfile,IO_CACHE *indexfile);
static int write_keys(SORTPARAM *param,uchar * *sort_keys,
50
		      uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
51
static void make_sortkey(SORTPARAM *param,uchar *to, uchar *ref_pos);
52
static void register_used_fields(SORTPARAM *param);
53
static int merge_index(SORTPARAM *param,uchar *sort_buffer,
unknown's avatar
unknown committed
54 55 56
		       BUFFPEK *buffpek,
		       uint maxbuffer,IO_CACHE *tempfile,
		       IO_CACHE *outfile);
57 58
static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count, 
                       FILESORT_INFO *table_sort);
59 60
static uint suffix_length(ulong string_length);
static uint sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length,
61
		       bool *multi_byte_charset);
unknown's avatar
unknown committed
62 63 64
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,
65
                                uchar *buff);
unknown's avatar
unknown committed
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
/**
  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
85
			(Needed by UPDATE/INSERT or ALTER TABLE)
unknown's avatar
unknown committed
86
  @param examined_rows	Store number of examined rows here
87

unknown's avatar
unknown committed
88 89 90
  @todo
    check why we do this (param.keys--)
  @note
91 92 93
    If we sort by position (like if sort_positions is 1) filesort() will
    call table->prepare_for_position().

unknown's avatar
unknown committed
94
  @retval
95
    HA_POS_ERROR	Error
unknown's avatar
unknown committed
96 97 98
  @retval
    \#			Number of rows
  @retval
99 100
    examined_rows	will be set to number of examined rows
*/
101

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

  /*
   Release InnoDB's adaptive hash index latch (if holding) before
   running a sort.
  */
  ha_release_temporary_latches(thd);

130
  /* 
131 132 133
    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.
134 135 136
  */
  memcpy(&table_sort, &table->sort, sizeof(FILESORT_INFO));
  table->sort.io_cache= NULL;
137
  
138
  outfile= table_sort.io_cache;
unknown's avatar
unknown committed
139
  my_b_clear(&tempfile);
140 141 142
  my_b_clear(&buffpek_pointers);
  buffpek=0;
  error= 1;
143
  bzero((char*) &param,sizeof(param));
144
  param.sort_length= sortlength(thd, sortorder, s_length, &multi_byte_charset);
145
  param.ref_length= table->file->ref_length;
unknown's avatar
unknown committed
146 147
  param.addon_field= 0;
  param.addon_length= 0;
148 149
  if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
      !table->fulltext_searched && !sort_positions)
unknown's avatar
unknown committed
150 151 152 153 154 155 156 157 158
  {
    /* 
      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);
  }
159 160 161 162 163

  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
164 165 166
  if (param.addon_field)
  {
    param.res_length= param.addon_length;
167
    if (!(table_sort.addon_buf= (uchar *) my_malloc(param.addon_length,
unknown's avatar
unknown committed
168 169 170 171 172 173 174 175 176 177 178 179 180
                                                    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
181
  param.max_rows= max_rows;
unknown's avatar
unknown committed
182

183 184
  if (select && select->quick)
  {
185
    status_var_increment(thd->status_var.filesort_range_count);
186 187 188
  }
  else
  {
189
    status_var_increment(thd->status_var.filesort_scan_count);
190
  }
unknown's avatar
unknown committed
191
#ifdef CAN_TRUST_RANGE
192
  if (select && select->quick && select->quick->records > 0L)
unknown's avatar
unknown committed
193 194
  {
    records=min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
195
		table->file->stats.records)+EXTRA_RECORDS;
unknown's avatar
unknown committed
196 197 198
    selected_records_file=0;
  }
  else
199
#endif
unknown's avatar
unknown committed
200
  {
unknown's avatar
unknown committed
201 202 203 204 205 206 207
    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
208 209 210
    selected_records_file= 0;
  }

211
  if (multi_byte_charset &&
212
      !(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME))))
unknown's avatar
unknown committed
213 214
    goto err;

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

240
  param.keys--;  			/* TODO: check why we do this */
241
  param.sort_form= table;
unknown's avatar
unknown committed
242
  param.end=(param.local_sortorder=sortorder)+s_length;
243
  if ((records=find_all_keys(&param,select,sort_keys, &buffpek_pointers,
unknown's avatar
unknown committed
244 245 246
			     &tempfile, selected_records_file)) ==
      HA_POS_ERROR)
    goto err;
unknown's avatar
unknown committed
247
  maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
248

249
  if (maxbuffer == 0)			// The whole set is in memory
unknown's avatar
unknown committed
250
  {
251
    if (save_index(&param,sort_keys,(uint) records, &table_sort))
unknown's avatar
unknown committed
252 253 254 255
      goto err;
  }
  else
  {
unknown's avatar
unknown committed
256 257 258 259 260
    if (table_sort.buffpek && table_sort.buffpek_len < maxbuffer)
    {
      x_free(table_sort.buffpek);
      table_sort.buffpek= 0;
    }
261
    if (!(table_sort.buffpek=
262
          (uchar *) read_buffpek_from_file(&buffpek_pointers, maxbuffer,
unknown's avatar
unknown committed
263
                                 table_sort.buffpek)))
264
      goto err;
unknown's avatar
unknown committed
265 266
    buffpek= (BUFFPEK *) table_sort.buffpek;
    table_sort.buffpek_len= maxbuffer;
267
    close_cached_file(&buffpek_pointers);
unknown's avatar
unknown committed
268 269 270 271 272
	/* 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;
273 274
    if (reinit_io_cache(outfile,WRITE_CACHE,0L,0,0))
      goto err;
unknown's avatar
unknown committed
275

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

 err:
unknown's avatar
unknown committed
298
  if (param.tmp_buffer)
unknown's avatar
unknown committed
299
    x_free(param.tmp_buffer);
unknown's avatar
unknown committed
300 301
  if (!subselect || !subselect->is_uncacheable())
  {
302
    x_free((uchar*) sort_keys);
unknown's avatar
unknown committed
303
    table_sort.sort_keys= 0;
304
    x_free((uchar*) buffpek);
unknown's avatar
unknown committed
305 306 307
    table_sort.buffpek= 0;
    table_sort.buffpek_len= 0;
  }
unknown's avatar
unknown committed
308
  close_cached_file(&tempfile);
309
  close_cached_file(&buffpek_pointers);
unknown's avatar
unknown committed
310 311 312 313 314 315 316 317 318 319 320 321 322
  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
323 324
    my_message(ER_FILSORT_ABORT, ER(ER_FILSORT_ABORT),
               MYF(ME_ERROR+ME_WAITTANG));
325
  else
326 327
    statistic_add(thd->status_var.filesort_rows,
		  (ulong) records, &LOCK_status);
328
  *examined_rows= param.examined_rows;
unknown's avatar
unknown committed
329
#ifdef SKIP_DBUG_IN_FILESORT
unknown's avatar
unknown committed
330 331
  DBUG_POP();			/* Ok to DBUG */
#endif
332
  memcpy(&table->sort, &table_sort, sizeof(FILESORT_INFO));
unknown's avatar
unknown committed
333
  DBUG_PRINT("exit",("records: %ld", (long) records));
unknown's avatar
unknown committed
334 335 336 337
  DBUG_RETURN(error ? HA_POS_ERROR : records);
} /* filesort */


unknown's avatar
unknown committed
338
void filesort_free_buffers(TABLE *table, bool full)
unknown's avatar
unknown committed
339 340 341
{
  if (table->sort.record_pointers)
  {
342
    my_free((uchar*) table->sort.record_pointers,MYF(0));
unknown's avatar
unknown committed
343 344
    table->sort.record_pointers=0;
  }
unknown's avatar
unknown committed
345 346 347 348
  if (full)
  {
    if (table->sort.sort_keys )
    {
349
      x_free((uchar*) table->sort.sort_keys);
unknown's avatar
unknown committed
350 351 352 353
      table->sort.sort_keys= 0;
    }
    if (table->sort.buffpek)
    {
354
      x_free((uchar*) table->sort.buffpek);
unknown's avatar
unknown committed
355 356 357 358
      table->sort.buffpek= 0;
      table->sort.buffpek_len= 0;
    }
  }
unknown's avatar
unknown committed
359 360 361 362 363 364 365 366 367
  if (table->sort.addon_buf)
  {
    my_free((char *) table->sort.addon_buf, MYF(0));
    my_free((char *) table->sort.addon_field, MYF(MY_ALLOW_ZERO_PTR));
    table->sort.addon_buf=0;
    table->sort.addon_field=0;
  }
}

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

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

377 378 379
  if (old_pos ||
      (old_pos= (char**) my_malloc((uint) fields*(length+sizeof(char*)),
				   my_flag)))
unknown's avatar
unknown committed
380 381 382 383 384 385 386 387 388
  {
    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
389
/** Read 'count' number of buffer pointers into memory. */
390

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

unknown's avatar
unknown committed
464
/**
unknown's avatar
unknown committed
465
  Search after sort_keys and write them into tempfile.
unknown's avatar
unknown committed
466 467 468 469 470 471 472 473 474 475 476
  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
477
    Basic idea:
unknown's avatar
unknown committed
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495
    @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
496
    Number of records written on success.
unknown's avatar
unknown committed
497
  @retval
unknown's avatar
unknown committed
498 499
    HA_POS_ERROR on error.
*/
unknown's avatar
unknown committed
500 501 502

static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select,
			     uchar **sort_keys,
503
			     IO_CACHE *buffpek_pointers,
unknown's avatar
unknown committed
504 505 506 507
			     IO_CACHE *tempfile, IO_CACHE *indexfile)
{
  int error,flag,quick_select;
  uint idx,indexpos,ref_length;
508
  uchar *ref_pos,*next_pos,ref_buff[MAX_REFLENGTH];
unknown's avatar
unknown committed
509 510
  my_off_t record;
  TABLE *sort_form;
unknown's avatar
unknown committed
511
  THD *thd= current_thd;
512
  volatile THD::killed_state *killed= &thd->killed;
unknown's avatar
unknown committed
513
  handler *file;
514
  MY_BITMAP *save_read_set, *save_write_set;
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
    if (error == 0 && (!select || select->skip_record() == 0))
unknown's avatar
unknown committed
608 609 610
    {
      if (idx == param->keys)
      {
611 612
	if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
	  DBUG_RETURN(HA_POS_ERROR);
613 614
	idx=0;
	indexpos++;
unknown's avatar
unknown committed
615 616 617
      }
      make_sortkey(param,sort_keys[idx++],ref_pos);
    }
unknown's avatar
unknown committed
618 619
    else
      file->unlock_row();
unknown's avatar
unknown committed
620
    /* It does not make sense to read more keys in case of a fatal error */
621
    if (thd->is_error())
622
      break;
unknown's avatar
unknown committed
623
  }
624
  if (!quick_select)
625 626
  {
    (void) file->extra(HA_EXTRA_NO_CACHE);	/* End cacheing of records */
unknown's avatar
unknown committed
627 628
    if (!next_pos)
      file->ha_rnd_end();
629 630
  }

631
  if (thd->is_error())
632 633
    DBUG_RETURN(HA_POS_ERROR);
  
634 635 636
  /* 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
637 638 639 640 641 642
  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 */
  }
643
  if (indexpos && idx &&
644 645
      write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
    DBUG_RETURN(HA_POS_ERROR);			/* purecov: inspected */
unknown's avatar
unknown committed
646
  DBUG_RETURN(my_b_inited(tempfile) ?
unknown's avatar
unknown committed
647
	      (ha_rows) (my_b_tell(tempfile)/param->rec_length) :
unknown's avatar
unknown committed
648 649 650 651
	      idx);
} /* find_all_keys */


unknown's avatar
unknown committed
652 653
/**
  @details
unknown's avatar
unknown committed
654
  Sort the buffer and write:
unknown's avatar
unknown committed
655 656 657 658 659 660 661 662 663 664 665 666 667 668
  -# 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
669
    0 OK
unknown's avatar
unknown committed
670
  @retval
unknown's avatar
unknown committed
671 672
    1 Error
*/
unknown's avatar
unknown committed
673

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

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

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


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

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);
728
    break;
729 730 731 732 733 734 735
  default:
    mi_int4store(to, length);
    break;
  }
}


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

static void make_sortkey(register SORTPARAM *param,
739
			 register uchar *to, uchar *ref_pos)
unknown's avatar
unknown committed
740 741 742 743 744 745 746 747 748
{
  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
749
    bool maybe_null=0;
unknown's avatar
unknown committed
750 751 752 753 754 755
    if ((field=sort_field->field))
    {						// Field
      if (field->maybe_null())
      {
	if (field->is_null())
	{
unknown's avatar
unknown committed
756 757 758 759
	  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
760 761 762 763 764 765
	  to+= sort_field->length+1;
	  continue;
	}
	else
	  *to++=1;
      }
766
      field->sort_string(to, sort_field->length);
unknown's avatar
unknown committed
767 768 769 770
    }
    else
    {						// Item
      Item *item=sort_field->item;
771
      maybe_null= item->maybe_null;
unknown's avatar
unknown committed
772 773
      switch (sort_field->result_type) {
      case STRING_RESULT:
774
      {
unknown's avatar
unknown committed
775 776 777 778 779 780 781 782 783 784 785 786 787 788 789
        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
790
          {
791 792 793 794 795 796 797
            /* 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
798 799 800
            DBUG_PRINT("warning",
                       ("Got null on something that shouldn't be null"));
            bzero((char*) to,sort_field->length);	// Avoid crash
801
            /* purecov: end */
unknown's avatar
unknown committed
802
          }
unknown's avatar
unknown committed
803 804 805 806 807 808 809
          break;
        }
        length= res->length();
        sort_field_length= sort_field->length - sort_field->suffix_length;
        diff=(int) (sort_field_length - length);
        if (diff < 0)
        {
810
          diff=0;
unknown's avatar
unknown committed
811 812 813 814 815 816 817 818 819 820 821 822 823
          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
824
          {
unknown's avatar
unknown committed
825 826 827
            set_if_smaller(length,sort_field->length);
            memcpy(param->tmp_buffer,from,length);
            from=param->tmp_buffer;
unknown's avatar
unknown committed
828
          }
unknown's avatar
unknown committed
829 830 831 832 833 834 835 836 837 838
          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;
839
      }
unknown's avatar
unknown committed
840 841
      case INT_RESULT:
	{
842 843
          longlong value= item->val_int_result();
          if (maybe_null)
844
          {
unknown's avatar
unknown committed
845
	    *to++=1;				/* purecov: inspected */
846 847 848 849 850 851 852 853 854 855 856 857 858
            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
859 860 861 862 863 864 865 866
#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
867 868 869 870
          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
871 872 873 874
#else
	  to[3]= (uchar) value;
	  to[2]= (uchar) (value >> 8);
	  to[1]= (uchar) (value >> 16);
unknown's avatar
unknown committed
875 876 877 878
          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
879 880 881
#endif
	  break;
	}
unknown's avatar
unknown committed
882 883
      case DECIMAL_RESULT:
        {
884
          my_decimal dec_buf, *dec_val= item->val_decimal_result(&dec_buf);
885 886 887 888 889 890 891 892
          if (maybe_null)
          {
            if (item->null_value)
            { 
              bzero((char*)to, sort_field->length+1);
              to++;
              break;
            }
unknown's avatar
unknown committed
893
            *to++=1;
894
          }
895
          my_decimal2binary(E_DEC_FATAL_ERROR, dec_val, to,
unknown's avatar
unknown committed
896 897 898 899
                            item->max_length - (item->decimals ? 1:0),
                            item->decimals);
         break;
        }
unknown's avatar
unknown committed
900 901
      case REAL_RESULT:
	{
902
          double value= item->val_result();
903 904 905 906 907 908 909 910
	  if (maybe_null)
          {
            if (item->null_value)
            {
              bzero((char*) to,sort_field->length+1);
              to++;
              break;
            }
unknown's avatar
unknown committed
911
	    *to++=1;
912
          }
913
	  change_double_for_sort(value,(uchar*) to);
unknown's avatar
unknown committed
914 915
	  break;
	}
916
      case ROW_RESULT:
unknown's avatar
unknown committed
917
      default: 
unknown's avatar
unknown committed
918 919 920
	// This case should never be choosen
	DBUG_ASSERT(0);
	break;
unknown's avatar
unknown committed
921 922 923 924
      }
    }
    if (sort_field->reverse)
    {							/* Revers key */
unknown's avatar
unknown committed
925 926
      if (maybe_null)
        to[-1]= ~to[-1];
unknown's avatar
unknown committed
927 928 929 930 931 932 933 934 935 936
      length=sort_field->length;
      while (length--)
      {
	*to = (uchar) (~ *to);
	to++;
      }
    }
    else
      to+= sort_field->length;
  }
unknown's avatar
unknown committed
937 938 939 940 941 942 943 944 945 946 947

  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;
948
    DBUG_ASSERT(addonf != 0);
unknown's avatar
unknown committed
949 950 951 952 953
    bzero((char *) nulls, addonf->offset);
    to+= addonf->offset;
    for ( ; (field= addonf->field) ; addonf++)
    {
      if (addonf->null_bit && field->is_null())
954
      {
unknown's avatar
unknown committed
955
        nulls[addonf->null_offset]|= addonf->null_bit;
956 957 958 959
#ifdef HAVE_purify
	bzero(to, addonf->length);
#endif
      }
unknown's avatar
unknown committed
960
      else
961 962
      {
#ifdef HAVE_purify
963
        uchar *end= field->pack(to, field->ptr);
964 965 966 967
	uint length= (uint) ((to + addonf->length) - end);
	DBUG_ASSERT((int) length >= 0);
	if (length)
	  bzero(end, length);
968
#else
969
        (void) field->pack(to, field->ptr);
970 971
#endif
      }
unknown's avatar
unknown committed
972 973 974 975 976 977
      to+= addonf->length;
    }
  }
  else
  {
    /* Save filepos last */
978
    memcpy((uchar*) to, ref_pos, (size_t) param->ref_length);
unknown's avatar
unknown committed
979
  }
unknown's avatar
unknown committed
980 981 982
  return;
}

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

/*
  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,
1007
                             (uchar *) table);
1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025
    }
  }

  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();
  }
}


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

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


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

1052 1053
int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
		    BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
unknown's avatar
unknown committed
1054
{
1055
  register uint i;
unknown's avatar
unknown committed
1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069
  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)
  {
1070 1071 1072 1073
    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
1074
    lastbuff=buffpek;
1075
    for (i=0 ; i <= *maxbuffer-MERGEBUFF*3/2 ; i+=MERGEBUFF)
unknown's avatar
unknown committed
1076
    {
1077
      if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
unknown's avatar
unknown committed
1078
			buffpek+i,buffpek+i+MERGEBUFF-1,0))
1079
      goto cleanup;
unknown's avatar
unknown committed
1080
    }
1081
    if (merge_buffers(param,from_file,to_file,sort_buffer,lastbuff++,
unknown's avatar
unknown committed
1082 1083 1084 1085 1086
		      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;
1087 1088
    setup_io_cache(from_file);
    setup_io_cache(to_file);
unknown's avatar
unknown committed
1089 1090
    *maxbuffer= (uint) (lastbuff-buffpek)-1;
  }
1091
cleanup:
unknown's avatar
unknown committed
1092 1093
  close_cached_file(to_file);			// This holds old result
  if (to_file == t_file)
1094
  {
unknown's avatar
unknown committed
1095
    *t_file=t_file2;				// Copy result file
1096 1097
    setup_io_cache(t_file);
  }
unknown's avatar
unknown committed
1098 1099 1100 1101 1102

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


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

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

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

  if ((count=(uint) min((ha_rows) buffpek->max_keys,buffpek->count)))
  {
1118
    if (my_pread(fromfile->file,(uchar*) buffpek->base,
unknown's avatar
unknown committed
1119
		 (length= rec_length*count),buffpek->file_pos,MYF_RW))
unknown's avatar
unknown committed
1120 1121 1122 1123 1124 1125
      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
1126
  return (count*rec_length);
unknown's avatar
unknown committed
1127 1128 1129
} /* read_to_buffer */


unknown's avatar
unknown committed
1130 1131 1132 1133 1134 1135 1136 1137 1138
/**
  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
1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162
*/

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
1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178
/**
  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
1179
*/
unknown's avatar
unknown committed
1180

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

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

1208
  error=0;
unknown's avatar
unknown committed
1209 1210 1211 1212 1213 1214 1215 1216 1217
  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
1218 1219 1220
  /* The following will fire if there is not enough space in sort_buffer */
  DBUG_ASSERT(maxcount!=0);
  
unknown's avatar
unknown committed
1221 1222 1223 1224 1225 1226 1227 1228 1229 1230
  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
1231
  if (init_queue(&queue, (uint) (Tb-Fb)+1, offsetof(BUFFPEK,key), 0,
unknown's avatar
unknown committed
1232
                 (queue_compare) cmp, first_cmp_arg))
unknown's avatar
unknown committed
1233
    DBUG_RETURN(1);                                /* purecov: inspected */
unknown's avatar
unknown committed
1234 1235 1236
  for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
  {
    buffpek->base= strpos;
unknown's avatar
unknown committed
1237 1238 1239
    buffpek->max_keys= maxcount;
    strpos+= (uint) (error= (int) read_to_buffer(from_file, buffpek,
                                                                         rec_length));
unknown's avatar
unknown committed
1240 1241
    if (error == -1)
      goto err;					/* purecov: inspected */
unknown's avatar
unknown committed
1242
    buffpek->max_keys= buffpek->mem_count;	// If less data in buffers than expected
1243
    queue_insert(&queue, (uchar*) buffpek);
unknown's avatar
unknown committed
1244 1245
  }

1246 1247 1248 1249 1250 1251 1252 1253 1254 1255
  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
1256 1257
    buffpek= (BUFFPEK*) queue_top(&queue);
    memcpy(param->unique_buff, buffpek->key, rec_length);
1258
    if (my_b_write(to_file, (uchar*) buffpek->key, rec_length))
1259
    {
unknown's avatar
unknown committed
1260
      error=1; goto err;                        /* purecov: inspected */
1261
    }
unknown's avatar
unknown committed
1262
    buffpek->key+= rec_length;
1263
    buffpek->mem_count--;
1264 1265
    if (!--max_rows)
    {
unknown's avatar
unknown committed
1266 1267
      error= 0;                                       /* purecov: inspected */
      goto end;                                       /* purecov: inspected */
1268
    }
unknown's avatar
unknown committed
1269
    queue_replaced(&queue);                        // Top element has been used
1270 1271
  }
  else
unknown's avatar
unknown committed
1272
    cmp= 0;                                        // Not unique
1273

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

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

  /*
    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
1337
    if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (uchar**) &buffpek->key))
1338
    {
unknown's avatar
unknown committed
1339
      buffpek->key+= rec_length;         // Remove duplicate
1340 1341 1342 1343
      --buffpek->mem_count;
    }
  }

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

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


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

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


1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413
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
1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425
/**
  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
1426 1427
    sortorder->need_strxnfrm is set 1 if we have to use strxnfrm

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

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

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

      if (use_strnxfrm((cs=sortorder->field->sort_charset())))
unknown's avatar
unknown committed
1451
      {
1452 1453 1454
        sortorder->need_strxnfrm= 1;
        *multi_byte_charset= 1;
        sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
unknown's avatar
unknown committed
1455 1456 1457 1458 1459 1460
      }
      if (sortorder->field->maybe_null())
	length++;				// Place for NULL marker
    }
    else
    {
unknown's avatar
unknown committed
1461 1462 1463 1464
      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
1465 1466
      case STRING_RESULT:
	sortorder->length=sortorder->item->max_length;
1467
        set_if_smaller(sortorder->length, thd->variables.max_sort_length);
1468
	if (use_strnxfrm((cs=sortorder->item->collation.collation)))
unknown's avatar
unknown committed
1469
	{ 
1470
          sortorder->length= cs->coll->strnxfrmlen(cs, sortorder->length);
1471 1472
	  sortorder->need_strxnfrm= 1;
	  *multi_byte_charset= 1;
1473
	}
1474 1475 1476 1477 1478 1479
        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
1480 1481 1482 1483 1484 1485 1486 1487
	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
1488 1489 1490 1491 1492 1493
      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
1494 1495 1496
      case REAL_RESULT:
	sortorder->length=sizeof(double);
	break;
1497
      case ROW_RESULT:
unknown's avatar
unknown committed
1498
      default: 
unknown's avatar
unknown committed
1499 1500
	// This case should never be choosen
	DBUG_ASSERT(0);
unknown's avatar
unknown committed
1501
	break;
unknown's avatar
unknown committed
1502 1503 1504 1505
      }
      if (sortorder->item->maybe_null)
	length++;				// Place for NULL marker
    }
unknown's avatar
unknown committed
1506
    set_if_smaller(sortorder->length, thd->variables.max_sort_length);
unknown's avatar
unknown committed
1507 1508 1509 1510 1511 1512 1513 1514
    length+=sortorder->length;
  }
  sortorder->field= (Field*) 0;			// end marker
  DBUG_PRINT("info",("sort_length: %d",length));
  return length;
}


unknown's avatar
unknown committed
1515
/**
unknown's avatar
unknown committed
1516
  Get descriptors of fields appended to sorted fields and
unknown's avatar
unknown committed
1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532
  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
1533 1534 1535
    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
1536
  @return
unknown's avatar
unknown committed
1537
    Pointer to the layout descriptors for the appended fields, if any
unknown's avatar
unknown committed
1538 1539
  @retval
    NULL   if we do not store field values with sort data.
unknown's avatar
unknown committed
1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550
*/

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;
1551 1552
  MY_BITMAP *read_set= (*ptabfield)->table->read_set;

1553 1554 1555 1556 1557 1558 1559 1560
  /*
    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
1561 1562
  */
  *plength= 0;
1563

unknown's avatar
unknown committed
1564 1565
  for (pfield= ptabfield; (field= *pfield) ; pfield++)
  {
1566
    if (!bitmap_is_set(read_set, field->field_index))
unknown's avatar
unknown committed
1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588
      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++)
  {
1589
    if (!bitmap_is_set(read_set, field->field_index))
unknown's avatar
unknown committed
1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614
      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
1615 1616
/**
  Copy (unpack) values appended to sorted fields from a buffer back to
unknown's avatar
unknown committed
1617 1618
  their regular positions specified by the Field::ptr pointers.

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

unknown's avatar
unknown committed
1622
  @note
unknown's avatar
unknown committed
1623 1624 1625
    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
1626
  @return
unknown's avatar
unknown committed
1627 1628 1629 1630
    void.
*/

static void 
1631
unpack_addon_fields(struct st_sort_addon_field *addon_field, uchar *buff)
unknown's avatar
unknown committed
1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643
{
  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();
1644
    field->unpack(field->ptr, buff + addonf->offset);
unknown's avatar
unknown committed
1645 1646 1647
  }
}

unknown's avatar
unknown committed
1648 1649 1650 1651 1652 1653 1654
/*
** 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)

1655
void change_double_for_sort(double nr,uchar *to)
unknown's avatar
unknown committed
1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669
{
  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
    memcpy_fixed(tmp,&nr,sizeof(nr));
#else
    {
      uchar *ptr= (uchar*) &nr;
1670
#if defined(__FLOAT_WORD_ORDER) && (__FLOAT_WORD_ORDER == __BIG_ENDIAN)
unknown's avatar
unknown committed
1671 1672 1673
      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
1674 1675
      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
1676
#endif
unknown's avatar
unknown committed
1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694
    }
#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;
    }
  }
}