/* do not edit automatically generated by mc from SymbolKey. */
/* SymbolKey.mod binary tree operations for storing symbols.
Copyright (C) 2001-2025 Free Software Foundation, Inc.
Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>.
This file is part of GNU Modula-2.
GNU Modula-2 is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
GNU Modula-2 is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU Modula-2; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include <stdbool.h>
# if !defined (PROC_D)
# define PROC_D
typedef void (*PROC_t) (void);
typedef struct { PROC_t proc; } PROC;
# endif
# if !defined (FALSE)
# define FALSE (1==0)
# endif
#include <stddef.h>
# include "GStorage.h"
#if defined(__cplusplus)
# undef NULL
# define NULL 0
#endif
#define _SymbolKey_C
#include "GSymbolKey.h"
# include "GStorage.h"
# include "GStrIO.h"
# include "GNumberIO.h"
# include "GNameKey.h"
# include "GAssertion.h"
# include "GDebug.h"
# define SymbolKey_NulKey 0
typedef struct SymbolKey_IsSymbol_p SymbolKey_IsSymbol;
typedef struct SymbolKey_PerformOperation_p SymbolKey_PerformOperation;
typedef struct SymbolKey_Node_r SymbolKey_Node;
typedef SymbolKey_Node *SymbolKey_SymbolTree__opaque;
struct SymbolKey_Node_r {
NameKey_Name KeyName;
unsigned int KeySym;
SymbolKey_SymbolTree__opaque Left;
SymbolKey_SymbolTree__opaque Right;
};
extern "C" void SymbolKey_InitTree (SymbolKey_SymbolTree *t);
extern "C" void SymbolKey_KillTree (SymbolKey_SymbolTree *t);
/*
ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
*/
extern "C" unsigned int SymbolKey_GetSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey);
/*
ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
*/
extern "C" void SymbolKey_PutSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey, unsigned int SymKey);
/*
DelSymKey - deletes an entry in the binary tree.
NB in order for this to work we must ensure that the InitTree sets
both Left and Right to NIL.
*/
extern "C" void SymbolKey_DelSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey);
/*
IsEmptyTree - returns true if SymbolTree, t, is empty.
*/
extern "C" bool SymbolKey_IsEmptyTree (SymbolKey_SymbolTree t);
/*
DoesTreeContainAny - returns true if SymbolTree, t, contains any
symbols which in turn return true when procedure,
P, is called with a symbol as its parameter.
The SymbolTree root is empty apart from the field,
Left, hence we need two procedures.
*/
extern "C" bool SymbolKey_DoesTreeContainAny (SymbolKey_SymbolTree t, SymbolKey_IsSymbol P);
/*
ForeachNodeDo - for each node in SymbolTree, t, a procedure, P,
is called with the node symbol as its parameter.
The tree root node only contains a legal Left pointer,
therefore we need two procedures to examine this tree.
*/
extern "C" void SymbolKey_ForeachNodeDo (SymbolKey_SymbolTree t, SymbolKey_PerformOperation P);
/*
ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
*/
extern "C" bool SymbolKey_ContainsSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey);
/*
NoOfNodes - returns the number of nodes in the tree t.
*/
extern "C" unsigned int SymbolKey_NoOfNodes (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition);
/*
ForeachNodeConditionDo - traverse the tree t and for any node which satisfied
condition call P.
*/
extern "C" void SymbolKey_ForeachNodeConditionDo (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P);
/*
FindNodeParentInTree - find a node, child, in a binary tree, t, with name equal to n.
if an entry is found, parent is set to the node above child.
*/
static void FindNodeParentInTree (SymbolKey_SymbolTree__opaque t, NameKey_Name n, SymbolKey_SymbolTree__opaque *child, SymbolKey_SymbolTree__opaque *parent);
/*
SearchForAny - performs the search required for DoesTreeContainAny.
The root node always contains a nul data value,
therefore we must skip over it.
*/
static bool SearchForAny (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol P);
/*
SearchAndDo - searches all the nodes in SymbolTree, t, and
calls procedure, P, with a node as its parameter.
It traverse the tree in order.
*/
static void SearchAndDo (SymbolKey_SymbolTree__opaque t, SymbolKey_PerformOperation P);
/*
CountNodes - wrapper for NoOfNodes.
*/
static unsigned int CountNodes (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, unsigned int count);
/*
SearchConditional - wrapper for ForeachNodeConditionDo.
*/
static void SearchConditional (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P);
/*
FindNodeParentInTree - find a node, child, in a binary tree, t, with name equal to n.
if an entry is found, parent is set to the node above child.
*/
static void FindNodeParentInTree (SymbolKey_SymbolTree__opaque t, NameKey_Name n, SymbolKey_SymbolTree__opaque *child, SymbolKey_SymbolTree__opaque *parent)
{
/* remember to skip the sentinal value and assign parent and child */
(*parent) = t;
if (t == NULL)
{
Debug_Halt ((const char *) "parameter t should never be NIL", 31, (const char *) "../../gcc/m2/gm2-compiler/SymbolKey.mod", 39, (const char *) "FindNodeParentInTree", 20, 241);
}
Assertion_Assert (t->Right == NULL);
(*child) = t->Left;
if ((*child) != NULL)
{
do {
if (n < (*child)->KeyName)
{
(*parent) = (*child);
(*child) = (*child)->Left;
}
else if (n > (*child)->KeyName)
{
/* avoid dangling else. */
(*parent) = (*child);
(*child) = (*child)->Right;
}
} while (! (((*child) == NULL) || (n == (*child)->KeyName)));
}
}
/*
SearchForAny - performs the search required for DoesTreeContainAny.
The root node always contains a nul data value,
therefore we must skip over it.
*/
static bool SearchForAny (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol P)
{
if (t == NULL)
{
return false;
}
else
{
return (((*P.proc) (t->KeySym)) || (SearchForAny (t->Left, P))) || (SearchForAny (t->Right, P));
}
/* static analysis guarentees a RETURN statement will be used before here. */
__builtin_unreachable ();
}
/*
SearchAndDo - searches all the nodes in SymbolTree, t, and
calls procedure, P, with a node as its parameter.
It traverse the tree in order.
*/
static void SearchAndDo (SymbolKey_SymbolTree__opaque t, SymbolKey_PerformOperation P)
{
if (t != NULL)
{
SearchAndDo (t->Right, P);
(*P.proc) (t->KeySym);
SearchAndDo (t->Left, P);
}
}
/*
CountNodes - wrapper for NoOfNodes.
*/
static unsigned int CountNodes (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, unsigned int count)
{
if (t != NULL)
{
if ((*condition.proc) (t->KeySym))
{
count += 1;
}
count = CountNodes (t->Left, condition, count);
count = CountNodes (t->Right, condition, count);
}
return count;
/* static analysis guarentees a RETURN statement will be used before here. */
__builtin_unreachable ();
}
/*
SearchConditional - wrapper for ForeachNodeConditionDo.
*/
static void SearchConditional (SymbolKey_SymbolTree__opaque t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P)
{
if (t != NULL)
{
SearchConditional (t->Right, condition, P);
if ((t->KeySym != 0) && ((*condition.proc) (t->KeySym)))
{
(*P.proc) (t->KeySym);
}
SearchConditional (t->Left, condition, P);
}
}
extern "C" void SymbolKey_InitTree (SymbolKey_SymbolTree *t)
{
Storage_ALLOCATE ((void **) &(*t), sizeof (SymbolKey_Node)); /* The value entity */
static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Left = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Right = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
}
extern "C" void SymbolKey_KillTree (SymbolKey_SymbolTree *t)
{
/*
we used to get problems compiling KillTree below - so it was split
into the two procedures below.
PROCEDURE KillTree (VAR t: SymbolTree) ;
BEGIN
IF t#NIL
THEN
Kill(t) ; Would like to place Kill in here but the compiler
gives a type incompatible error... so i've split
the procedure into two. - Problem i think with
VAR t at the top?
t := NIL
END
END KillTree ;
PROCEDURE Kill (t: SymbolTree) ;
BEGIN
IF t#NIL
THEN
Kill(t^.Left) ;
Kill(t^.Right) ;
DISPOSE(t)
END
END Kill ;
*/
if ((*t) != NULL)
{
SymbolKey_KillTree (reinterpret_cast<SymbolKey_SymbolTree *> (&static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Left));
SymbolKey_KillTree (reinterpret_cast<SymbolKey_SymbolTree *> (&static_cast<SymbolKey_SymbolTree__opaque> ((*t))->Right));
Storage_DEALLOCATE ((void **) &(*t), sizeof (SymbolKey_Node));
(*t) = static_cast<SymbolKey_SymbolTree> (NULL);
}
}
/*
ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
*/
extern "C" unsigned int SymbolKey_GetSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
{
SymbolKey_SymbolTree__opaque father;
SymbolKey_SymbolTree__opaque child;
FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father);
if (child == NULL)
{
return static_cast<unsigned int> (SymbolKey_NulKey);
}
else
{
return child->KeySym;
}
/* static analysis guarentees a RETURN statement will be used before here. */
__builtin_unreachable ();
}
/*
ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
*/
extern "C" void SymbolKey_PutSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey, unsigned int SymKey)
{
SymbolKey_SymbolTree__opaque father;
SymbolKey_SymbolTree__opaque child;
FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father);
if (child == NULL)
{
/* no child found, now is NameKey less than father or greater? */
if (father == t)
{
/* empty tree, add it to the left branch of t */
Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
father->Left = child;
}
else
{
if (NameKey < father->KeyName)
{
Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
father->Left = child;
}
else if (NameKey > father->KeyName)
{
/* avoid dangling else. */
Storage_ALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
father->Right = child;
}
}
child->Right = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
child->Left = static_cast<SymbolKey_SymbolTree__opaque> (NULL);
child->KeySym = SymKey;
child->KeyName = NameKey;
}
else
{
Debug_Halt ((const char *) "symbol already stored", 21, (const char *) "../../gcc/m2/gm2-compiler/SymbolKey.mod", 39, (const char *) "PutSymKey", 9, 156);
}
}
/*
DelSymKey - deletes an entry in the binary tree.
NB in order for this to work we must ensure that the InitTree sets
both Left and Right to NIL.
*/
extern "C" void SymbolKey_DelSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
{
SymbolKey_SymbolTree__opaque i;
SymbolKey_SymbolTree__opaque child;
SymbolKey_SymbolTree__opaque father;
FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father); /* find father and child of the node */
if ((child != NULL) && (child->KeyName == NameKey))
{
/* Have found the node to be deleted */
if (father->Right == child)
{
/* most branch of child^.Left. */
if (child->Left != NULL)
{
/* Scan for Right most node of child^.Left */
i = child->Left;
while (i->Right != NULL)
{
i = i->Right;
}
i->Right = child->Right;
father->Right = child->Left;
}
else
{
/* (as in a single linked list) to child^.Right */
father->Right = child->Right;
}
Storage_DEALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
}
else
{
/* branch of child^.Right */
if (child->Right != NULL)
{
/* Scan for Left most node of child^.Right */
i = child->Right;
while (i->Left != NULL)
{
i = i->Left;
}
i->Left = child->Left;
father->Left = child->Right;
}
else
{
/* (as in a single linked list) to child^.Left. */
father->Left = child->Left;
}
Storage_DEALLOCATE ((void **) &child, sizeof (SymbolKey_Node));
}
}
else
{
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 *) "../../gcc/m2/gm2-compiler/SymbolKey.mod", 39, (const char *) "DelSymKey", 9, 223);
}
}
/*
IsEmptyTree - returns true if SymbolTree, t, is empty.
*/
extern "C" bool SymbolKey_IsEmptyTree (SymbolKey_SymbolTree t)
{
return static_cast<SymbolKey_SymbolTree__opaque> (t)->Left == NULL;
/* static analysis guarentees a RETURN statement will be used before here. */
__builtin_unreachable ();
}
/*
DoesTreeContainAny - returns true if SymbolTree, t, contains any
symbols which in turn return true when procedure,
P, is called with a symbol as its parameter.
The SymbolTree root is empty apart from the field,
Left, hence we need two procedures.
*/
extern "C" bool SymbolKey_DoesTreeContainAny (SymbolKey_SymbolTree t, SymbolKey_IsSymbol P)
{
return SearchForAny (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, P);
/* static analysis guarentees a RETURN statement will be used before here. */
__builtin_unreachable ();
}
/*
ForeachNodeDo - for each node in SymbolTree, t, a procedure, P,
is called with the node symbol as its parameter.
The tree root node only contains a legal Left pointer,
therefore we need two procedures to examine this tree.
*/
extern "C" void SymbolKey_ForeachNodeDo (SymbolKey_SymbolTree t, SymbolKey_PerformOperation P)
{
SearchAndDo (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, P);
}
/*
ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey.
*/
extern "C" bool SymbolKey_ContainsSymKey (SymbolKey_SymbolTree t, NameKey_Name NameKey)
{
SymbolKey_SymbolTree__opaque father;
SymbolKey_SymbolTree__opaque child;
FindNodeParentInTree (static_cast<SymbolKey_SymbolTree__opaque> (t), NameKey, &child, &father);
return child != NULL;
/* static analysis guarentees a RETURN statement will be used before here. */
__builtin_unreachable ();
}
/*
NoOfNodes - returns the number of nodes in the tree t.
*/
extern "C" unsigned int SymbolKey_NoOfNodes (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition)
{
return CountNodes (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, condition, 0);
/* static analysis guarentees a RETURN statement will be used before here. */
__builtin_unreachable ();
}
/*
ForeachNodeConditionDo - traverse the tree t and for any node which satisfied
condition call P.
*/
extern "C" void SymbolKey_ForeachNodeConditionDo (SymbolKey_SymbolTree t, SymbolKey_IsSymbol condition, SymbolKey_PerformOperation P)
{
if (t != NULL)
{
Assertion_Assert (static_cast<SymbolKey_SymbolTree__opaque> (t)->Right == NULL);
SearchConditional (static_cast<SymbolKey_SymbolTree__opaque> (t)->Left, condition, P);
}
}
extern "C" void _M2_SymbolKey_init (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
{
}
extern "C" void _M2_SymbolKey_fini (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
{
}