c - 优化 malloc 实现的隔离列表组织

Question

我正在研究cs:app malloc lab(我不是在寻找已实现的答案，只是在寻找高级流程)，如果您不熟悉该实验室，则需要实现malloc()。

我有堆 block ，其大小、状态 in_use 以及指向下一个/上一个空闲 block 的指针(如果该 block 未分配)，这最适合 空闲 block 的链接列表(显式空闲列表)。由于我们已经知道堆的最大大小是 2^32，所以我正在考虑将其切换到 BST 中的隔离列表，其中根节点定义大小类别并具有指向其空闲列表的指针(例如，大小为 2^n 的对象存储在节点列表中，其中 node->class == n)。

直觉告诉我，使用 AVL 树可以加快空闲 block 的查找速度和新大小类别的插入速度，并且使用隔离列表有助于减少碎片，但我对此类系统的思考还比较陌生。有人可以证实/否认我的推理吗？ (希望这不是一个太模糊的问题!)

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.