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 __RCSID("$NetBSD: msort.c,v 1.29 2009/11/06 18:34:22 joerg Exp $");
  68
  69 #include <stdlib.h>
  70 #include <string.h>
  71 #include <unistd.h>
  72
  73 /* Subroutines using comparisons: merge sort and check order */
  74 #define DELETE (1)
  75
  76 typedef struct mfile {
  77         FILE         *fp;
  78         get_func_t   get;
  79         RECHEADER    *rec;
  80         u_char       *end;
  81 } MFILE;
  82
  83 static int cmp(RECHEADER *, RECHEADER *);
  84 static int insert(struct mfile **, struct mfile *, int, int);
  85 static void merge_sort_fstack(FILE *, put_func_t, struct field *);
  86
  87 /*
  88  * Number of files merge() can merge in one pass.
  89  */
  90 #define MERGE_FNUM      16
  91
  92 static struct mfile fstack[MERGE_FNUM];
  93 static struct mfile fstack_1[MERGE_FNUM];
  94 static struct mfile fstack_2[MERGE_FNUM];
  95 static int fstack_count, fstack_1_count, fstack_2_count;
  96
  97 void
  98 save_for_merge(FILE *fp, get_func_t get, struct field *ftbl)
  99 {
 100         FILE *mfp, *mfp1, *mfp2;
 101
 102         if (fstack_count == MERGE_FNUM) {
 103                 /* Must reduce the number of temporary files */
 104                 mfp = ftmp();
 105                 merge_sort_fstack(mfp, putrec, ftbl);
 106                 /* Save output in next layer */
 107                 if (fstack_1_count == MERGE_FNUM) {
 108                         mfp1 = ftmp();
 109                         memcpy(fstack, fstack_1, sizeof fstack);
 110                         merge_sort_fstack(mfp1, putrec, ftbl);
 111                         if (fstack_2_count == MERGE_FNUM) {
 112                                 /* More than 4096 files! */
 113                                 mfp2 = ftmp();
 114                                 memcpy(fstack, fstack_2, sizeof fstack);
 115                                 merge_sort_fstack(mfp2, putrec, ftbl);
 116                                 fstack_2[0].fp = mfp2;
 117                                 fstack_2_count = 1;
 118                         }
 119                         fstack_2[fstack_2_count].fp = mfp1;
 120                         fstack_2[fstack_2_count].get = geteasy;
 121                         fstack_2_count++;
 122                         fstack_1_count = 0;
 123                 }
 124                 fstack_1[fstack_1_count].fp = mfp;
 125                 fstack_1[fstack_1_count].get = geteasy;
 126                 fstack_1_count++;
 127                 fstack_count = 0;
 128         }
 129
 130         fstack[fstack_count].fp = fp;
 131         fstack[fstack_count++].get = get;
 132 }
 133
 134 void
 135 fmerge(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl)
 136 {
 137         get_func_t get = SINGL_FLD ? makeline : makekey;
 138         FILE *fp;
 139         int i;
 140
 141         for (i = 0; i < nfiles; i++) {
 142                 fp = fopen(filelist->names[i], "r");
 143                 if (fp == NULL)
 144                         err(2, "%s", filelist->names[i]);
 145                 save_for_merge(fp, get, ftbl);
 146         }
 147
 148         merge_sort(outfp, putline, ftbl);
 149 }
 150
 151 void
 152 merge_sort(FILE *outfp, put_func_t put, struct field *ftbl)
 153 {
 154         int count = fstack_1_count + fstack_2_count;
 155         FILE *mfp;
 156         int i;
 157
 158         if (count == 0) {
 159                 /* All files in initial array */
 160                 merge_sort_fstack(outfp, put, ftbl);
 161                 return;
 162         }
 163
 164         count += fstack_count;
 165
 166         /* Too many files for one merge sort */
 167         for (;;) {
 168                 /* Sort latest 16 files */
 169                 i = count;
 170                 if (i > MERGE_FNUM)
 171                         i = MERGE_FNUM;
 172                 while (fstack_count > 0)
 173                         fstack[--i] = fstack[--fstack_count];
 174                 while (i > 0 && fstack_1_count > 0)
 175                         fstack[--i] = fstack_1[--fstack_1_count];
 176                 while (i > 0)
 177                         fstack[--i] = fstack_2[--fstack_2_count];
 178                 if (count <= MERGE_FNUM) {
 179                         /* Got all the data */
 180                         fstack_count = count;
 181                         merge_sort_fstack(outfp, put, ftbl);
 182                         return;
 183                 }
 184                 mfp = ftmp();
 185                 fstack_count = count > MERGE_FNUM ? MERGE_FNUM : count;
 186                 merge_sort_fstack(mfp, putrec, ftbl);
 187                 fstack[0].fp = mfp;
 188                 fstack[0].get = geteasy;
 189                 fstack_count = 1;
 190                 count -= MERGE_FNUM - 1;
 191         }
 192 }
 193
 194 static void
 195 merge_sort_fstack(FILE *outfp, put_func_t put, struct field *ftbl)
 196 {
 197         struct mfile *flistb[MERGE_FNUM], **flist = flistb, *cfile;
 198         RECHEADER *new_rec;
 199         u_char *new_end;
 200         void *tmp;
 201         int c, i, nfiles;
 202         size_t sz;
 203
 204         /* Read one record from each file (read again if a duplicate) */
 205         for (nfiles = i = 0; i < fstack_count; i++) {
 206                 cfile = &fstack[i];
 207                 if (cfile->rec == NULL) {
 208                         cfile->rec = allocrec(NULL, DEFLLEN);
 209                         cfile->end = (u_char *)cfile->rec + DEFLLEN;
 210                 }
 211                 rewind(cfile->fp);
 212
 213                 for (;;) {
 214                         c = cfile->get(cfile->fp, cfile->rec, cfile->end, ftbl);
 215                         if (c == EOF)
 216                                 break;
 217
 218                         if (c == BUFFEND) {
 219                                 /* Double buffer size */
 220                                 sz = (cfile->end - (u_char *)cfile->rec) * 2;
 221                                 cfile->rec = allocrec(cfile->rec, sz);
 222                                 cfile->end = (u_char *)cfile->rec + sz;
 223                                 continue;
 224                         }
 225
 226                         if (nfiles != 0) {
 227                                 if (insert(flist, cfile, nfiles, !DELETE))
 228                                         /* Duplicate removed */
 229                                         continue;
 230                         } else
 231                                 flist[0] = cfile;
 232                         nfiles++;
 233                         break;
 234                 }
 235         }
 236
 237         if (nfiles == 0)
 238                 return;
 239
 240         /*
 241          * We now loop reading a new record from the file with the
 242          * 'sorted first' existing record.
 243          * As each record is added, the 'first' record is written to the
 244          * output file - maintaining one record from each file in the sorted
 245          * list.
 246          */
 247         new_rec = allocrec(NULL, DEFLLEN);
 248         new_end = (u_char *)new_rec + DEFLLEN;
 249         for (;;) {
 250                 cfile = flist[0];
 251                 c = cfile->get(cfile->fp, new_rec, new_end, ftbl);
 252                 if (c == EOF) {
 253                         /* Write out last record from now-empty input */
 254                         put(cfile->rec, outfp);
 255                         if (--nfiles == 0)
 256                                 break;
 257                         /* Replace from file with now-first sorted record. */
 258                         /* (Moving base 'flist' saves copying everything!) */
 259                         flist++;
 260                         continue;
 261                 }
 262                 if (c == BUFFEND) {
 263                         /* Buffer not large enough - double in size */
 264                         sz = (new_end - (u_char *)new_rec) * 2;
 265                         new_rec = allocrec(new_rec, sz);
 266                         new_end = (u_char *)new_rec +sz;
 267                         continue;
 268                 }
 269
 270                 /* Swap in new buffer, saving old */
 271                 tmp = cfile->rec;
 272                 cfile->rec = new_rec;
 273                 new_rec = tmp;
 274                 tmp = cfile->end;
 275                 cfile->end = new_end;
 276                 new_end = tmp;
 277
 278                 /* Add into sort, removing the original first entry */
 279                 c = insert(flist, cfile, nfiles, DELETE);
 280                 if (c != 0 || (UNIQUE && cfile == flist[0]
 281                             && cmp(new_rec, cfile->rec) == 0)) {
 282                         /* Was an unwanted duplicate, restore buffer */
 283                         tmp = cfile->rec;
 284                         cfile->rec = new_rec;
 285                         new_rec = tmp;
 286                         tmp = cfile->end;
 287                         cfile->end = new_end;
 288                         new_end = tmp;
 289                         continue;
 290                 }
 291
 292                 /* Write out 'old' record */
 293                 put(new_rec, outfp);
 294         }
 295
 296         free(new_rec);
 297 }
 298
 299 /*
 300  * if delete: inserts rec in flist, deletes flist[0];
 301  * otherwise just inserts *rec in flist.
 302  * Returns 1 if record is a duplicate to be ignored.
 303  */
 304 static int
 305 insert(struct mfile **flist, struct mfile *rec, int ttop, int delete)
 306 {
 307         int mid, top = ttop, bot = 0, cmpv = 1;
 308
 309         for (mid = top / 2; bot + 1 != top; mid = (bot + top) / 2) {
 310                 cmpv = cmp(rec->rec, flist[mid]->rec);
 311                 if (cmpv == 0 ) {
 312                         if (UNIQUE)
 313                                 /* Duplicate key, read another record */
 314                                 /* NB: This doesn't guarantee to keep any
 315                                  * particular record. */
 316                                 return 1;
 317                         /*
 318                          * Apply sort by input file order.
 319                          * We could truncate the sort is the fileno are
 320                          * adjacent - but that is all too hard!
 321                          * The fileno cannot be equal, since we only have one
 322                          * record from each file (+ flist[0] which never
 323                          * comes here).
 324                          */
 325                         cmpv = rec < flist[mid] ? -1 : 1;
 326                         if (REVERSE)
 327                                 cmpv = -cmpv;
 328                 }
 329                 if (cmpv < 0)
 330                         top = mid;
 331                 else
 332                         bot = mid;
 333         }
 334
 335         /* At this point we haven't yet compared against flist[0] */
 336
 337         if (delete) {
 338                 /* flist[0] is ourselves, only the caller knows the old data */
 339                 if (bot != 0) {
 340                         memmove(flist, flist + 1, bot * sizeof(MFILE *));
 341                         flist[bot] = rec;
 342                 }
 343                 return 0;
 344         }
 345
 346         /* Inserting original set of records */
 347
 348         if (bot == 0 && cmpv != 0) {
 349                 /* Doesn't match flist[1], must compare with flist[0] */
 350                 cmpv = cmp(rec->rec, flist[0]->rec);
 351                 if (cmpv == 0 && UNIQUE)
 352                         return 1;
 353                 /* Add matching keys in file order (ie new is later) */
 354                 if (cmpv < 0)
 355                         bot = -1;
 356         }
 357         bot++;
 358         memmove(flist + bot + 1, flist + bot, (ttop - bot) * sizeof(MFILE *));
 359         flist[bot] = rec;
 360         return 0;
 361 }
 362
 363 /*
 364  * check order on one file
 365  */
 366 void
 367 order(struct filelist *filelist, struct field *ftbl)
 368 {
 369         get_func_t get = SINGL_FLD ? makeline : makekey;
 370         RECHEADER *crec, *prec, *trec;
 371         u_char *crec_end, *prec_end, *trec_end;
 372         FILE *fp;
 373         int c;
 374
 375         fp = fopen(filelist->names[0], "r");
 376         if (fp == NULL)
 377                 err(2, "%s", filelist->names[0]);
 378
 379         crec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
 380         crec_end = crec->data + DEFLLEN;
 381         prec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
 382         prec_end = prec->data + DEFLLEN;
 383
 384         /* XXX this does exit(0) for overlong lines */
 385         if (get(fp, prec, prec_end, ftbl) != 0)
 386                 exit(0);
 387         while (get(fp, crec, crec_end, ftbl) == 0) {
 388                 if (0 < (c = cmp(prec, crec))) {
 389                         crec->data[crec->length-1] = 0;
 390                         errx(1, "found disorder: %s", crec->data+crec->offset);
 391                 }
 392                 if (UNIQUE && !c) {
 393                         crec->data[crec->length-1] = 0;
 394                         errx(1, "found non-uniqueness: %s",
 395                             crec->data+crec->offset);
 396                 }
 397                 /*
 398                  * Swap pointers so that this record is on place pointed
 399                  * to by prec and new record is read to place pointed to by
 400                  * crec.
 401                  */
 402                 trec = prec;
 403                 prec = crec;
 404                 crec = trec;
 405                 trec_end = prec_end;
 406                 prec_end = crec_end;
 407                 crec_end = trec_end;
 408         }
 409         exit(0);
 410 }
 411
 412 static int
 413 cmp(RECHEADER *rec1, RECHEADER *rec2)
 414 {
 415         int len;
 416         int r;
 417
 418         /* key is weights */
 419         len = min(rec1->keylen, rec2->keylen);
 420         r = memcmp(rec1->data, rec2->data, len);
 421         if (r == 0)
 422                 r = rec1->keylen - rec2->keylen;
 423         if (REVERSE)
 424                 r = -r;
 425         return r;
 426 }