前面我们说到了基于链表的内存分配算法。但是之前我们也说过,其实内存分配一般有三个原则,最快、最优和最差。最快比较好理解,就是寻找到合适的节点就立即分配内存,我们在前面一篇博客采用的就是这个方法。最优呢,就是寻找可以满足当前内存分配的最小节点,这样不会有很大的浪费,但是有可能会产生碎片节点。最后一种就是最差分配算法,说是最差效果未必最差。因为在大的内存分配的时候至少不会很快产生内存碎片,对整个系统的稳定来说有可能是好事。所以这三种方法很难说哪一种好,哪一种不好,需要结合具体的应用场景客观进行分析。不过话说回来,内存碎片是无论如何都避免不了的。
首先,为了灵活对这三种分配算法进行配置,我们定义了宏开关,需要哪个就把那个开关放开。暂时默认打开的算法的是最快分配算法。
#define MAX_SPEED_MALLOC 0 #define MIN_SIZE_MALLOC 0 #define MAX_SIZE_MALLOC 1 |
因为之前已经讨论过最快分配算法,所以这里着重讨论的最优分配算法和最差分配算法。又由于两者的差别极小,所以单独分析其中一种算法也行。就拿最优分配算法来说,为了寻找到最小的节点,我们需要对整个链表进行遍历,这个还是比较消耗时间的。
while(pCur) pPre = pCur; |
寻找到pFind这个我们需要的节点之后,还需要从pFreeList中删除该节点。所以,我们需要进一步的判断和分析,
if(NULL == pFind) pPre = find_previous_node_in_list(pFind, pFreeList); return pFind; |
首先判断pFind前面有没有节点,如果没有表示pFreeList就是pFind,那么pFreeList需要自行向后退缩;当然如果当前的pFind节点是有前节点的,那么只需要把前节点的next指针重新更改一下即可。当然,这里还对原来的查找节点函数作了一下修改,使之更合理更通用。
/************************************************* MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList) if(NULL == pFind) return pPre; |