← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/unique.cc

  • Committer: Stewart Smith
  • Date: 2010-11-03 03:27:09 UTC
  • mto: (1902.1.1 build) (1910.1.2 build)
  • mto: This revision was merged to the branch mainline in revision 1903.
  • Revision ID: stewart@flamingspork.com-20101103032709-oyvfrc6eb8fzj0mr
fix docs warning: docs/unlock.rst:2: (WARNING/2) Title underline too short.

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