heap(3x) — unbundled C++

NAME

Heap - heap management class

SYNOPSIS

#include <codelibs/heap.h>
class Heap
{
public:
Heap(int cs = __HEAP_CHUNK_SIZE, int bs = __HEAP_BLOCK_SIZE);
~Heap();
void *alloc(unsigned long size);
void *realloc(void *ptr, unsigned long cursize,
unsigned long size);
unsigned long lastsize();
void free(void *ptr, unsigned long size);
};
CC ... -lcodelibs

DESCRIPTION

The Heap class is used to manage the allocation and deallocation of memory in dynamic heap. There can be multiple independent heap objects. Each heap object has its own memory pool that it manages. The memory pool is expanded with sbrk(2) if there is not a large enough block to satisfy the a request. When a heap object is destructed its memory pool (including any outstanding allocations) is made available for expanding the memory pools of other heap objects.

The allocation algorithm is first-fit using a sorted free list. Adjacent blocks in the free list are combined into a single block as part of the free operation. Blocks are always allocated in sizes that are multiples of the chunk size and are always aligned on an address that is also a multiple of the chunk size. The memory pool is always expanded in multiples of the block size. The allocator does not require any overhead space between free blocks.

Constructor and Destructor

The constructor for the Heap class takes two optional parameters. The first is the chunk size. This value defines the multiple by which blocks are allocated. The minimum chunk size is equivalent to a struct that contains a pointer and an integer. Increasing the chunk size may decrease external fragmentation but will also increase internal fragmentation. It may be useful to increase the chunk size if larger blocks will always be allocated from the heap. The chunk size also defines the minimum alignment. The second parameter is the block size. This value controls the minimum amount of memory that is added to the memory pool that is being managed. The default value for the block size is equivalent to the page size for the machine. Increasing the block size will decrease the number of calls made to sbrk(2) and therefore may be useful.

The destructor releases all memory that was sbrk(2)’d for the memory pool for use by other heap objects. Any memory that was allocated using the heap object should not be referenced after the heap is destroyed.

Member functions

The alloc function acquires a block of memory that contains a minimum of size bytes. The size of block that was actually returned is contained in the first sizeof(unsigned long) bytes of the block. A type cast to (unsigned long *) may be used to get the actual size. The remainder of the block is undefined. If sbrk(2) fails for any reason then this function returns NULL.

The realloc function expands a previously allocated block. The pointer, ptr, to the block, the actual size, cursize, of the block, and the desired new block size, size, are passed as parameters. This function returns NULL if the size of the block can not be changed for any reason. If NULL is returned then the block passed in is left unchanged and not deallocated.

The lastsize function returns the size of the last block successfully allocated by either alloc or realloc. It is the preferred way to get the actual block size as realloc cannot return the new size within the allocated memory as alloc can.

The free function deallocates a block that has been allocated with either alloc or realloc. It takes as parameters a pointer to the block, ptr, and the actual size of the block, size.

WARNING

Major trauma will result if an attempt is made to either realloc or free a block on a different heap from the one that it was originally allocated on.

Museum