Return to BSD News archive
Xref: sserve comp.os.386bsd.questions:12276 comp.os.386bsd.development:2376 comp.os.386bsd.misc:3154
Path: sserve!newshost.anu.edu.au!harbinger.cc.monash.edu.au!msuinfo!agate!howland.reston.ans.net!EU.net!Germany.EU.net!netmbx.de!zelator!deadline.bln.sub.org!boavista.panic.bln.sub.org!boavista.bln.sub.org!erdmann
From: erdmann@boavista.bln.sub.org (Michael Erdmann)
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?
Date: 10 Aug 1994 22:05:18 GMT
Organization: private
Lines: 58
Distribution: world
Message-ID: <32biuu$1l4@boavista.bln.sub.org>
References: <30lrf3$2ii@acmez.gatech.edu> <311m2e$o33@agate.berkeley.edu> <1994Aug10.151130.1017@rhodes>
Reply-To: erdmann@boavista.bln.sub.org (Michael Erdmann)
NNTP-Posting-Host: 200.0.0.1
In article <1994Aug10.151130.1017@rhodes>, stuart@zen.mathcs.rhodes.edu (Brian L. Stuart) writes:
|> In article <324v1b$14g@boavista.bln.sub.org>, erdmann@boavista.bln.sub.org (Michael Erdmann) writes:
|> |>
|> |> 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.
|>
I think you are right! If there is a wide range of record sizes to be
expected, the doubling of the intermeadiate buffer is better,
because it will save lots of reallocs (and bcopy's).
M.Erdmann