Line data Source code
1 : /* do not edit automatically generated by mc from SymbolKey. */
2 : /* SymbolKey.mod binary tree operations for storing symbols.
3 :
4 : Copyright (C) 2001-2026 Free Software Foundation, Inc.
5 : Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>.
6 :
7 : This file is part of GNU Modula-2.
8 :
9 : GNU Modula-2 is free software; you can redistribute it and/or modify
10 : it under the terms of the GNU General Public License as published by
11 : the Free Software Foundation; either version 3, or (at your option)
12 : any later version.
13 :
14 : GNU Modula-2 is distributed in the hope that it will be useful, but
15 : WITHOUT ANY WARRANTY; without even the implied warranty of
16 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 : General Public License for more details.
18 :
19 : You should have received a copy of the GNU General Public License
20 : along with GNU Modula-2; see the file COPYING3. If not see
21 : <http://www.gnu.org/licenses/>. */
22 :
23 : #include "config.h"
24 : #include "system.h"
25 : #include <stdbool.h>
26 : # if !defined (PROC_D)
27 : # define PROC_D
28 : typedef void (*PROC_t) (void);
29 : typedef struct { PROC_t proc; } PROC;
30 : # endif
31 :
32 : # if !defined (FALSE)
33 : # define FALSE (1==0)
34 : # endif
35 :
36 : # include "GStorage.h"
37 : #if defined(__cplusplus)
38 : # undef NULL
39 : # define NULL 0
40 : #endif
41 : #define _SymbolKey_C
42 :
43 : #include "GSymbolKey.h"
44 : # include "GStorage.h"
45 : # include "GStrIO.h"
46 : # include "GNumberIO.h"
47 : # include "GNameKey.h"
48 : # include "GAssertion.h"
49 : # include "GDebug.h"
50 :
51 : # define SymbolKey_NulKey 0
52 : typedef struct SymbolKey_IsSymbol_p SymbolKey_IsSymbol;
53 :
54 : typedef struct SymbolKey_PerformOperation_p SymbolKey_PerformOperation;
55 :
56 : typedef struct SymbolKey_Node_r SymbolKey_Node;
57 :
58 : typedef SymbolKey_Node *SymbolKey_SymbolTree__opaque;
59 :
60 : struct SymbolKey_Node_r {
61 : NameKey_Name KeyName;
62 : unsigned int KeySym;
63 : SymbolKey_SymbolTree__opaque Left;
64 : SymbolKey_SymbolTree__opaque Right;
65 : };
66 :
67 : extern "C" void SymbolKey_InitTree (SymbolKey_SymbolTree *t);
68 : extern "C" void SymbolKey_KillTree (SymbolKey_SymbolTree *t);
69 :
70 : /*
71 : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
72 : */
73 :
74 : extern "C" unsigned int SymbolKey_GetSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey);
75 :
76 : /*
77 : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
78 : */
79 :
80 : extern "C" void SymbolKey_PutSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey, unsigned int SymKey);
81 :
82 : /*
83 : DelSymKey - deletes an entry in the binary tree.
84 :
85 : NB in order for this to work we must ensure that the InitTree sets
86 : both Left and Right to NIL.
87 : */
88 :
89 : extern "C" void SymbolKey_DelSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey);
90 :
91 : /*
92 : IsEmptyTree - returns true if SymbolTree, t, is empty.
93 : */
94 :
95 : extern "C" bool SymbolKey_IsEmptyTree (SymbolKey_SymbolTree t);
96 :
97 : /*
98 : DoesTreeContainAny - returns true if SymbolTree, t, contains any
99 : symbols which in turn return true when procedure,
100 : P, is called with a symbol as its parameter.
101 : The SymbolTree root is empty apart from the field,
102 : Left, hence we need two procedures.
103 : */
104 :
105 : extern "C" bool SymbolKey_DoesTreeContainAny (SymbolKey_SymbolTree t, SymbolKey_IsSymbol P);
106 :
107 : /*
108 : ForeachNodeDo - for each node in SymbolTree, t, a procedure, P,
109 : is called with the node symbol as its parameter.
110 : The tree root node only contains a legal Left pointer,
111 : therefore we need two procedures to examine this tree.
112 : */
113 :
114 : extern "C" void SymbolKey_ForeachNodeDo (SymbolKey_SymbolTree t, SymbolKey_PerformOperation P);
115 :
116 : /*
117 : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
118 : */
119 :
120 : extern "C" bool SymbolKey_ContainsSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey);
121 :
122 : /*
123 : NoOfNodes - returns the number of nodes in the tree t.
124 : */
125 :
126 : extern "C" unsigned int SymbolKey_NoOfNodes (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition);
127 :
128 : /*
129 : ForeachNodeConditionDo - traverse the tree t and for any node which satisfied
130 : condition call P.
131 : */
132 :
133 : extern "C" void SymbolKey_ForeachNodeConditionDo (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P);
134 :
135 : /*
136 : FindNodeParentInTree - find a node, child, in a binary tree, t, with name equal to n.
137 : if an entry is found, parent is set to the node above child.
138 : */
139 :
140 : static void FindNodeParentInTree (SymbolKey_SymbolTree__opaque t, NameKey_Name n, SymbolKey_SymbolTree__opaque *child, SymbolKey_SymbolTree__opaque *parent);
141 :
142 : /*
143 : SearchForAny - performs the search required for DoesTreeContainAny.
144 : The root node always contains a nul data value,
145 : therefore we must skip over it.
146 : */
147 :
148 : static bool SearchForAny (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol P);
149 :
150 : /*
151 : SearchAndDo - searches all the nodes in SymbolTree, t, and
152 : calls procedure, P, with a node as its parameter.
153 : It traverse the tree in order.
154 : */
155 :
156 : static void SearchAndDo (SymbolKey_SymbolTree__opaque t, SymbolKey_PerformOperation P);
157 :
158 : /*
159 : CountNodes - wrapper for NoOfNodes.
160 : */
161 :
162 : static unsigned int CountNodes (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, unsigned int count);
163 :
164 : /*
165 : SearchConditional - wrapper for ForeachNodeConditionDo.
166 : */
167 :
168 : static void SearchConditional (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P);
169 :
170 :
171 : /*
172 : FindNodeParentInTree - find a node, child, in a binary tree, t, with name equal to n.
173 : if an entry is found, parent is set to the node above child.
174 : */
175 :
176 516030937 : static void FindNodeParentInTree (SymbolKey_SymbolTree__opaque t, NameKey_Name n, SymbolKey_SymbolTree__opaque *child, SymbolKey_SymbolTree__opaque *parent)
177 : {
178 : /* remember to skip the sentinal value and assign parent and child */
179 516030937 : (*parent) = t;
180 516030937 : if (t == NULL)
181 : {
182 0 : Debug_Halt ((const char *) "parameter t should never be NIL", 31, (const char *) "/home/worker/buildworker/tiber-lcov/build/gcc/m2/gm2-compiler/SymbolKey.mod", 75, (const char *) "FindNodeParentInTree", 20, 241);
183 : }
184 516030937 : Assertion_Assert (t->Right == NULL);
185 516030937 : (*child) = t->Left;
186 516030937 : if ((*child) != NULL)
187 : {
188 5073434091 : do {
189 5073434091 : if (n < (*child)->KeyName)
190 : {
191 807937665 : (*parent) = (*child);
192 807937665 : (*child) = (*child)->Left;
193 : }
194 4265496426 : else if (n > (*child)->KeyName)
195 : {
196 : /* avoid dangling else. */
197 4240328885 : (*parent) = (*child);
198 4240328885 : (*child) = (*child)->Right;
199 : }
200 5073434091 : } while (! (((*child) == NULL) || (n == (*child)->KeyName)));
201 : }
202 516030937 : }
203 :
204 :
205 : /*
206 : SearchForAny - performs the search required for DoesTreeContainAny.
207 : The root node always contains a nul data value,
208 : therefore we must skip over it.
209 : */
210 :
211 69186432 : static bool SearchForAny (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol P)
212 : {
213 69186432 : if (t == NULL)
214 : {
215 : return false;
216 : }
217 : else
218 : {
219 33389542 : return (((*P.proc) (t->KeySym)) || (SearchForAny (t->Left, P))) || (SearchForAny (t->Right, P));
220 : }
221 : /* static analysis guarentees a RETURN statement will be used before here. */
222 : __builtin_unreachable ();
223 : }
224 :
225 :
226 : /*
227 : SearchAndDo - searches all the nodes in SymbolTree, t, and
228 : calls procedure, P, with a node as its parameter.
229 : It traverse the tree in order.
230 : */
231 :
232 94836493 : static void SearchAndDo (SymbolKey_SymbolTree__opaque t, SymbolKey_PerformOperation P)
233 : {
234 176212825 : if (t != NULL)
235 : {
236 81376332 : SearchAndDo (t->Right, P);
237 81376332 : (*P.proc) (t->KeySym);
238 81376332 : SearchAndDo (t->Left, P);
239 : }
240 94836493 : }
241 :
242 :
243 : /*
244 : CountNodes - wrapper for NoOfNodes.
245 : */
246 :
247 270 : static unsigned int CountNodes (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, unsigned int count)
248 : {
249 421 : if (t != NULL)
250 : {
251 151 : if ((*condition.proc) (t->KeySym))
252 : {
253 0 : count += 1;
254 : }
255 151 : count = CountNodes (t->Left, condition, count);
256 151 : count = CountNodes (t->Right, condition, count);
257 : }
258 270 : return count;
259 : /* static analysis guarentees a RETURN statement will be used before here. */
260 : __builtin_unreachable ();
261 : }
262 :
263 :
264 : /*
265 : SearchConditional - wrapper for ForeachNodeConditionDo.
266 : */
267 :
268 0 : static void SearchConditional (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P)
269 : {
270 0 : if (t != NULL)
271 : {
272 0 : SearchConditional (t->Right, condition, P);
273 0 : if ((t->KeySym != 0) && ((*condition.proc) (t->KeySym)))
274 : {
275 0 : (*P.proc) (t->KeySym);
276 : }
277 0 : SearchConditional (t->Left, condition, P);
278 : }
279 0 : }
280 :
281 18482518 : extern "C" void SymbolKey_InitTree (SymbolKey_SymbolTree *t)
282 : {
283 18482518 : Storage_ALLOCATE ((void **) &(*t), sizeof (SymbolKey_Node)); /* The value entity */
284 18482518 : static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Left = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
285 18482518 : static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Right = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
286 18482518 : }
287 :
288 0 : extern "C" void SymbolKey_KillTree (SymbolKey_SymbolTree *t)
289 : {
290 : /*
291 : we used to get problems compiling KillTree below - so it was split
292 : into the two procedures below.
293 :
294 :
295 : PROCEDURE KillTree (VAR t: SymbolTree) ;
296 : BEGIN
297 : IF t#NIL
298 : THEN
299 : Kill(t) ; Would like to place Kill in here but the compiler
300 : gives a type incompatible error... so i've split
301 : the procedure into two. - Problem i think with
302 : VAR t at the top?
303 : t := NIL
304 : END
305 : END KillTree ;
306 :
307 :
308 : PROCEDURE Kill (t: SymbolTree) ;
309 : BEGIN
310 : IF t#NIL
311 : THEN
312 : Kill(t^.Left) ;
313 : Kill(t^.Right) ;
314 : DISPOSE(t)
315 : END
316 : END Kill ;
317 : */
318 0 : if ((*t) != NULL)
319 : {
320 0 : SymbolKey_KillTree (reinterpret_cast<SymbolKey_SymbolTree *> (&static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Left));
321 0 : SymbolKey_KillTree (reinterpret_cast<SymbolKey_SymbolTree *> (&static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Right));
322 0 : Storage_DEALLOCATE ((void **) &(*t), sizeof (SymbolKey_Node));
323 0 : (*t) = static_cast<SymbolKey_SymbolTree> (NULL);
324 : }
325 0 : }
326 :
327 :
328 : /*
329 : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
330 : */
331 :
332 450253883 : extern "C" unsigned int SymbolKey_GetSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
333 : {
334 450253883 : SymbolKey_SymbolTree__opaque father;
335 450253883 : SymbolKey_SymbolTree__opaque child;
336 :
337 450253883 : FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father);
338 450253883 : if (child == NULL)
339 : {
340 : return static_cast<unsigned int> (SymbolKey_NulKey);
341 : }
342 : else
343 : {
344 107218229 : return child->KeySym;
345 : }
346 : /* static analysis guarentees a RETURN statement will be used before here. */
347 : __builtin_unreachable ();
348 : }
349 :
350 :
351 : /*
352 : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
353 : */
354 :
355 55552822 : extern "C" void SymbolKey_PutSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey, unsigned int SymKey)
356 : {
357 55552822 : SymbolKey_SymbolTree__opaque father;
358 55552822 : SymbolKey_SymbolTree__opaque child;
359 :
360 55552822 : FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father);
361 55552822 : if (child == NULL)
362 : {
363 : /* no child found, now is NameKey less than father or greater? */
364 55552822 : if (father == t)
365 : {
366 : /* empty tree, add it to the left branch of t */
367 7934838 : Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
368 7934838 : father->Left = child;
369 : }
370 : else
371 : {
372 47617984 : if (NameKey < father->KeyName)
373 : {
374 10721586 : Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
375 10721586 : father->Left = child;
376 : }
377 36896398 : else if (NameKey > father->KeyName)
378 : {
379 : /* avoid dangling else. */
380 36896398 : Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
381 36896398 : father->Right = child;
382 : }
383 : }
384 55552822 : child->Right = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
385 55552822 : child->Left = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
386 55552822 : child->KeySym = SymKey;
387 55552822 : child->KeyName = NameKey;
388 : }
389 : else
390 : {
391 0 : Debug_Halt ((const char *) "symbol already stored", 21, (const char *) "/home/worker/buildworker/tiber-lcov/build/gcc/m2/gm2-compiler/SymbolKey.mod", 75, (const char *) "PutSymKey", 9, 156);
392 : }
393 55552822 : }
394 :
395 :
396 : /*
397 : DelSymKey - deletes an entry in the binary tree.
398 :
399 : NB in order for this to work we must ensure that the InitTree sets
400 : both Left and Right to NIL.
401 : */
402 :
403 10224232 : extern "C" void SymbolKey_DelSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
404 : {
405 10224232 : SymbolKey_SymbolTree__opaque i;
406 10224232 : SymbolKey_SymbolTree__opaque child;
407 10224232 : SymbolKey_SymbolTree__opaque father;
408 :
409 10224232 : FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father); /* find father and child of the node */
410 10224232 : if ((child != NULL) && (child->KeyName == NameKey))
411 : {
412 : /* Have found the node to be deleted */
413 10224232 : if (father->Right == child)
414 : {
415 : /* most branch of child^.Left. */
416 3629768 : if (child->Left != NULL)
417 : {
418 : /* Scan for Right most node of child^.Left */
419 : i = child->Left;
420 147742 : while (i->Right != NULL)
421 : {
422 : i = i->Right;
423 : }
424 91828 : i->Right = child->Right;
425 91828 : father->Right = child->Left;
426 : }
427 : else
428 : {
429 : /* (as in a single linked list) to child^.Right */
430 3537940 : father->Right = child->Right;
431 : }
432 3629768 : Storage_DEALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
433 : }
434 : else
435 : {
436 : /* branch of child^.Right */
437 6594464 : if (child->Right != NULL)
438 : {
439 : /* Scan for Left most node of child^.Right */
440 : i = child->Right;
441 1522441 : while (i->Left != NULL)
442 : {
443 : i = i->Left;
444 : }
445 1096274 : i->Left = child->Left;
446 1096274 : father->Left = child->Right;
447 : }
448 : else
449 : {
450 : /* (as in a single linked list) to child^.Left. */
451 5498190 : father->Left = child->Left;
452 : }
453 6594464 : Storage_DEALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
454 : }
455 : }
456 : else
457 : {
458 0 : Debug_Halt ((const char *) "trying to delete a symbol that is not in the tree - the compiler never expects this to occur", 92, (const char *) "/home/worker/buildworker/tiber-lcov/build/gcc/m2/gm2-compiler/SymbolKey.mod", 75, (const char *) "DelSymKey", 9, 223);
459 : }
460 10224232 : }
461 :
462 :
463 : /*
464 : IsEmptyTree - returns true if SymbolTree, t, is empty.
465 : */
466 :
467 244198 : extern "C" bool SymbolKey_IsEmptyTree (SymbolKey_SymbolTree t)
468 : {
469 244198 : return static_cast<SymbolKey_SymbolTree__opaque> (t)->Left == NULL;
470 : /* static analysis guarentees a RETURN statement will be used before here. */
471 : __builtin_unreachable ();
472 : }
473 :
474 :
475 : /*
476 : DoesTreeContainAny - returns true if SymbolTree, t, contains any
477 : symbols which in turn return true when procedure,
478 : P, is called with a symbol as its parameter.
479 : The SymbolTree root is empty apart from the field,
480 : Left, hence we need two procedures.
481 : */
482 :
483 2407586 : extern "C" bool SymbolKey_DoesTreeContainAny (SymbolKey_SymbolTree t, SymbolKey_IsSymbol P)
484 : {
485 2407586 : return SearchForAny (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, P);
486 : /* static analysis guarentees a RETURN statement will be used before here. */
487 : __builtin_unreachable ();
488 : }
489 :
490 :
491 : /*
492 : ForeachNodeDo - for each node in SymbolTree, t, a procedure, P,
493 : is called with the node symbol as its parameter.
494 : The tree root node only contains a legal Left pointer,
495 : therefore we need two procedures to examine this tree.
496 : */
497 :
498 13460161 : extern "C" void SymbolKey_ForeachNodeDo (SymbolKey_SymbolTree t, SymbolKey_PerformOperation P)
499 : {
500 13460161 : SearchAndDo (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, P);
501 13460161 : }
502 :
503 :
504 : /*
505 : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
506 : */
507 :
508 0 : extern "C" bool SymbolKey_ContainsSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
509 : {
510 0 : SymbolKey_SymbolTree__opaque father;
511 0 : SymbolKey_SymbolTree__opaque child;
512 :
513 0 : FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father);
514 0 : return child != NULL;
515 : /* static analysis guarentees a RETURN statement will be used before here. */
516 : __builtin_unreachable ();
517 : }
518 :
519 :
520 : /*
521 : NoOfNodes - returns the number of nodes in the tree t.
522 : */
523 :
524 119 : extern "C" unsigned int SymbolKey_NoOfNodes (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition)
525 : {
526 119 : return CountNodes (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, condition, 0);
527 : /* static analysis guarentees a RETURN statement will be used before here. */
528 : __builtin_unreachable ();
529 : }
530 :
531 :
532 : /*
533 : ForeachNodeConditionDo - traverse the tree t and for any node which satisfied
534 : condition call P.
535 : */
536 :
537 0 : extern "C" void SymbolKey_ForeachNodeConditionDo (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P)
538 : {
539 0 : if (t != NULL)
540 : {
541 0 : Assertion_Assert (static_cast<SymbolKey_SymbolTree__opaque> (t)->Right == NULL);
542 0 : SearchConditional (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, condition, P);
543 : }
544 0 : }
545 :
546 14952 : extern "C" void _M2_SymbolKey_init (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
547 : {
548 14952 : }
549 :
550 0 : extern "C" void _M2_SymbolKey_fini (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
551 : {
552 0 : }
|
