关于内存管理/空闲列表使用红黑树和双向链表实现恒定时间内存合并的问题

Question

前言：我试图理解数据结构和算法，因为它们与内存分配策略有关。在这种情况下，有一个大型的固定大小的内存池，其中的块将被分配给用户/从用户处释放，类似于调用

malloc()

或

free()

。

阅读本文：

他在最后提到使用排序双向链表在 O(1) 时间内实现合并操作。我正在努力想象如何应用链表来实现恒定的时间复杂度。

我的第一个想法是列表将按每个节点指针的地址排序，这样简单的计算

(Node + Node->size == Node->next)

就会告诉你两个内存块是否可以合并，但插入将是一个 O(N) 操作，因为你当新节点空闲时，需要找到合适的位置插入新节点。此外，双向链表的这种用法与本文的前半部分没有太大不同，即使用单链表来执行内存池块的所有分配/释放。

有人可以澄清双向链表与红黑树协同工作以实现 O(log(n)) 插入和删除（分别是释放和分配）以及 O(1) 合并的目的吗？

Answer 1

双向链表包含所有块（空闲的和已分配的），按起始地址排序，因此当一个块变为空闲时，这是一个

O(1)

操作，用于检查其左右邻居中的一个（或两个）是否是空闲的也免费。如果是这样，则与它们合并是一个

O(logN)

操作：合并将从列表中删除一个（或两个）条目 (

O(1)

) 并增加要合并到的块的大小（在树中更新它 -

O(logN)

），因此列表需要以某种方式与树交叉链接才能找到该块的节点。如果没有，则将这个新的空闲块插入到树中是一个

O(logN)

操作。

分配将在树中找到最适合的空闲块节点（

O(logN)

），减小其大小（更新，或者如果大小匹配则将其从树中删除 - 两者都

O(logN)

），并拆分“空闲”条目在列表中分成较小尺寸的“已分配”和“空闲”条目（

O(1)

），因此树还需要与列表交叉链接才能找到该条目。

根据您的内存布局，您可能还需要额外的哈希映射才能通过指针在

O(1)

中查找分配的列表条目（当执行

free()

时），并且还能够在

O(1)

中判断是否存在块该列表是空闲的或已分配的。

或者您可以将所有内容平铺在内存中，如rbtree_best_fit

的 Boost 文档

图表中所示。

因此，

malloc()

和

free()

都必然会修改树，因此不可避免地是

O(logN)

最坏的情况。然而，由于双向链表，合并特别是

O(1)

。