1 // Copyright (C) 1999-2012 Core Technologies.
2 //
3 // This file is part of tpasm.
4 //
5 // tpasm is free software; you can redistribute it and/or modify
6 // it under the terms of the tpasm LICENSE AGREEMENT.
7 //
8 // tpasm is distributed in the hope that it will be useful,
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 // tpasm LICENSE AGREEMENT for more details.
12 //
13 // You should have received a copy of the tpasm LICENSE AGREEMENT
14 // along with tpasm; see the file "LICENSE.TXT".
15
16
17 // Low level symbol table handling
18
19 #include "include.h"
20
21 #define ST_MAX_HASH_TABLE_BITS 10 // maximum number of bits that will be used for a hash table lookup
22
23 struct SYM_TABLE_NODE
24 {
25 SYM_TABLE_NODE
26 *next,
27 *prev,
28 *hashNext,
29 *hashPrev;
30 void
31 *data;
32 unsigned int
33 hashValue; // value that the key below hashes to
34 char
35 name[1]; // variable length array which contains the name of the symbol
36 };
37
38 struct SYM_TABLE
39 {
40 SYM_TABLE_NODE
41 *first, // linearly linked table
42 *last;
43 unsigned int
44 hashTableBits; // tells how many bits of the hash value are used to index the hash list (also implies the size of the hash list)
45 SYM_TABLE_NODE
46 *hashList[1]; // variable length hash table
47 };
48
STHash(const char * name)49 static unsigned int STHash(const char *name)
50 // Return the full hash value for the given name.
51 {
52 unsigned int
53 hash;
54 unsigned int
55 count;
56 unsigned char
57 c;
58
59 hash=0;
60 for(count=0;(c=name[count]);count++)
61 {
62 c=tolower(c); // make hash case-insensitive so we can search either way
63 hash^=1<<(c&0x0F);
64 hash^=((c>>4)&0x0F)<<(count&0x07);
65 }
66 return(hash);
67 }
68
STCompNames(const char * name1,const char * name2)69 static inline bool STCompNames(const char *name1,const char *name2)
70 // Compares the given names and returns true if they are the same.
71 {
72 return(strcmp(name1,name2)==0);
73 }
74
STCompNamesNoCase(const char * name1,const char * name2)75 static inline bool STCompNamesNoCase(const char *name1,const char *name2)
76 // Compares the given names and returns true if they are the same.
77 {
78 return(strcasecmp(name1,name2)==0);
79 }
80
STFindNode(SYM_TABLE * table,const char * name)81 SYM_TABLE_NODE *STFindNode(SYM_TABLE *table,const char *name)
82 // Find the node with the given name.
83 // return NULL if none could be located
84 {
85 unsigned int
86 hashIndex;
87 SYM_TABLE_NODE
88 *node;
89
90 hashIndex=STHash(name)&((1<<table->hashTableBits)-1);
91
92 node=table->hashList[hashIndex];
93 while(node&&!STCompNames(name,node->name))
94 {
95 node=node->hashNext;
96 }
97 return(node);
98 }
99
STFindNodeNoCase(SYM_TABLE * table,const char * name)100 SYM_TABLE_NODE *STFindNodeNoCase(SYM_TABLE *table,const char *name)
101 // Find the first node with the given (case insensitive) name.
102 // return NULL if none could be located
103 {
104 unsigned int
105 hashIndex;
106 SYM_TABLE_NODE
107 *node;
108
109 hashIndex=STHash(name)&((1<<table->hashTableBits)-1);
110
111 node=table->hashList[hashIndex];
112 while(node&&!STCompNamesNoCase(name,node->name))
113 {
114 node=node->hashNext;
115 }
116 return(node);
117 }
118
STRemoveEntry(SYM_TABLE * table,SYM_TABLE_NODE * node)119 void STRemoveEntry(SYM_TABLE *table,SYM_TABLE_NODE *node)
120 // Removes any entry with the given name from the table.
121 {
122 if(node->hashNext) // first unlink it from the hash table
123 {
124 node->hashNext->hashPrev=node->hashPrev;
125 }
126
127 if(node->hashPrev)
128 {
129 node->hashPrev->hashNext=node->hashNext;
130 }
131 else
132 {
133 table->hashList[node->hashValue&((1<<table->hashTableBits)-1)]=node->hashNext;
134 }
135
136 if(node->prev==NULL) // then unlink it from the ordered list
137 {
138 table->first=node->next;
139 if(node->next==NULL)
140 {
141 table->last=NULL;
142 }
143 else
144 {
145 node->next->prev=NULL;
146 }
147 }
148 else
149 {
150 node->prev->next=node->next;
151 if(node->next==NULL)
152 {
153 table->last=node->prev;
154 }
155 else
156 {
157 node->next->prev=node->prev;
158 }
159 }
160
161 DisposePtr(node); // and then destroy it
162 }
163
STCreateNode(const char * name,void * data)164 static SYM_TABLE_NODE *STCreateNode(const char *name,void *data)
165 // Returns a new node containing the given name and data.
166 // NOTE: the hash value is calculated at this time, and placed into
167 // the node as well
168 {
169 SYM_TABLE_NODE
170 *newNode;
171
172 if((newNode=(SYM_TABLE_NODE*)NewPtr(sizeof(SYM_TABLE_NODE)+strlen(name)+1)))
173 {
174 newNode->data=data;
175 newNode->hashValue=STHash(name);
176 strcpy(newNode->name,name);
177 return(newNode);
178 }
179 return(NULL);
180 }
181
STAddEntryAtStart(SYM_TABLE * table,const char * name,void * data)182 SYM_TABLE_NODE *STAddEntryAtStart(SYM_TABLE *table,const char *name,void *data)
183 // Adds the given name and data to table as the first entry.
184 // It is allowed for two names in the table to have the same value, but
185 // it is not guaranteed which will be returned when searching
186 {
187 SYM_TABLE_NODE
188 *newNode;
189 unsigned int
190 hashIndex;
191
192 if((newNode=STCreateNode(name,data)))
193 {
194 hashIndex=newNode->hashValue&((1<<table->hashTableBits)-1);
195 if(table->hashList[hashIndex])
196 {
197 table->hashList[hashIndex]->hashPrev=newNode;
198 }
199 newNode->hashNext=table->hashList[hashIndex]; // link into hash list
200 newNode->hashPrev=NULL;
201 table->hashList[hashIndex]=newNode;
202
203 if(table->first) // then link into ordered list
204 {
205 table->first->prev=newNode;
206 }
207 else
208 {
209 table->last=newNode; // first entry in the table
210 }
211 newNode->next=table->first;
212 newNode->prev=NULL;
213 table->first=newNode;
214 }
215 return(newNode);
216 }
217
STAddEntryAtEnd(SYM_TABLE * table,const char * name,void * data)218 SYM_TABLE_NODE *STAddEntryAtEnd(SYM_TABLE *table,const char *name,void *data)
219 // Adds the given name and data to table as the last entry.
220 // It is allowed for two names in the table to have the same value, but
221 // it is not guaranteed which will be returned when searching
222 {
223 SYM_TABLE_NODE
224 *newNode;
225 unsigned int
226 hashIndex;
227
228 if((newNode=STCreateNode(name,data)))
229 {
230 hashIndex=newNode->hashValue&((1<<table->hashTableBits)-1);
231
232 if(table->hashList[hashIndex])
233 {
234 table->hashList[hashIndex]->hashPrev=newNode;
235 }
236 newNode->hashNext=table->hashList[hashIndex]; // link into hash list
237 newNode->hashPrev=NULL;
238 table->hashList[hashIndex]=newNode;
239
240 if(table->last) // then link into ordered list
241 {
242 table->last->next=newNode;
243 }
244 else
245 {
246 table->first=newNode; // first entry in the table
247 }
248 newNode->prev=table->last;
249 newNode->next=NULL;
250 table->last=newNode;
251 }
252 return(newNode);
253 }
254
STFindDataForName(SYM_TABLE * table,const char * name)255 void *STFindDataForName(SYM_TABLE *table,const char *name)
256 // Finds the data for name in the table.
257 // Returns pointer to the node's data on success, NULL otherwise.
258 {
259 SYM_TABLE_NODE
260 *curNode;
261
262 if((curNode=STFindNode(table,name)))
263 {
264 return(curNode->data);
265 }
266 return(NULL);
267 }
268
STFindDataForNameNoCase(SYM_TABLE * table,const char * name)269 void *STFindDataForNameNoCase(SYM_TABLE *table,const char *name)
270 // Finds the data for (case insensitive) name in the table.
271 // Returns pointer to the node's data on success, NULL otherwise.
272 {
273 SYM_TABLE_NODE
274 *curNode;
275
276 if((curNode=STFindNodeNoCase(table,name)))
277 {
278 return(curNode->data);
279 }
280 return(NULL);
281 }
282
STFindFirstEntry(SYM_TABLE * table)283 SYM_TABLE_NODE *STFindFirstEntry(SYM_TABLE *table)
284 // Return the first node linked to table
285 {
286 return(table->first);
287 }
288
STFindLastEntry(SYM_TABLE * table)289 SYM_TABLE_NODE *STFindLastEntry(SYM_TABLE *table)
290 // Return the last node linked to table
291 {
292 return(table->last);
293 }
294
STFindNextEntry(SYM_TABLE * table,SYM_TABLE_NODE * previousEntry)295 SYM_TABLE_NODE *STFindNextEntry(SYM_TABLE *table,SYM_TABLE_NODE *previousEntry)
296 // return the entry just after previousEntry in table
297 {
298 return(previousEntry->next);
299 }
300
STFindPrevEntry(SYM_TABLE * table,SYM_TABLE_NODE * nextEntry)301 SYM_TABLE_NODE *STFindPrevEntry(SYM_TABLE *table,SYM_TABLE_NODE *nextEntry)
302 // return the entry just before nextEntry in table
303 {
304 return(nextEntry->prev);
305 }
306
STNodeName(SYM_TABLE_NODE * node)307 const char *STNodeName(SYM_TABLE_NODE *node)
308 // Return the name of the passed symbol table node.
309 {
310 return(node->name);
311 }
312
STNodeData(SYM_TABLE_NODE * node)313 void *STNodeData(SYM_TABLE_NODE *node)
314 // Return the data of the passed symbol table node.
315 {
316 return(node->data);
317 }
318
STNumEntries(SYM_TABLE * table)319 unsigned int STNumEntries(SYM_TABLE *table)
320 // Returns the number of entries in the table.
321 {
322 SYM_TABLE_NODE
323 *curEnt;
324 unsigned int
325 numEnts;
326
327 numEnts=0;
328
329 curEnt=table->first;
330 while(curEnt!=NULL)
331 {
332 numEnts++;
333 curEnt=curEnt->next;
334 }
335
336 return(numEnts);
337 }
338
STDisposeSymbolTable(SYM_TABLE * table)339 void STDisposeSymbolTable(SYM_TABLE *table)
340 // Dispose of all memory allocated for the given symbol table. Note that
341 // the links are not maintained during the process.
342 {
343 SYM_TABLE_NODE
344 *curEnt,
345 *tmpEnt;
346
347 curEnt=table->first;
348 while(curEnt)
349 {
350 tmpEnt=curEnt->next;
351 DisposePtr(curEnt);
352 curEnt=tmpEnt;
353 }
354 DisposePtr(table);
355 }
356
STNewSymbolTable(unsigned int expectedEntries)357 SYM_TABLE *STNewSymbolTable(unsigned int expectedEntries)
358 // Create and initialize a new symbol table.
359 // expectedEntries is used to work out the size of the hash table.
360 // If it is passed as 0, it suggests that the number of entries could
361 // be arbitrarily large.
362 {
363 SYM_TABLE
364 *table;
365 unsigned int
366 count;
367 unsigned int
368 hashTableBits;
369
370 if(expectedEntries)
371 {
372 hashTableBits=0;
373 while((hashTableBits<ST_MAX_HASH_TABLE_BITS)&&(((unsigned int)(1<<hashTableBits))<expectedEntries/2)) // shoot for two entries per hash bucket
374 {
375 hashTableBits++;
376 }
377 }
378 else
379 {
380 hashTableBits=ST_MAX_HASH_TABLE_BITS;
381 }
382
383 if((table=(SYM_TABLE*)NewPtr(sizeof(SYM_TABLE)+(1<<hashTableBits)*sizeof(SYM_TABLE_NODE *))))
384 {
385 table->first=table->last=NULL;
386 table->hashTableBits=hashTableBits;
387 for(count=0;count<(unsigned int)(1<<hashTableBits);count++)
388 {
389 table->hashList[count]=NULL;
390 }
391 return(table);
392 }
393 return(NULL);
394 }
395