Memory Allocation

Memory allocation is the process of setting aside sections of memory in a program to be used to store variables, and instances of structures and classes. There are two basic types of memory allocation:

When you declare a variable or an instance of a structure or class. The memory for that object is allocated by the operating system. The name you declare for the object can then be used to access that block of memory.

When you use dynamic memory allocation you have the operating system designate a block of memory of the appropriate size while the program is running. This is done either with the new operator or with a call to the malloc function. The block of memory is allocated and a pointer to the block is returned. This is then stored in a pointer to the appropriate data type.

The Heap

The Heap is that portion of computer memory, allocated to a running application, where memory can be allocated for variables, class instances, etc. From a program's heap the OS allocates memory for dynamic use. Given a pointer to any one of the allocated blocks the OS can search in either direction to locate a block big enough to fill a dynamic memory allocation request.

Blocks of memory allocated on the heap are actually a special type of data structure consisting of (1) A pointer to the end of the previous block, (2) a pointer to the end of this block, (3) the allocated block of memory which can vary in size depending on its use, (4) a pointer to the beginning of this block, and (5) a pointer to the next block.

The Heap Layout.
Blank spaces between allocated blocks are where previously used blocks have been deallocated.

Depending on the type of operating system there are two possible algorithms that can be implemented in order to locate a block of memory in the heap to allocate:

First-Fit - The needed amount of memory is allocated in the first block located in the heap that is big enough. This is faster but can result in greater fragmentation* of the heap.
Best-Fit - All of the heap is searched and the needed amount of memory is allocated in the block where there is the least amount of memory left over. Slower but can result in less fragmentation*.

*Heap Fragmentation - the condition that results when there is a lot of memory allocation and deallocation taking place in a program while it is running. With either memory allocation algorithm method a point may be reached where an attempt to allocate additional memory may fail. There may be enough total memory available in the heap, but it is just not all in one place. Some operating systems (Mac OS most noteably) have a special algorithm that reduces heap fragmentation through a process known as compacting the heap. That is allocated blocks in the heap are moved together and pointers to these blocks are changed to match the new locations. This can be done automatically without the programmer having to provide any special coding and completely invisible to the user.

Foot Shot Warnings

These are some things to be careful of when allocating memory for used in linked data structures.


	It is a standing joke among old time C programmers that you must be careful when writing code because C will happily let you shoot yourself in the foot. In keeping with this idea here are some things to be careful of when allocating memory for use in linked data structures.

Creating dangling pointers. In the example two instances of struct simple are created an linked by setting S1->next = S2. Unfortunately when S2 is deleted you are left with S1->next still pointing at the now unallocated memory location.

Creating garbage with no way to do garbage collection. Garbage collection means deallocating dynamic memory when it is no longer needed using the delete operator. Failure to do so, for example, by moving a pointer to a block of memory without first deallocating it, leaves allocated memory with no reference to it to delete it, i.e. garbage.

Dereferencing the NULL pointer. In spite of the fact that this seems to be a no-brainer it is very easy to do. You must carefully study an algorithm to determine if it is possible for it to set a pointer to NULL and include code to handle this possibility.

Forgetting to mark the end of a list. Many linked data types use NULL in pointers to indicate that is the end of the line of linked structures. If you fail to set this pointer to NULL is it not done automatically. Any non-NULL value, even if it is garbage, may be misinterpreted as a valid memory address.

Failure to handle boundary cases. When inserting and deleting items from a linked structure the algorithm must take into account all possible cases. For example, in the insert algorithm for an ordered linked list you may be inserting a new item into (1) an empty list, (2) at the head of the list, (3) somewhere in the middle of the list, or (4) at the end of the list. Failure to handle all of the possible cases can result in poionter problems.