| Standards / Extensions | C or C++ | Dependencies |
|---|---|---|
XPG4 |
both |
#define _XOPEN_SOURCE
#include <search.h>
void *tsearch(const void *key, void **rootp,
int (*compar)(const void *, const void *));The tsearch() function is used to build and access a binary search tree. The key argument is a pointer to an element to be accessed or stored. If there is a node in the tree whose element is equal to the value pointed to by key, a pointer to this found node is returned. Otherwise, the value pointed to by key is inserted (that is, a new node is created and the value of key is copied to this node), and a pointer to this node returned. Only pointers are copied, so the calling routine must store the data. The rootp argument points to a variable that points to the root node of the tree. A NULL pointer value for the variable pointed to by rootp denotes an empty tree; in this case, the variable will be set to point to the node which will be at the root of the new tree.
Comparisons are made with a user-supplied routine, the address of which is passed as the compar argument. This routine is called with two arguments, the pointers to the elements being compared. The user-supplied routine must return an integer less than, equal to or greater than 0, according to whether the first argument is to be considered less than, equal to or greater than the second argument. The comparison functions need not compare every byte, so arbitrary data may be contained in the elements in addition to the values being compared.
Threading Behavior: Since the tree is anchored by the user's rootp pointer, the tree storage is visible to the user and could be shared among threads. The user would be responsible for serializing access to a shared tree. There are no variables related to these functions which are internal to the library and/or give rise to multithreading considerations.
Special behavior for C++: Because C and C++ linkage conventions are incompatible, tsearch() cannot receive a C++ function pointer as the comparator argument. If you attempt to pass a C++ function pointer to tsearch(), the compiler will flag it as an error. You can pass a C or C++ function to tsearch() by declaring it as extern "C".
If the node is found, tsearch() returns a pointer to it, otherwise it returns a pointer to the inserted item.
If there is not enough space available to create a new node, or if rootp is a NULL pointer on entry, tsearch() returns a NULL pointer.
No errors are defined.