tree.c 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224
  1. /*
  2. ** tree.c
  3. ** TecCGraf - PUC-Rio
  4. */
  5. char *rcs_tree="$Id: tree.c,v 1.1 1994/07/19 21:24:17 celes Exp $";
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include "lua.h"
  9. #include "tree.h"
  10. #include "table.h"
  11. #define lua_strcmp(a,b) (a[0]<b[0]?(-1):(a[0]>b[0]?(1):strcmp(a,b)))
  12. typedef struct TreeNode
  13. {
  14. struct TreeNode *right;
  15. struct TreeNode *left;
  16. Word index;
  17. char str[1]; /* \0 byte already reserved */
  18. } TreeNode;
  19. static TreeNode *string_root = NULL;
  20. static TreeNode *constant_root = NULL;
  21. static TreeNode *variable_root = NULL;
  22. /*
  23. ** Insert a new string/constant/variable at the tree.
  24. */
  25. static char *tree_create (TreeNode **node, char *str, int *created)
  26. {
  27. if (*node == NULL)
  28. {
  29. *node = (TreeNode *) malloc (sizeof(TreeNode)+strlen(str));
  30. if (*node == NULL)
  31. lua_error ("memoria insuficiente\n");
  32. (*node)->left = (*node)->right = NULL;
  33. strcpy((*node)->str, str);
  34. (*node)->index = UNMARKED_STRING;
  35. *created = 1;
  36. return (*node)->str;
  37. }
  38. else
  39. {
  40. int c = lua_strcmp(str, (*node)->str);
  41. if (c < 0)
  42. return tree_create(&(*node)->left, str, created);
  43. else if (c > 0)
  44. return tree_create(&(*node)->right, str, created);
  45. else
  46. return (*node)->str;
  47. }
  48. }
  49. char *lua_strcreate (char *str)
  50. {
  51. int created=0;
  52. char *s = tree_create(&string_root, str, &created);
  53. if (created)
  54. {
  55. if (lua_nentity == lua_block) lua_pack ();
  56. lua_nentity++;
  57. }
  58. return s;
  59. }
  60. char *lua_constcreate (char *str)
  61. {
  62. int created;
  63. return tree_create(&constant_root, str, &created);
  64. }
  65. char *lua_varcreate (char *str)
  66. {
  67. int created;
  68. return tree_create(&variable_root, str, &created);
  69. }
  70. /*
  71. ** Free a node of the tree
  72. */
  73. static TreeNode *lua_strfree (TreeNode *parent)
  74. {
  75. if (parent->left == NULL && parent->right == NULL) /* no child */
  76. {
  77. free (parent);
  78. return NULL;
  79. }
  80. else if (parent->left == NULL) /* only right child */
  81. {
  82. TreeNode *p = parent->right;
  83. free (parent);
  84. return p;
  85. }
  86. else if (parent->right == NULL) /* only left child */
  87. {
  88. TreeNode *p = parent->left;
  89. free (parent);
  90. return p;
  91. }
  92. else /* two children */
  93. {
  94. TreeNode *p = parent, *r = parent->right;
  95. while (r->left != NULL)
  96. {
  97. p = r;
  98. r = r->left;
  99. }
  100. if (p == parent)
  101. {
  102. r->left = parent->left;
  103. parent->left = NULL;
  104. parent->right = r->right;
  105. r->right = lua_strfree(parent);
  106. }
  107. else
  108. {
  109. TreeNode *t = r->right;
  110. r->left = parent->left;
  111. r->right = parent->right;
  112. parent->left = NULL;
  113. parent->right = t;
  114. p->left = lua_strfree(parent);
  115. }
  116. return r;
  117. }
  118. }
  119. /*
  120. ** Traverse tree for garbage collection
  121. */
  122. static TreeNode *lua_travcollector (TreeNode *r)
  123. {
  124. if (r == NULL) return NULL;
  125. r->right = lua_travcollector(r->right);
  126. r->left = lua_travcollector(r->left);
  127. if (r->index == UNMARKED_STRING)
  128. {
  129. ++lua_recovered;
  130. return lua_strfree(r);
  131. }
  132. else
  133. {
  134. r->index = UNMARKED_STRING;
  135. return r;
  136. }
  137. }
  138. /*
  139. ** Garbage collection function.
  140. ** This function traverse the tree freening unindexed strings
  141. */
  142. void lua_strcollector (void)
  143. {
  144. string_root = lua_travcollector(string_root);
  145. }
  146. /*
  147. ** Return next variable.
  148. */
  149. static TreeNode *tree_next (TreeNode *node, char *str)
  150. {
  151. #if 0
  152. if (node == NULL) return NULL;
  153. if (str == NULL || lua_strcmp(str, node->str) < 0)
  154. {
  155. TreeNode *result = tree_next(node->left, str);
  156. return result == NULL ? node : result;
  157. }
  158. else
  159. {
  160. return tree_next(node->right, str);
  161. }
  162. #else
  163. if (node == NULL) return NULL;
  164. else if (str == NULL) return node;
  165. else
  166. {
  167. int c = lua_strcmp(str, node->str);
  168. if (c == 0)
  169. return node->left != NULL ? node->left : node->right;
  170. else if (c < 0)
  171. {
  172. TreeNode *result = tree_next(node->left, str);
  173. return result != NULL ? result : node->right;
  174. }
  175. else
  176. return tree_next(node->right, str);
  177. }
  178. #endif
  179. }
  180. char *lua_varnext (char *n)
  181. {
  182. TreeNode *result = tree_next(variable_root, n);
  183. return result != NULL ? result->str : NULL;
  184. }
  185. /*
  186. ** Given an id, find the string with exaustive search
  187. */
  188. static char *tree_name (TreeNode *node, Word index)
  189. {
  190. if (node == NULL) return NULL;
  191. if (node->index == index) return node->str;
  192. else
  193. {
  194. char *result = tree_name(node->left, index);
  195. return result != NULL ? result : tree_name(node->right, index);
  196. }
  197. }
  198. char *lua_varname (Word index)
  199. {
  200. return tree_name(variable_root, index);
  201. }