"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
How are you going to efficiently find the beginning of the
previous block if you only store the size of the current block?
If you can't find the beginning of the previous block, how can
you do consolidation?
As we allocate and free memory the arena fragments. We store the fragments
as a linked list which is always kept in ascending order.
When a block is freed you can find its place in the list by walking it until
two pointers straddle the block to be freed.
To consolidate, we need to know the size and the intial position of the
previous block, the size and intial position of the block to be freed, and
the size and intial position of the following block. Since the intial
position of the block to free is given by the pointer, it follows that all
we need to store is the size, in a block that is allocated. Blocks in the
free list, however, need both size information and pointers to the next
block.
If you attempt to store the location of the previous block you run into
problems when it is broken up or consolidated by further allocations.
Walking a linked list is fast, but it is still an O(N) operation. In
practise the easiest way of getting rid of this inefficiency is to treat
small blocks specially. You then have only a few big allocations to run from
the general-purpose allocator. If you are sufficiently determined you can
store all the free blocks in a balanced binary tree and find the position of
the free block that way.