Merging upstream version 6.8.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 356 insertions, 0 deletions

diff --git a/man/man3/tsearch.3 b/man/man3/tsearch.3
new file mode 100644
index 0000000..c4aaf18
--- /dev/null
+++ b/man/man3/tsearch.3
@@ -0,0 +1,356 @@
+'\" t
+.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
+.\"
+.\" SPDX-License-Identifier: Linux-man-pages-copyleft
+.\"
+.TH tsearch 3 2024-05-02 "Linux man-pages (unreleased)"
+.SH NAME
+tsearch, tfind, tdelete, twalk, twalk_r, tdestroy \- manage a binary search tree
+.SH LIBRARY
+Standard C library
+.RI ( libc ", " \-lc )
+.SH SYNOPSIS
+.nf
+.B #include <search.h>
+.P
+.B typedef enum { preorder, postorder, endorder, leaf } VISIT;
+.P
+.BI "void *tsearch(const void *" key ", void **" rootp ,
+.BI "                int (*" compar ")(const void *, const void *));"
+.BI "void *tfind(const void *" key ", void *const *" rootp ,
+.BI "                int (*" compar ")(const void *, const void *));"
+.BI "void *tdelete(const void *restrict " key ", void **restrict " rootp ,
+.BI "                int (*" compar ")(const void *, const void *));"
+.BI "void twalk(const void *" root ,
+.BI "                void (*" action ")(const void *" nodep ", VISIT " which ,
+.BI "                               int " depth ));
+.P
+.BR "#define _GNU_SOURCE" "         /* See feature_test_macros(7) */"
+.B #include <search.h>
+.P
+.BI "void twalk_r(const void *" root ,
+.BI "                void (*" action ")(const void *" nodep ", VISIT " which ,
+.BI "                               void *" closure ),
+.BI "                void *" closure );
+.BI "void tdestroy(void *" root ", void (*" free_node ")(void *" nodep ));
+.fi
+.SH DESCRIPTION
+.BR tsearch (),
+.BR tfind (),
+.BR twalk (),
+and
+.BR tdelete ()
+manage a
+binary search tree.
+They are generalized from Knuth (6.2.2) Algorithm T.
+The first field in each node of the tree is a pointer to the
+corresponding data item.
+(The calling program must store the actual data.)
+.I compar
+points to a comparison routine, which takes
+pointers to two items.
+It should return an integer which is negative,
+zero, or positive, depending on whether the first item is less than,
+equal to, or greater than the second.
+.P
+.BR tsearch ()
+searches the tree for an item.
+.I key
+points to the item to be searched for.
+.I rootp
+points to a variable which points to the root of the tree.
+If the tree is empty,
+then the variable that
+.I rootp
+points to should be set to NULL.
+If the item is found in the tree, then
+.BR tsearch ()
+returns a pointer
+to the corresponding tree node.
+(In other words,
+.BR tsearch ()
+returns a pointer to a pointer to the data item.)
+If the item is not found, then
+.BR tsearch ()
+adds it, and returns a
+pointer to the corresponding tree node.
+.P
+.BR tfind ()
+is like
+.BR tsearch (),
+except that if the item is not
+found, then
+.BR tfind ()
+returns NULL.
+.P
+.BR tdelete ()
+deletes an item from the tree.
+Its arguments are the same as for
+.BR tsearch ().
+.P
+.BR twalk ()
+performs depth-first, left-to-right traversal of a binary
+tree.
+.I root
+points to the starting node for the traversal.
+If that node is not the root, then only part of the tree will be visited.
+.BR twalk ()
+calls the user function
+.I action
+each time a node is
+visited (that is, three times for an internal node, and once for a
+leaf).
+.IR action ,
+in turn, takes three arguments.
+The first argument is a pointer to the node being visited.
+The structure of the node is unspecified,
+but it is possible to cast the pointer to a pointer-to-pointer-to-element
+in order to access the element stored within the node.
+The application must not modify the structure pointed to by this argument.
+The second argument is an integer which
+takes one of the values
+.BR preorder ,
+.BR postorder ,
+or
+.B endorder
+depending on whether this is the first, second, or
+third visit to the internal node,
+or the value
+.B leaf
+if this is the single visit to a leaf node.
+(These symbols are defined in
+.IR <search.h> .)
+The third argument is the depth of the node;
+the root node has depth zero.
+.P
+(More commonly,
+.BR preorder ,
+.BR postorder ,
+and
+.B endorder
+are known as
+.BR preorder ,
+.BR inorder ,
+and
+.BR postorder :
+before visiting the children, after the first and before the second,
+and after visiting the children.
+Thus, the choice of name
+.B post\%order
+is rather confusing.)
+.P
+.BR twalk_r ()
+is similar to
+.BR twalk (),
+but instead of the
+.I depth
+argument, the
+.I closure
+argument pointer is passed to each invocation of the action callback,
+unchanged.
+This pointer can be used to pass information to and from
+the callback function in a thread-safe fashion, without resorting
+to global variables.
+.P
+.BR tdestroy ()
+removes the whole tree pointed to by
+.IR root ,
+freeing all resources allocated by the
+.BR tsearch ()
+function.
+For the data in each tree node the function
+.I free_node
+is called.
+The pointer to the data is passed as the argument to the function.
+If no such work is necessary,
+.I free_node
+must point to a function
+doing nothing.
+.SH RETURN VALUE
+.BR tsearch ()
+returns a pointer to a matching node in the tree, or to
+the newly added node, or NULL if there was insufficient memory
+to add the item.
+.BR tfind ()
+returns a pointer to the node, or
+NULL if no match is found.
+If there are multiple items that match the key,
+the item whose node is returned is unspecified.
+.P
+.BR tdelete ()
+returns a pointer to the parent of the node deleted, or
+NULL if the item was not found.
+If the deleted node was the root node,
+.BR tdelete ()
+returns a dangling pointer that must not be accessed.
+.P
+.BR tsearch (),
+.BR tfind (),
+and
+.BR tdelete ()
+also
+return NULL if
+.I rootp
+was NULL on entry.
+.SH ATTRIBUTES
+For an explanation of the terms used in this section, see
+.BR attributes (7).
+.TS
+allbox;
+lbx lb lb
+l l l.
+Interface	Attribute	Value
+T{
+.na
+.nh
+.BR tsearch (),
+.BR tfind (),
+.BR tdelete ()
+T}	Thread safety	MT-Safe race:rootp
+T{
+.na
+.nh
+.BR twalk ()
+T}	Thread safety	MT-Safe race:root
+T{
+.na
+.nh
+.BR twalk_r ()
+T}	Thread safety	MT-Safe race:root
+T{
+.na
+.nh
+.BR tdestroy ()
+T}	Thread safety	MT-Safe
+.TE
+.SH STANDARDS
+.TP
+.BR tsearch ()
+.TQ
+.BR tfind ()
+.TQ
+.BR tdelete ()
+.TQ
+.BR twalk ()
+POSIX.1-2008.
+.TP
+.BR tdestroy ()
+.TQ
+.BR twalk_r ()
+GNU.
+.SH HISTORY
+.TP
+.BR tsearch ()
+.TQ
+.BR tfind ()
+.TQ
+.BR tdelete ()
+.TQ
+.BR twalk ()
+POSIX.1-2001, POSIX.1-2008, SVr4.
+.TP
+.BR twalk_r ()
+glibc 2.30.
+.SH NOTES
+.BR twalk ()
+takes a pointer to the root, while the other functions
+take a pointer to a variable which points to the root.
+.P
+.BR tdelete ()
+frees the memory required for the node in the tree.
+The user is responsible for freeing the memory for the corresponding
+data.
+.P
+The example program depends on the fact that
+.BR twalk ()
+makes no
+further reference to a node after calling the user function with
+argument "endorder" or "leaf".
+This works with the GNU library
+implementation, but is not in the System V documentation.
+.SH EXAMPLES
+The following program inserts twelve random numbers into a binary
+tree, where duplicate numbers are collapsed, then prints the numbers
+in order.
+.P
+.\" SRC BEGIN (tsearch.c)
+.EX
+#define _GNU_SOURCE     /* Expose declaration of tdestroy() */
+#include <search.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+\&
+static void *root = NULL;
+\&
+static void *
+xmalloc(size_t n)
+{
+    void *p;
+\&
+    p = malloc(n);
+    if (p)
+        return p;
+    fprintf(stderr, "insufficient memory\en");
+    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\en", *datap);
+        break;
+    case endorder:
+        break;
+    case leaf:
+        datap = *(int **) nodep;
+        printf("%6d\en", *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);
+}
+.EE
+.\" SRC END
+.SH SEE ALSO
+.BR bsearch (3),
+.BR hsearch (3),
+.BR lsearch (3),
+.BR qsort (3)