Re: [avr-libc-dev] malloc implementation

[Joerg Wunsch]

As Bertolt Mildner wrote:

> I just had a quick look at malloc.c and saw that in step 2 the free
> list is walked through a second time.

> Why is this necessary when in step 1 the smallest fitting chunk has
> already been found?

See the comments (for step 2).  Btw., I just notice a minor mistake in
the comment in step 1: of course, the *smallest* chunk that would
still fit the request is recorded, not the largest one.

The second walk is necessary as the smallest fitting entry needs to be
split up, and disconnected from the list.  While we still have the
size of this chunk (recorded from step 1), we have to find its
position in the list again.  As it is a single linked list, you can
only change entries while walking the list.

Step 1 can only do its job immediately (and thus stop walking at once)
if the size fits exactly, as this is the optimal entry that could be
found.  If the ``best fit'' is not an exact match, you don't know that
for sure initially.

The idea of the two-step algorithm is to always return exactly fitting
junks if possible, to avoid memory fragmentation.

-- 
cheers, J"org               .-.-.   --... ...--   -.. .  DL8DTL

http://www.sax.de/~joerg/                        NIC: JW11-RIPE
Never trust an operating system you don't have sources for. ;-)