Simulators

Implicit Free List

In an implicit free list, the main information we have at out disposal are the size field and status bits. The term implicit free list comes from the fact that the connection between a block and its previous/next block is not made explicit anywhere, but implied through the current address and the value of the size field. For the next block, this is simply the current address plus the size, and for the previous block, this is the current address minus the value of the previous footer.

This minimalism makes this implementation one of the easiest to understand, but outside of that there's not much that's appealing about the implicit free list. Compared to its more complex cousins the explicit free list and the segregated free list, its allocation performance can be terrible, since it must iterate through allocated blocks as well as free ones instead of being able to go directly to the next free block through the use of explicit references, as seen in the demo below.

This is a demonstration of an implicit free list based dynamic memory allocator that:

• uses the first fit placement policy
• splits if a valid block bigger than the required size is found
• does coalescing immediately after free operations

Each of the individual cells is a word that contains an address. Since I'm following the outline of Bryant and O'Hallaron, which uses 32 bit addressing, each word is 4 bytes long. Per convention, the end of the heap is marked with the constant 1, which would be interpreted as a header that's allocated but has size 0 (serving as a sentinel value for right-coalescing). The start of the heap is unused for padding, and so is denoted with the placeholder [START] (try out a free operation yourself to see why no such sentinel value is needed for left-coalescing).