19.3 General Memory Management Concepts 883
Boolean in order to keep the pseudocode simple. In practice you can make this a 1-bit
quantity, using the high-order bit of the size variable.
class HeaderBlock
{
public:
bool Used;
unsigned int Size;
Block* Prev;
Block* Next;
};
class FooterBlock
{
public:
bool Used;
unsigned int Size;
};
It is possible to represent a doubly linked list with only a single pointer member
per object. The trick is to store the exclusive-or of the addresses of the previous and
next blocks. If P is the address of the previous block and N is the address of the
next block, the current block stores P ⊗ N,where⊗ denotes the exclusive-or of
the address treated as integer values. Two useful properties for exclusive-or are P =
(P ⊗ N) ⊗ N and