Implementation

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

Implementation

Program gives the declaration of the concrete storage pool class SinglyLinkedPool. This class is derived from the abstract base class StoragePool. The public interface of the class comprises a constructor, the destructor, and the two member functions Acquire and Release.

program30561
Program: SinglyLinkedPool Class Definition

The two nested struct definitions, Header and Block, correspond to the structure layout shown in Figure . Specifically, the Header structure contains information which appears in the first block of an area, regardless of whether it is reserved or free. The Block structure contains a union. In C++, the elements of a union occupy the same space. I.e., if the block is reserved, the userPart of the block has been allocated to the user. On the other hand, if the block is free, the next field is used to point to the next element of the free list.

Notice how the size of the Block structure is controlled. In this case, the size is set to 16 bytes. Recall that an area is a set of contiguous blocks. Therefore, the size of an area is a multiple of 16 bytes. The selection of a block size of 16 represents a trade-off. If the block size is too large, then space is wasted when a user requests an amount of storage that that is not a multiple of 16. On the other hand, if the block size is too small, then it is possible for the memory pool to become excessively fragmented. E.g., it is possible for the free list to contain many small areas. The choice of 16 is somewhat arbitrary. However, values between 8 and 16 are typical. In this implementation the size of a block (in bytes) is required to be at least

because we must be able to link a one-block area into the free list. On a 32-bit machine the minimum block size is typically 8 bytes.