1 /* asmitree.c */
2 /*****************************************************************************/
3 /* SPDX-License-Identifier: GPL-2.0-only OR GPL-3.0-only */
4 /* */
5 /* AS-Portierung */
6 /* */
7 /* Opcode-Abfrage als Binaerbaum */
8 /* */
9 /* Historie: 30.10.1996 Grundsteinlegung */
10 /* 8.10.1997 Hash-Tabelle */
11 /* 6.12.1998 dynamisches Kopieren der Namen */
12 /* */
13 /*****************************************************************************/
14
15 #include "stdinc.h"
16 #include <string.h>
17
18 #include "chunks.h"
19 #include "strutil.h"
20 #include "asmdef.h"
21 #include "asmsub.h"
22
23 #include "asmitree.h"
24
25 /*---------------------------------------------------------------------------*/
26
AddSingle(PInstTreeNode * Node,char * NName,InstProc NProc,Word NIndex)27 static Boolean AddSingle(PInstTreeNode *Node, char *NName, InstProc NProc, Word NIndex)
28 {
29 PInstTreeNode p1, p2;
30 Boolean Result = False;
31
32 ChkStack();
33
34 if (!*Node)
35 {
36 *Node = (PInstTreeNode) malloc(sizeof(TInstTreeNode));
37 (*Node)->Left = NULL;
38 (*Node)->Right = NULL;
39 (*Node)->Proc = NProc;
40 (*Node)->Index = NIndex;
41 (*Node)->Balance = 0;
42 (*Node)->Name = as_strdup(NName);
43 Result = True;
44 }
45 else if (strcmp(NName, (*Node)->Name) < 0)
46 {
47 if (AddSingle(&((*Node)->Left), NName, NProc, NIndex))
48 switch ((*Node)->Balance)
49 {
50 case 1:
51 (*Node)->Balance = 0;
52 break;
53 case 0:
54 (*Node)->Balance = -1;
55 Result = True;
56 break;
57 case -1:
58 p1 = (*Node)->Left;
59 if (p1->Balance == -1)
60 {
61 (*Node)->Left = p1->Right;
62 p1->Right = (*Node);
63 (*Node)->Balance = 0;
64 *Node = p1;
65 }
66 else
67 {
68 p2 = p1->Right;
69 p1->Right = p2->Left;
70 p2->Left = p1;
71 (*Node)->Left = p2->Right;
72 p2->Right = (*Node);
73 (*Node)->Balance = (p2->Balance == -1) ? 1 : 0;
74 p1->Balance = (p2->Balance == 1) ? -1 : 0;
75 *Node = p2;
76 }
77 (*Node)->Balance = 0;
78 break;
79 }
80 }
81 else
82 {
83 if (AddSingle(&((*Node)->Right), NName, NProc, NIndex))
84 switch ((*Node)->Balance)
85 {
86 case -1:
87 (*Node)->Balance = 0;
88 break;
89 case 0:
90 (*Node)->Balance = 1;
91 Result = True;
92 break;
93 case 1:
94 p1 = (*Node)->Right;
95 if (p1->Balance == 1)
96 {
97 (*Node)->Right = p1->Left;
98 p1->Left = (*Node);
99 (*Node)->Balance = 0;
100 *Node = p1;
101 }
102 else
103 {
104 p2 = p1->Left;
105 p1->Left = p2->Right;
106 p2->Right = p1;
107 (*Node)->Right = p2->Left;
108 p2->Left = (*Node);
109 (*Node)->Balance = (p2->Balance == 1) ? -1 : 0;
110 p1->Balance = (p2->Balance == -1) ? 1 : 0;
111 *Node = p2;
112 }
113 (*Node)->Balance = 0;
114 break;
115 }
116 }
117 return Result;
118 }
119
AddInstTree(PInstTreeNode * Root,char * NName,InstProc NProc,Word NIndex)120 void AddInstTree(PInstTreeNode *Root, char *NName, InstProc NProc, Word NIndex)
121 {
122 AddSingle(Root, NName, NProc, NIndex);
123 }
124
ClearSingle(PInstTreeNode * Node)125 static void ClearSingle(PInstTreeNode *Node)
126 {
127 ChkStack();
128
129 if (*Node)
130 {
131 free((*Node)->Name);
132 ClearSingle(&((*Node)->Left));
133 ClearSingle(&((*Node)->Right));
134 free(*Node);
135 *Node = NULL;
136 }
137 }
138
ClearInstTree(PInstTreeNode * Root)139 void ClearInstTree(PInstTreeNode *Root)
140 {
141 ClearSingle(Root);
142 }
143
SearchInstTree(PInstTreeNode Root,char * OpPart)144 Boolean SearchInstTree(PInstTreeNode Root, char *OpPart)
145 {
146 int z;
147
148 z = 0;
149 while ((Root) && (strcmp(Root->Name, OpPart)))
150 {
151 Root = (strcmp(OpPart, Root->Name) < 0) ? Root->Left : Root->Right;
152 z++;
153 }
154
155 if (!Root)
156 return False;
157 else
158 {
159 Root->Proc(Root->Index);
160 return True;
161 }
162 }
163
PNode(PInstTreeNode Node,Word Lev)164 static void PNode(PInstTreeNode Node, Word Lev)
165 {
166 ChkStack();
167 if (Node)
168 {
169 PNode(Node->Left, Lev + 1);
170 printf("%*s %s %p %p %d\n", 5 * Lev, "", Node->Name, (void*)Node->Left, (void*)Node->Right, Node->Balance);
171 PNode(Node->Right, Lev + 1);
172 }
173 }
174
PrintInstTree(PInstTreeNode Root)175 void PrintInstTree(PInstTreeNode Root)
176 {
177 PNode(Root, 0);
178 }
179
180 /*----------------------------------------------------------------------------*/
181
GetKey(const char * Name,LongWord TableSize)182 static int GetKey(const char *Name, LongWord TableSize)
183 {
184 register unsigned char *p;
185 LongWord tmp = 0;
186
187 for (p = (unsigned char *)Name; *p != '\0'; p++)
188 tmp = (tmp << 2) + ((LongWord)*p);
189 return tmp % TableSize;
190 }
191
CreateInstTable(int TableSize)192 PInstTable CreateInstTable(int TableSize)
193 {
194 int z;
195 PInstTableEntry tmp;
196 PInstTable tab;
197
198 tmp = (PInstTableEntry) malloc(sizeof(TInstTableEntry) * TableSize);
199 for (z = 0; z < TableSize; z++)
200 tmp[z].Name = NULL;
201 tab = (PInstTable) malloc(sizeof(TInstTable));
202 tab->Fill = 0;
203 tab->Size = TableSize;
204 tab->Entries = tmp;
205 tab->Dynamic = FALSE;
206 return tab;
207 }
208
SetDynamicInstTable(PInstTable Table)209 void SetDynamicInstTable(PInstTable Table)
210 {
211 Table->Dynamic = TRUE;
212 }
213
DestroyInstTable(PInstTable tab)214 void DestroyInstTable(PInstTable tab)
215 {
216 int z;
217
218 if (tab->Dynamic)
219 for (z = 0; z < tab->Size; z++)
220 free(tab->Entries[z].Name);
221
222 free(tab->Entries);
223 free(tab);
224 }
225
AddInstTable(PInstTable tab,const char * Name,Word Index,InstProc Proc)226 void AddInstTable(PInstTable tab, const char *Name, Word Index, InstProc Proc)
227 {
228 LongWord h0 = GetKey(Name, tab->Size), z = 0;
229
230 /* mindestens ein freies Element lassen, damit der Sucher garantiert terminiert */
231
232 if (tab->Size - 1 <= tab->Fill)
233 {
234 fprintf(stderr, "\nhash table overflow\n");
235 exit(255);
236 }
237 while (1)
238 {
239 if (!tab->Entries[h0].Name)
240 {
241 tab->Entries[h0].Name = (tab->Dynamic) ? as_strdup(Name) : (char*)Name;
242 tab->Entries[h0].Proc = Proc;
243 tab->Entries[h0].Index = Index;
244 tab->Entries[h0].Coll = z;
245 tab->Fill++;
246 return;
247 }
248 if (!strcmp(tab->Entries[h0].Name, Name))
249 {
250 printf("%s double in table\n", Name);
251 exit(255);
252 }
253 z++;
254 if ((LongInt)(++h0) == tab->Size)
255 h0 = 0;
256 }
257 }
258
RemoveInstTable(PInstTable tab,const char * Name)259 void RemoveInstTable(PInstTable tab, const char *Name)
260 {
261 LongWord h0 = GetKey(Name, tab->Size);
262
263 while (1)
264 {
265 if (!tab->Entries[h0].Name)
266 return;
267 else if (!strcmp(tab->Entries[h0].Name, Name))
268 {
269 tab->Entries[h0].Name = NULL;
270 tab->Entries[h0].Proc = NULL;
271 tab->Fill--;
272 return;
273 }
274 if ((LongInt)(++h0) == tab->Size)
275 h0 = 0;
276 }
277 }
278
LookupInstTable(PInstTable tab,const char * Name)279 Boolean LookupInstTable(PInstTable tab, const char *Name)
280 {
281 LongWord h0 = GetKey(Name, tab->Size);
282
283 while (1)
284 {
285 if (!tab->Entries[h0].Name)
286 return False;
287 else if (!strcmp(tab->Entries[h0].Name, Name))
288 {
289 tab->Entries[h0].Proc(tab->Entries[h0].Index);
290 return True;
291 }
292 if ((LongInt)(++h0) == tab->Size)
293 h0 = 0;
294 }
295 }
296
PrintInstTable(FILE * stream,PInstTable tab)297 void PrintInstTable(FILE *stream, PInstTable tab)
298 {
299 int z;
300
301 for (z = 0; z < tab->Size; z++)
302 if (tab->Entries[z].Name)
303 fprintf(stream, "[%3d]: %-10s Index %4d Coll %2d\n", z,
304 tab->Entries[z].Name, tab->Entries[z].Index, tab->Entries[z].Coll);
305 }
306
307 /*----------------------------------------------------------------------------*/
308
asmitree_init(void)309 void asmitree_init(void)
310 {
311 }
312