Branch data 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-2024 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 : 312525762 : 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 : 312525762 : (*parent) = t;
180 : 312525762 : 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 : 312525762 : Assertion_Assert (t->Right == NULL);
185 : 312525762 : (*child) = t->Left;
186 : 312525762 : if ((*child) != NULL)
187 : : {
188 : 2995547836 : do {
189 : 2995547836 : if (n < (*child)->KeyName)
190 : : {
191 : 461101154 : (*parent) = (*child);
192 : 461101154 : (*child) = (*child)->Left;
193 : : }
194 : 2534446682 : else if (n > (*child)->KeyName)
195 : : {
196 : : /* avoid dangling else. */
197 : 2523295465 : (*parent) = (*child);
198 : 2523295465 : (*child) = (*child)->Right;
199 : : }
200 : 2995547836 : } while (! (((*child) == NULL) || (n == (*child)->KeyName)));
201 : : }
202 : 312525762 : }
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 : 46521924 : static bool SearchForAny (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol P)
212 : : {
213 : 46521924 : if (t == NULL)
214 : : {
215 : : return false;
216 : : }
217 : : else
218 : : {
219 : 22510500 : 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 : 45112893 : static void SearchAndDo (SymbolKey_SymbolTree__opaque t, SymbolKey_PerformOperation P)
233 : : {
234 : 86138622 : if (t != NULL)
235 : : {
236 : 41025729 : SearchAndDo (t->Right, P);
237 : 41025729 : (*P.proc) (t->KeySym);
238 : 41025729 : SearchAndDo (t->Left, P);
239 : : }
240 : 45112893 : }
241 : :
242 : :
243 : : /*
244 : : CountNodes - wrapper for NoOfNodes.
245 : : */
246 : :
247 : 198 : static unsigned int CountNodes (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, unsigned int count)
248 : : {
249 : 306 : if (t != NULL)
250 : : {
251 : 108 : if ((*condition.proc) (t->KeySym))
252 : : {
253 : 108 : count += 1;
254 : : }
255 : 108 : count = CountNodes (t->Left, condition, count);
256 : 108 : count = CountNodes (t->Right, condition, count);
257 : : }
258 : 198 : 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 : 198 : static void SearchConditional (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P)
269 : : {
270 : 306 : if (t != NULL)
271 : : {
272 : 108 : SearchConditional (t->Right, condition, P);
273 : 108 : if ((t->KeySym != 0) && ((*condition.proc) (t->KeySym)))
274 : : {
275 : 108 : (*P.proc) (t->KeySym);
276 : : }
277 : 108 : SearchConditional (t->Left, condition, P);
278 : : }
279 : 198 : }
280 : :
281 : 13339197 : extern "C" void SymbolKey_InitTree (SymbolKey_SymbolTree *t)
282 : : {
283 : 13339197 : Storage_ALLOCATE ((void **) &(*t), sizeof (SymbolKey_Node)); /* The value entity */
284 : 13339197 : static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Left = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
285 : 13339197 : static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Right = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
286 : 13339197 : }
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 : 266956402 : extern "C" unsigned int SymbolKey_GetSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
333 : : {
334 : 266956402 : SymbolKey_SymbolTree__opaque father;
335 : 266956402 : SymbolKey_SymbolTree__opaque child;
336 : :
337 : 266956402 : FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father);
338 : 266956402 : if (child == NULL)
339 : : {
340 : : return static_cast<unsigned int> (SymbolKey_NulKey);
341 : : }
342 : : else
343 : : {
344 : 60876407 : 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 : 38961852 : extern "C" void SymbolKey_PutSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey, unsigned int SymKey)
356 : : {
357 : 38961852 : SymbolKey_SymbolTree__opaque father;
358 : 38961852 : SymbolKey_SymbolTree__opaque child;
359 : :
360 : 38961852 : FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father);
361 : 38961852 : if (child == NULL)
362 : : {
363 : : /* no child found, now is NameKey less than father or greater? */
364 : 38961852 : if (father == t)
365 : : {
366 : : /* empty tree, add it to the left branch of t */
367 : 4561995 : Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
368 : 4561995 : father->Left = child;
369 : : }
370 : : else
371 : : {
372 : 34399857 : if (NameKey < father->KeyName)
373 : : {
374 : 7401642 : Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
375 : 7401642 : father->Left = child;
376 : : }
377 : 26998215 : else if (NameKey > father->KeyName)
378 : : {
379 : : /* avoid dangling else. */
380 : 26998215 : Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
381 : 26998215 : father->Right = child;
382 : : }
383 : : }
384 : 38961852 : child->Right = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
385 : 38961852 : child->Left = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
386 : 38961852 : child->KeySym = SymKey;
387 : 38961852 : 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 : 38961852 : }
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 : 6607508 : extern "C" void SymbolKey_DelSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
404 : : {
405 : 6607508 : SymbolKey_SymbolTree__opaque i;
406 : 6607508 : SymbolKey_SymbolTree__opaque child;
407 : 6607508 : SymbolKey_SymbolTree__opaque father;
408 : :
409 : 6607508 : FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father); /* find father and child of the node */
410 : 6607508 : if ((child != NULL) && (child->KeyName == NameKey))
411 : : {
412 : : /* Have found the node to be deleted */
413 : 6607508 : if (father->Right == child)
414 : : {
415 : : /* most branch of child^.Left. */
416 : 2747744 : if (child->Left != NULL)
417 : : {
418 : : /* Scan for Right most node of child^.Left */
419 : : i = child->Left;
420 : 108990 : while (i->Right != NULL)
421 : : {
422 : : i = i->Right;
423 : : }
424 : 59422 : i->Right = child->Right;
425 : 59422 : father->Right = child->Left;
426 : : }
427 : : else
428 : : {
429 : : /* (as in a single linked list) to child^.Right */
430 : 2688322 : father->Right = child->Right;
431 : : }
432 : 2747744 : Storage_DEALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
433 : : }
434 : : else
435 : : {
436 : : /* branch of child^.Right */
437 : 3859764 : if (child->Right != NULL)
438 : : {
439 : : /* Scan for Left most node of child^.Right */
440 : : i = child->Right;
441 : 1040701 : while (i->Left != NULL)
442 : : {
443 : : i = i->Left;
444 : : }
445 : 710909 : i->Left = child->Left;
446 : 710909 : father->Left = child->Right;
447 : : }
448 : : else
449 : : {
450 : : /* (as in a single linked list) to child^.Left. */
451 : 3148855 : father->Left = child->Left;
452 : : }
453 : 3859764 : 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 : 6607508 : }
461 : :
462 : :
463 : : /*
464 : : IsEmptyTree - returns true if SymbolTree, t, is empty.
465 : : */
466 : :
467 : 541111 : extern "C" bool SymbolKey_IsEmptyTree (SymbolKey_SymbolTree t)
468 : : {
469 : 541111 : 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 : 1501104 : extern "C" bool SymbolKey_DoesTreeContainAny (SymbolKey_SymbolTree t, SymbolKey_IsSymbol P)
484 : : {
485 : 1501104 : 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 : 4087164 : extern "C" void SymbolKey_ForeachNodeDo (SymbolKey_SymbolTree t, SymbolKey_PerformOperation P)
499 : : {
500 : 4087164 : SearchAndDo (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, P);
501 : 4087164 : }
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 : 90 : extern "C" unsigned int SymbolKey_NoOfNodes (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition)
525 : : {
526 : 90 : 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 : 90 : extern "C" void SymbolKey_ForeachNodeConditionDo (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P)
538 : : {
539 : 90 : if (t != NULL)
540 : : {
541 : 90 : Assertion_Assert (static_cast<SymbolKey_SymbolTree__opaque> (t)->Right == NULL);
542 : 90 : SearchConditional (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, condition, P);
543 : : }
544 : 90 : }
545 : :
546 : 15942 : extern "C" void _M2_SymbolKey_init (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
547 : : {
548 : 15942 : }
549 : :
550 : 0 : extern "C" void _M2_SymbolKey_fini (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
551 : : {
552 : 0 : }
|
