_tsearch.c 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223
  1. /* Copyright (C) 1994 Free Software Foundation, Inc.
  2. This file is part of the GNU C Library.
  3. The GNU C Library is free software; you can redistribute it and/or
  4. modify it under the terms of the GNU Library General Public License as
  5. published by the Free Software Foundation; either version 2 of the
  6. License, or (at your option) any later version.
  7. The GNU C Library is distributed in the hope that it will be useful,
  8. but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  10. Library General Public License for more details.
  11. You should have received a copy of the GNU Library General Public
  12. License along with the GNU C Library; see the file COPYING.LIB. If
  13. not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  14. Cambridge, MA 02139, USA. */
  15. /*
  16. * Tree search generalized from Knuth (6.2.2) Algorithm T just like
  17. * the AT&T man page says.
  18. *
  19. * The node_t structure is for internal use only, lint doesn't grok it.
  20. *
  21. * Written by reading the System V Interface Definition, not the code.
  22. *
  23. * Totally public domain.
  24. */
  25. /*LINTLIBRARY*/
  26. #include <search.h>
  27. #include <stdlib.h>
  28. /* This routine is not very bad. It makes many assumptions about
  29. * the compiler. It assumpts that the first field in node must be
  30. * the "key" field, which points to the datum. It is a very trick
  31. * stuff. H.J.
  32. */
  33. typedef struct node_t
  34. {
  35. void *key;
  36. struct node_t *left, *right;
  37. } node;
  38. #ifdef L_tsearch
  39. /* find or insert datum into search tree.
  40. char *key; key to be located
  41. register node **rootp; address of tree root
  42. int (*compar)(); ordering function
  43. */
  44. /* libc_hidden_proto(tsearch) */
  45. void *tsearch(__const void *key, void **vrootp, __compar_fn_t compar)
  46. {
  47. register node *q;
  48. register node **rootp = (node **) vrootp;
  49. if (rootp == (struct node_t **)0)
  50. return ((struct node_t *)0);
  51. while (*rootp != (struct node_t *)0) /* Knuth's T1: */
  52. {
  53. int r;
  54. if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */
  55. return (*rootp); /* we found it! */
  56. rootp = (r < 0) ?
  57. &(*rootp)->left : /* T3: follow left branch */
  58. &(*rootp)->right; /* T4: follow right branch */
  59. }
  60. q = (node *) malloc(sizeof(node)); /* T5: key not found */
  61. if (q != (struct node_t *)0) /* make new node */
  62. {
  63. *rootp = q; /* link new node to old */
  64. q->key = (void *)key; /* initialize new node */
  65. q->left = q->right = (struct node_t *)0;
  66. }
  67. return (q);
  68. }
  69. libc_hidden_def(tsearch)
  70. #endif
  71. #ifdef L_tfind
  72. /* libc_hidden_proto(tfind) */
  73. void *tfind(__const void *key, void * __const *vrootp, __compar_fn_t compar)
  74. {
  75. register node **rootp = (node **) vrootp;
  76. if (rootp == (struct node_t **)0)
  77. return ((struct node_t *)0);
  78. while (*rootp != (struct node_t *)0) /* Knuth's T1: */
  79. {
  80. int r;
  81. if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */
  82. return (*rootp); /* we found it! */
  83. rootp = (r < 0) ?
  84. &(*rootp)->left : /* T3: follow left branch */
  85. &(*rootp)->right; /* T4: follow right branch */
  86. }
  87. return NULL;
  88. }
  89. libc_hidden_def(tfind)
  90. #endif
  91. #ifdef L_tdelete
  92. /* delete node with given key
  93. char *key; key to be deleted
  94. register node **rootp; address of the root of tree
  95. int (*compar)(); comparison function
  96. */
  97. void *tdelete(__const void *key, void ** vrootp, __compar_fn_t compar)
  98. {
  99. node *p;
  100. register node *q;
  101. register node *r;
  102. int cmp;
  103. register node **rootp = (node **) vrootp;
  104. if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0)
  105. return ((struct node_t *)0);
  106. while ((cmp = (*compar)(key, (*rootp)->key)) != 0)
  107. {
  108. p = *rootp;
  109. rootp = (cmp < 0) ?
  110. &(*rootp)->left : /* follow left branch */
  111. &(*rootp)->right; /* follow right branch */
  112. if (*rootp == (struct node_t *)0)
  113. return ((struct node_t *)0); /* key not found */
  114. }
  115. r = (*rootp)->right; /* D1: */
  116. if ((q = (*rootp)->left) == (struct node_t *)0) /* Left (struct node_t *)0? */
  117. q = r;
  118. else if (r != (struct node_t *)0) /* Right link is null? */
  119. {
  120. if (r->left == (struct node_t *)0) /* D2: Find successor */
  121. {
  122. r->left = q;
  123. q = r;
  124. }
  125. else
  126. { /* D3: Find (struct node_t *)0 link */
  127. for (q = r->left; q->left != (struct node_t *)0; q = r->left)
  128. r = q;
  129. r->left = q->right;
  130. q->left = (*rootp)->left;
  131. q->right = (*rootp)->right;
  132. }
  133. }
  134. free((struct node_t *) *rootp); /* D4: Free node */
  135. *rootp = q; /* link parent to new node */
  136. return(p);
  137. }
  138. #endif
  139. #ifdef L_twalk
  140. /* Walk the nodes of a tree
  141. register node *root; Root of the tree to be walked
  142. register void (*action)(); Function to be called at each node
  143. register int level;
  144. */
  145. static void trecurse(__const void *vroot, __action_fn_t action, int level)
  146. {
  147. register node *root = (node *) vroot;
  148. if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
  149. (*action)(root, leaf, level);
  150. else
  151. {
  152. (*action)(root, preorder, level);
  153. if (root->left != (struct node_t *)0)
  154. trecurse(root->left, action, level + 1);
  155. (*action)(root, postorder, level);
  156. if (root->right != (struct node_t *)0)
  157. trecurse(root->right, action, level + 1);
  158. (*action)(root, endorder, level);
  159. }
  160. }
  161. /* void twalk(root, action) Walk the nodes of a tree
  162. node *root; Root of the tree to be walked
  163. void (*action)(); Function to be called at each node
  164. PTR
  165. */
  166. void twalk(__const void *vroot, __action_fn_t action)
  167. {
  168. register __const node *root = (node *) vroot;
  169. if (root != (node *)0 && action != (__action_fn_t) 0)
  170. trecurse(root, action, 0);
  171. }
  172. #endif
  173. #ifdef __USE_GNU
  174. #ifdef L_tdestroy
  175. /* The standardized functions miss an important functionality: the
  176. tree cannot be removed easily. We provide a function to do this. */
  177. static void
  178. internal_function
  179. tdestroy_recurse (node *root, __free_fn_t freefct)
  180. {
  181. if (root->left != NULL)
  182. tdestroy_recurse (root->left, freefct);
  183. if (root->right != NULL)
  184. tdestroy_recurse (root->right, freefct);
  185. (*freefct) ((void *) root->key);
  186. /* Free the node itself. */
  187. free (root);
  188. }
  189. /* libc_hidden_proto(tdestroy) */
  190. void tdestroy (void *vroot, __free_fn_t freefct)
  191. {
  192. node *root = (node *) vroot;
  193. if (root != NULL) {
  194. tdestroy_recurse (root, freefct);
  195. }
  196. }
  197. libc_hidden_def(tdestroy)
  198. #endif
  199. #endif
  200. /* tsearch.c ends here */