Dynamic memory allocation requires that the allocator returns requests for memory and memory to be returned to the system.

The easiest form of dynamic memory allocation is to allocate a contiguous block of memory, and then divide this into n equally sized blocks. Then, a stack is used to track those blocks that have not yet been allocated.

For example, if we started with a block of 80 bytes, we could divide this into blocks of 8 bytes. This would leave us with 10 blocks that could be allocated. In order to track these, when the blocks are not assigned, we will cast each block as a pointer (that is, a 4-byte address assuming we are dealing with a 32-bit machine). We then assign the top of the stack to point to the address of the block of memory, the first four bytes of that block are used to store the address of the next block, and so on, until we get to the end where the address stored will be NULL indicating the base of the stack. This is shown in Figure 1.

Figure 1. An initialized data structure for allocating memory.

Now, suppose that there is a request for one block of memory. In this case, we

• check if the top of the stack is NULL, in which case we simply return NULL;
• otherwise, we
  • temporarily store the address of the top of the stack,
  • set the top of the stack to the address stored in that block, and
  • return that temporarily stored address.

Thus, we would end up with the situation shown in Figure 2 where the task requesting the block could now use it as it deems appropriate.

Figure 2. The stack following one block being allocated.

If there are another three requests for blocks of memory, we would end up with the situation shown in Figure 3.

Figure 3. The unallocated blocks following a sequence of four memory allocations.

Now, suppose that the 2nd allocated block is freed. In this case, it now becomes the top of the stack:

• the block is cast as being able to store a pointer and it is assigned the current top of the stack, and
• the top of the stack is assigned the address of the freed block.

Thus, the situation now would look as shown in Figure 4.

Figure 4. The state of the stack if the 2nd allocated block is freed.

Finally, Figure 5 shows the state of the stack if the 4th allocated block is freed next.

Figure 5. The state of the stack if the 4th allocated block is freed.

qalloc specification

Photo by DAVID ILIFF. License: CC-BY-SA 3.0

The signatures of the three functions are:

   void qinit( size_t n );
   void *qalloc();
   void qfree( void *mem_block );

where the q stands for quick (all these allocations and de-allocations occur in Θ(1) time). The requirements are:

void qinit( size_t n )

Divide the allocated memory into blocks of size n where n ≥ sizeof( void * ).

void *qalloc()

Allocate the block on the top of the stack, returning NULL if no blocks are available.

void qfree( void *mem_block )

Push the block back onto the stack, doing nothing if the argument is NULL.

An implementation of this libary is in the source files.

Using qalloc

We will now use this with our previous project with a singly linked lists where memory allocation was done with malloc(...) and free(...). Now we will use qalloc() and qfree(...).

You will need to find a type.h specific for the Keil board, say in C:\Keil\ARM\Boards\Keil\MCB1700\USBMem\type.h (or wherever the appropriate path is).

You must now make five changes:

1. Include qalloc.h in main.c.
2. In main.c, you must initialize the quick memory allocator so that each block is the size of a single_node_t: qinit( sizeof( single_node_t ) );
3. Include qalloc.h in single_list.c.
4. In single_list.c, you must replace the call to malloc(...) with a call to qalloc().

5. In single_list.c, you must replace the call to free(...) with a call to qfree(...).

Now you no longer require stdlib.h nor MicroLIB, so remove the corresponding include pre-processor directive and in the Options panel, unselect Use MircoLIB. (You may still require MicroLIB if you have since changed the project to use something in stdio.h.)