Освобождение памяти malloc из кругового связанного списка

Question

Я заранее прошу прощения, если это невероятно глупый вопрос ...

В настоящее время у меня есть круговой связанный список.Количество узлов обычно считается неизменным.Когда я хочу добавить к нему, я выделяю количество узлов (например, 100000 или около того) и склеиваю их. Эта часть отлично работает, когда я размещаю узлы по одному.

Я хочу попытатьсявыделить по блокам:

NODE *temp_node = node->next;
NODE *free_nodes = malloc( size_block * sizeof( NODE ) );
node->next = free_nodes;
for ( i = 0; i < size_block - 1; i++ ) {
    free_nodes[i].src = 1;
    free_nodes[i].dst = 0;
    free_nodes[i].next = &free_nodes[i+1];
}
free_nodes[size_block - 1].next = temp_node;

Список работает до тех пор, пока я не пытаюсь освободить что-либо (ошибка «glibc обнаружено: двойное освобождение или повреждение»).Интуитивно, я думаю, это потому, что его освобождение не освобождает один узел, а циклический переход по обычному способу - попытка освободить его несколько раз (плюс освобождение всего блока, вероятно, приводит к отсоединению всех других указателей от узлов, которые все еще существуют?), но:

1. Может ли кто-нибудь объяснить, пожалуйста, в явном виде, что происходит?
2. Есть ли способ распределить узлы по блокам и не разбивать их?

Цель этого заключается в том, что я вызываю malloc сотни тысяч раз, и было бы хорошо, если бы все было быстрее.Если есть лучший способ обойти это, или я не могу ожидать, что это станет быстрее, я был бы также признателен за это.:)

Answer 1

Может кто-нибудь объяснить мне, что происходит?

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

Есть ли способ распределить узлы по блокам, а не разбивать вещи?

Выделите разные сегменты памяти для каждого блока. В вашем коде (который не является полным) должно быть что-то вроде:

for ( i = 0; i < size_block ; i++ ) {
    free_nodes[i] = malloc (sizeof( NODE ));
}

Answer 2

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

Придумать свои собственные способы это сложно и обычно не стоит. Современные среды выполнения имеют довольно эффективную сборку мусора за malloc / free (для ее буферов, а не для распределения пользователей), и вам будет трудно добиться чего-то лучшего, лучшего, более эффективного, но все же гарантирующего согласованность вашего данные.

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

Answer 3

Когда вы освобождаете узел, вы освобождаете все выделение, с которым был выделен узел.Вы должны как-то договориться об освобождении сразу всей группы узлов.

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