c - 运行中内存不足时撤消C动态数据结构的变化

Question

我正在用 C 实现一些支持各种操作的复杂数据结构。这种数据结构使用了许多其他动态结构(图形、AVL 树、链表)，并且一切都在使用动态内存。

当做一些操作时，例如插入我的数据结构，显然我必须分配内存，有时会分配很多内存(因此结构会增长)。这会导致在执行某些操作的过程中内存不足(malloc() 返回 NULL)。现在，我不想终止我的程序，而是让操作的调用者知道操作失败并让调用者继续执行。

我的问题是，当操作在执行过程中由于内存分配失败而失败时，我想撤消调用该操作后所做的事情，撤消数据结构中的那些更改，就好像这个操作是从未调用过(因此将数据结构恢复到执行操作之前的状态)。我需要它，因为我希望我的数据结构处于有效且可用的状态，即使操作失败，这样我也可以继续使用它。

由于数据结构非常先进，我正在寻找有关在调用操作之前将动态数据结构恢复到其状态的通用方法、提示和技巧。也许您在处理此类问题方面有一些经验，听说过这个问题，或者可以推荐一些关于它或相关源代码的书籍/文章。

编辑:一个小的简化示例将从 C++ 中设置<>。根据 STL 文档，set::insert 即使在抛出异常时也能正常工作，因此它能够以某种方式恢复在执行 set::insert 期间所做的更改，即使 set 的底层数据结构(可能是红黑树)非常先进.

引自 cplusplus.com:“如果要插入单个元素，则在发生异常时容器中没有任何变化(强保证)。否则，保证容器以有效状态结束(基本保证)。”

Answer 1

处理此类情况的常用方法是，您首先进行空运行并分配整个操作所需的内存。并且实际上只有在所有分配都成功时才进行更新。

当然，这可能总是是可能的，因为您可能必须调用其他没有“试运行”模式的操作，或者某些分配在您实际执行操作之前可能不会显示。对于这种情况，复制数据结构通常是最好的选择。同样，由于复制是只读操作，因此很容易中止和撤消。

用户可能希望避免重复和跟踪额外数据结构或进行试运行的开销。所以这个特性可以做成一个可选特性(可以使用#ifdef)，用户可以选择反转操作或终止整个程序。