Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Implementation

Program gif declares the class DoublyLinkedPool. It is a concrete class 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. In addition, two private member functions, Unlink and InsertAfter are declared. These abstract common linked list manipulations.

   program31248
Program: DoublyLinkedPool Class Definition

The nested structures Header and Block are used to implement the layout shown in Figure gif. The Header structure contains information which appears in the first block of an area, regardless of whether it is reserved or free. In this case, the header comprises two members, status and length, packed into a single word of memory. The first member is a one-bit field of type Status. Status is an enumeration of the values reserved and free. The second field in the header, length, records the length in blocks of the associated area.

The Block structure contains a union. The union overlays an instance of the structure Links, which is used to hold pointers to the next and previous elements of the free list when the block is free, with the userPart of the block which is the space given to the user when the block is reserved.

In this implementation the size of a block (in bytes) is required to be at least

displaymath68107

On a 32-bit machine the minimum block size is typically 12 bytes. In the implementation shown in Program gif, the size of the Block structure is set to 16 bytes.




next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.