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