1 /* trees.c */
2 /*****************************************************************************/
3 /* SPDX-License-Identifier: GPL-2.0-only OR GPL-3.0-only */
4 /* */
5 /* AS-Portierung */
6 /* */
7 /* Tree management */
8 /* */
9 /*****************************************************************************/
10
11 #include "stdinc.h"
12 #include <string.h>
13 #include <ctype.h>
14
15 #include "endian.h"
16 #include "nls.h"
17 #include "asmdef.h"
18 #include "asmsub.h"
19 #include "asmpars.h"
20
21 #include "trees.h"
22
23 Boolean BalanceTrees;
24
StrCmp(const char * s1,const char * s2,LongInt Hand1,LongInt Hand2)25 static ShortInt StrCmp(const char *s1, const char *s2, LongInt Hand1, LongInt Hand2)
26 {
27 int tmp;
28
29 tmp = (*s1) - (*s2);
30 if (!tmp)
31 tmp = strcmp(s1, s2);
32 if (!tmp)
33 tmp = Hand1 - Hand2;
34 if (tmp < 0)
35 return -1;
36 if (tmp > 0)
37 return 1;
38 return 0;
39 }
40
IterTree(PTree Tree,TTreeCallback Callback,void * pData)41 void IterTree(PTree Tree, TTreeCallback Callback, void *pData)
42 {
43 ChkStack();
44 if (Tree)
45 {
46 if (Tree->Left) IterTree(Tree->Left, Callback, pData);
47 Callback(Tree, pData);
48 if (Tree->Right) IterTree(Tree->Right, Callback, pData);
49 }
50 }
51
TreeDepthIter(PTree Tree,LongInt Level,LongInt * pMin,LongInt * pMax)52 static void TreeDepthIter(PTree Tree, LongInt Level, LongInt *pMin, LongInt *pMax)
53 {
54 ChkStack();
55 if (Tree)
56 {
57 TreeDepthIter(Tree->Left, Level + 1, pMin, pMax);
58 TreeDepthIter(Tree->Right, Level + 1, pMin, pMax);
59 }
60 else
61 {
62 if (Level > *pMax) *pMax = Level;
63 if (Level < *pMin) *pMin = Level;
64 }
65 }
66
GetTreeDepth(PTree Tree,LongInt * pMin,LongInt * pMax)67 void GetTreeDepth(PTree Tree, LongInt *pMin, LongInt *pMax)
68 {
69 *pMin = MaxLongInt; *pMax = 0;
70 TreeDepthIter(Tree, 0, pMin, pMax);
71 }
72
DestroyTree(PTree * Tree,TTreeCallback Callback,void * pData)73 void DestroyTree(PTree *Tree, TTreeCallback Callback, void *pData)
74 {
75 ChkStack();
76 if (*Tree)
77 {
78 if ((*Tree)->Left) DestroyTree(&((*Tree)->Left), Callback, pData);
79 if ((*Tree)->Right) DestroyTree(&((*Tree)->Right), Callback, pData);
80 Callback(*Tree, pData);
81 if ((*Tree)->Name)
82 {
83 free((*Tree)->Name); (*Tree)->Name = NULL;
84 }
85 free(*Tree); *Tree = NULL;
86 }
87 }
88
DumpTreeIter(PTree Tree,LongInt Level)89 static void DumpTreeIter(PTree Tree, LongInt Level)
90 {
91 ChkStack();
92 if (Tree)
93 {
94 if (Tree->Left) DumpTreeIter(Tree->Left, Level + 1);
95 fprintf(Debug,"%*s%s\n", 6 * Level, "", Tree->Name);
96 if (Tree->Right) DumpTreeIter(Tree->Right, Level + 1);
97 }
98 }
99
DumpTree(PTree Tree)100 void DumpTree(PTree Tree)
101 {
102 DumpTreeIter(Tree, 0);
103 }
104
SearchTree(PTree Tree,char * Name,LongInt Attribute)105 PTree SearchTree(PTree Tree, char *Name, LongInt Attribute)
106 {
107 ShortInt SErg = -1;
108
109 while ((Tree) && (SErg != 0))
110 {
111 SErg = StrCmp(Name, Tree->Name, Attribute, Tree->Attribute);
112 if (SErg < 0) Tree = Tree->Left;
113 else if (SErg > 0) Tree = Tree->Right;
114 }
115 return Tree;
116 }
117
EnterTree(PTree * PDest,PTree Neu,TTreeAdder Adder,void * pData)118 Boolean EnterTree(PTree *PDest, PTree Neu, TTreeAdder Adder, void *pData)
119 {
120 PTree Hilf, p1, p2;
121 Boolean Grown, Result;
122 ShortInt CompErg;
123
124 /* check for stack overflow, nothing yet inserted */
125
126 ChkStack(); Result = False;
127
128 /* arrived at a leaf? --> simply add */
129
130 if (*PDest == NULL)
131 {
132 (*PDest) = Neu;
133 (*PDest)->Balance = 0; (*PDest)->Left = NULL; (*PDest)->Right = NULL;
134 Adder(NULL, Neu, pData);
135 return True;
136 }
137
138 /* go right, left, or straight? */
139
140 CompErg = StrCmp(Neu->Name, (*PDest)->Name, Neu->Attribute, (*PDest)->Attribute);
141
142 /* left ? */
143
144 if (CompErg > 0)
145 {
146 Grown = EnterTree(&((*PDest)->Right), Neu, Adder, pData);
147 if ((BalanceTrees) && (Grown))
148 switch ((*PDest)->Balance)
149 {
150 case -1:
151 (*PDest)->Balance = 0; break;
152 case 0:
153 (*PDest)->Balance = 1; Result = True; break;
154 case 1:
155 p1 = (*PDest)->Right;
156 if (p1->Balance == 1)
157 {
158 (*PDest)->Right = p1->Left; p1->Left = *PDest;
159 (*PDest)->Balance = 0; *PDest = p1;
160 }
161 else
162 {
163 p2 = p1->Left;
164 p1->Left = p2->Right; p2->Right = p1;
165 (*PDest)->Right = p2->Left; p2->Left = *PDest;
166 if (p2->Balance == 1) (*PDest)->Balance = (-1); else (*PDest)->Balance = 0;
167 if (p2->Balance == -1) p1 ->Balance = 1; else p1 ->Balance = 0;
168 *PDest = p2;
169 }
170 (*PDest)->Balance = 0;
171 break;
172 }
173 }
174
175 /* right ? */
176
177 else if (CompErg < 0)
178 {
179 Grown = EnterTree(&((*PDest)->Left), Neu, Adder, pData);
180 if ((BalanceTrees) && (Grown))
181 switch ((*PDest)->Balance)
182 {
183 case 1:
184 (*PDest)->Balance = 0;
185 break;
186 case 0:
187 (*PDest)->Balance = -1;
188 Result = True;
189 break;
190 case -1:
191 p1 = (*PDest)->Left;
192 if (p1->Balance == (-1))
193 {
194 (*PDest)->Left = p1->Right;
195 p1->Right = *PDest;
196 (*PDest)->Balance = 0;
197 *PDest = p1;
198 }
199 else
200 {
201 p2 = p1->Right;
202 p1->Right = p2->Left;
203 p2->Left = p1;
204 (*PDest)->Left = p2->Right;
205 p2->Right = *PDest;
206 if (p2->Balance == (-1)) (*PDest)->Balance = 1; else (*PDest)->Balance = 0;
207 if (p2->Balance == 1) p1 ->Balance = (-1); else p1 ->Balance = 0;
208 *PDest = p2;
209 }
210 (*PDest)->Balance = 0;
211 break;
212 }
213 }
214
215 /* otherwise we might replace the node */
216
217 else
218 {
219 if (Adder(PDest, Neu, pData))
220 {
221 Neu->Left = (*PDest)->Left; Neu->Right = (*PDest)->Right;
222 Neu->Balance = (*PDest)->Balance;
223 Hilf = *PDest; *PDest = Neu;
224 if (Hilf->Name)
225 {
226 free(Hilf->Name); Hilf->Name = NULL;
227 }
228 free(Hilf);
229 }
230 }
231
232 return Result;
233 }
234