← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/unique.cc

  • Committer: Brian Aker
  • Date: 2010-12-08 22:35:56 UTC
  • mfrom: (1819.9.158 update-innobase)
  • Revision ID: brian@tangent.org-20101208223556-37mi4omqg7lkjzf3
Merge in Stewart's changes, 1.3 changes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/unique.cc
11
11
 
12
12
   You should have received a copy of the GNU General Public License
13
13
   along with this program; if not, write to the Free Software
14
 
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
14
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
15
15
 
16
16
/*
17
17
  Function to handle quick removal of duplicates
21
21
  The basic idea is as follows:
22
22
 
23
23
  Store first all strings in a binary tree, ignoring duplicates.
24
 
  When the tree uses more memory than 'max_heap_table_size',
25
 
  write the tree (in sorted order) out to disk and start with a new tree.
26
 
  When all data has been generated, merge the trees (removing any found
27
 
  duplicates).
28
24
 
29
25
  The unique entries will be returned in sort order, to ensure that we do the
30
26
  deletes in disk order.
31
27
*/
32
28
 
33
 
#include <drizzled/server_includes.h>
34
 
#include <drizzled/sql_sort.h>
35
 
#include <drizzled/session.h>
36
 
#include CMATH_H
 
29
#include "config.h"
 
30
 
 
31
#include <math.h>
 
32
 
 
33
#include <queue>
 
34
 
 
35
#include "drizzled/sql_sort.h"
 
36
#include "drizzled/session.h"
 
37
#include "drizzled/sql_list.h"
 
38
#include "drizzled/internal/iocache.h"
37
39
 
38
40
#if defined(CMATH_NAMESPACE)
39
41
using namespace CMATH_NAMESPACE;
40
42
#endif
41
43
 
 
44
using namespace std;
42
45
 
43
 
int unique_write_to_file(unsigned char* key,
44
 
                         element_count count __attribute__((unused)),
45
 
                         Unique *unique)
 
46
namespace drizzled
46
47
{
47
 
  /*
48
 
    Use unique->size (size of element stored in the tree) and not
49
 
    unique->tree.size_of_element. The latter is different from unique->size
50
 
    when tree implementation chooses to store pointer to key in TREE_ELEMENT
51
 
    (instead of storing the element itself there)
52
 
  */
53
 
  return my_b_write(&unique->file, key, unique->size) ? 1 : 0;
54
 
}
55
48
 
56
49
int unique_write_to_ptrs(unsigned char* key,
57
 
                         element_count count __attribute__((unused)),
58
 
                         Unique *unique)
 
50
                         uint32_t, Unique *unique)
59
51
{
60
52
  memcpy(unique->record_pointers, key, unique->size);
61
53
  unique->record_pointers+=unique->size;
63
55
}
64
56
 
65
57
Unique::Unique(qsort_cmp2 comp_func, void * comp_func_fixed_arg,
66
 
               uint32_t size_arg, uint64_t max_in_memory_size_arg)
67
 
  :max_in_memory_size(max_in_memory_size_arg), size(size_arg), elements(0)
 
58
               uint32_t size_arg, size_t max_in_memory_size_arg)
 
59
  : max_in_memory_size(max_in_memory_size_arg),
 
60
    size(size_arg),
 
61
    elements(0)
68
62
{
69
 
  my_b_clear(&file);
70
 
  init_tree(&tree, (ulong) (max_in_memory_size / 16), 0, size, comp_func, 0,
 
63
  // Second element is max size for memory use in unique sort
 
64
  init_tree(&tree, 0, 0, size, comp_func, false,
71
65
            NULL, comp_func_fixed_arg);
72
 
  /* If the following fail's the next add will also fail */
73
 
  my_init_dynamic_array(&file_ptrs, sizeof(BUFFPEK), 16, 16);
74
 
  /*
75
 
    If you change the following, change it in get_max_elements function, too.
76
 
  */
77
 
  max_elements= (ulong) (max_in_memory_size /
78
 
                         ALIGN_SIZE(sizeof(TREE_ELEMENT)+size));
79
 
  open_cached_file(&file, drizzle_tmpdir,TEMP_PREFIX, DISK_BUFFER_SIZE,
80
 
                   MYF(MY_WME));
81
66
}
82
67
 
83
68
 
103
88
 
104
89
 
105
90
/*
106
 
  Calculate cost of merge_buffers function call for given sequence of
107
 
  input stream lengths and store the number of rows in result stream in *last.
108
 
 
109
 
  SYNOPSIS
110
 
    get_merge_buffers_cost()
111
 
      buff_elems  Array of #s of elements in buffers
112
 
      elem_size   Size of element stored in buffer
113
 
      first       Pointer to first merged element size
114
 
      last        Pointer to last merged element size
115
 
 
116
 
  RETURN
117
 
    Cost of merge_buffers operation in disk seeks.
118
 
 
119
 
  NOTES
120
 
    It is assumed that no rows are eliminated during merge.
121
 
    The cost is calculated as
122
 
 
123
 
      cost(read_and_write) + cost(merge_comparisons).
124
 
 
125
 
    All bytes in the sequences is read and written back during merge so cost
126
 
    of disk io is 2*elem_size*total_buf_elems/IO_SIZE (2 is for read + write)
127
 
 
128
 
    For comparisons cost calculations we assume that all merged sequences have
129
 
    the same length, so each of total_buf_size elements will be added to a sort
130
 
    heap with (n_buffers-1) elements. This gives the comparison cost:
131
 
 
132
 
      total_buf_elems* log2(n_buffers) / TIME_FOR_COMPARE_ROWID;
133
 
*/
134
 
 
135
 
static double get_merge_buffers_cost(uint32_t *buff_elems __attribute__((unused)),
136
 
                                     uint32_t elem_size,
137
 
                                     uint32_t *first, uint32_t *last)
138
 
{
139
 
  uint32_t total_buf_elems= 0;
140
 
  for (uint32_t *pbuf= first; pbuf <= last; pbuf++)
141
 
    total_buf_elems+= *pbuf;
142
 
  *last= total_buf_elems;
143
 
 
144
 
  int n_buffers= last - first + 1;
145
 
 
146
 
  /* Using log2(n)=log(n)/log(2) formula */
147
 
  return 2*((double)total_buf_elems*elem_size) / IO_SIZE +
148
 
     total_buf_elems*log((double) n_buffers) / (TIME_FOR_COMPARE_ROWID * M_LN2);
149
 
}
150
 
 
151
 
 
152
 
/*
153
 
  Calculate cost of merging buffers into one in Unique::get, i.e. calculate
154
 
  how long (in terms of disk seeks) the two calls
155
 
    merge_many_buffs(...);
156
 
    merge_buffers(...);
157
 
  will take.
158
 
 
159
 
  SYNOPSIS
160
 
    get_merge_many_buffs_cost()
161
 
      buffer        buffer space for temporary data, at least
162
 
                    Unique::get_cost_calc_buff_size bytes
163
 
      maxbuffer     # of full buffers
164
 
      max_n_elems   # of elements in first maxbuffer buffers
165
 
      last_n_elems  # of elements in last buffer
166
 
      elem_size     size of buffer element
167
 
 
168
 
  NOTES
169
 
    maxbuffer+1 buffers are merged, where first maxbuffer buffers contain
170
 
    max_n_elems elements each and last buffer contains last_n_elems elements.
171
 
 
172
 
    The current implementation does a dumb simulation of merge_many_buffs
173
 
    function actions.
174
 
 
175
 
  RETURN
176
 
    Cost of merge in disk seeks.
177
 
*/
178
 
 
179
 
static double get_merge_many_buffs_cost(uint32_t *buffer,
180
 
                                        uint32_t maxbuffer, uint32_t max_n_elems,
181
 
                                        uint32_t last_n_elems, int elem_size)
182
 
{
183
 
  register int i;
184
 
  double total_cost= 0.0;
185
 
  uint32_t *buff_elems= buffer; /* #s of elements in each of merged sequences */
186
 
 
187
 
  /*
188
 
    Set initial state: first maxbuffer sequences contain max_n_elems elements
189
 
    each, last sequence contains last_n_elems elements.
190
 
  */
191
 
  for (i = 0; i < (int)maxbuffer; i++)
192
 
    buff_elems[i]= max_n_elems;
193
 
  buff_elems[maxbuffer]= last_n_elems;
194
 
 
195
 
  /*
196
 
    Do it exactly as merge_many_buff function does, calling
197
 
    get_merge_buffers_cost to get cost of merge_buffers.
198
 
  */
199
 
  if (maxbuffer >= MERGEBUFF2)
200
 
  {
201
 
    while (maxbuffer >= MERGEBUFF2)
202
 
    {
203
 
      uint32_t lastbuff= 0;
204
 
      for (i = 0; i <= (int) maxbuffer - MERGEBUFF*3/2; i += MERGEBUFF)
205
 
      {
206
 
        total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
207
 
                                           buff_elems + i,
208
 
                                           buff_elems + i + MERGEBUFF-1);
209
 
        lastbuff++;
210
 
      }
211
 
      total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
212
 
                                         buff_elems + i,
213
 
                                         buff_elems + maxbuffer);
214
 
      maxbuffer= lastbuff;
215
 
    }
216
 
  }
217
 
 
218
 
  /* Simulate final merge_buff call. */
219
 
  total_cost += get_merge_buffers_cost(buff_elems, elem_size,
220
 
                                       buff_elems, buff_elems + maxbuffer);
221
 
  return total_cost;
222
 
}
223
 
 
224
 
 
225
 
/*
226
91
  Calculate cost of using Unique for processing nkeys elements of size
227
92
  key_size using max_in_memory_size memory.
228
93
 
257
122
 
258
123
      Approximate value of log2(N!) is calculated by log2_n_fact function.
259
124
 
 
125
       
 
126
      (The Next two are historical, we do all unique operations in memory or fail)
 
127
 
260
128
    2. Cost of merging.
261
129
      If only one tree is created by Unique no merging will be necessary.
262
130
      Otherwise, we model execution of merge_many_buff function and count
269
137
      these will be random seeks.
270
138
*/
271
139
 
272
 
double Unique::get_use_cost(uint32_t *buffer, uint32_t nkeys, uint32_t key_size,
273
 
                            uint64_t max_in_memory_size)
 
140
double Unique::get_use_cost(uint32_t *, uint32_t nkeys, uint32_t key_size,
 
141
                            size_t max_in_memory_size_arg)
274
142
{
275
143
  ulong max_elements_in_tree;
276
144
  ulong last_tree_elems;
277
 
  int   n_full_trees; /* number of trees in unique - 1 */
278
145
  double result;
279
146
 
280
 
  max_elements_in_tree= ((ulong) max_in_memory_size /
 
147
  max_elements_in_tree= ((ulong) max_in_memory_size_arg /
281
148
                         ALIGN_SIZE(sizeof(TREE_ELEMENT)+key_size));
282
149
 
283
 
  n_full_trees=    nkeys / max_elements_in_tree;
284
150
  last_tree_elems= nkeys % max_elements_in_tree;
285
151
 
286
152
  /* Calculate cost of creating trees */
287
153
  result= 2*log2_n_fact(last_tree_elems + 1.0);
288
 
  if (n_full_trees)
289
 
    result+= n_full_trees * log2_n_fact(max_elements_in_tree + 1.0);
290
154
  result /= TIME_FOR_COMPARE_ROWID;
291
155
 
292
 
 
293
 
  if (!n_full_trees)
294
 
    return result;
295
 
 
296
 
  /*
297
 
    There is more then one tree and merging is necessary.
298
 
    First, add cost of writing all trees to disk, assuming that all disk
299
 
    writes are sequential.
300
 
  */
301
 
  result += DISK_SEEK_BASE_COST * n_full_trees *
302
 
              ceil(((double) key_size)*max_elements_in_tree / IO_SIZE);
303
 
  result += DISK_SEEK_BASE_COST * ceil(((double) key_size)*last_tree_elems / IO_SIZE);
304
 
 
305
 
  /* Cost of merge */
306
 
  double merge_cost= get_merge_many_buffs_cost(buffer, n_full_trees,
307
 
                                               max_elements_in_tree,
308
 
                                               last_tree_elems, key_size);
309
 
  if (merge_cost < 0.0)
310
 
    return merge_cost;
311
 
 
312
 
  result += merge_cost;
313
 
  /*
314
 
    Add cost of reading the resulting sequence, assuming there were no
315
 
    duplicate elements.
316
 
  */
317
 
  result += ceil((double)key_size*nkeys/IO_SIZE);
318
 
 
319
156
  return result;
320
157
}
321
158
 
322
159
Unique::~Unique()
323
160
{
324
 
  close_cached_file(&file);
325
 
  delete_tree(&tree);
326
 
  delete_dynamic(&file_ptrs);
327
 
}
328
 
 
329
 
 
330
 
    /* Write tree to disk; clear tree */
331
 
bool Unique::flush()
332
 
{
333
 
  BUFFPEK file_ptr;
334
 
  elements+= tree.elements_in_tree;
335
 
  file_ptr.count=tree.elements_in_tree;
336
 
  file_ptr.file_pos=my_b_tell(&file);
337
 
 
338
 
  if (tree_walk(&tree, (tree_walk_action) unique_write_to_file,
339
 
                (void*) this, left_root_right) ||
340
 
      insert_dynamic(&file_ptrs, (unsigned char*) &file_ptr))
341
 
    return 1;
342
 
  delete_tree(&tree);
343
 
  return 0;
 
161
  delete_tree(&tree);
344
162
}
345
163
 
346
164
 
347
165
/*
348
 
  Clear the tree and the file.
 
166
  Clear the tree.
349
167
  You must call reset() if you want to reuse Unique after walk().
350
168
*/
351
169
 
353
171
Unique::reset()
354
172
{
355
173
  reset_tree(&tree);
356
 
  /*
357
 
    If elements != 0, some trees were stored in the file (see how
358
 
    flush() works). Note, that we can not count on my_b_tell(&file) == 0
359
 
    here, because it can return 0 right after walk(), and walk() does not
360
 
    reset any Unique member.
361
 
  */
362
 
  if (elements)
363
 
  {
364
 
    reset_dynamic(&file_ptrs);
365
 
    reinit_io_cache(&file, WRITE_CACHE, 0L, 0, 1);
366
 
  }
367
 
  elements= 0;
368
 
}
369
 
 
370
 
/*
371
 
  The comparison function, passed to queue_init() in merge_walk() and in
372
 
  merge_buffers() when the latter is called from Uniques::get() must
373
 
  use comparison function of Uniques::tree, but compare members of struct
374
 
  BUFFPEK.
375
 
*/
376
 
 
377
 
#ifdef __cplusplus
378
 
extern "C" {
379
 
#endif
380
 
 
381
 
static int buffpek_compare(void *arg, unsigned char *key_ptr1, unsigned char *key_ptr2)
382
 
{
383
 
  BUFFPEK_COMPARE_CONTEXT *ctx= (BUFFPEK_COMPARE_CONTEXT *) arg;
384
 
  return ctx->key_compare(ctx->key_compare_arg,
385
 
                          *((unsigned char **) key_ptr1), *((unsigned char **)key_ptr2));
386
 
}
387
 
 
388
 
#ifdef __cplusplus
389
 
}
390
 
#endif
391
 
 
392
 
 
393
 
 
394
 
/*
395
 
  DESCRIPTION
396
 
 
397
 
    Function is very similar to merge_buffers, but instead of writing sorted
398
 
    unique keys to the output file, it invokes walk_action for each key.
399
 
    This saves I/O if you need to pass through all unique keys only once.
400
 
 
401
 
  SYNOPSIS
402
 
    merge_walk()
403
 
  All params are 'IN' (but see comment for begin, end):
404
 
    merge_buffer       buffer to perform cached piece-by-piece loading
405
 
                       of trees; initially the buffer is empty
406
 
    merge_buffer_size  size of merge_buffer. Must be aligned with
407
 
                       key_length
408
 
    key_length         size of tree element; key_length * (end - begin)
409
 
                       must be less or equal than merge_buffer_size.
410
 
    begin              pointer to BUFFPEK struct for the first tree.
411
 
    end                pointer to BUFFPEK struct for the last tree;
412
 
                       end > begin and [begin, end) form a consecutive
413
 
                       range. BUFFPEKs structs in that range are used and
414
 
                       overwritten in merge_walk().
415
 
    walk_action        element visitor. Action is called for each unique
416
 
                       key.
417
 
    walk_action_arg    argument to walk action. Passed to it on each call.
418
 
    compare            elements comparison function
419
 
    compare_arg        comparison function argument
420
 
    file               file with all trees dumped. Trees in the file
421
 
                       must contain sorted unique values. Cache must be
422
 
                       initialized in read mode.
423
 
  RETURN VALUE
424
 
    0     ok
425
 
    <> 0  error
426
 
*/
427
 
 
428
 
static bool merge_walk(unsigned char *merge_buffer, ulong merge_buffer_size,
429
 
                       uint32_t key_length, BUFFPEK *begin, BUFFPEK *end,
430
 
                       tree_walk_action walk_action, void *walk_action_arg,
431
 
                       qsort_cmp2 compare, void *compare_arg,
432
 
                       IO_CACHE *file)
433
 
{
434
 
  BUFFPEK_COMPARE_CONTEXT compare_context = { compare, compare_arg };
435
 
  QUEUE queue;
436
 
  if (end <= begin ||
437
 
      merge_buffer_size < (ulong) (key_length * (end - begin + 1)) ||
438
 
      init_queue(&queue, (uint) (end - begin), offsetof(BUFFPEK, key), 0,
439
 
                 buffpek_compare, &compare_context))
440
 
    return 1;
441
 
  /* we need space for one key when a piece of merge buffer is re-read */
442
 
  merge_buffer_size-= key_length;
443
 
  unsigned char *save_key_buff= merge_buffer + merge_buffer_size;
444
 
  uint32_t max_key_count_per_piece= (uint) (merge_buffer_size/(end-begin) /
445
 
                                        key_length);
446
 
  /* if piece_size is aligned reuse_freed_buffer will always hit */
447
 
  uint32_t piece_size= max_key_count_per_piece * key_length;
448
 
  uint32_t bytes_read;               /* to hold return value of read_to_buffer */
449
 
  BUFFPEK *top;
450
 
  int res= 1;
451
 
  /*
452
 
    Invariant: queue must contain top element from each tree, until a tree
453
 
    is not completely walked through.
454
 
    Here we're forcing the invariant, inserting one element from each tree
455
 
    to the queue.
456
 
  */
457
 
  for (top= begin; top != end; ++top)
458
 
  {
459
 
    top->base= merge_buffer + (top - begin) * piece_size;
460
 
    top->max_keys= max_key_count_per_piece;
461
 
    bytes_read= read_to_buffer(file, top, key_length);
462
 
    if (bytes_read == (uint) (-1))
463
 
      goto end;
464
 
    assert(bytes_read);
465
 
    queue_insert(&queue, (unsigned char *) top);
466
 
  }
467
 
  top= (BUFFPEK *) queue_top(&queue);
468
 
  while (queue.elements > 1)
469
 
  {
470
 
    /*
471
 
      Every iteration one element is removed from the queue, and one is
472
 
      inserted by the rules of the invariant. If two adjacent elements on
473
 
      the top of the queue are not equal, biggest one is unique, because all
474
 
      elements in each tree are unique. Action is applied only to unique
475
 
      elements.
476
 
    */
477
 
    void *old_key= top->key;
478
 
    /*
479
 
      read next key from the cache or from the file and push it to the
480
 
      queue; this gives new top.
481
 
    */
482
 
    top->key+= key_length;
483
 
    if (--top->mem_count)
484
 
      queue_replaced(&queue);
485
 
    else /* next piece should be read */
486
 
    {
487
 
      /* save old_key not to overwrite it in read_to_buffer */
488
 
      memcpy(save_key_buff, old_key, key_length);
489
 
      old_key= save_key_buff;
490
 
      bytes_read= read_to_buffer(file, top, key_length);
491
 
      if (bytes_read == (uint) (-1))
492
 
        goto end;
493
 
      else if (bytes_read > 0)      /* top->key, top->mem_count are reset */
494
 
        queue_replaced(&queue);     /* in read_to_buffer */
495
 
      else
496
 
      {
497
 
        /*
498
 
          Tree for old 'top' element is empty: remove it from the queue and
499
 
          give all its memory to the nearest tree.
500
 
        */
501
 
        queue_remove(&queue, 0);
502
 
        reuse_freed_buff(&queue, top, key_length);
503
 
      }
504
 
    }
505
 
    top= (BUFFPEK *) queue_top(&queue);
506
 
    /* new top has been obtained; if old top is unique, apply the action */
507
 
    if (compare(compare_arg, old_key, top->key))
508
 
    {
509
 
      if (walk_action(old_key, 1, walk_action_arg))
510
 
        goto end;
511
 
    }
512
 
  }
513
 
  /*
514
 
    Applying walk_action to the tail of the last tree: this is safe because
515
 
    either we had only one tree in the beginning, either we work with the
516
 
    last tree in the queue.
517
 
  */
518
 
  do
519
 
  {
520
 
    do
521
 
    {
522
 
      if (walk_action(top->key, 1, walk_action_arg))
523
 
        goto end;
524
 
      top->key+= key_length;
525
 
    }
526
 
    while (--top->mem_count);
527
 
    bytes_read= read_to_buffer(file, top, key_length);
528
 
    if (bytes_read == (uint) (-1))
529
 
      goto end;
530
 
  }
531
 
  while (bytes_read);
532
 
  res= 0;
533
 
end:
534
 
  delete_queue(&queue);
535
 
  return res;
 
174
  assert(elements == 0);
536
175
}
537
176
 
538
177
 
548
187
  SYNOPSIS
549
188
    Unique:walk()
550
189
  All params are 'IN':
551
 
    action  function-visitor, typed in include/my_tree.h
 
190
    action  function-visitor, typed in include/tree.h
552
191
            function is called for each unique element
553
192
    arg     argument for visitor, which is passed to it on each call
554
193
  RETURN VALUE
558
197
 
559
198
bool Unique::walk(tree_walk_action action, void *walk_action_arg)
560
199
{
561
 
  int res;
562
 
  unsigned char *merge_buffer;
563
 
 
564
 
  if (elements == 0)                       /* the whole tree is in memory */
565
 
    return tree_walk(&tree, action, walk_action_arg, left_root_right);
566
 
 
567
 
  /* flush current tree to the file to have some memory for merge buffer */
568
 
  if (flush())
569
 
    return 1;
570
 
  if (flush_io_cache(&file) || reinit_io_cache(&file, READ_CACHE, 0L, 0, 0))
571
 
    return 1;
572
 
  if (!(merge_buffer= (unsigned char *) my_malloc((ulong) max_in_memory_size, MYF(0))))
573
 
    return 1;
574
 
  res= merge_walk(merge_buffer, (ulong) max_in_memory_size, size,
575
 
                  (BUFFPEK *) file_ptrs.buffer,
576
 
                  (BUFFPEK *) file_ptrs.buffer + file_ptrs.elements,
577
 
                  action, walk_action_arg,
578
 
                  tree.compare, tree.custom_arg, &file);
579
 
  free((char*) merge_buffer);
580
 
  return res;
 
200
  return tree_walk(&tree, action, walk_action_arg, left_root_right);
581
201
}
582
202
 
583
203
/*
587
207
 
588
208
bool Unique::get(Table *table)
589
209
{
590
 
  SORTPARAM sort_param;
591
 
  table->sort.found_records=elements+tree.elements_in_tree;
 
210
  table->sort.found_records= elements+tree.elements_in_tree;
592
211
 
593
 
  if (my_b_tell(&file) == 0)
 
212
  if ((record_pointers=table->sort.record_pointers= (unsigned char*)
 
213
       malloc(size * tree.elements_in_tree)))
594
214
  {
595
 
    /* Whole tree is in memory;  Don't use disk if you don't need to */
596
 
    if ((record_pointers=table->sort.record_pointers= (unsigned char*)
597
 
         my_malloc(size * tree.elements_in_tree, MYF(0))))
598
 
    {
599
 
      (void) tree_walk(&tree, (tree_walk_action) unique_write_to_ptrs,
600
 
                       this, left_root_right);
601
 
      return 0;
602
 
    }
 
215
    (void) tree_walk(&tree, (tree_walk_action) unique_write_to_ptrs,
 
216
                     this, left_root_right);
 
217
    return 0;
603
218
  }
604
 
  /* Not enough memory; Save the result to file && free memory used by tree */
605
 
  if (flush())
606
 
    return 1;
607
 
 
608
 
  IO_CACHE *outfile=table->sort.io_cache;
609
 
  BUFFPEK *file_ptr= (BUFFPEK*) file_ptrs.buffer;
610
 
  uint32_t maxbuffer= file_ptrs.elements - 1;
611
 
  unsigned char *sort_buffer;
612
 
  my_off_t save_pos;
613
 
  bool error=1;
614
 
 
615
 
      /* Open cached file if it isn't open */
616
 
  outfile=table->sort.io_cache=(IO_CACHE*) my_malloc(sizeof(IO_CACHE),
617
 
                                MYF(MY_ZEROFILL));
618
 
 
619
 
  if (!outfile || (! my_b_inited(outfile) && open_cached_file(outfile,drizzle_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER, MYF(MY_WME))))
620
 
    return 1;
621
 
  reinit_io_cache(outfile,WRITE_CACHE,0L,0,0);
622
 
 
623
 
  memset(&sort_param, 0, sizeof(sort_param));
624
 
  sort_param.max_rows= elements;
625
 
  sort_param.sort_form=table;
626
 
  sort_param.rec_length= sort_param.sort_length= sort_param.ref_length=
627
 
    size;
628
 
  sort_param.keys= (uint) (max_in_memory_size / sort_param.sort_length);
629
 
  sort_param.not_killable=1;
630
 
 
631
 
  if (!(sort_buffer=(unsigned char*) my_malloc((sort_param.keys+1) *
632
 
                                       sort_param.sort_length,
633
 
                                       MYF(0))))
634
 
    return 1;
635
 
  sort_param.unique_buff= sort_buffer+(sort_param.keys*
636
 
                                       sort_param.sort_length);
637
 
 
638
 
  sort_param.compare= (qsort2_cmp) buffpek_compare;
639
 
  sort_param.cmp_context.key_compare= tree.compare;
640
 
  sort_param.cmp_context.key_compare_arg= tree.custom_arg;
641
 
 
642
 
  /* Merge the buffers to one file, removing duplicates */
643
 
  if (merge_many_buff(&sort_param,sort_buffer,file_ptr,&maxbuffer,&file))
644
 
    goto err;
645
 
  if (flush_io_cache(&file) ||
646
 
      reinit_io_cache(&file,READ_CACHE,0L,0,0))
647
 
    goto err;
648
 
  if (merge_buffers(&sort_param, &file, outfile, sort_buffer, file_ptr,
649
 
                    file_ptr, file_ptr+maxbuffer,0))
650
 
    goto err;
651
 
  error=0;
652
 
err:
653
 
  if (sort_buffer)
654
 
    free(sort_buffer);
655
 
  if (flush_io_cache(outfile))
656
 
    error=1;
657
 
 
658
 
  /* Setup io_cache for reading */
659
 
  save_pos=outfile->pos_in_file;
660
 
  if (reinit_io_cache(outfile,READ_CACHE,0L,0,0))
661
 
    error=1;
662
 
  outfile->end_of_file=save_pos;
663
 
  return error;
 
219
  /* Not enough memory */
 
220
  return 1;
664
221
}
 
222
 
 
223
} /* namespace drizzled */