Отмена изменений в динамических структурах данных C, когда в середине операции возникает нехватка памяти

Question

Я реализую некоторую сложную структуру данных в C, поддерживающую различные операции. Эта структура данных использует много других динамических структур (графы, деревья AVL, связанные списки), и все использует динамическую память.

При выполнении какой-либо операции, например, вставки в мою структуру данных, очевидно, что мне приходится выделять память, иногда большую ее часть (поэтому структура увеличивается). Это может привести к нехватке памяти (malloc () возвращает NULL) в середине выполнения некоторой операции. Теперь я хотел бы не завершать свою программу, но сообщить вызывающему оператору, что операция завершилась неудачно, и позволить вызывающему продолжить выполнение.

Моя проблема заключается в том, что, когда операция завершается неудачей в середине ее выполнения из-за сбоя выделения памяти, я хотел бы отменить то, что было сделано с момента вызова операции, отменить эти изменения в структуре данных, чтобы эта операция была никогда не вызывается (поэтому верните структуру данных в состояние прямо перед выполнением операции). Мне это нужно, потому что я хочу, чтобы моя структура данных была в допустимом и пригодном для использования состоянии, даже если операция не удалась, поэтому я могу продолжать ее использовать.

Поскольку структура данных достаточно продвинута, я ищу общие методы, советы и подсказки относительно возврата динамической структуры данных в ее состояние непосредственно перед вызовом операции. Возможно, у вас есть некоторый опыт решения таких проблем, вы слышали об этой проблеме или можете предложить несколько книг / статей, касающихся ее или связанных исходных кодов.

РЕДАКТИРОВАТЬ: немного упрощенный пример будет установлен <> из C ++. Согласно документации STL, set :: insert работает хорошо, даже когда генерируется исключение, поэтому он каким-то образом способен отменить изменения, сделанные во время выполнения set :: insert, даже если базовая структура данных набора (вероятно, красно-черные деревья) достаточно продвинута .

Цитата из cplusplus.com: «Если нужно вставить один элемент, в случае исключения изменения в контейнере отсутствуют (строгая гарантия). В противном случае контейнер гарантированно завершится в действительном состоянии (базовая гарантия). "

Answer 1

Обычный подход для обработки таких случаев - сначала выполнить пробный прогон и выделить память, необходимую для всей операции. И фактически сделать обновление, только если все распределения успешны.

Конечно, это не может всегда быть возможным, потому что вам, возможно, придется вызывать другие операции, которые не имеют режима «пробного запуска», или некоторые выделения могут не отображаться, пока вы фактически не выполните операцию. В таких случаях дублирование структуры данных обычно является наилучшим вариантом. Опять же, поскольку дублирование является операцией только для чтения, ее легко прервать и отменить.

Пользователь может захотеть избежать дублирования и отслеживания дополнительных структур данных или выполнения пробных прогонов. Таким образом, эта функция может быть сделана как дополнительная функция (возможно, использовать #ifdef), где пользователь может выбирать между отменой операции или завершением всей программы.

Answer 2

В C ++ один общий подход состоит в том, чтобы построить результат в форме «временного», а затем поменять местами временное и результат. Вы также можете внести дополнительные изменения, которые не могут произойти сбой после обмена.

Вы можете взглянуть на Что такое иероглиф копирования и обмена? для вдохновения - даже если это особый вариант использования свопа, и вам может не понадобиться копия-часть.