Доступ к данным узла через POSIX tdelete ()

Question

Страница man для функций двоичного дерева POSIX включает следующие операторы:

tdelete() возвращает указатель на родительский элемент удаленного элемента или NULL, еслиэлемент не был найден.

tdelete() освобождает память, необходимую для узла в дереве.Пользователь отвечает за освобождение памяти для соответствующих данных.

Это означает, что нет способа получить доступ к данным узла для данного ключа из вызова tdelete().Необходимо будет вызвать tfind() (а не tsearch(), чтобы не добавлять данный ключ), выполнить уничтожение данных узла, а затем вызвать tdelete() с тем же ключом, чтобы удалить узел из двоичного дерева..

Правильно ли я истолковал это?Есть ли какой-нибудь способ обойти ограничения в этом подходе?

1. Если ключ выделен в куче, его нельзя освободить (или сделать бесполезным для используемой функции сравнения) доузел удален.Это требует вызова tfind() для получения указателя на данные, tdelete() для удаления узла, а затем уничтожения данных, извлеченных из вызова tfind().
2. Для удаления узла требуются два поиска иуничтожить вложенные данные.

Answer 1

Мэтт, я думаю, что ваша интерпретация верна.Для отдельного удаления элементов это кажется неизбежным.(Но, во всяком случае, для операции \ Omega \ log N стоимость только в 2 раза больше;)

Долгое время я не использовал эти функции, но, просматривая старый код, похоже, что вы можете избежатьчасть накладных расходов, если вы одновременно уничтожаете дерево (если это ваш случай), используя два вызова twalk:

1. , подсчитывающих число N элементов в вашем дереве с помощьюсоответствующий вызов twalk
2. выделить массив размером N указателей на элементы дерева
3. заполнить этот массив за секунду twalk через дерево
4. runчерез этот массив и для каждого узла дерева сначала удалите его данные, а затем сам узел

Если вам действительно нужна такая вещь, вы можете найти потокобезопасную инкапсуляцию C ++ этих вызовов в нашей библиотеке parXXL в каталоге par/sys.

Answer 2

Я никогда раньше не использовал этот набор функций, но, похоже, вы правы.Однако я бы попытался использовать указатель, возвращаемый из tfind() в качестве аргумента rootp для tdelete().Это должно сделать второй поиск по существу неактивным.AFAICT, структура данных позволяет обрабатывать любой узел как корень, чтобы вы могли найти этот узел и затем удалить его из поддерева с корнем в найденном узле.

Answer 3

Как и Д.Шоули, я никогда раньше не использовал эти функции, поэтому я написал небольшую тестовую программу, которая приводит к утечке памяти.значения «внутри двоичного дерева» являются копиями указателей на данные.Копии управляются функциями <search.h>, а данные должны управляться программой.

Память 0xcb8030 должна быть освобождена путем вызова tdelete(), соответствующего 0xcb8010 (элемент сзначение 0) должно быть освобождено программой (как и ранее потерянное 0xcb8060).