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