分类： C/C++
2009-05-10 13:41:57
第二版是在第一版的基础上进行改进的。
由于第一版只使用链表进行管理，每次存放和查找都要遍历链表，耗时甚多。因此在链表的基础上，我们加入了hash进行管理。
#define NUMBER_OF_LIST_IN_MALLOC 3
#define MALLOC_MANAGE_LIST 0
#define MALLOC_FREE_LIST 1
#define MALLOC_USED_LIST 2
struct malloc_header
{
struct DListNode list[NUMBER_OF_LIST_IN_MALLOC];
uint_32 addr;
int size;
};
Hash功能模块
struct hash_struct_info
struct hash_struct_info
{
int size;
struct DListHeader hash_list[MAX_HASH_HEADER_LEN];
int (*cmp)(void*, void*);
int (*hash)(void *);
struct DListHeader* (*get_list_header)(struct hash_struct_info *head, struct DListNode *src);
struct DListNode * (*search_node)(struct hash_struct_info *head, struct DListNode *src);
int (*insert_node)(struct hash_struct_info *head, struct DListNode *src);
struct DListNode * (*delete_node)(struct hash_struct_info *head, struct DListNode *src);
};
Hash功能模块提供了一套默认的操作函数，同时也允许用户改变相应的功能函数，即使用自己定义的函数：
int hash_init(struct hash_struct_info *head, int (*hash)(void *), int (*cmp)(void*, void*));int hash_change_function(struct hash_struct_info *, int, void (*handler)(void));
malloc和free
假设在某一个阶段，内存分配处于一下一种状态，其中，used_pointer是管理正在使用的块的hash, free_buckets是管理空闲块的hash.
Normal 0 7.8 磅 0 2 false false false EN-US ZH-CN X-NONE MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:普通表格; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Calibri","sans-serif";}
现在，我们申请一个空闲块。
申请的流程：
1. 通过以申请块的大小取hash值，hash的取值算法为：Size / MALLOC_FREE_SIZE_INC
free_bucket[0] 连接的是0 ~ MALLOC_FREE_SIZE_INC – 1之间大小的空闲块
free_bucket[1] MALLOC_FREE_SIZE_INC ~ 2 * MALLOC_FREE_SIZE_INC – 1之间大小的空闲块
free_bucket[2] 2 * MALLOC_FREE_SIZE_INC ~ 3 * MALLOC_FREE_SIZE_INC – 1之间大小的空闲块
……
free_bucket[MAX_HASH_HEADER_LEN - 1] 大于 （MAX_HASH_HEADER_LEN - 1）* MALLOC_FREE_SIZE_INC 的空闲块
2. 通过hash值，找到相应的free_bucket，如果free_bucket是非空链表，则返回，否则，向下查找free_bucket，知道遇到第一个非空的free_bucket，如果没有找到符合要求的free_bucket，则返回最后一个free_bucket。
free函数需要处理四种情况：
1. 释放的空闲块前后都是正在使用的；
2. 释放的空闲块前面的一块是空闲的；
3. 释放的空闲块后面的一块是空闲的；
4. 释放的空闲块前面和后面都是空闲的；
下面只显示一种情况作为样例，即第三种情况：
