Implicit Free List

In an implicit free list, the main information we have at our 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 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 represents a word in memory. In this demonstration, which uses 32 bit addressing is used, so each word is 4 bytes long, which is what's reflected in the addresses above each block.

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] (The role of the sentinel for left-coalescing is done by the block header for the very first block in the heap).