usr.bin/sort/files.c

   1 /*      $NetBSD: files.c,v 1.40 2009/10/07 21:03:29 dsl 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: files.c,v 1.40 2009/10/07 21:03:29 dsl Exp $");
  68
  69 #include <string.h>
  70
  71 /* Align records in temporary files to avoid misaligned copies */
  72 #define REC_ROUNDUP(n) (((n) + sizeof (long) - 1) & ~(sizeof (long) - 1))
  73
  74 static ssize_t  seq(FILE *, u_char **);
  75
  76 /*
  77  * this is called when there is no special key. It's only called
  78  * in the first fsort pass.
  79  */
  80
  81 static u_char *opos;
  82 static size_t osz;
  83
  84 void
  85 makeline_copydown(RECHEADER *recbuf)
  86 {
  87         memmove(recbuf->data, opos, osz);
  88 }
  89
  90 int
  91 makeline(FILE *fp, RECHEADER *recbuf, u_char *bufend,
  92   struct field __attribute ((unused)) *dummy2)
  93 {
  94         u_char *pos;
  95         int c;
  96
  97         pos = recbuf->data;
  98         if (osz != 0) {
  99                 /*
 100                  * Buffer shortage is solved by either of two ways:
 101                  * o flush previous buffered data and start using the
 102                  *   buffer from start.
 103                  *   makeline_copydown() above must be called.
 104                  * o realloc buffer
 105                  *
 106                  * This code has relied on realloc changing 'bufend',
 107                  * but that isn't necessarily true.
 108                  */
 109                 pos += osz;
 110                 osz = 0;
 111         }
 112
 113         while (pos < bufend) {
 114                 c = getc(fp);
 115                 if (c == EOF) {
 116                         if (pos == recbuf->data) {
 117                                 FCLOSE(fp);
 118                                 return EOF;
 119                         }
 120                         /* Add terminator to partial line */
 121                         c = REC_D;
 122                 }
 123                 *pos++ = c;
 124                 if (c == REC_D) {
 125                         recbuf->offset = 0;
 126                         recbuf->length = pos - recbuf->data;
 127                         recbuf->keylen = recbuf->length - 1;
 128                         return (0);
 129                 }
 130         }
 131
 132         /* Ran out of buffer space... */
 133         if (recbuf->data < bufend) {
 134                 /* Remember where the partial record is */
 135                 osz = pos - recbuf->data;
 136                 opos = recbuf->data;
 137         }
 138         return (BUFFEND);
 139 }
 140
 141 /*
 142  * This generates keys. It's only called in the first fsort pass
 143  */
 144 int
 145 makekey(FILE *fp, RECHEADER *recbuf, u_char *bufend, struct field *ftbl)
 146 {
 147         static u_char *line_data;
 148         static ssize_t line_size;
 149         static int overflow = 0;
 150
 151         /* We get re-entered after returning BUFFEND - save old data */
 152         if (overflow) {
 153                 overflow = enterkey(recbuf, bufend, line_data, line_size, ftbl);
 154                 return overflow ? BUFFEND : 0;
 155         }
 156
 157         line_size = seq(fp, &line_data);
 158         if (line_size == 0) {
 159                 FCLOSE(fp);
 160                 return EOF;
 161         }
 162
 163         if (line_size > bufend - recbuf->data) {
 164                 overflow = 1;
 165         } else {
 166                 overflow = enterkey(recbuf, bufend, line_data, line_size, ftbl);
 167         }
 168         return overflow ? BUFFEND : 0;
 169 }
 170
 171 /*
 172  * get a line of input from fp
 173  */
 174 static ssize_t
 175 seq(FILE *fp, u_char **line)
 176 {
 177         static u_char *buf;
 178         static size_t buf_size = DEFLLEN;
 179         u_char *end, *pos;
 180         int c;
 181         u_char *new_buf;
 182
 183         if (!buf) {
 184                 /* one-time initialization */
 185                 buf = malloc(buf_size);
 186                 if (!buf)
 187                     err(2, "malloc of linebuf for %zu bytes failed",
 188                             buf_size);
 189         }
 190
 191         end = buf + buf_size;
 192         pos = buf;
 193         while ((c = getc(fp)) != EOF) {
 194                 *pos++ = c;
 195                 if (c == REC_D) {
 196                         *line = buf;
 197                         return pos - buf;
 198                 }
 199                 if (pos == end) {
 200                         /* Long line - double size of buffer */
 201                         /* XXX: Check here for stupidly long lines */
 202                         buf_size *= 2;
 203                         new_buf = realloc(buf, buf_size);
 204                         if (!new_buf)
 205                                 err(2, "realloc of linebuf to %zu bytes failed",
 206                                         buf_size);
 207
 208                         end = new_buf + buf_size;
 209                         pos = new_buf + (pos - buf);
 210                         buf = new_buf;
 211                 }
 212         }
 213
 214         if (pos != buf) {
 215                 /* EOF part way through line - add line terminator */
 216                 *pos++ = REC_D;
 217                 *line = buf;
 218                 return pos - buf;
 219         }
 220
 221         return 0;
 222 }
 223
 224 /*
 225  * write a key/line pair to a temporary file
 226  */
 227 void
 228 putrec(const RECHEADER *rec, FILE *fp)
 229 {
 230         EWRITE(rec, 1, REC_ROUNDUP(offsetof(RECHEADER, data) + rec->length), fp);
 231 }
 232
 233 /*
 234  * write a line to output
 235  */
 236 void
 237 putline(const RECHEADER *rec, FILE *fp)
 238 {
 239         EWRITE(rec->data+rec->offset, 1, rec->length - rec->offset, fp);
 240 }
 241
 242 /*
 243  * write dump of key to output (for -Dk)
 244  */
 245 void
 246 putkeydump(const RECHEADER *rec, FILE *fp)
 247 {
 248         EWRITE(rec, 1, REC_ROUNDUP(offsetof(RECHEADER, data) + rec->offset), fp);
 249 }
 250
 251 /*
 252  * get a record from a temporary file. (Used by merge sort.)
 253  */
 254 int
 255 geteasy(FILE *fp, RECHEADER *rec, u_char *end,
 256   struct field __attribute__ ((unused)) *dummy2)
 257 {
 258         length_t file_len;
 259         int i;
 260
 261         (void)sizeof (char[offsetof(RECHEADER, length) == 0 ? 1 : -1]);
 262
 263         if ((u_char *)(rec + 1) > end)
 264                 return (BUFFEND);
 265         if (!fread(&rec->length, 1, sizeof rec->length, fp)) {
 266                 fclose(fp);
 267                 return (EOF);
 268         }
 269         file_len = REC_ROUNDUP(offsetof(RECHEADER, data) + rec->length);
 270         if (end - rec->data < (ptrdiff_t)file_len) {
 271                 for (i = sizeof rec->length - 1; i >= 0;  i--)
 272                         ungetc(*((char *) rec + i), fp);
 273                 return (BUFFEND);
 274         }
 275
 276         fread(&rec->length + 1, file_len - sizeof rec->length, 1, fp);
 277         return (0);
 278 }