[ale] OT: C not C++ Question

[John Mills]

Danny -

Thanks for the pointer on 'alloca'.

On 29 Dec 2002, Danny Cox wrote:

> On Sat, 2002-12-28 at 23:20, cfowler wrote:
> > I've been working on a little project to replicate the success I've had
> > in Java (fast programming) to C (slow programming).  I've been
> > replicating the Java classes to C and not C++.  But I've come into an
> > interesting issue where since we have no garbage collector in C that we
> > must be extremely careful to free all allocated data.  All the code in
> > 'liboop' malloc()'s each object.

> Henry's alloca() uses malloc, but keeps the blocks in a linked list. 
> Calling alloca(0) in the "top loop" of your program performs garbage
> collection.

A three-fold approach used in some embedded designs is:

 1) Fix the allowable number of each type of allocated variable,
 2) Allocate the space in a suitably linked list (such as a
    'short-circuited' ring) in your code's initialization, and
 3) Provide a mechanism to selectively use and free space in any given
    list (ring), returning a success or error indication to allocation
    calls.

Maybe a picture (Is this really any better???):

 typeAring ->a1->a2-> ... ->aj-> ... ->an-+
             ^               |         |
             | (in use) ...  V (avail) V
             +---------------+---------+

The node type includes the required element storage, plus the pointers and
other overhead to implement the desired 'virtual' data structure. The top
node (my 'typeAring') includes a 'free space' counter to keep track of
usage and 'overhead' pointers to identify the current 'head', 'tail', and
'active' data nodes.

I saw this in Ada, credited to Booch and called the 'managed ring'
approach. Robust and efficient at the cost of pre-dedicating available
storage up-front, by data type. I don't recall anything that would make
this hard to implement in 'C', but some 'googling' might be in order to
track it down.

Alternatively:
 I once used a pair of simple, doubly-linked lists to handle
operator-stored arguments similar to what one might use in a programmed
calculator. (This was a scan trajectory for an antenna.) I built the
'free' list at init time, then moved its nodes to and from the 'program'
lists in response to operator keystrokes.

I also made a mistake in the de-allocation step, and one unfortunate
ex-colleage had to find this some time after I had left the company.
 &8-P) *#@(&!!!

(This was in 8080 assembler code in a previous Universe.)

 - John Mills

_______________________________________________
Ale mailing list
Ale at ale.org
http://www.ale.org/mailman/listinfo/ale