usr.bin/sort/msort.c

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