| 摘要 |
A method and system for allocating and freeing memory is provided. In a preferred embodiment, a requesting program running on a computer system allocates a logically contiguous block of memory (a "heap") for the temporary storage of data structures. A Heap Manager, provided by the present invention, manages the heap in response to requests from the requesting program. The Heap Manager allocates and frees blocks within the heap. The Heap Manager logically divides the heap into segments and maintains a free list for each segment. The free list is a list of the free blocks contained in a segment. The heap has an associated free block array and an associated size tree. The free block array has a plurality of entries; each entry points to a free list for a segment. Each leaf node of the size tree corresponds to a plurality of entries in the free block array. A value contained in each leaf node indicates the size of the largest free block in the segments corresponding to the plurality of entries. The size tree is arranged in such a way that the value of each node is equal to the largest value of its child nodes. The Heap Manager selects a free block for allocation to the requesting program by searching the size tree and the free block array and selecting a segment that contains a free block that will satisfy the request, and then searching the free list corresponding to the selected segment to locate the smallest free block that satisfies the request. The Heap Manager frees a block in a segment by updating the free list for the segment, the free block array entry that points to the free list, and the size tree. |
