questions about malloc & co.

[Chris Brown]

In v7n127 W.P. Reeder describes a problem concerning repeated use of
malloc and free. Since the nodes he is allocating "come in only a few
sizes", a solution would be to maintain one's own linked list of free
nodes. There would be one such list for each size of node. 

Often there is a pointer field already within the node's struct which can
be pressed into service as the 'next' pointer in the linked list.  If not,
you'll have to use a cast or a union to get one.

Then, instead of calling malloc(), you pop a node off the list. Of course,
if the list is empty, you have to call the real malloc() to get a new
node. This happens lots of times whilst the memory usage is developing,
then tails off. Instead of a call to free(), you push the node back onto
the appropriate linked list. free() is never called.

Even if you didn't have a problem with malloc() to work around, you'll
find this technique much more efficient if you are frequently creating and
destroying nodes in a small range of sizes.