← Back to branch summary

~mdcallag/+junk/5.1-map

« back to all changes in this revision

Viewing changes to myisam/sort.c

  • Committer: sasha at sashanet
  • Date: 2001-04-12 01:09:00 UTC
  • mfrom: (669.1.1)
  • Revision ID: sp1r-sasha@mysql.sashanet.com-20010412010900-14282
Ugly merge of 3.23 changes into 4.0 - fix up needed

Show diffs side-by-side

added added

removed removed

Lines of Context:
myisam/sort.c
1
1
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
2
 
   
 
2
 
3
3
   This program is free software; you can redistribute it and/or modify
4
4
   it under the terms of the GNU General Public License as published by
5
5
   the Free Software Foundation; either version 2 of the License, or
6
6
   (at your option) any later version.
7
 
   
 
7
 
8
8
   This program is distributed in the hope that it will be useful,
9
9
   but WITHOUT ANY WARRANTY; without even the implied warranty of
10
10
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
11
   GNU General Public License for more details.
12
 
   
 
12
 
13
13
   You should have received a copy of the GNU General Public License
14
14
   along with this program; if not, write to the Free Software
15
15
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
19
19
  them in sorted order through SORT_INFO functions.
20
20
*/
21
21
 
22
 
#include "myisamdef.h"
 
22
#include "fulltext.h"
23
23
#if defined(MSDOS) || defined(__WIN__)
24
24
#include <fcntl.h>
25
25
#else
49
49
 
50
50
static ha_rows NEAR_F find_all_keys(MI_SORT_PARAM *info,uint keys,
51
51
                                    uchar **sort_keys,
52
 
                                    BUFFPEK *buffpek,int *maxbuffer,
53
 
                                    IO_CACHE *tempfile);
 
52
                                    DYNAMIC_ARRAY *buffpek,int *maxbuffer,
 
53
                                    IO_CACHE *tempfile,
 
54
                                    IO_CACHE *tempfile_for_exceptions);
54
55
static int NEAR_F write_keys(MI_SORT_PARAM *info,uchar * *sort_keys,
55
56
                             uint count, BUFFPEK *buffpek,IO_CACHE *tempfile);
 
57
static int NEAR_F write_key(MI_SORT_PARAM *info, uchar *key, IO_CACHE *tempfile);
56
58
static int NEAR_F write_index(MI_SORT_PARAM *info,uchar * *sort_keys,
57
59
                              uint count);
58
60
static int NEAR_F merge_many_buff(MI_SORT_PARAM *info,uint keys,
67
69
                                BUFFPEK *Fb, BUFFPEK *Tb);
68
70
static int NEAR_F merge_index(MI_SORT_PARAM *,uint,uchar **,BUFFPEK *, int,
69
71
                              IO_CACHE *);
70
 
static char **make_char_array(uint fields,uint length,myf my_flag);
71
72
 
72
73
        /* Creates a index of sorted keys */
73
74
        /* Returns 0 if everything went ok */
77
78
{
78
79
  int error,maxbuffer,skr;
79
80
  uint memavl,old_memavl,keys,sort_length;
80
 
  BUFFPEK *buffpek;
 
81
  DYNAMIC_ARRAY buffpek;
81
82
  ha_rows records;
82
83
  uchar **sort_keys;
83
 
  IO_CACHE tempfile;
 
84
  IO_CACHE tempfile, tempfile_for_exceptions;
84
85
  DBUG_ENTER("_create_index_by_sort");
85
86
  DBUG_PRINT("enter",("sort_length: %d", info->key_length));
86
87
 
87
88
  my_b_clear(&tempfile);
88
 
  buffpek= (BUFFPEK *) NULL; sort_keys= (uchar **) NULL; error= 1;
 
89
  my_b_clear(&tempfile_for_exceptions);
 
90
  bzero((char*) &buffpek,sizeof(buffpek));
 
91
  sort_keys= (uchar **) NULL; error= 1;
89
92
  maxbuffer=1;
90
93
 
91
94
  memavl=max(sortbuff_size,MIN_SORT_MEMORY);
113
116
      }
114
117
      while ((maxbuffer= (int) (records/(keys-1)+1)) != skr);
115
118
 
116
 
    if ((sort_keys= (uchar **) make_char_array(keys,sort_length,MYF(0))))
 
119
    if (sort_keys=(uchar **)my_malloc(keys*(sort_length+sizeof(char*))+HA_FT_MAXLEN, MYF(0)))
117
120
    {
118
 
      if ((buffpek = (BUFFPEK*) my_malloc((uint) (sizeof(BUFFPEK)*
119
 
                                                  (uint) maxbuffer),
120
 
                                          MYF(0))))
 
121
      if (init_dynamic_array(&buffpek, sizeof(BUFFPEK), maxbuffer, maxbuffer/2))
 
122
        my_free((gptr) sort_keys,MYF(0));
 
123
      else
121
124
        break;
122
 
      else
123
 
        my_free((gptr) sort_keys,MYF(0));
124
125
    }
125
126
    old_memavl=memavl;
126
127
    if ((memavl=memavl/4*3) < MIN_SORT_MEMORY && old_memavl > MIN_SORT_MEMORY)
136
137
  if (!no_messages)
137
138
    printf("  - Searching for keys, allocating buffer for %d keys\n",keys);
138
139
 
139
 
  if ((records=find_all_keys(info,keys,sort_keys,buffpek,&maxbuffer,&tempfile))
 
140
  if ((records=find_all_keys(info,keys,sort_keys,&buffpek,&maxbuffer,
 
141
                                  &tempfile,&tempfile_for_exceptions))
140
142
      == HA_POS_ERROR)
141
143
    goto err; /* purecov: tested */
142
144
  if (maxbuffer == 0)
153
155
    {
154
156
      if (!no_messages)
155
157
        printf("  - Merging %lu keys\n",records); /* purecov: tested */
156
 
      if (merge_many_buff(info,keys,sort_keys,buffpek,&maxbuffer,&tempfile))
 
158
      if (merge_many_buff(info,keys,sort_keys,
 
159
                  dynamic_element(&buffpek,0,BUFFPEK *),&maxbuffer,&tempfile))
157
160
        goto err; /* purecov: inspected */
158
161
    }
159
162
    if (flush_io_cache(&tempfile) ||
161
164
      goto err; /* purecov: inspected */
162
165
    if (!no_messages)
163
166
      puts("  - Last merge and dumping keys"); /* purecov: tested */
164
 
    if (merge_index(info,keys,sort_keys,buffpek,maxbuffer,&tempfile))
 
167
    if (merge_index(info,keys,sort_keys,dynamic_element(&buffpek,0,BUFFPEK *),
 
168
                    maxbuffer,&tempfile))
165
169
      goto err; /* purecov: inspected */
166
170
  }
 
171
 
 
172
  if (flush_pending_blocks(info->sort_info->param))
 
173
    goto err;
 
174
 
 
175
  if (my_b_inited(&tempfile_for_exceptions))
 
176
  {
 
177
    MI_INFO *index=info->sort_info->info;
 
178
    uint     keyno=info->sort_info->key;
 
179
    uint     key_length, ref_length=index->s->rec_reflength;
 
180
 
 
181
    if (flush_io_cache(&tempfile_for_exceptions) ||
 
182
        reinit_io_cache(&tempfile_for_exceptions,READ_CACHE,0L,0,0))
 
183
      goto err;
 
184
 
 
185
    while (!my_b_read(&tempfile_for_exceptions,(byte*)&key_length, sizeof(key_length))
 
186
        && !my_b_read(&tempfile_for_exceptions,(byte*)sort_keys,(uint)key_length))
 
187
    {
 
188
        if (_mi_ck_write(index,keyno,(byte*)sort_keys,key_length-ref_length)) goto err;
 
189
    }
 
190
  }
 
191
 
167
192
  error =0;
168
193
 
169
194
err:
170
195
  if (sort_keys)
171
196
    my_free((gptr) sort_keys,MYF(0));
172
 
  if (buffpek)
173
 
    my_free((gptr) buffpek,MYF(0));
 
197
  delete_dynamic(&buffpek);
174
198
  close_cached_file(&tempfile);
 
199
  close_cached_file(&tempfile_for_exceptions);
175
200
 
176
201
  DBUG_RETURN(error ? -1 : 0);
177
202
} /* _create_index_by_sort */
180
205
        /* Search after all keys and place them in a temp. file */
181
206
 
182
207
static ha_rows NEAR_F find_all_keys(MI_SORT_PARAM *info, uint keys,
183
 
                                    uchar **sort_keys, BUFFPEK *buffpek,
184
 
                                    int *maxbuffer, IO_CACHE *tempfile)
 
208
                                    uchar **sort_keys, DYNAMIC_ARRAY *buffpek,
 
209
                                    int *maxbuffer, IO_CACHE *tempfile,
 
210
                                    IO_CACHE *tempfile_for_exceptions)
185
211
{
186
212
  int error;
187
 
  uint idx,indexpos;
 
213
  uint idx;
188
214
  DBUG_ENTER("find_all_keys");
189
215
 
190
 
  idx=indexpos=error=0;
 
216
  idx=error=0;
 
217
  sort_keys[0]=(char*)(sort_keys+keys);
191
218
 
192
 
  while (!(error=(*info->key_read)(info->sort_info,sort_keys[idx])))
 
219
  while(!(error=(*info->key_read)(info->sort_info,sort_keys[idx])))
193
220
  {
194
 
    if ((uint) ++idx == keys)
195
 
    {
196
 
      if (indexpos >= (uint) *maxbuffer ||
197
 
          write_keys(info,sort_keys,idx-1,buffpek+indexpos,tempfile))
198
 
        DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
 
221
    if (info->sort_info->real_key_length > info->key_length)
 
222
    {
 
223
      if (write_key(info,sort_keys[idx],tempfile_for_exceptions))
 
224
        DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
 
225
      continue;
 
226
    }
 
227
 
 
228
    if (++idx == keys)
 
229
    {
 
230
      if (write_keys(info,sort_keys,idx-1,(BUFFPEK *)alloc_dynamic(buffpek),tempfile))
 
231
      DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
 
232
 
 
233
      sort_keys[0]=(char*)(sort_keys+keys);
199
234
      memcpy(sort_keys[0],sort_keys[idx-1],(size_t) info->key_length);
200
 
      idx=1; indexpos++;
 
235
      idx=1;
201
236
    }
 
237
    sort_keys[idx]=sort_keys[idx-1]+info->key_length;
202
238
  }
203
239
  if (error > 0)
204
240
    DBUG_RETURN(HA_POS_ERROR);          /* Aborted by get_key */ /* purecov: inspected */
205
 
  if (indexpos)
206
 
    if (indexpos >= (uint) *maxbuffer ||
207
 
        write_keys(info,sort_keys,idx,buffpek+indexpos,tempfile))
 
241
  if (buffpek->elements)
 
242
  {
 
243
    if (write_keys(info,sort_keys,idx,(BUFFPEK *)alloc_dynamic(buffpek),tempfile))
208
244
      DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
209
 
  *maxbuffer=(int) indexpos;
210
 
  DBUG_RETURN(indexpos*(keys-1)+idx);
 
245
    *maxbuffer=buffpek->elements-1;
 
246
  }
 
247
  else
 
248
    *maxbuffer=0;
 
249
 
 
250
  DBUG_RETURN((*maxbuffer)*(keys-1)+idx);
211
251
} /* find_all_keys */
212
252
 
213
 
 
214
253
        /* Write all keys in memory to file for later merge */
215
254
 
216
255
static int NEAR_F write_keys(MI_SORT_PARAM *info, register uchar **sort_keys,
222
261
  DBUG_ENTER("write_keys");
223
262
 
224
263
  qsort2((byte*) sort_keys,count,sizeof(byte*),(qsort2_cmp) info->key_cmp,
225
 
        info->sort_info);
 
264
         info->sort_info);
226
265
  if (!my_b_inited(tempfile) &&
227
266
      open_cached_file(tempfile, info->tmpdir, "ST", DISK_BUFFER_SIZE,
228
267
                       info->myf_rw))
229
268
    DBUG_RETURN(1); /* purecov: inspected */
 
269
 
230
270
  buffpek->file_pos=my_b_tell(tempfile);
231
271
  buffpek->count=count;
232
272
 
237
277
} /* write_keys */
238
278
 
239
279
 
 
280
static int NEAR_F write_key(MI_SORT_PARAM *info, uchar *key, IO_CACHE *tempfile)
 
281
{
 
282
  uint key_length=info->sort_info->real_key_length;
 
283
  DBUG_ENTER("write_key");
 
284
 
 
285
  if (!my_b_inited(tempfile) &&
 
286
      open_cached_file(tempfile, info->tmpdir, "ST", DISK_BUFFER_SIZE,
 
287
                       info->myf_rw))
 
288
    DBUG_RETURN(1);
 
289
 
 
290
  if (my_b_write(tempfile,(byte*)&key_length,sizeof(key_length)) ||
 
291
      my_b_write(tempfile,(byte*)key,(uint) key_length))
 
292
    DBUG_RETURN(1);
 
293
  DBUG_RETURN(0);
 
294
} /* write_key */
 
295
 
240
296
        /* Write index */
241
297
 
242
298
static int NEAR_F write_index(MI_SORT_PARAM *info, register uchar **sort_keys,
326
382
        /* If to_file == 0 then use info->key_write */
327
383
 
328
384
static int NEAR_F
329
 
merge_buffers(MI_SORT_PARAM *info, uint keys, IO_CACHE *from_file, 
 
385
merge_buffers(MI_SORT_PARAM *info, uint keys, IO_CACHE *from_file,
330
386
              IO_CACHE *to_file, uchar **sort_keys, BUFFPEK *lastbuff,
331
387
              BUFFPEK *Fb, BUFFPEK *Tb)
332
388
{
472
528
  DBUG_RETURN(0);
473
529
} /* merge_index */
474
530
 
475
 
 
476
 
        /* Make a pointer of arrays to keys */
477
 
 
478
 
static char **make_char_array(register uint fields, uint length, myf my_flag)
479
 
{
480
 
  register char **pos;
481
 
  char **old_pos,*char_pos;
482
 
  DBUG_ENTER("make_char_array");
483
 
 
484
 
  if ((old_pos= (char**) my_malloc( fields*(length+sizeof(char*)), my_flag)))
485
 
  {
486
 
    pos=old_pos; char_pos=((char*) (pos+fields)) -length;
487
 
    while (fields--)
488
 
      *(pos++) = (char_pos+= length);
489
 
  }
490
 
 
491
 
  DBUG_RETURN(old_pos);
492
 
} /* make_char_array */