1 /* HASHING TABLE */
2
3 #include <stdlib.h>
4 #include <stdio.h>
5 #include <string.h>
6
7 #include "asm.h"
8 #include "expression.h"
9
10 #define TABLE_SIZE (1<<13) /* size of hash table (must be power of 2) */
11 #define MAGICKA_KONSTANTA 13 /* proof MJ's magic constant */
12
13 struct info{
14 int address; /* label address/value */
15 char *pointer; /* pointer to a label name */
16 unsigned lineno; /* defining line no */
17 char *expr; /* to evaluate equations */
18 bool flag; /* to detect cycles in evaluation */
19 bool uniq; /* to allow redefinitions */
20 };
21
22 struct table_type{ /* HASHING TABLE */
23 unsigned char count;
24 struct info *element;
25 };
26
27 static struct info *last_ele, *just_ele; /* last for write, just for read-access */
28 static struct table_type entry[TABLE_SIZE];
29 static unsigned counter;
30
31
table_entries(void)32 unsigned table_entries(void)
33 {
34 return counter;
35 }
36
37
38 /* hashing function */
39
40 static unsigned
hashl(char * slovo,unsigned len)41 hashl(char *slovo, unsigned len)
42 {
43 unsigned b=0;
44
45 while(len--)
46 {
47 b+=slovo[len];
48 b*=MAGICKA_KONSTANTA;
49 }
50 return b&(TABLE_SIZE-1);
51 }
52
53
54 static unsigned
hash(char * slovo)55 hash(char *slovo)
56 {
57 return hashl(slovo,strlen(slovo));
58 }
59
60
next_table_entry(char ** key,int * value,unsigned * lineno)61 int next_table_entry(char **key, int *value, unsigned *lineno)
62 {
63 static unsigned a=0, c=0;
64 while (c >= entry[a].count)
65 { c=0; if (++a == TABLE_SIZE) return a=0; }
66 *key=entry[a].element[c].pointer;
67 *value=entry[a].element[c].address;
68 *lineno=entry[a].element[c].lineno;
69 c++;
70 return 1;
71 }
72
73
74 /* adds item to hash table */
75 /* returns nullpointer in case of error else the table address of label */
76
77 int
add_to_table(char * key,int value,unsigned lineno,bool copy)78 add_to_table(char *key,int value,unsigned lineno, bool copy)
79 {
80 unsigned a,c;
81 a=hash(key);
82 c=entry[a].count;
83 if (!(c&c-1))
84 { entry[a].element=realloc(entry[a].element,(2*c+!c)*sizeof(struct info));
85 if (!entry[a].element)return 0; }
86 if (copy)
87 { unsigned len=strlen(key);
88 char *temp= malloc(len+1);
89 if (!temp) return 0;
90 memcpy(temp,key,len);
91 temp[len]=0;
92 entry[a].element[c].pointer=temp;
93 }
94 else
95 entry[a].element[c].pointer=key;
96 last_ele= &entry[a].element[c];
97 last_ele->address=value;
98 last_ele->lineno=lineno;
99 last_ele->expr= NULL;
100 last_ele->uniq= 1;
101 counter++;
102 if (!++entry[a].count)
103 {fprintf(stderr,"Error: internal hash counter overflow\n"); return 0;}
104 return 1;
105 }
106
107
update_last_added_entry(int value,char * txt,bool unique)108 void update_last_added_entry(int value, char *txt, bool unique)
109 {
110 last_ele->address=value;
111 last_ele->expr=txt;
112 last_ele->flag=0;
113 last_ele->uniq=unique;
114 }
115
116 /* tests if label is in table, returns 1 or 0 */
117 /* refresh global variable last_ele */
118
119 bool
reaccess_label(char * key,unsigned lineno)120 reaccess_label(char *key, unsigned lineno)
121 {
122 int a,b;
123
124 a=hash(key);
125 if (!entry[a].count) return 0;
126 for (b=0;b<entry[a].count;b++)
127 if (!strcmp(key,entry[a].element[b].pointer) &&
128 (!lineno || entry[a].element[b].lineno == lineno))
129 { last_ele= &entry[a].element[b];
130 return 1;
131 }
132 return 0;
133 }
134
135
136 /* tests if label is in table, returns 1 or 0 */
137 /* stores address of label in *value if it is in table and value!=0 */
138
139 int
is_in_table(char * key,unsigned len,int * value,unsigned lineno)140 is_in_table(char *key, unsigned len, int *value, unsigned lineno)
141 {
142 int a,b,c;
143
144 /* if not in table we need address in first pass to check JR distance */
145 /* but for EQU we need its true value for possible range check later */
146 a=len?hashl(key,len):hash(key);
147 if (!entry[a].count) return 0;
148 c= -1;
149 for (b=0;b<entry[a].count;b++)
150 if (len && !strncmp(key,entry[a].element[b].pointer,len) ||
151 !len && !strcmp(key,entry[a].element[b].pointer) )
152 { if (!entry[a].element[b].uniq && lineno &&
153 entry[a].element[b].lineno > lineno)
154 break;
155 c=b;
156 if (entry[a].element[b].uniq || !entry[a].element[b].lineno || !lineno)
157 break;
158 }
159 if (c < 0) return 0;
160 b=c;
161 just_ele= &entry[a].element[b];
162 if (value)
163 { if (!just_ele->expr)
164 *value=just_ele->address;
165 else if (compile_pass() != 1)
166 { if (just_ele->flag&1)
167 return 0;
168 just_ele->flag |= 1;
169 if (parse_expr(just_ele->expr, value, lineno))
170 return 0;
171 just_ele= &entry[a].element[b];
172 just_ele->flag &= ~1;
173 just_ele->address= *value;
174 free(just_ele->expr);
175 just_ele->expr=NULL;
176 }
177 else
178 return 0;
179 }
180 return 1;
181 }
182
183
184 bool
last_label_reusable(void)185 last_label_reusable(void)
186 {
187 return !just_ele->uniq;
188 }
189
190
191 /* initializes hash table */
192
193 void
hash_table_init(void)194 hash_table_init(void)
195 {
196 int a;
197
198 for (a=0;a<TABLE_SIZE;a++)
199 {
200 entry[a].count=0;
201 entry[a].element=NULL;
202 }
203 counter=0;
204 }
205
206
207 /* removes hash table from memory */
208
209 void
free_hash_table(void)210 free_hash_table(void)
211 {
212 int a,b;
213 for (a=0;a<TABLE_SIZE;a++)
214 {
215 for (b=0;b<entry[a].count;b++)
216 { free(entry[a].element[b].pointer);
217 free(entry[a].element[b].expr);
218 }
219 free(entry[a].element);
220 }
221 }
222