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_H
42 : : #define _SymbolKey_C
43 : :
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;
59 : :
60 : : typedef bool (*SymbolKey_IsSymbol_t) (unsigned int);
61 : : struct SymbolKey_IsSymbol_p { SymbolKey_IsSymbol_t proc; };
62 : :
63 : : typedef void (*SymbolKey_PerformOperation_t) (unsigned int);
64 : : struct SymbolKey_PerformOperation_p { SymbolKey_PerformOperation_t proc; };
65 : :
66 : : struct SymbolKey_Node_r {
67 : : NameKey_Name KeyName;
68 : : unsigned int KeySym;
69 : : SymbolKey_SymbolTree Left;
70 : : SymbolKey_SymbolTree Right;
71 : : };
72 : :
73 : : extern "C" void SymbolKey_InitTree (SymbolKey_SymbolTree *t);
74 : : extern "C" void SymbolKey_KillTree (SymbolKey_SymbolTree *t);
75 : :
76 : : /*
77 : : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
78 : : */
79 : :
80 : : extern "C" unsigned int SymbolKey_GetSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey);
81 : :
82 : : /*
83 : : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
84 : : */
85 : :
86 : : extern "C" void SymbolKey_PutSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey, unsigned int SymKey);
87 : :
88 : : /*
89 : : DelSymKey - deletes an entry in the binary tree.
90 : :
91 : : NB in order for this to work we must ensure that the InitTree sets
92 : : both Left and Right to NIL.
93 : : */
94 : :
95 : : extern "C" void SymbolKey_DelSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey);
96 : :
97 : : /*
98 : : IsEmptyTree - returns true if SymbolTree, t, is empty.
99 : : */
100 : :
101 : : extern "C" bool SymbolKey_IsEmptyTree (SymbolKey_SymbolTree t);
102 : :
103 : : /*
104 : : DoesTreeContainAny - returns true if SymbolTree, t, contains any
105 : : symbols which in turn return true when procedure,
106 : : P, is called with a symbol as its parameter.
107 : : The SymbolTree root is empty apart from the field,
108 : : Left, hence we need two procedures.
109 : : */
110 : :
111 : : extern "C" bool SymbolKey_DoesTreeContainAny (SymbolKey_SymbolTree t, SymbolKey_IsSymbol P);
112 : :
113 : : /*
114 : : ForeachNodeDo - for each node in SymbolTree, t, a procedure, P,
115 : : is called with the node symbol as its parameter.
116 : : The tree root node only contains a legal Left pointer,
117 : : therefore we need two procedures to examine this tree.
118 : : */
119 : :
120 : : extern "C" void SymbolKey_ForeachNodeDo (SymbolKey_SymbolTree t, SymbolKey_PerformOperation P);
121 : :
122 : : /*
123 : : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
124 : : */
125 : :
126 : : extern "C" bool SymbolKey_ContainsSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey);
127 : :
128 : : /*
129 : : NoOfNodes - returns the number of nodes in the tree t.
130 : : */
131 : :
132 : : extern "C" unsigned int SymbolKey_NoOfNodes (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition);
133 : :
134 : : /*
135 : : ForeachNodeConditionDo - traverse the tree t and for any node which satisfied
136 : : condition call P.
137 : : */
138 : :
139 : : extern "C" void SymbolKey_ForeachNodeConditionDo (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P);
140 : :
141 : : /*
142 : : FindNodeParentInTree - find a node, child, in a binary tree, t, with name equal to n.
143 : : if an entry is found, parent is set to the node above child.
144 : : */
145 : :
146 : : static void FindNodeParentInTree (SymbolKey_SymbolTree t, NameKey_Name n, SymbolKey_SymbolTree *child, SymbolKey_SymbolTree *parent);
147 : :
148 : : /*
149 : : SearchForAny - performs the search required for DoesTreeContainAny.
150 : : The root node always contains a nul data value,
151 : : therefore we must skip over it.
152 : : */
153 : :
154 : : static bool SearchForAny (SymbolKey_SymbolTree t, SymbolKey_IsSymbol P);
155 : :
156 : : /*
157 : : SearchAndDo - searches all the nodes in SymbolTree, t, and
158 : : calls procedure, P, with a node as its parameter.
159 : : It traverse the tree in order.
160 : : */
161 : :
162 : : static void SearchAndDo (SymbolKey_SymbolTree t, SymbolKey_PerformOperation P);
163 : :
164 : : /*
165 : : CountNodes - wrapper for NoOfNodes.
166 : : */
167 : :
168 : : static unsigned int CountNodes (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, unsigned int count);
169 : :
170 : : /*
171 : : SearchConditional - wrapper for ForeachNodeConditionDo.
172 : : */
173 : :
174 : : static void SearchConditional (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P);
175 : :
176 : :
177 : : /*
178 : : FindNodeParentInTree - find a node, child, in a binary tree, t, with name equal to n.
179 : : if an entry is found, parent is set to the node above child.
180 : : */
181 : :
182 : 283182892 : static void FindNodeParentInTree (SymbolKey_SymbolTree t, NameKey_Name n, SymbolKey_SymbolTree *child, SymbolKey_SymbolTree *parent)
183 : : {
184 : : /* remember to skip the sentinal value and assign parent and child */
185 : 283182892 : (*parent) = t;
186 : 283182892 : if (t == NULL)
187 : : {
188 : 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);
189 : : }
190 : 283182892 : Assertion_Assert (t->Right == NULL);
191 : 283182892 : (*child) = t->Left;
192 : 283182892 : if ((*child) != NULL)
193 : : {
194 : 2818577728 : do {
195 : 2818577728 : if (n < (*child)->KeyName)
196 : : {
197 : 395328869 : (*parent) = (*child);
198 : 395328869 : (*child) = (*child)->Left;
199 : : }
200 : 2423248859 : else if (n > (*child)->KeyName)
201 : : {
202 : : /* avoid dangling else. */
203 : 2414045444 : (*parent) = (*child);
204 : 2414045444 : (*child) = (*child)->Right;
205 : : }
206 : 2818577728 : } while (! (((*child) == NULL) || (n == (*child)->KeyName)));
207 : : }
208 : 283182892 : }
209 : :
210 : :
211 : : /*
212 : : SearchForAny - performs the search required for DoesTreeContainAny.
213 : : The root node always contains a nul data value,
214 : : therefore we must skip over it.
215 : : */
216 : :
217 : 45720142 : static bool SearchForAny (SymbolKey_SymbolTree t, SymbolKey_IsSymbol P)
218 : : {
219 : 45720142 : if (t == NULL)
220 : : {
221 : : return false;
222 : : }
223 : : else
224 : : {
225 : 22106075 : return (((*P.proc) (t->KeySym)) || (SearchForAny (t->Left, P))) || (SearchForAny (t->Right, P));
226 : : }
227 : : /* static analysis guarentees a RETURN statement will be used before here. */
228 : : __builtin_unreachable ();
229 : : }
230 : :
231 : :
232 : : /*
233 : : SearchAndDo - searches all the nodes in SymbolTree, t, and
234 : : calls procedure, P, with a node as its parameter.
235 : : It traverse the tree in order.
236 : : */
237 : :
238 : 43251660 : static void SearchAndDo (SymbolKey_SymbolTree t, SymbolKey_PerformOperation P)
239 : : {
240 : 82790419 : if (t != NULL)
241 : : {
242 : 39538759 : SearchAndDo (t->Right, P);
243 : 39538759 : (*P.proc) (t->KeySym);
244 : 39538759 : SearchAndDo (t->Left, P);
245 : : }
246 : 43251660 : }
247 : :
248 : :
249 : : /*
250 : : CountNodes - wrapper for NoOfNodes.
251 : : */
252 : :
253 : 162 : static unsigned int CountNodes (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, unsigned int count)
254 : : {
255 : 252 : if (t != NULL)
256 : : {
257 : 90 : if ((*condition.proc) (t->KeySym))
258 : : {
259 : 90 : count += 1;
260 : : }
261 : 90 : count = CountNodes (t->Left, condition, count);
262 : 90 : count = CountNodes (t->Right, condition, count);
263 : : }
264 : 162 : return count;
265 : : /* static analysis guarentees a RETURN statement will be used before here. */
266 : : __builtin_unreachable ();
267 : : }
268 : :
269 : :
270 : : /*
271 : : SearchConditional - wrapper for ForeachNodeConditionDo.
272 : : */
273 : :
274 : 162 : static void SearchConditional (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P)
275 : : {
276 : 252 : if (t != NULL)
277 : : {
278 : 90 : SearchConditional (t->Right, condition, P);
279 : 90 : if ((t->KeySym != 0) && ((*condition.proc) (t->KeySym)))
280 : : {
281 : 90 : (*P.proc) (t->KeySym);
282 : : }
283 : 90 : SearchConditional (t->Left, condition, P);
284 : : }
285 : 162 : }
286 : :
287 : 13357744 : extern "C" void SymbolKey_InitTree (SymbolKey_SymbolTree *t)
288 : : {
289 : 13357744 : Storage_ALLOCATE ((void **) &(*t), sizeof (SymbolKey_Node)); /* The value entity */
290 : 13357744 : (*t)->Left = NULL;
291 : 13357744 : (*t)->Right = NULL;
292 : 13357744 : }
293 : :
294 : 0 : extern "C" void SymbolKey_KillTree (SymbolKey_SymbolTree *t)
295 : : {
296 : : /*
297 : : we used to get problems compiling KillTree below - so it was split
298 : : into the two procedures below.
299 : :
300 : :
301 : : PROCEDURE KillTree (VAR t: SymbolTree) ;
302 : : BEGIN
303 : : IF t#NIL
304 : : THEN
305 : : Kill(t) ; Would like to place Kill in here but the compiler
306 : : gives a type incompatible error... so i've split
307 : : the procedure into two. - Problem i think with
308 : : VAR t at the top?
309 : : t := NIL
310 : : END
311 : : END KillTree ;
312 : :
313 : :
314 : : PROCEDURE Kill (t: SymbolTree) ;
315 : : BEGIN
316 : : IF t#NIL
317 : : THEN
318 : : Kill(t^.Left) ;
319 : : Kill(t^.Right) ;
320 : : DISPOSE(t)
321 : : END
322 : : END Kill ;
323 : : */
324 : 0 : if ((*t) != NULL)
325 : : {
326 : 0 : SymbolKey_KillTree (&(*t)->Left);
327 : 0 : SymbolKey_KillTree (&(*t)->Right);
328 : 0 : Storage_DEALLOCATE ((void **) &(*t), sizeof (SymbolKey_Node));
329 : 0 : (*t) = NULL;
330 : : }
331 : 0 : }
332 : :
333 : :
334 : : /*
335 : : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
336 : : */
337 : :
338 : 238177808 : extern "C" unsigned int SymbolKey_GetSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
339 : : {
340 : 238177808 : SymbolKey_SymbolTree father;
341 : 238177808 : SymbolKey_SymbolTree child;
342 : :
343 : 238177808 : FindNodeParentInTree (t, NameKey, &child, &father);
344 : 238177808 : if (child == NULL)
345 : : {
346 : : return static_cast<unsigned int> (SymbolKey_NulKey);
347 : : }
348 : : else
349 : : {
350 : 54463700 : return child->KeySym;
351 : : }
352 : : /* static analysis guarentees a RETURN statement will be used before here. */
353 : : __builtin_unreachable ();
354 : : }
355 : :
356 : :
357 : : /*
358 : : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
359 : : */
360 : :
361 : 38566954 : extern "C" void SymbolKey_PutSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey, unsigned int SymKey)
362 : : {
363 : 38566954 : SymbolKey_SymbolTree father;
364 : 38566954 : SymbolKey_SymbolTree child;
365 : :
366 : 38566954 : FindNodeParentInTree (t, NameKey, &child, &father);
367 : 38566954 : if (child == NULL)
368 : : {
369 : : /* no child found, now is NameKey less than father or greater? */
370 : 38566954 : if (father == t)
371 : : {
372 : : /* empty tree, add it to the left branch of t */
373 : 4479929 : Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
374 : 4479929 : father->Left = child;
375 : : }
376 : : else
377 : : {
378 : 34087025 : if (NameKey < father->KeyName)
379 : : {
380 : 7197152 : Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
381 : 7197152 : father->Left = child;
382 : : }
383 : 26889873 : else if (NameKey > father->KeyName)
384 : : {
385 : : /* avoid dangling else. */
386 : 26889873 : Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
387 : 26889873 : father->Right = child;
388 : : }
389 : : }
390 : 38566954 : child->Right = NULL;
391 : 38566954 : child->Left = NULL;
392 : 38566954 : child->KeySym = SymKey;
393 : 38566954 : child->KeyName = NameKey;
394 : : }
395 : : else
396 : : {
397 : 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);
398 : : }
399 : 38566954 : }
400 : :
401 : :
402 : : /*
403 : : DelSymKey - deletes an entry in the binary tree.
404 : :
405 : : NB in order for this to work we must ensure that the InitTree sets
406 : : both Left and Right to NIL.
407 : : */
408 : :
409 : 6438130 : extern "C" void SymbolKey_DelSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
410 : : {
411 : 6438130 : SymbolKey_SymbolTree i;
412 : 6438130 : SymbolKey_SymbolTree child;
413 : 6438130 : SymbolKey_SymbolTree father;
414 : :
415 : 6438130 : FindNodeParentInTree (t, NameKey, &child, &father); /* find father and child of the node */
416 : 6438130 : if ((child != NULL) && (child->KeyName == NameKey))
417 : : {
418 : : /* Have found the node to be deleted */
419 : 6438130 : if (father->Right == child)
420 : : {
421 : : /* most branch of child^.Left. */
422 : 2745319 : if (child->Left != NULL)
423 : : {
424 : : /* Scan for Right most node of child^.Left */
425 : : i = child->Left;
426 : 103988 : while (i->Right != NULL)
427 : : {
428 : : i = i->Right;
429 : : }
430 : 57003 : i->Right = child->Right;
431 : 57003 : father->Right = child->Left;
432 : : }
433 : : else
434 : : {
435 : : /* (as in a single linked list) to child^.Right */
436 : 2688316 : father->Right = child->Right;
437 : : }
438 : 2745319 : Storage_DEALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
439 : : }
440 : : else
441 : : {
442 : : /* branch of child^.Right */
443 : 3692811 : if (child->Right != NULL)
444 : : {
445 : : /* Scan for Left most node of child^.Right */
446 : : i = child->Right;
447 : 1004648 : while (i->Left != NULL)
448 : : {
449 : : i = i->Left;
450 : : }
451 : 679173 : i->Left = child->Left;
452 : 679173 : father->Left = child->Right;
453 : : }
454 : : else
455 : : {
456 : : /* (as in a single linked list) to child^.Left. */
457 : 3013638 : father->Left = child->Left;
458 : : }
459 : 3692811 : Storage_DEALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
460 : : }
461 : : }
462 : : else
463 : : {
464 : 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);
465 : : }
466 : 6438130 : }
467 : :
468 : :
469 : : /*
470 : : IsEmptyTree - returns true if SymbolTree, t, is empty.
471 : : */
472 : :
473 : 544555 : extern "C" bool SymbolKey_IsEmptyTree (SymbolKey_SymbolTree t)
474 : : {
475 : 544555 : return t->Left == NULL;
476 : : /* static analysis guarentees a RETURN statement will be used before here. */
477 : : __builtin_unreachable ();
478 : : }
479 : :
480 : :
481 : : /*
482 : : DoesTreeContainAny - returns true if SymbolTree, t, contains any
483 : : symbols which in turn return true when procedure,
484 : : P, is called with a symbol as its parameter.
485 : : The SymbolTree root is empty apart from the field,
486 : : Left, hence we need two procedures.
487 : : */
488 : :
489 : 1508136 : extern "C" bool SymbolKey_DoesTreeContainAny (SymbolKey_SymbolTree t, SymbolKey_IsSymbol P)
490 : : {
491 : 1508136 : return SearchForAny (t->Left, P);
492 : : /* static analysis guarentees a RETURN statement will be used before here. */
493 : : __builtin_unreachable ();
494 : : }
495 : :
496 : :
497 : : /*
498 : : ForeachNodeDo - for each node in SymbolTree, t, a procedure, P,
499 : : is called with the node symbol as its parameter.
500 : : The tree root node only contains a legal Left pointer,
501 : : therefore we need two procedures to examine this tree.
502 : : */
503 : :
504 : 3712901 : extern "C" void SymbolKey_ForeachNodeDo (SymbolKey_SymbolTree t, SymbolKey_PerformOperation P)
505 : : {
506 : 3712901 : SearchAndDo (t->Left, P);
507 : 3712901 : }
508 : :
509 : :
510 : : /*
511 : : ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
512 : : */
513 : :
514 : 0 : extern "C" bool SymbolKey_ContainsSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
515 : : {
516 : 0 : SymbolKey_SymbolTree father;
517 : 0 : SymbolKey_SymbolTree child;
518 : :
519 : 0 : FindNodeParentInTree (t, NameKey, &child, &father);
520 : 0 : return child != NULL;
521 : : /* static analysis guarentees a RETURN statement will be used before here. */
522 : : __builtin_unreachable ();
523 : : }
524 : :
525 : :
526 : : /*
527 : : NoOfNodes - returns the number of nodes in the tree t.
528 : : */
529 : :
530 : 72 : extern "C" unsigned int SymbolKey_NoOfNodes (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition)
531 : : {
532 : 72 : return CountNodes (t->Left, condition, 0);
533 : : /* static analysis guarentees a RETURN statement will be used before here. */
534 : : __builtin_unreachable ();
535 : : }
536 : :
537 : :
538 : : /*
539 : : ForeachNodeConditionDo - traverse the tree t and for any node which satisfied
540 : : condition call P.
541 : : */
542 : :
543 : 72 : extern "C" void SymbolKey_ForeachNodeConditionDo (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P)
544 : : {
545 : 72 : if (t != NULL)
546 : : {
547 : 72 : Assertion_Assert (t->Right == NULL);
548 : 72 : SearchConditional (t->Left, condition, P);
549 : : }
550 : 72 : }
551 : :
552 : 16817 : extern "C" void _M2_SymbolKey_init (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
553 : : {
554 : 16817 : }
555 : :
556 : 0 : extern "C" void _M2_SymbolKey_fini (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
557 : : {
558 : 0 : }
|
