logo

oasis-root

Compiled tree of Oasis Linux based on own branch at <https://hacktivis.me/git/oasis/> git clone https://anongit.hacktivis.me/git/oasis-root.git

tdelete.3p (10937B)


  1. '\" et
  2. .TH TDELETE "3P" 2017 "IEEE/The Open Group" "POSIX Programmer's Manual"
  3. .\"
  4. .SH PROLOG
  5. This manual page is part of the POSIX Programmer's Manual.
  6. The Linux implementation of this interface may differ (consult
  7. the corresponding Linux manual page for details of Linux behavior),
  8. or the interface may not be implemented on Linux.
  9. .\"
  10. .SH NAME
  11. tdelete,
  12. tfind,
  13. tsearch,
  14. twalk
  15. \(em manage a binary search tree
  16. .SH SYNOPSIS
  17. .LP
  18. .nf
  19. #include <search.h>
  20. .P
  21. void *tdelete(const void *restrict \fIkey\fP, void **restrict \fIrootp\fP,
  22. int(*\fIcompar\fP)(const void *, const void *));
  23. void *tfind(const void *\fIkey\fP, void *const *\fIrootp\fP,
  24. int(*\fIcompar\fP)(const void *, const void *));
  25. void *tsearch(const void *\fIkey\fP, void **\fIrootp\fP,
  26. int (*\fIcompar\fP)(const void *, const void *));
  27. void twalk(const void *\fIroot\fP,
  28. void (*\fIaction\fP)(const void *, VISIT, int));
  29. .fi
  30. .SH DESCRIPTION
  31. The
  32. \fItdelete\fR(),
  33. \fItfind\fR(),
  34. \fItsearch\fR(),
  35. and
  36. \fItwalk\fR()
  37. functions manipulate binary search trees. Comparisons are made with a
  38. user-supplied routine, the address of which is passed as the
  39. .IR compar
  40. argument. This routine is called with two arguments, which are the
  41. pointers to the elements being compared. The application shall ensure
  42. that the user-supplied routine returns an integer less than, equal to,
  43. or greater than 0, according to whether the first argument is to be
  44. considered less than, equal to, or greater than the second argument.
  45. The comparison function need not compare every byte, so arbitrary data
  46. may be contained in the elements in addition to the values being
  47. compared.
  48. .P
  49. The
  50. \fItsearch\fR()
  51. function shall build and access the tree. The
  52. .IR key
  53. argument is a pointer to an element to be accessed or stored. If there
  54. is a node in the tree whose element is equal to the value pointed to by
  55. .IR key ,
  56. a pointer to this found node shall be returned. Otherwise, the value
  57. pointed to by
  58. .IR key
  59. shall be inserted (that is, a new node is created and the value of
  60. .IR key
  61. is copied to this node), and a pointer to this node returned. Only
  62. pointers are copied, so the application shall ensure that the calling
  63. routine stores the data. The
  64. .IR rootp
  65. argument points to a variable that points to the root node of the
  66. tree. A null pointer value for the variable pointed to by
  67. .IR rootp
  68. denotes an empty tree; in this case, the variable shall be set to point
  69. to the node which shall be at the root of the new tree.
  70. .P
  71. Like
  72. \fItsearch\fR(),
  73. \fItfind\fR()
  74. shall search for a node in the tree, returning a pointer to it if found.
  75. However, if it is not found,
  76. \fItfind\fR()
  77. shall return a null pointer. The arguments for
  78. \fItfind\fR()
  79. are the same as for
  80. \fItsearch\fR().
  81. .P
  82. The
  83. \fItdelete\fR()
  84. function shall delete a node from a binary search tree. The arguments
  85. are the same as for
  86. \fItsearch\fR().
  87. The variable pointed to by
  88. .IR rootp
  89. shall be changed if the deleted node was the root of the tree.
  90. If the deleted node was the root of the tree and had no children, the
  91. variable pointed to by
  92. .IR rootp
  93. shall be set to a null pointer. The
  94. \fItdelete\fR()
  95. function shall return a pointer to the parent of the deleted node, or
  96. an unspecified non-null pointer if the deleted node was the root node,
  97. or a null pointer if the node is not found.
  98. .P
  99. If
  100. \fItsearch\fR()
  101. adds an element to a tree, or
  102. \fItdelete\fR()
  103. successfully deletes an element from a tree, the concurrent use of
  104. that tree in another thread, or use of pointers produced by a previous
  105. call to
  106. \fItfind\fR()
  107. or
  108. \fItsearch\fR(),
  109. produces undefined results.
  110. .P
  111. The
  112. \fItwalk\fR()
  113. function shall traverse a binary search tree. The
  114. .IR root
  115. argument is a pointer to the root node of the tree to be traversed.
  116. (Any node in a tree may be used as the root for a walk below that
  117. node.) The argument
  118. .IR action
  119. is the name of a routine to be invoked at each node. This routine is,
  120. in turn, called with three arguments. The first argument shall be the
  121. address of the node being visited. The structure pointed to by this
  122. argument is unspecified and shall not be modified by the application,
  123. but it shall be possible to cast a pointer-to-node into a
  124. pointer-to-pointer-to-element to access the element stored in the node.
  125. The second argument shall be a value from an enumeration data type:
  126. .sp
  127. .RS 4
  128. .nf
  129. typedef enum { preorder, postorder, endorder, leaf } VISIT;
  130. .fi
  131. .P
  132. .RE
  133. .P
  134. (defined in
  135. .IR <search.h> ),
  136. depending on whether this is the first, second, or third time that the
  137. node is visited (during a depth-first, left-to-right traversal of the
  138. tree), or whether the node is a leaf. The third argument shall be
  139. the level of the node in the tree, with the root being level 0.
  140. .P
  141. If the calling function alters the pointer to the root, the result is
  142. undefined.
  143. .P
  144. If the functions pointed to by
  145. .IR action
  146. or
  147. .IR compar
  148. (for any of these binary search functions) change the tree, the results
  149. are undefined.
  150. .P
  151. These functions are thread-safe only as long as multiple threads
  152. do not access the same tree.
  153. .SH "RETURN VALUE"
  154. If the node is found, both
  155. \fItsearch\fR()
  156. and
  157. \fItfind\fR()
  158. shall return a pointer to it. If not,
  159. \fItfind\fR()
  160. shall return a null pointer, and
  161. \fItsearch\fR()
  162. shall return a pointer to the inserted item.
  163. .P
  164. A null pointer shall be returned by
  165. \fItsearch\fR()
  166. if there is not enough space available to create a new node.
  167. .P
  168. A null pointer shall be returned by
  169. \fItdelete\fR(),
  170. \fItfind\fR(),
  171. and
  172. \fItsearch\fR()
  173. if
  174. .IR rootp
  175. is a null pointer on entry.
  176. .P
  177. The
  178. \fItdelete\fR()
  179. function shall return a pointer to the parent of the deleted node, or
  180. an unspecified non-null pointer if the deleted node was the root node,
  181. or a null pointer if the node is not found.
  182. .P
  183. The
  184. \fItwalk\fR()
  185. function shall not return a value.
  186. .SH ERRORS
  187. No errors are defined.
  188. .LP
  189. .IR "The following sections are informative."
  190. .SH "EXAMPLES"
  191. The following code reads in strings and stores structures containing a
  192. pointer to each string and a count of its length. It then walks the
  193. tree, printing out the stored strings and their lengths in alphabetical
  194. order.
  195. .sp
  196. .RS 4
  197. .nf
  198. #include <limits.h>
  199. #include <search.h>
  200. #include <stdlib.h>
  201. #include <string.h>
  202. #include <stdio.h>
  203. .P
  204. struct element { /* Pointers to these are stored in the tree. */
  205. int count;
  206. char string[];
  207. };
  208. .P
  209. void *root = NULL; /* This points to the root. */
  210. .P
  211. int main(void)
  212. {
  213. char str[_POSIX2_LINE_MAX+1];
  214. int length = 0;
  215. struct element *elementptr;
  216. void *node;
  217. void print_node(const void *, VISIT, int);
  218. int node_compare(const void *, const void *),
  219. delete_root(const void *, const void *);
  220. .P
  221. while (fgets(str, sizeof(str), stdin)) {
  222. /* Set element. */
  223. length = strlen(str);
  224. if (str[length-1] == \(aq\en\(aq)
  225. str[--length] = \(aq\e0\(aq;
  226. elementptr = malloc(sizeof(struct element) + length + 1);
  227. strcpy(elementptr->string, str);
  228. elementptr->count = 1;
  229. /* Put element into the tree. */
  230. node = tsearch((void *)elementptr, &root, node_compare);
  231. if (node == NULL) {
  232. fprintf(stderr,
  233. "tsearch: Not enough space available\en");
  234. exit(EXIT_FAILURE);
  235. }
  236. else if (*(struct element **)node != elementptr) {
  237. /* A node containing the element already exists */
  238. (*(struct element **)node)->count++;
  239. free(elementptr);
  240. }
  241. }
  242. twalk(root, print_node);
  243. .P
  244. /* Delete all nodes in the tree */
  245. while (root != NULL) {
  246. elementptr = *(struct element **)root;
  247. printf("deleting node: string = %s, count = %d\en",
  248. elementptr->string,
  249. elementptr->count);
  250. tdelete((void *)elementptr, &root, delete_root);
  251. free(elementptr);
  252. }
  253. .P
  254. return 0;
  255. }
  256. .P
  257. /*
  258. * This routine compares two nodes, based on an
  259. * alphabetical ordering of the string field.
  260. */
  261. int
  262. node_compare(const void *node1, const void *node2)
  263. {
  264. return strcmp(((const struct element *) node1)->string,
  265. ((const struct element *) node2)->string);
  266. }
  267. .P
  268. /*
  269. * This comparison routine can be used with tdelete()
  270. * when explicitly deleting a root node, as no comparison
  271. * is necessary.
  272. */
  273. int
  274. delete_root(const void *node1, const void *node2)
  275. {
  276. return 0;
  277. }
  278. .P
  279. /*
  280. * This routine prints out a node, the second time
  281. * twalk encounters it or if it is a leaf.
  282. */
  283. void
  284. print_node(const void *ptr, VISIT order, int level)
  285. {
  286. const struct element *p = *(const struct element **) ptr;
  287. .P
  288. if (order == postorder || order == leaf) {
  289. (void) printf("string = %s, count = %d\en",
  290. p->string, p->count);
  291. }
  292. }
  293. .fi
  294. .P
  295. .RE
  296. .SH "APPLICATION USAGE"
  297. The
  298. .IR root
  299. argument to
  300. \fItwalk\fR()
  301. is one level of indirection less than the
  302. .IR rootp
  303. arguments to
  304. \fItdelete\fR()
  305. and
  306. \fItsearch\fR().
  307. .P
  308. There are two nomenclatures used to refer to the order in which tree
  309. nodes are visited. The
  310. \fItwalk\fR()
  311. function uses \fBpreorder\fP, \fBpostorder\fP, and \fBendorder\fP to
  312. refer respectively to visiting a node before any of its children, after
  313. its left child and before its right, and after both its children. The
  314. alternative nomenclature uses \fBpreorder\fP, \fBinorder\fP, and
  315. \fBpostorder\fP to refer to the same visits, which could result in some
  316. confusion over the meaning of \fBpostorder\fP.
  317. .P
  318. Since the return value of
  319. \fItdelete\fR()
  320. is an unspecified non-null pointer in the case that the root of the tree
  321. has been deleted, applications should only use the return value of
  322. \fItdelete\fR()
  323. as indication of success or failure and should not assume it can be
  324. dereferenced. Some implementations in this case will return a pointer to
  325. the new root of the tree (or to an empty tree if the deleted root node
  326. was the only node in the tree); other implementations return arbitrary
  327. non-null pointers.
  328. .SH RATIONALE
  329. None.
  330. .SH "FUTURE DIRECTIONS"
  331. None.
  332. .SH "SEE ALSO"
  333. .IR "\fIhcreate\fR\^(\|)",
  334. .IR "\fIlsearch\fR\^(\|)"
  335. .P
  336. The Base Definitions volume of POSIX.1\(hy2017,
  337. .IR "\fB<search.h>\fP"
  338. .\"
  339. .SH COPYRIGHT
  340. Portions of this text are reprinted and reproduced in electronic form
  341. from IEEE Std 1003.1-2017, Standard for Information Technology
  342. -- Portable Operating System Interface (POSIX), The Open Group Base
  343. Specifications Issue 7, 2018 Edition,
  344. Copyright (C) 2018 by the Institute of
  345. Electrical and Electronics Engineers, Inc and The Open Group.
  346. In the event of any discrepancy between this version and the original IEEE and
  347. The Open Group Standard, the original IEEE and The Open Group Standard
  348. is the referee document. The original Standard can be obtained online at
  349. http://www.opengroup.org/unix/online.html .
  350. .PP
  351. Any typographical or formatting errors that appear
  352. in this page are most likely
  353. to have been introduced during the conversion of the source files to
  354. man page format. To report such errors, see
  355. https://www.kernel.org/doc/man-pages/reporting_bugs.html .