Return to BSD News archive
Xref: sserve comp.os.386bsd.questions:12253 comp.os.386bsd.development:2373 comp.os.386bsd.misc:3141
Path: sserve!newshost.anu.edu.au!harbinger.cc.monash.edu.au!bunyip.cc.uq.oz.au!munnari.oz.au!constellation!convex!convex!cs.utexas.edu!swrinde!emory!nntp.msstate.edu!nntp.memphis.edu!nntp.rhodes.edu!zen.mathcs.rhodes.edu!stuart
Newsgroups: comp.os.386bsd.questions,comp.os.386bsd.development,comp.os.386bsd.misc
Subject: Re: Why does FreeBSD 1.1.5 say gets() is unsafe?
Message-ID: <1994Aug10.151130.1017@rhodes>
From: stuart@zen.mathcs.rhodes.edu (Brian L. Stuart)
Date: 10 Aug 94 15:11:29 -0500
References: <30lrf3$2ii@acmez.gatech.edu> <311m2e$o33@agate.berkeley.edu>
<324v1b$14g@boavista.bln.sub.org>
Distribution: world
Nntp-Posting-Host: zen.mathcs.rhodes.edu
Lines: 79
In article <324v1b$14g@boavista.bln.sub.org>, erdmann@boavista.bln.sub.org (Michael Erdmann) writes:
|> In article <CturD6.3C1@cs.vu.nl>, kjb@cs.vu.nl (Kees J. Bot) writes:
|> |>
|> |> I personally don't use gets() or fgets() ever. Typical example of my
|> |> code attached below. (allocate() and fatal() are left to your
|> |> imagination.)
|> |> --
|>
|> 2. The function read1line
|> -------------------------
|> I have to agree with Kees J. Bot, i am using also some function like
|> he has given with some slight changes:
|>
|> 1. The allocation stratagy was to expensive. Allways when the string
|> was reallocated twice the current size was allocated leaving lots
|> of unused memory in the return string (but how cares these days).
|>
|> I have introduced an intermediate buffer which is dynmicaly
|> increased by a fixed increment.
|> And the final string is returned via strdup.
|>
|> char *read1line(FILE *fp)
|> /* Read one line from a file. Result is a malloc()'d string or NULL for EOF */
|> {
|> static char *line = NULL;
|> size_t lineLength=80;
|> size_t idx;
|> int c;
|>
|> if( line ==NULL )
|> line = malloc(lineLength*sizeof(char));
|>
|> for(idx=0; (c= getc(fp)) != EOF && c != '\n'; ++idx) {
|> if (idx == lineLength ) {
|> lineLength += lineLength ;
|> line= realloc(line, lineLength*sizeof(char));
|> }
|> line[idx]= c;
|> }
|> ...
At the risk of picking an excessively fine nit (and mixing my metaphors),
a good argument can be made for doubling the size of the array rather
than adding a fixed amount. realloc() may need to copy the previously
allocated block to a position with enough free space. So realloc()ing
a block previously of size k will take O(k) time (big-O, of course, implies
that we're talking worst case). If we ultimately need n bytes, then
doubling will lead to ln n realloc()s and the sum up to ln n of 2^k
is O(n). Adding a constant amount leads to O(n) realloc()s and the sum
is O(n^2). It is true that doubling will lead to waste bounded by n
whereas adding a fixed amount bounds the waste by the increment. It
seems to be the classic time vs. space tradeoff. Since I'm using O(n)
space anyway, I tend to use the doubling approach. On top of that, I
like to pick my initial size to be a little bigger than the expected
size. That way, in the typical case, there's no copying and very
little wasted space.
|> 2. Upon EOF the function schould not check for the error. This should
|> allways be done by the caller, because only he knows what to do
|> in case of an error.
On this one, it depends. If this code is in a layer that is used in several
applications, then yes the error should be passed on up. On the other hand
if it is in an application specific library layer, then handling the error
here amortizes the error handling development across all uses in the application
suite. I find this technique useful in both places and not just in regards
to gets(), but for any array I don't know at compile time. Since becoming the
nth (where n is large) person to discover this for himself, I find I don't
use linked lists nearly as often. They still have their uses, of course,
but you don't need them just to get around setting compile time limits
on linear structures.
Forgive me for letting the academic in me out for a while. He's been
suitably disciplined and shouldn't bother you again :-)
Brian L. Stuart
Math/CS Dept, Rhodes College, Memphis, TN 38112
stuart@mathcs.rhodes.edu