usr.bin/sort/msort.c

   1 /*      $NetBSD: msort.c,v 1.29 2009/11/06 18:34:22 joerg Exp $ */
   2
   3 /*-
   4  * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Ben Harris and Jaromir Dolecek.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*-
  33  * Copyright (c) 1993
  34  *      The Regents of the University of California.  All rights reserved.
  35  *
  36  * This code is derived from software contributed to Berkeley by
  37  * Peter McIlroy.
  38  *
  39  * Redistribution and use in source and binary forms, with or without
  40  * modification, are permitted provided that the following conditions
  41  * are met:
  42  * 1. Redistributions of source code must retain the above copyright
  43  *    notice, this list of conditions and the following disclaimer.
  44  * 2. Redistributions in binary form must reproduce the above copyright
  45  *    notice, this list of conditions and the following disclaimer in the
  46  *    documentation and/or other materials provided with the distribution.
  47  * 3. Neither the name of the University nor the names of its contributors
  48  *    may be used to endorse or promote products derived from this software
  49  *    without specific prior written permission.
  50  *
  51  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  52  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  53  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  54  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  55  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  56  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  57  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  58  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  59  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  60  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  61  * SUCH DAMAGE.
  62  */
  63
  64 #include "sort.h"
  65 #include "fsort.h"
  66
  67 #include <stdlib.h>
  68 #include <string.h>
  69 #include <unistd.h>
  70
  71 /* Subroutines using comparisons: merge sort and check order */
  72 #define DELETE (1)
  73
  74 typedef struct mfile {
  75         FILE         *fp;
  76         get_func_t   get;
  77         RECHEADER    *rec;
  78         u_char       *end;
  79 } MFILE;
  80
  81 static int cmp(RECHEADER *, RECHEADER *);
  82 static int insert(struct mfile **, struct mfile *, int, int);
  83 static void merge_sort_fstack(FILE *, put_func_t, struct field *);
  84
  85 /*
  86  * Number of files merge() can merge in one pass.
  87  */
  88 #define MERGE_FNUM      16
  89
  90 static struct mfile fstack[MERGE_FNUM];
  91 static struct mfile fstack_1[MERGE_FNUM];
  92 static struct mfile fstack_2[MERGE_FNUM];
  93 static int fstack_count, fstack_1_count, fstack_2_count;
  94
  95 void
  96 save_for_merge(FILE *fp, get_func_t get, struct field *ftbl)
  97 {
  98         FILE *mfp, *mfp1, *mfp2;
  99
 100         if (fstack_count == MERGE_FNUM) {
 101                 /* Must reduce the number of temporary files */
 102                 mfp = ftmp();
 103                 merge_sort_fstack(mfp, putrec, ftbl);
 104                 /* Save output in next layer */
 105                 if (fstack_1_count == MERGE_FNUM) {
 106                         mfp1 = ftmp();
 107                         memcpy(fstack, fstack_1, sizeof fstack);
 108                         merge_sort_fstack(mfp1, putrec, ftbl);
 109                         if (fstack_2_count == MERGE_FNUM) {
 110                                 /* More than 4096 files! */
 111                                 mfp2 = ftmp();
 112                                 memcpy(fstack, fstack_2, sizeof fstack);
 113                                 merge_sort_fstack(mfp2, putrec, ftbl);
 114                                 fstack_2[0].fp = mfp2;
 115                                 fstack_2_count = 1;
 116                         }
 117                         fstack_2[fstack_2_count].fp = mfp1;
 118                         fstack_2[fstack_2_count].get = geteasy;
 119                         fstack_2_count++;
 120                         fstack_1_count = 0;
 121                 }
 122                 fstack_1[fstack_1_count].fp = mfp;
 123                 fstack_1[fstack_1_count].get = geteasy;
 124                 fstack_1_count++;
 125                 fstack_count = 0;
 126         }
 127
 128         fstack[fstack_count].fp = fp;
 129         fstack[fstack_count++].get = get;
 130 }
 131
 132 void
 133 fmerge(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl)
 134 {
 135         get_func_t get = SINGL_FLD ? makeline : makekey;
 136         FILE *fp;
 137         int i;
 138
 139         for (i = 0; i < nfiles; i++) {
 140                 fp = fopen(filelist->names[i], "r");
 141                 if (fp == NULL)
 142                         err(2, "%s", filelist->names[i]);
 143                 save_for_merge(fp, get, ftbl);
 144         }
 145
 146         merge_sort(outfp, putline, ftbl);
 147 }
 148
 149 void
 150 merge_sort(FILE *outfp, put_func_t put, struct field *ftbl)
 151 {
 152         int count = fstack_1_count + fstack_2_count;
 153         FILE *mfp;
 154         int i;
 155
 156         if (count == 0) {
 157                 /* All files in initial array */
 158                 merge_sort_fstack(outfp, put, ftbl);
 159                 return;
 160         }
 161
 162         count += fstack_count;
 163
 164         /* Too many files for one merge sort */
 165         for (;;) {
 166                 /* Sort latest 16 files */
 167                 i = count;
 168                 if (i > MERGE_FNUM)
 169                         i = MERGE_FNUM;
 170                 while (fstack_count > 0)
 171                         fstack[--i] = fstack[--fstack_count];
 172                 while (i > 0 && fstack_1_count > 0)
 173                         fstack[--i] = fstack_1[--fstack_1_count];
 174                 while (i > 0)
 175                         fstack[--i] = fstack_2[--fstack_2_count];
 176                 if (count <= MERGE_FNUM) {
 177                         /* Got all the data */
 178                         fstack_count = count;
 179                         merge_sort_fstack(outfp, put, ftbl);
 180                         return;
 181                 }
 182                 mfp = ftmp();
 183                 fstack_count = count > MERGE_FNUM ? MERGE_FNUM : count;
 184                 merge_sort_fstack(mfp, putrec, ftbl);
 185                 fstack[0].fp = mfp;
 186                 fstack[0].get = geteasy;
 187                 fstack_count = 1;
 188                 count -= MERGE_FNUM - 1;
 189         }
 190 }
 191
 192 static void
 193 merge_sort_fstack(FILE *outfp, put_func_t put, struct field *ftbl)
 194 {
 195         struct mfile *flistb[MERGE_FNUM], **flist = flistb, *cfile;
 196         RECHEADER *new_rec;
 197         u_char *new_end;
 198         void *tmp;
 199         int c, i, nfiles;
 200         size_t sz;
 201
 202         /* Read one record from each file (read again if a duplicate) */
 203         for (nfiles = i = 0; i < fstack_count; i++) {
 204                 cfile = &fstack[i];
 205                 if (cfile->rec == NULL) {
 206                         cfile->rec = allocrec(NULL, DEFLLEN);
 207                         cfile->end = (u_char *)cfile->rec + DEFLLEN;
 208                 }
 209                 rewind(cfile->fp);
 210
 211                 for (;;) {
 212                         c = cfile->get(cfile->fp, cfile->rec, cfile->end, ftbl);
 213                         if (c == EOF)
 214                                 break;
 215
 216                         if (c == BUFFEND) {
 217                                 /* Double buffer size */
 218                                 sz = (cfile->end - (u_char *)cfile->rec) * 2;
 219                                 cfile->rec = allocrec(cfile->rec, sz);
 220                                 cfile->end = (u_char *)cfile->rec + sz;
 221                                 continue;
 222                         }
 223
 224                         if (nfiles != 0) {
 225                                 if (insert(flist, cfile, nfiles, !DELETE))
 226                                         /* Duplicate removed */
 227                                         continue;
 228                         } else
 229                                 flist[0] = cfile;
 230                         nfiles++;
 231                         break;
 232                 }
 233         }
 234
 235         if (nfiles == 0)
 236                 return;
 237
 238         /*
 239          * We now loop reading a new record from the file with the
 240          * 'sorted first' existing record.
 241          * As each record is added, the 'first' record is written to the
 242          * output file - maintaining one record from each file in the sorted
 243          * list.
 244          */
 245         new_rec = allocrec(NULL, DEFLLEN);
 246         new_end = (u_char *)new_rec + DEFLLEN;
 247         for (;;) {
 248                 cfile = flist[0];
 249                 c = cfile->get(cfile->fp, new_rec, new_end, ftbl);
 250                 if (c == EOF) {
 251                         /* Write out last record from now-empty input */
 252                         put(cfile->rec, outfp);
 253                         if (--nfiles == 0)
 254                                 break;
 255                         /* Replace from file with now-first sorted record. */
 256                         /* (Moving base 'flist' saves copying everything!) */
 257                         flist++;
 258                         continue;
 259                 }
 260                 if (c == BUFFEND) {
 261                         /* Buffer not large enough - double in size */
 262                         sz = (new_end - (u_char *)new_rec) * 2;
 263                         new_rec = allocrec(new_rec, sz);
 264                         new_end = (u_char *)new_rec +sz;
 265                         continue;
 266                 }
 267
 268                 /* Swap in new buffer, saving old */
 269                 tmp = cfile->rec;
 270                 cfile->rec = new_rec;
 271                 new_rec = tmp;
 272                 tmp = cfile->end;
 273                 cfile->end = new_end;
 274                 new_end = tmp;
 275
 276                 /* Add into sort, removing the original first entry */
 277                 c = insert(flist, cfile, nfiles, DELETE);
 278                 if (c != 0 || (UNIQUE && cfile == flist[0]
 279                             && cmp(new_rec, cfile->rec) == 0)) {
 280                         /* Was an unwanted duplicate, restore buffer */
 281                         tmp = cfile->rec;
 282                         cfile->rec = new_rec;
 283                         new_rec = tmp;
 284                         tmp = cfile->end;
 285                         cfile->end = new_end;
 286                         new_end = tmp;
 287                         continue;
 288                 }
 289
 290                 /* Write out 'old' record */
 291                 put(new_rec, outfp);
 292         }
 293
 294         free(new_rec);
 295 }
 296
 297 /*
 298  * if delete: inserts rec in flist, deletes flist[0];
 299  * otherwise just inserts *rec in flist.
 300  * Returns 1 if record is a duplicate to be ignored.
 301  */
 302 static int
 303 insert(struct mfile **flist, struct mfile *rec, int ttop, int delete)
 304 {
 305         int mid, top = ttop, bot = 0, cmpv = 1;
 306
 307         for (mid = top / 2; bot + 1 != top; mid = (bot + top) / 2) {
 308                 cmpv = cmp(rec->rec, flist[mid]->rec);
 309                 if (cmpv == 0 ) {
 310                         if (UNIQUE)
 311                                 /* Duplicate key, read another record */
 312                                 /* NB: This doesn't guarantee to keep any
 313                                  * particular record. */
 314                                 return 1;
 315                         /*
 316                          * Apply sort by input file order.
 317                          * We could truncate the sort is the fileno are
 318                          * adjacent - but that is all too hard!
 319                          * The fileno cannot be equal, since we only have one
 320                          * record from each file (+ flist[0] which never
 321                          * comes here).
 322                          */
 323                         cmpv = rec < flist[mid] ? -1 : 1;
 324                         if (REVERSE)
 325                                 cmpv = -cmpv;
 326                 }
 327                 if (cmpv < 0)
 328                         top = mid;
 329                 else
 330                         bot = mid;
 331         }
 332
 333         /* At this point we haven't yet compared against flist[0] */
 334
 335         if (delete) {
 336                 /* flist[0] is ourselves, only the caller knows the old data */
 337                 if (bot != 0) {
 338                         memmove(flist, flist + 1, bot * sizeof(MFILE *));
 339                         flist[bot] = rec;
 340                 }
 341                 return 0;
 342         }
 343
 344         /* Inserting original set of records */
 345
 346         if (bot == 0 && cmpv != 0) {
 347                 /* Doesn't match flist[1], must compare with flist[0] */
 348                 cmpv = cmp(rec->rec, flist[0]->rec);
 349                 if (cmpv == 0 && UNIQUE)
 350                         return 1;
 351                 /* Add matching keys in file order (ie new is later) */
 352                 if (cmpv < 0)
 353                         bot = -1;
 354         }
 355         bot++;
 356         memmove(flist + bot + 1, flist + bot, (ttop - bot) * sizeof(MFILE *));
 357         flist[bot] = rec;
 358         return 0;
 359 }
 360
 361 /*
 362  * check order on one file
 363  */
 364 void
 365 order(struct filelist *filelist, struct field *ftbl)
 366 {
 367         get_func_t get = SINGL_FLD ? makeline : makekey;
 368         RECHEADER *crec, *prec, *trec;
 369         u_char *crec_end, *prec_end, *trec_end;
 370         FILE *fp;
 371         int c;
 372
 373         fp = fopen(filelist->names[0], "r");
 374         if (fp == NULL)
 375                 err(2, "%s", filelist->names[0]);
 376
 377         crec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
 378         crec_end = crec->data + DEFLLEN;
 379         prec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
 380         prec_end = prec->data + DEFLLEN;
 381
 382         /* XXX this does exit(0) for overlong lines */
 383         if (get(fp, prec, prec_end, ftbl) != 0)
 384                 exit(0);
 385         while (get(fp, crec, crec_end, ftbl) == 0) {
 386                 if (0 < (c = cmp(prec, crec))) {
 387                         crec->data[crec->length-1] = 0;
 388                         errx(1, "found disorder: %s", crec->data+crec->offset);
 389                 }
 390                 if (UNIQUE && !c) {
 391                         crec->data[crec->length-1] = 0;
 392                         errx(1, "found non-uniqueness: %s",
 393                             crec->data+crec->offset);
 394                 }
 395                 /*
 396                  * Swap pointers so that this record is on place pointed
 397                  * to by prec and new record is read to place pointed to by
 398                  * crec.
 399                  */
 400                 trec = prec;
 401                 prec = crec;
 402                 crec = trec;
 403                 trec_end = prec_end;
 404                 prec_end = crec_end;
 405                 crec_end = trec_end;
 406         }
 407         exit(0);
 408 }
 409
 410 static int
 411 cmp(RECHEADER *rec1, RECHEADER *rec2)
 412 {
 413         int len;
 414         int r;
 415
 416         /* key is weights */
 417         len = min(rec1->keylen, rec2->keylen);
 418         r = memcmp(rec1->data, rec2->data, len);
 419         if (r == 0)
 420                 r = rec1->keylen - rec2->keylen;
 421         if (REVERSE)
 422                 r = -r;
 423         return r;
 424 }