summaryrefslogtreecommitdiff
path: root/tree.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>1994-11-14 19:40:14 -0200
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>1994-11-14 19:40:14 -0200
commit86b35cf4f6a824880239069d0afe282e95806aaa (patch)
tree78352c354fc6befe1af900606cb84b23a40235e0 /tree.c
parent3b7a36653b5da227502ec5a3c677b6a351af67be (diff)
downloadlua-86b35cf4f6a824880239069d0afe282e95806aaa.tar.gz
lua-86b35cf4f6a824880239069d0afe282e95806aaa.tar.bz2
lua-86b35cf4f6a824880239069d0afe282e95806aaa.zip
unification of symbol tree and constant tree
Diffstat (limited to 'tree.c')
-rw-r--r--tree.c69
1 files changed, 11 insertions, 58 deletions
diff --git a/tree.c b/tree.c
index ae5a19de..bca29994 100644
--- a/tree.c
+++ b/tree.c
@@ -3,7 +3,7 @@
3** TecCGraf - PUC-Rio 3** TecCGraf - PUC-Rio
4*/ 4*/
5 5
6char *rcs_tree="$Id: tree.c,v 1.2 1994/10/18 17:36:11 celes Exp roberto $"; 6char *rcs_tree="$Id: tree.c,v 1.3 1994/11/10 20:41:37 roberto Exp roberto $";
7 7
8 8
9#include <stdlib.h> 9#include <stdlib.h>
@@ -17,22 +17,13 @@ char *rcs_tree="$Id: tree.c,v 1.2 1994/10/18 17:36:11 celes Exp roberto $";
17#define lua_strcmp(a,b) (a[0]<b[0]?(-1):(a[0]>b[0]?(1):strcmp(a,b))) 17#define lua_strcmp(a,b) (a[0]<b[0]?(-1):(a[0]>b[0]?(1):strcmp(a,b)))
18 18
19 19
20typedef struct TreeNode
21{
22 struct TreeNode *right;
23 struct TreeNode *left;
24 Word index;
25 char str[1]; /* \0 byte already reserved */
26} TreeNode;
27
28static TreeNode *string_root = NULL; 20static TreeNode *string_root = NULL;
29static TreeNode *constant_root = NULL; 21static TreeNode *constant_root = NULL;
30static TreeNode *variable_root = NULL;
31 22
32/* 23/*
33** Insert a new string/constant/variable at the tree. 24** Insert a new string/constant/variable at the tree.
34*/ 25*/
35static char *tree_create (TreeNode **node, char *str, int *created) 26static TreeNode *tree_create (TreeNode **node, char *str, int *created)
36{ 27{
37 if (*node == NULL) 28 if (*node == NULL)
38 { 29 {
@@ -41,9 +32,9 @@ static char *tree_create (TreeNode **node, char *str, int *created)
41 lua_error("not enough memory"); 32 lua_error("not enough memory");
42 (*node)->left = (*node)->right = NULL; 33 (*node)->left = (*node)->right = NULL;
43 strcpy((*node)->str, str); 34 strcpy((*node)->str, str);
44 (*node)->index = UNMARKED_STRING; 35 (*node)->varindex = (*node)->constindex = UNMARKED_STRING;
45 *created = 1; 36 *created = 1;
46 return (*node)->str; 37 return *node;
47 } 38 }
48 else 39 else
49 { 40 {
@@ -53,35 +44,28 @@ static char *tree_create (TreeNode **node, char *str, int *created)
53 else if (c > 0) 44 else if (c > 0)
54 return tree_create(&(*node)->right, str, created); 45 return tree_create(&(*node)->right, str, created);
55 else 46 else
56 return (*node)->str; 47 return *node;
57 } 48 }
58} 49}
59 50
60char *lua_strcreate (char *str) 51char *lua_strcreate (char *str)
61{ 52{
62 int created=0; 53 int created=0;
63 char *s = tree_create(&string_root, str, &created); 54 TreeNode *t = tree_create(&string_root, str, &created);
64 if (created) 55 if (created)
65 { 56 {
66 if (lua_nentity == lua_block) lua_pack (); 57 if (lua_nentity == lua_block) lua_pack ();
67 lua_nentity++; 58 lua_nentity++;
68 } 59 }
69 return s; 60 return t->str;
70} 61}
71 62
72char *lua_constcreate (char *str) 63TreeNode *lua_constcreate (char *str)
73{ 64{
74 int created; 65 int created;
75 return tree_create(&constant_root, str, &created); 66 return tree_create(&constant_root, str, &created);
76} 67}
77 68
78char *lua_varcreate (char *str)
79{
80 int created;
81 return tree_create(&variable_root, str, &created);
82}
83
84
85 69
86/* 70/*
87** Free a node of the tree 71** Free a node of the tree
@@ -141,14 +125,14 @@ static TreeNode *lua_travcollector (TreeNode *r)
141 if (r == NULL) return NULL; 125 if (r == NULL) return NULL;
142 r->right = lua_travcollector(r->right); 126 r->right = lua_travcollector(r->right);
143 r->left = lua_travcollector(r->left); 127 r->left = lua_travcollector(r->left);
144 if (r->index == UNMARKED_STRING) 128 if (r->constindex == UNMARKED_STRING)
145 { 129 {
146 ++lua_recovered; 130 ++lua_recovered;
147 return lua_strfree(r); 131 return lua_strfree(r);
148 } 132 }
149 else 133 else
150 { 134 {
151 r->index = UNMARKED_STRING; 135 r->constindex = UNMARKED_STRING;
152 return r; 136 return r;
153 } 137 }
154} 138}
@@ -168,18 +152,6 @@ void lua_strcollector (void)
168*/ 152*/
169static TreeNode *tree_next (TreeNode *node, char *str) 153static TreeNode *tree_next (TreeNode *node, char *str)
170{ 154{
171#if 0
172 if (node == NULL) return NULL;
173 if (str == NULL || lua_strcmp(str, node->str) < 0)
174 {
175 TreeNode *result = tree_next(node->left, str);
176 return result == NULL ? node : result;
177 }
178 else
179 {
180 return tree_next(node->right, str);
181 }
182#else
183 if (node == NULL) return NULL; 155 if (node == NULL) return NULL;
184 else if (str == NULL) return node; 156 else if (str == NULL) return node;
185 else 157 else
@@ -195,30 +167,11 @@ static TreeNode *tree_next (TreeNode *node, char *str)
195 else 167 else
196 return tree_next(node->right, str); 168 return tree_next(node->right, str);
197 } 169 }
198#endif
199} 170}
200 171
201char *lua_varnext (char *n) 172char *lua_varnext (char *n)
202{ 173{
203 TreeNode *result = tree_next(variable_root, n); 174 TreeNode *result = tree_next(constant_root, n);
204 return result != NULL ? result->str : NULL; 175 return result != NULL ? result->str : NULL;
205} 176}
206 177
207
208/*
209** Given an id, find the string with exaustive search
210*/
211static char *tree_name (TreeNode *node, Word index)
212{
213 if (node == NULL) return NULL;
214 if (node->index == index) return node->str;
215 else
216 {
217 char *result = tree_name(node->left, index);
218 return result != NULL ? result : tree_name(node->right, index);
219 }
220}
221char *lua_varname (Word index)
222{
223 return tree_name(variable_root, index);
224}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-17 00:01:22 +0000