Other Alias
tfind, tdelete, twalk, tdestroyОБЗОР
#include <search.h>
void *tsearch(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void *tfind(const void *key, void *const *rootp,
int (*compar)(const void *, const void *));
void *tdelete(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void twalk(const void *root, void (*action)(const void *nodep,
const VISIT which,
const int depth));
#define _GNU_SOURCE /* см. feature_test_macros(7) */
#include <search.h>
void tdestroy(void *root, void (*free_node)(void *nodep));
ОПИСАНИЕ
Функции tsearch(), tfind(), twalk() и tdelete() позволяют работать с двоичным деревом. Они реализуют «Algorithm T» Д. Кнута (6.2.2). Первое поле в каждом узле дерева является указателем на соответствующий элемент данных (вызывающая программа должна хранить реальные данные). Аргумент compar указывает на процедуру сравнения, которой передаются указатели на два элемента данных. Эта процедура должна возвращать отрицательное, нулевое или положительное значение, если первый элемент меньше, равен или больше чем второй.Функция tsearch() ищет в дереве элемент, на который указывает key. Аргумент rootp указывает на переменную, которая указывает на корень дерева. Если дерево пустое, то переменная, на которую ссылается rootp, должна быть равна NULL. Если элемент найден, то tsearch() возвращает указатель на него, иначе tsearch() добавляет его и возвращает указатель на только что созданный элемент.
Функция tfind() похожа на tsearch(), за исключением того, что tfind() в случае нулевого результата поиска возвращает NULL.
Функция tdelete() удаляет элемент из дерева. Аргументы те же, что и для tsearch().
Функция twalk() выполняет обход дерева, сначала в глубину, затем слева направо. Аргумент root указывает на начальный элемент обхода. Если этот узел не является корневым, то будет пройдена только часть дерева. Функция twalk вызывает пользовательскую функцию action для каждого посещаемого узла (то есть три раза для внутреннего узла и один раз для конечного узла-листа). Функция action получает три аргумента. Первый — указатель на посещаемый узел. Структура узла не определена, но возможно привести указатель к указателю на указатель на элемент, чтобы получить доступ к элементу, хранящемуся внутри узла. Приложение не должно изменять структуру, на которую указывает этот аргумент. Второй — целое число, принимающее значение preorder, postorder или endorder в зависимости от того, в первый, второй или третий раз посещается внутренний узел, или значение leaf, если это единственный просмотр узла-листа. Эти символы определены в <search.h>. Третий аргумент — это глубина текущего погружения в дерево; для корня она равна нулю.
(В общем случае, функции preorder, postorder и endorder известны как preorder, inorder и postorder: перед посещением потомков, после первого посещения и перед вторым и после посещения. Таким образом, выбор имени postorder приводит к путанице.)
Функция tdestroy() удаляет всё дерево, на которое указывает rootp, высвобождая все ресурсы, выделенные функцией tsearch(). Для данных каждого узла дерева вызывается функция free_node. Указатель на данные передаётся в аргумент функции. Если делать ничего не нужно, то в free_node нужно указать функцию, которая ничего не делает.
ВОЗВРАЩАЕМОЕ ЗНАЧЕНИЕ
Функция tsearch() возвращает указатель на соответствующий элемент дерева или добавляет элемент и возвращает указатель на него, а также возвращает NULL, если для нового элемента недостаточно памяти. Функция tfind() возвращает указатель на элемент или NULL, если совпадений не найдено. Если есть несколько элементов с одинаковым ключом, то какой из них будет возвращён — не определено.Функция tdelete() возвращает указатель на родителя удалённого элемента, или NULL, если элемент не найден.
Функции tsearch(), tfind() и tdelete() также возвращают NULL, если rootp для записи был равен NULL.
АТРИБУТЫ
Описание терминов данного раздела смотрите в attributes(7).| Интерфейс | Атрибут | Значение |
|
tsearch(),
tfind(),
tdelete() | безвредность в нитях | безвредно (MT-Safe race:rootp) |
| twalk() | безвредность в нитях | безвредно (MT-Safe race:root) |
| tdestroy() | безвредность в нитях | безвредно (MT-Safe) |
СООТВЕТСТВИЕ СТАНДАРТАМ
POSIX.1-2001, POSIX.1-2008, SVr4. Функция tdestroy() является расширением GNU.ЗАМЕЧАНИЯ
Функции twalk() передаётся указатель на корень, а остальные функции ожидают указатель на переменную, которая указывает на корень.Функция tdelete() освобождает память, которая необходима для хранения элемента в дереве. Пользователь отвечает за освобождение памяти, использованной для хранения соответствующих данных.
Программа в примере зависит от того, что twalk() больше не ссылается на узел после вызова пользовательской функции с аргументом «endorder» или «leaf». Это работает с реализацией библиотеки GNU, но этого нет в документации System V.
ПРИМЕР
Приведённая ниже программа вставляет двенадцать случайных чисел в двоичное дерево, в котором повторяющиеся числа удаляются, а затем печатает их по порядку.
#define _GNU_SOURCE /* для объявления tdestroy() */
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
static void *root = NULL;
static void *
xmalloc(unsigned n)
{
void *p;
p = malloc(n);
if (p)
return p;
fprintf(stderr, "недостаточно памяти\n");
exit(EXIT_FAILURE);
}
static int
compare(const void *pa, const void *pb)
{
if (*(int *) pa < *(int *) pb)
return -1;
if (*(int *) pa > *(int *) pb)
return 1;
return 0;
}
static void
action(const void *nodep, const VISIT which, const int depth)
{
int *datap;
switch (which) {
case preorder:
break;
case postorder:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break;
case endorder:
break;
case leaf:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break;
}
}
int
main(void)
{
int i, *ptr;
void *val;
srand(time(NULL));
for (i = 0; i < 12; i++) {
ptr = xmalloc(sizeof(int));
*ptr = rand() & 0xff;
val = tsearch((void *) ptr, &root, compare);
if (val == NULL)
exit(EXIT_FAILURE);
else if ((*(int **) val) != ptr)
free(ptr);
}
twalk(root, action);
tdestroy(root, free);
exit(EXIT_SUCCESS);
}