tsearch(3) Library Functions Manual tsearch(3) tsearch, tfind, tdelete, twalk, twalk_r, tdestroy - manage a binary search tree LIBRARY Standard C library (libc, -lc) #include typedef enum { preorder, postorder, endorder, leaf } VISIT; 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 *restrict key, void **restrict rootp, int (*compar)(const void *, const void *)); void twalk(const void *root, void (*action)(const void *nodep, VISIT which, int depth)); #define _GNU_SOURCE /* feature_test_macros(7) */ #include void twalk_r(const void *root, void (*action)(const void *nodep, VISIT which, void *closure), void *closure); void tdestroy(void *root, void (*free_node)(void *nodep)); tsearch(), tfind(), twalk() tdelete() . <> . (6.2.2). ( ). compar , . , , , . tsearch() . key . rootp , . , , rootp, NULL. , tsearch() ( , tsearch() ). , tsearch() . tfind() tsearch(), , tfind() NULL. tdelete() . , tsearch(). twalk() , , . root . , . twalk action ( -). action . -- . , , , . , . -- , preorder, postorder endorder , , , leaf, -. . -- ; . ( , preorder, postorder endorder preorder, inorder postorder: , . , postorder .) twalk_r() twalk(), depth - closure . , . tdestroy() , rootp, , tsearch(). free_node. . , free_node , . tsearch() , NULL, . tfind() NULL, . , -- . tdelete() NULL, . , tdelete() , . tsearch(), tfind() tdelete() NULL, rootp NULL. attributes(7). +----------------------------+----------------------------------------------------------+--------------------------+ | | | | +----------------------------+----------------------------------------------------------+--------------------------+ |tsearch(), tfind(), | | MT-Safe race:rootp | |tdelete() | | | +----------------------------+----------------------------------------------------------+--------------------------+ |twalk() | | MT-Safe race:root | +----------------------------+----------------------------------------------------------+--------------------------+ |twalk_r() | | MT-Safe race:root | +----------------------------+----------------------------------------------------------+--------------------------+ |tdestroy() | | MT-Safe | +----------------------------+----------------------------------------------------------+--------------------------+ tsearch() tfind() tdelete() twalk() POSIX.1-2008. tdestroy() twalk_r() GNU. tsearch() tfind() tdelete() twalk() POSIX.1-2001, POSIX.1-2008, SVr4. twalk_r() glibc 2.30. twalk() , , . tdelete() , . , . , twalk() <> <>. GNU, System V. , , . #define _GNU_SOURCE /* Expose declaration of tdestroy() */ #include #include #include #include #include static void *root = NULL; static void * xmalloc(size_t n) { void *p; p = malloc(n); if (p) return p; fprintf(stderr, "insufficient memory\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, VISIT which, 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 *ptr; int **val; srand(time(NULL)); for (unsigned int i = 0; i < 12; i++) { ptr = xmalloc(sizeof(*ptr)); *ptr = rand() & 0xff; val = tsearch(ptr, &root, compare); if (val == NULL) exit(EXIT_FAILURE); if (*val != ptr) free(ptr); } twalk(root, action); tdestroy(root, free); exit(EXIT_SUCCESS); } . bsearch(3), hsearch(3), lsearch(3), qsort(3) Azamat Hackimov , Dmitry Bolkhovskikh , Yuri Kozlov ; GNU 3 , . . , , . Linux man-pages 6.06 31 2023 . tsearch(3)