Stack Storage

Stack storage, as mentioned before, comes from the same free memory list as does heap storage. Stack storage requires a separate allocation routine for a couple reasons. They are:

• the memory allocation algorithm is different (it is not first-fit)
• when we keep track of a stack, we keep track of its highest address (not its lowest one as we do for heap memory). Thus getstk() returns the high address of the found free block, not the lowest address as is returned by getmem().

So what does getstk() do? It searches through the free memory list (much as getmem() does) looking for an appropriate chunk of memory. Getstk() does not stop at the first such block, but instead searches the entire memory list and chooses the one found with the highest address. If you think about it, it could be much more efficient if the free list was doubly-linked so that getstk() could do a reverse-search first-fit. Also if you think about it, you'll notice that the act of splitting a block of free memory in two (because it is bigger than requested) is very easy if the mblock structure is kept at the low address of the free block, as getstk() returns the high address of getstk().

Freestk() is simply a macro that calls freemem(). There is no need to write a new routine as it does the exact same job. The only wrinkle is that we keep track of stacks according to high addresses, not low ones. Freemem() expects the low address of the block to be freed. Thus the macro converts the stack (high) address to a low one by subtracting the length before calling freemem().