Связанный список, содержащий другие связанные списки и бесплатно

Question

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

Если я добавлю ключ в начало моей структуры магическое число, которое я могу проверить, разыменовав пустоту * и выяснив, что это список?

РЕДАКТИРОВАТЬ: вызывающие абоненты не вставляют меньшие списки, которые они вставляют моими функциями. Я не хочу, чтобы вызывающие абоненты имели дело с обновлением нескольких списков только того, на который они имеют указатель.

Answer 1

Этот вопрос действительно зависит от того, чья ответственность состоит в том, чтобы очистить записи в списке. Если ваша структура отвечает за очистку памяти, на которую ссылаются поля void *, то здесь у вас есть гораздо более серьезная проблема, а именно то, что при void * обращении к некоторому произвольному блоку памяти вы никогда не узнаете, что правильно чтобы освободить это. Например, если у вас есть реализация динамического массива в соответствии с C ++ std::vector, тогда ваш void * может указывать на структуру, которая сама содержит указатель, и ваш список должен знать, что он должен спускаться в эту структуру, чтобы рекурсивно освободить его динамически распределенный блок. Случай, который вы описываете, где вы пропускаете вложенный список, - это только частный случай этой более общей проблемы.

Если, с другой стороны, список не отвечает за очистку памяти, на которую ссылаются void * s, которые он хранит, то вам не стоит беспокоиться об этой проблеме вообще.

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

Answer 2

Мой совет будет, если вообще возможно, немного упростить вещи и просто убедиться, что один связанный список содержит только один тип объекта.

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

Answer 3

Это не просто то, что ваш void* может указывать на список. Может указывать на любую динамически выделяемую память.

Способ, которым GLib решает эту проблему, заключается в том, что вызывающая сторона несет ответственность за освобождение всего, на что указывает void *data списка. См http://library.gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html#g-list-free.

Альтернатива (которую также предоставляет GLib) состоит в создании функции, которая принимает указатель на функцию и вызывает ее для каждого void *data при прохождении списка. Посмотри вверх g_list_free_full.

Answer 4

Чтобы ответить на вопрос, в чем заключается мудрость «Если я добавлю ключ в начало моей структуры магическое число, которое я могу проверить, разыменовав пустоту * и выяснив, что это список?»

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

Самое простое эффективное решение состоит в том, что если вам нужен узел, чтобы знать, что он указывает на список, укажите флаг в узле, сообщив об этом.

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