为 malloc 实现优化隔离列表组织

Question

我正在研究 cs:app malloc lab（我不是在寻找已实现的答案，只是在寻找高级流程），如果您不熟悉，请执行 malloc() .

我有大小为 in_use 的堆块，以及一个指向 next/previous 空闲块的指针（如果该块未分配），它最适合 空闲块的链接列表（显式空闲列表）。因为我们已经知道堆的最大大小是 2^32，所以我正在考虑将其切换到 BST 中的 隔离列表 ，其中根节点定义大小class 并有一个指向其空闲列表的指针（例如，大小为 2^n 的对象存储在 node->class == n 的节点列表中）。

直觉告诉我，使用 AVL 树会加快查找空闲块和插入新大小 classes 的速度，并且使用隔离列表有助于减轻碎片化，但我的想法仍然相对较新关于这些类型的系统。有人可以 confirm/deny 我的推理吗？（希望这不是一个太模糊的问题！）

Answer 1

start with two pointers.  
#define SIZE_OF_HEAP = &endHeap - &Heap;
freePtr = &Heap; 
Heap = NULL;  // at start, the first linked list entry has no following entry
usedPtr = NULL;

with each allocation, insert the address into the usedPtr list
update the freePtr list to 'skip around' the allocated block

with each free, remove the block info from the userPtr list
insert the block info into the freePtr list (by address magnitude)
check if any two freePtr blocks are adjacent
if adjacent, the merge into a single block

The heap processing should have an 'initial' state, for
any initialization 
(like setting the initial values of the usedPtr and freePtr 
     linked list head values  
     then change state to 'ready')

be sure to handle cases such as when the address passed to free() is not on the usedPtr linked list

be sure to handle cases such as when there is no freePtr block large enough to accommodate the requested block size.

Note: these linked lists, other than the head pointers, 
     are actually embedded in the heap at the beginning of each block. 
Should also keep a small buffer at the end of each allocated block 
set it to some known value, like '0xdead' or the address of the block
so can check to see if the heap has been corrupted

effectively this results in two linked lists, 
between the two linked lists, all of the heap is covered.

 note: the address passed back to the caller 
 is actually the address past the end of the linked list entry for the block.  
 SO an actual allocation is slightly larger than what the user requested.

be sure each returned address to the user is on a 32/64 bit boundary.

为 malloc 实现优化隔离列表组织

optimizing segregated list organization for malloc implementation

c

data-structures

linked-list

malloc

binary-search-tree