Brent's Implementation of First Fit Allocation Strategy

This algorithm has an overhaead of only 4 bytes per block to record the size of the block. The time require to free or allocate the block is O(log W) where W is the maximum number of words allocated dynamicaly. According to the paper this algoritm should be faster than other simple first fit, especially for large number of small blocks. The storage area is divided into S segments numbered 0...S-1. Basically two arrays are maintained : [a] PointerArray[0 ... S-1], pointer to the first block in segment i and [b] SegmentTree[0 ..2S-1] which maintains the whole area as heap. Each block also has a control word which is a signed integer. The number gives the size of the block and the sign indicates whether the block is free or not.

The BrentMemAlloc class has the following methods:

• BrentSeg(p) - returns the index of the segment containing address p.
• BrentDouble() - this just doubles the number of segments actually in use.
• BrentFix1(p) - does housekeeping if a block with control word Size(p) will be allocated or merged with a block on its left in a different segment.
• BrentFix2(p) - does the housekeeping after the block with control word Size(p) is freed or merged with the block on its right or created by spliting.
• BrentPred(p) - return the predessor of block p.
• BrentAllocate(size) - Returns index of a block of size atleast "size".
• BrentDeallocate(address) - frees the block starting at "address".