contrib/sort/append.c

   1 /*      $NetBSD: append.c,v 1.10 2001/02/19 20:50:17 jdolecek Exp $     */
   2
   3 /*-
   4  * Copyright (c) 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Peter McIlroy.
   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  * 3. All advertising materials mentioning features or use of this software
  19  *    must display the following acknowledgement:
  20  *      This product includes software developed by the University of
  21  *      California, Berkeley and its contributors.
  22  * 4. Neither the name of the University nor the names of its contributors
  23  *    may be used to endorse or promote products derived from this software
  24  *    without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  */
  38
  39 #include "sort.h"
  40
  41 #ifndef lint
  42 __RCSID("$NetBSD: append.c,v 1.10 2001/02/19 20:50:17 jdolecek Exp $");
  43 __SCCSID("@(#)append.c  8.1 (Berkeley) 6/6/93");
  44 #endif /* not lint */
  45
  46 #include <stdlib.h>
  47 #include <string.h>
  48
  49 #define OUTPUT {                                                        \
  50         if ((n = cpos - ppos) > 1) {                                    \
  51                 for (; ppos < cpos; ++ppos)                             \
  52                         *ppos -= odepth;                                \
  53                 ppos -= n;                                              \
  54                 if (stable_sort)                                        \
  55                         sradixsort(ppos, n, wts1, REC_D);               \
  56                 else                                                    \
  57                         radixsort(ppos, n, wts1, REC_D);                \
  58                 for (; ppos < cpos; ppos++) {                           \
  59                         prec = (const RECHEADER *) (*ppos - sizeof(TRECHEADER));\
  60                         put(prec, fp);                                  \
  61                 }                                                       \
  62         } else put(prec, fp);                                           \
  63 }
  64
  65 /*
  66  * copy sorted lines to output; check for uniqueness
  67  */
  68 void
  69 append(keylist, nelem, depth, fp, put, ftbl)
  70         const u_char **keylist;
  71         int nelem;
  72         int depth;
  73         FILE *fp;
  74         put_func_t put;
  75         struct field *ftbl;
  76 {
  77         u_char *wts, *wts1;
  78         int n, odepth;
  79         const u_char **cpos, **ppos, **lastkey;
  80         const u_char *cend, *pend, *start;
  81         const struct recheader *crec, *prec;
  82
  83         if (*keylist == '\0' && UNIQUE)
  84                 return;
  85         wts1 = wts = ftbl[0].weights;
  86         if ((!UNIQUE) && SINGL_FLD) {
  87                 if ((ftbl[0].flags & F) && (ftbl[0].flags & R))
  88                         wts1 = Rascii;
  89                 else if (ftbl[0].flags & F)
  90                         wts1 = ascii;
  91                 odepth = depth;
  92         }
  93         lastkey = keylist + nelem;
  94         depth += sizeof(TRECHEADER);
  95         if (SINGL_FLD && (UNIQUE || wts1 != wts)) {
  96                 ppos = keylist;
  97                 prec = (const RECHEADER *) (*ppos - depth);
  98                 if (UNIQUE)
  99                         put(prec, fp);
 100                 for (cpos = &keylist[1]; cpos < lastkey; cpos++) {
 101                         crec = (const RECHEADER *) (*cpos - depth);
 102                         if (crec->length  == prec->length) {
 103                                 /*
 104                                  * Set pend and cend so that trailing NUL and
 105                                  * record separator is ignored.
 106                                  */
 107                                 pend = (const u_char *) &prec->data + prec->length - 2;
 108                                 cend = (const u_char *) &crec->data + crec->length - 2;
 109                                 for (start = *cpos; cend >= start; cend--) {
 110                                         if (wts[*cend] != wts[*pend])
 111                                                 break;
 112                                         pend--;
 113                                 }
 114                                 if (pend + 1 != *ppos) {
 115                                         if (!UNIQUE) {
 116                                                 OUTPUT;
 117                                         } else
 118                                                 put(crec, fp);
 119                                         ppos = cpos;
 120                                         prec = crec;
 121                                 }
 122                         } else {
 123                                 if (!UNIQUE) {
 124                                         OUTPUT;
 125                                 } else
 126                                         put(crec, fp);
 127                                 ppos = cpos;
 128                                 prec = crec;
 129                         }
 130                 }
 131                 if (!UNIQUE)  { OUTPUT; }
 132         } else if (UNIQUE) {
 133                 ppos = keylist;
 134                 prec = (const RECHEADER *) (*ppos - depth);
 135                 put(prec, fp);
 136                 for (cpos = &keylist[1]; cpos < lastkey; cpos++) {
 137                         crec = (const RECHEADER *) (*cpos - depth);
 138                         if (crec->offset == prec->offset) {
 139                                 /*
 140                                  * Set pend and cend so that trailing NUL and
 141                                  * record separator is ignored.
 142                                  */
 143                                 pend = (const u_char *) &prec->data + prec->offset - 2;
 144                                 cend = (const u_char *) &crec->data + crec->offset - 2;
 145                                 for (start = *cpos; cend >= start; cend--) {
 146                                         if (wts[*cend] != wts[*pend])
 147                                                 break;
 148                                         pend--;
 149                                 }
 150                                 if (pend + 1 != *ppos) {
 151                                         ppos = cpos;
 152                                         prec = crec;
 153                                         put(prec, fp);
 154                                 }
 155                         } else {
 156                                 ppos = cpos;
 157                                 prec = crec;
 158                                 put(prec, fp);
 159                         }
 160                 }
 161         } else for (cpos = keylist; cpos < lastkey; cpos++) {
 162                 crec = (const RECHEADER *) (*cpos - depth);
 163                 put(crec, fp);
 164         }
 165 }
 166
 167 /*
 168  * output the already sorted eol bin.
 169  */
 170 void
 171 rd_append(binno, infl0, nfiles, outfp, buffer, bufend)
 172         u_char *buffer;
 173         int infl0;
 174         int binno, nfiles;
 175         FILE *outfp;
 176         u_char *bufend;
 177 {
 178         RECHEADER *rec;
 179
 180         rec = (RECHEADER *) buffer;
 181         if (!getnext(binno, infl0, NULL, nfiles,
 182                         (RECHEADER *) buffer, bufend, 0)) {
 183                 putline(rec, outfp);
 184                 while (getnext(binno, infl0, NULL, nfiles, (RECHEADER *) buffer,
 185                         bufend, 0) == 0) {
 186                         if (!UNIQUE)
 187                                 putline(rec, outfp);
 188                 }
 189         }
 190 }
 191
 192 /*
 193  * append plain text--used after sorting the biggest bin.
 194  */
 195 void
 196 concat(a, b)
 197         FILE *a, *b;
 198 {
 199         int nread;
 200         char buffer[4096];
 201
 202         rewind(b);
 203         while ((nread = fread(buffer, 1, 4096, b)) > 0)
 204                 EWRITE(buffer, 1, nread, a);
 205 }