Memory allocation/deallocation for tree? Any good way?

[Doug Gwyn]

In article <20872:Jan1017:54:3891 at kramden.acf.nyu.edu> brnstnd at kramden.acf.nyu.edu (Dan Bernstein) writes:
>In article <14805 at smoke.brl.mil> gwyn at smoke.brl.mil (Doug Gwyn) writes:
>> In article <MCDANIEL.91Jan9102148 at dolphin.adi.com> mcdaniel at adi.com (Tim McDaniel) writes:
>> >A free() that did nothing would satisfy ANSI C, ...
>> Not strictly true, as the standard specifies that the storage is made
>> available for subsequent allocation.  However, there is no strictly
>> conforming way to test for this behavior.
>Doesn't as-if kick in here? A conforming program cannot figure out that
>a no-op is different from the definition of free(); therefore the no-op
>works as if it were a free() satisfying the literal definition;
>therefore the no-op is a valid implementation of free(). Where's the
>mistake?

The mistake is that failure of a strictly-conforming program to detect
an error in the implementation does not magically let the implementation
off the hook.  It is fairly simple to write a strictly-conforming test
program that would EVENTUALLY discover this implementation flaw, but
there is no guaranteed upper bound on the amount of time that it would
take to discover the problem.  Indeed, this strikes me as a useful test
to add to C compiler validation suites:  while not guaranteeing that any
such deficient implementation would be detected, it could at least loop
the test enough times to be fairly sure of detecting such a problem in
most common environments.  For example:

	#include <stdio.h>	/* for fprintf, stderr */
	#include <stdlib.h>	/* for exit, EXIT_*, free, malloc, size_t */
	#define ALLOCS 100000L
	#define SIZE ((size_t)10000)
	int main(void) {
		register void *p;
		register long n;
		for (n = 0; n < ALLOCS; ++n) {
			if ((p = malloc(SIZE)) == NULL) {
				fprintf(stderr, "FAILED on iteration %ld\n", n);
				exit(EXIT_FAILURE);
			}
			free(p);
		}
		return EXIT_SUCCESS;
	}