公开(公告)号：US5561786A

公开(公告)日：1996-10-01

申请号：US372131

申请日：1994-08-24

申请人： Peter L. Morse

发明人： Peter L. Morse

IPC分类号： G06F12/02 ,  G06F15/40 ,  G06F9/44

CPC分类号： G06F12/023 ,  Y10S707/99953 ,  Y10S707/99956

摘要： A method and system for allocating and freeing memory is provided. 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 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 contains entries, each entry pointing to a free list. Each leaf node of the size tree corresponds to 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 entries. The Heap Manager selects a free block for allocation to the requesting program by searching to size tree and the free block array and selecting 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.

摘要翻译： 提供了一种用于分配和释放存储器的方法和系统。 在计算机系统上运行的请求程序为数据结构的临时存储分配逻辑上连续的存储块（“堆”）。 由本发明提供的堆管理器响应于请求程序的请求来管理堆。 堆经理在逻辑上将堆划分成段，并为每个段维护一个空闲列表。 免费列表是段中包含的空闲块的列表。 堆具有相关联的空闲块数组和相关联的大小树。 自由块数组包含条目，每个条目指向一个空闲列表。 大小树的每个叶节点对应于自由块数组中的条目。 每个叶节点中包含的值表示对应于条目的段中最大空闲块的大小。 堆管理器通过搜索大小树和空闲块阵列并选择包含可满足请求的空闲块的段，并选择一个空闲块来分配给请求程序，然后搜索与所选段对应的空闲列表来定位 满足请求的最小的空闲块。