4.3 A Small-Object Allocator

The small-object allocator described in this chapter sports a four-layered structure, shown in Figure 4.3. The upper layers use functionality provided by the lower layers. At the bottom is a Chunk type. Each object of type Chunk contains and manages a chunk of memory consisting of an integral number of fixed-size blocks. Chunk contains logic that allows you to allocate and deallocate memory blocks. When there are no more blocks available in the chunk, the allocation function fails by returning zero.

The next layer features the FixedAllocator class. A FixedAllocator object uses Chunk as a building block. FixedAllocator's primary purpose is to satisfy memory requests that go beyond a Chunk's capacity. FixedAllocator does this by aggregating an array of Chunks. Whenever a request for memory comes and all existing Chunks are occupied, FixedAllocator creates a new Chunk and appends it to the array. Then it satisfies the request by forwarding the request to that new Chunk.

SmallObjAllocator provides general allocation and deallocation functions. A SmallObjAllocator holds several FixedAllocator objects, each specialized for allocating objects of one size. Depending on the number of bytes requested, SmallObjAllocator dispatches memory allocation requests to one of its FixedAllocators or to the default ::operator new if the size requested is too large.

Finally, SmallObject wraps FixedAllocator to offer encapsulated allocation services for C++ classes. SmallObject overloads operator new and operator delete and passes them to a SmallObjAllocator object. This way, you make your objects benefit from specialized allocation by simply deriving them from SmallObject.

You can also use SmallObjAllocator and FixedAllocator directly. (Chunk is too primitive and unsafe, so it is defined in the private section of FixedAllocator.) Most of the time, however, client code will simply derive from the SmallObject base class to take advantage of efficient allocation. That's quite an easy-to-use interface.