Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!rice!sun-spots-request
From: mcvax!aivru.sheffield.ac.uk!chris@uunet.uu.net (Chris Brown)
Newsgroups: comp.sys.sun
Subject: Re: questions about malloc & co.
Message-ID: <8902070951.AA02703@aivru.uucp>
Date: 15 Feb 89 17:40:00 GMT
Sender: usenet@rice.edu
Organization: Sun-Spots
Lines: 18
Approved: Sun-Spots@rice.edu
Original-Date: Tue, 7 Feb 89 09:51:12 GMT
X-Sun-Spots-Digest: Volume 7, Issue 156, message 5 of 11
X-Issue-Reference: v7n127

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.