Data Structures and Algorithms with Object-Oriented Design Patterns in C++

The singly-linked free list used in the preceding section is kept sorted in order to facilitate the coalescing of adjacent free areas. The only way to determine whether a particular area is free is to see if it appears in the free list. Since we need to examine adjacent areas to determine whether they can be combined, the free list is kept sorted. That way, adjacent areas appear next to one another in the free list.

Unfortunately since the free list must be kept sorted, every time an area is released it must be inserted into the list at the correct position. This means that the running time of the Release operation is O(n) in the worst case, where n is the number of blocks in the storage pool.

The essence of the problem is that we cannot tell by looking at an area whether it is reserved or free. So, the solution must be to record the allocation status of the area in the area itself.

A secondary problem with the use of a singly-linked free list is that, given a pointer to an area, we cannot extract that area from the free list without traversing the list. This is because in order to extract an element from a linked list, we need to know the predecessor of that element. And in a singly-linked list we must search from the head of the list to find the predecessor. The solution is, of course, to use a doubly-linked free list.

Finally, we shall play an interesting algorithmic trick: In order to coalesce adjacent free areas, we need to traverse the free list. However, since we must traverse the free list in the Acquire operation, in order to find a free area of a suitable size, we shall do the coalescing in the Acquire operation and not in the Release operation. While this does increase slightly the running time for Acquire, it means that Release can run in constant time.

Figure  shows a memory map of a storage pool managed using a doubly-linked list. The reserved areas in Figure  are exactly the same as those shown in Figure . The figure clearly indicates that there are adjacent uncoalesced free areas in the free list. What the figure cannot show is that the areas in the free list are not sorted.

Figure: Memory Map of a Doubly-Linked Storage Pool

As before, we implement the storage pool as an array of Blocks. The structure of a Block is shown in Figure . A sequence of consecutive, contiguous blocks in the array constitutes an area. Only the first block in each area is used to keep track of the entire area.