Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!sumax!polari!6sigma!blm
From: blm@6sigma.UUCP (Brian Matthews)
Newsgroups: comp.lang.c
Subject: Re: dynamic arrays (was: Re: lint on V.3)
Message-ID: <293@6sigma.UUCP>
Date: 5 Sep 89 22:52:14 GMT
References: <MRD.89Sep1110612@sun.clarkson.edu> <1394@redsox.bsw.com> <1123@virtech.UUCP> <282@6sigma.UUCP> <14064@bloom-beacon.MIT.EDU>
Reply-To: blm@6sigma.UUCP (Brian Matthews)
Organization: Six Sigma CASE, Inc.
Lines: 56

In article <14064@bloom-beacon.MIT.EDU> scs@adam.pika.mit.edu (Steve Summit) writes:
|[Crossposted to comp.lang.c because it's now a programming topic.]
|In article <282@6sigma.UUCP> blm@6sigma.UUCP (Brian Matthews) writes:
|>...I agree
|>with your comment that they shouldn't have hard-coded limits on anything.
|>...you may be able to get your vendor to
|>recompile with larger limits, but you probably won't be able to get
|>them to do the job right and replace the arrays with mallocs.
|Brian is probably right (many people think that dynamic
|allocation is hard), but I'd like to show how easy it can be.
|(It's beyond me, though, why a production compiler would be using
|arrays for symbol tables in the first place, rather than trees or
|hash tables.)

Actually I was a little misleading.  The symbol table does use a hash
table, but the structures for the individual symbols are allocated out
of a big array with code basically like the first chunk in Steve's message.
So the compiler isn't doing anything horrible like a linear search, but
it is working with a pool of structures with a fixed upper limit on the
number that can be allocated, which is the cause of the "too many names"
message from lint that started this discussion.

|[code to allocate out of a fixed array omitted]
|This is simple, straightforward, and correct; and drives
|people nuts because no matter how big you #define NELEM,
|one day somebody tries to exceed it.

Yep.  If there's one "universal computing message", it's that no matter
how big you make a limit, it isn't big enough.  They're arguing 16 bit
vs. 32 bit integers in comp.sys.mac.programmer, and there has been a lot
of discussion in the past about 16 bit inode numbers and 32 bit file and
file system sizes.

|[code to dynamically grow an array omitted]
|The nice thing is that no actual references to the array need to
|be changed, because the reference array[i] acts the same [4]
|whether array is a char *[] or a char **.
|Changing fixed-sized arrays to dynamic can therefore actually be
|quite simple.

Yep again.  It's also not much harder to convert to using malloc
for each structure, or to put the malloced arrays into a linked list
instead of copying a bunch of bytes when you grow the array (of course
then you have to touch all of the places that use the array, which
might be prohibitive in something like a compiler.)

The lesson, though, is the same.  Doing dynamic allocation is only
marginally more difficult than having a fixed size array (one could
argue that using a fixed size array is more difficult because you'll
have to do the fixed size array implementation, and then when your
customers complain, you'll have to go back and do the dynamic
implementation :-)
-- 
Brian L. Matthews			blm@6sigma.UUCP
Six Sigma CASE, Inc.			+1 206 854 6578
PO Box 40316, Bellevue, WA  98004