题外话:为什么叫“伙伴”?因为每块只能和特定的另一块合并。
参考了wiki上伙伴系统实现的链接,在此做一简单总结
这里采用二叉树管理内存单元,分配和释放的搜索时间复杂度O(logN),在这一点上优于最先匹配、最佳匹配和最差匹配。
每个节点标记对应的可用内存块大小
分配:
释放:
传入offset。从最底层节点向上回溯,遇到标记为0的节点即对应当初分配的内存块,恢复标记为块大小,继续回溯,如果左右子树标记相加等于父节点对应的块大小,则恢复父节点标记为块大小。