1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
/*
** tree.c
** TecCGraf - PUC-Rio
*/
char *rcs_tree="$Id: tree.c,v 1.13 1995/01/12 14:19:04 roberto Exp roberto $";
#include <string.h>
#include "mem.h"
#include "lua.h"
#include "tree.h"
#include "table.h"
#define lua_strcmp(a,b) (a[0]<b[0]?(-1):(a[0]>b[0]?(1):strcmp(a,b)))
typedef struct StringNode {
struct StringNode *next;
TaggedString ts;
} StringNode;
static StringNode *string_root = NULL;
static TreeNode *constant_root = NULL;
/*
** Insert a new constant/variable at the tree.
*/
static TreeNode *tree_create (TreeNode **node, char *str)
{
if (*node == NULL)
{
*node = (TreeNode *) luaI_malloc(sizeof(TreeNode)+strlen(str));
(*node)->left = (*node)->right = NULL;
strcpy((*node)->ts.str, str);
(*node)->ts.marked = 0;
(*node)->ts.hash = 0;
(*node)->varindex = (*node)->constindex = NOT_USED;
return *node;
}
else
{
int c = lua_strcmp(str, (*node)->ts.str);
if (c < 0)
return tree_create(&(*node)->left, str);
else if (c > 0)
return tree_create(&(*node)->right, str);
else
return *node;
}
}
TaggedString *lua_createstring (char *str)
{
StringNode *newString;
if (str == NULL) return NULL;
lua_pack();
newString = (StringNode *)luaI_malloc(sizeof(StringNode)+strlen(str));
newString->ts.marked = 0;
newString->ts.hash = 0;
strcpy(newString->ts.str, str);
newString->next = string_root;
string_root = newString;
return &(newString->ts);
}
TreeNode *lua_constcreate (char *str)
{
return tree_create(&constant_root, str);
}
/*
** Garbage collection function.
** This function traverse the string list freeing unindexed strings
*/
Long lua_strcollector (void)
{
StringNode *curr = string_root, *prev = NULL;
Long counter = 0;
while (curr)
{
StringNode *next = curr->next;
if (!curr->ts.marked)
{
if (prev == NULL) string_root = next;
else prev->next = next;
luaI_free(curr);
++counter;
}
else
{
curr->ts.marked = 0;
prev = curr;
}
curr = next;
}
return counter;
}
/*
** Traverse the constant tree looking for a specific symbol number
*/
static TreeNode *nodebysymbol (TreeNode *root, Word symbol)
{
TreeNode *t;
if (root == NULL) return NULL;
if (root->varindex == symbol) return root;
t = nodebysymbol(root->left, symbol);
if (t) return t;
return nodebysymbol(root->right, symbol);
}
TreeNode *luaI_nodebysymbol (Word symbol)
{
return nodebysymbol(constant_root, symbol);
}
|
