| Skip Navigation Links | |
| Exit Print View | |
 | man pages section 3: Basic Library Functions Oracle Solaris 11 Information Library |
| Skip Navigation Links | |
| Exit Print View | |
| man pages section 3: Basic Library Functions Oracle Solaris 11 Information Library |
enable_extended_FILE_stdio(3C)
posix_spawnattr_getschedparam(3C)
posix_spawnattr_getschedpolicy(3C)
posix_spawnattr_getsigdefault(3C)
posix_spawnattr_getsigignore_np(3C)
posix_spawnattr_getsigmask(3C)
posix_spawnattr_setschedparam(3C)
posix_spawnattr_setschedpolicy(3C)
posix_spawnattr_setsigdefault(3C)
posix_spawnattr_setsigignore_np(3C)
posix_spawnattr_setsigmask(3C)
posix_spawn_file_actions_addclose(3C)
posix_spawn_file_actions_addclosefrom_np(3C)
posix_spawn_file_actions_adddup2(3C)
posix_spawn_file_actions_addopen(3C)
posix_spawn_file_actions_destroy(3C)
posix_spawn_file_actions_init(3C)
pthread_attr_getdetachstate(3C)
pthread_attr_getinheritsched(3C)
pthread_attr_getschedparam(3C)
pthread_attr_getschedpolicy(3C)
pthread_attr_setdetachstate(3C)
pthread_attr_setinheritsched(3C)
pthread_attr_setschedparam(3C)
pthread_attr_setschedpolicy(3C)
pthread_barrierattr_destroy(3C)
pthread_barrierattr_getpshared(3C)
pthread_barrierattr_setpshared(3C)
pthread_condattr_getpshared(3C)
pthread_condattr_setpshared(3C)
pthread_cond_reltimedwait_np(3C)
pthread_key_create_once_np(3C)
pthread_mutexattr_getprioceiling(3C)
pthread_mutexattr_getprotocol(3C)
pthread_mutexattr_getpshared(3C)
pthread_mutexattr_getrobust(3C)
pthread_mutexattr_setprioceiling(3C)
pthread_mutexattr_setprotocol(3C)
pthread_mutexattr_setpshared(3C)
pthread_mutexattr_setrobust(3C)
pthread_mutex_getprioceiling(3C)
pthread_mutex_reltimedlock_np(3C)
pthread_mutex_setprioceiling(3C)
pthread_rwlockattr_destroy(3C)
pthread_rwlockattr_getpshared(3C)
pthread_rwlockattr_setpshared(3C)
pthread_rwlock_reltimedrdlock_np(3C)
pthread_rwlock_reltimedwrlock_np(3C)
pthread_rwlock_timedrdlock(3C)
pthread_rwlock_timedwrlock(3C)
rctlblk_get_enforced_value(3C)
- manage binary search trees
#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 *restrictkey,void **restrictrootp,int (*compar)(const void *, const void *));
voidtwalk(const void *root,void(*action) (void *, VISIT, int));
Thetsearch(),tfind(),tdelete(), andtwalk() functions are routines for manipulating binarysearch trees. They are generalized fromKnuth(6.2.2)AlgorithmsTandD. All comparisons are done with a user-supplied routine. This routine iscalled with two arguments, the pointers to the elements being compared. Itreturns an integer less than, equal to, or greater than 0, accordingto whether the first argument is to be considered less than, equal toor greater than the second argument. The comparison function need not compareevery byte, so arbitrary data may be contained in the elements inaddition to the values being compared.
Thetsearch() function is used to build and access the tree. Thekey argument is a pointer to a datum to be accessedor stored. If there is a datum in the tree equal to*key (the value pointed to bykey), a pointer to this found datumis returned. Otherwise,*key is inserted, and a pointer to it returned.Only pointers are copied, so the calling routine must store the data.Therootp argument points to a variable that points to the rootof the tree. A null value for the variable pointed to byrootpdenotes an empty tree; in this case, the variable will be setto point to the datum which will be at the root ofthe new tree.
Liketsearch(),tfind() will search for a datum in the tree, returninga pointer to it if found. However, if it is not found,tfind() will return a null pointer. The arguments fortfind() are thesame as fortsearch().
Thetdelete() function deletes a node from a binary search tree. Thearguments are the same as fortsearch(). The variable pointed tobyrootp will be changed if the deleted node was the rootof the tree.tdelete() returns a pointer to the parent of the deletednode, or a null pointer if the node is not found.
Thetwalk() function traverses a binary search tree. Theroot argument isthe root of the tree to be traversed. (Any node in atree may be used as the root for a walk below thatnode.)action is the name of a routine to be invoked at eachnode. This routine is, in turn, called with three arguments. The firstargument is the address of the node being visited. The second argumentis a value from an enumeration data type
typedef enum { preorder, postorder, endorder, leaf } VISIT;(defined in <search.h>), depending on whether this is the first, second orthird time that the node has been visited (during a depth-first, left-to-righttraversal of the tree), or whether the node is a leaf. Thethird argument is the level of the node in the tree, with theroot being level zero.
The pointers to the key and the root of the tree shouldbe of type pointer-to-element, and cast to type pointer-to-character. Similarly, although declaredas type pointer-to-character, the value returned should be cast into type pointer-to-element.
If the node is found, bothtsearch() andtfind() return a pointerto it. If not,tfind() returns a null pointer, andtsearch()returns a pointer to the inserted item.
A null pointer is returned bytsearch() if there is not enoughspace available to create a new node.
A null pointer is returned bytsearch(),tfind() andtdelete() ifrootpis a null pointer on entry.
Thetdelete() function returns a pointer to the parent of the deletednode, or a null pointer if the node is not found.
Thetwalk() function returns no value.
No errors are defined.
Theroot argument totwalk() is one level of indirection lessthan therootp arguments totsearch() andtdelete().
There are two nomenclatures used to refer to the order in whichtree nodes are visited.tsearch() uses preorder, postorder and endorder to referrespectively to visiting a node before any of its children, after itsleft child and before its right, and after both its children. The alternatenomenclature uses preorder, inorder and postorder to refer to the same visits,which could result in some confusion over the meaning of postorder.
If the calling function alters the pointer to the root, the resultsare unpredictable.
These functions safely allows concurrent access by multiple threads to disjoint data,such as overlapping subtrees or tables.
Example 1 A sample program of usingtsearch() function.
The following code reads in strings and stores structures containing a pointerto each string and a count of its length. It then walksthe tree, printing out the stored strings and their lengths in alphabeticalorder.
#include <string.h>#include <stdio.h>#include <search.h>struct node { char *string; int length;};char string_space[10000];struct node nodes[500];void *root = NULL;int node_compare(const void *node1, const void *node2) { return strcmp(((const struct node *) node1)->string, ((const struct node *) node2)->string);}void print_node(const void *node, VISIT order, int level) { if (order == preorder || order == leaf) { printf("length=%d, string=%20s\n", (*(struct node **)node)->length, (*(struct node **)node)->string); }}main(){ char *strptr = string_space; struct node *nodeptr = nodes; int i = 0; while (gets(strptr) != NULL && i++ < 500) { nodeptr->string = strptr; nodeptr->length = strlen(strptr); (void) tsearch((void *)nodeptr, &root, node_compare); strptr += nodeptr->length + 1; nodeptr++; } twalk(root, print_node);}Seeattributes(5) for descriptions of the following attributes:
|
bsearch(3C),hsearch(3C),lsearch(3C),attributes(5),standards(5)
Copyright © 2011, Oracle and/or its affiliates. All rights reserved.Legal Notices |   |