gcc/m2/mc-boot/GsymbolKey.c

   1 /* do not edit automatically generated by mc from symbolKey.  */
   2 /* symbolKey.mod provides binary tree operations for storing symbols.
   3
   4 Copyright (C) 2015-2022 Free Software Foundation, Inc.
   5 Contributed by Gaius Mulley <gaius@glam.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 #   if !defined (PROC_D)
  26 #      define PROC_D
  27        typedef void (*PROC_t) (void);
  28        typedef struct { PROC_t proc; } PROC;
  29 #   endif
  30
  31 #   if !defined (FALSE)
  32 #      define FALSE (1==0)
  33 #   endif
  34
  35 #   include "GStorage.h"
  36 #if defined(__cplusplus)
  37 #   undef NULL
  38 #   define NULL 0
  39 #endif
  40 #define _symbolKey_H
  41 #define _symbolKey_C
  42
  43 #   include "GStorage.h"
  44 #   include "GStrIO.h"
  45 #   include "GNumberIO.h"
  46 #   include "GDebug.h"
  47 #   include "GnameKey.h"
  48
  49 #   define symbolKey_NulKey NULL
  50 typedef struct symbolKey_isSymbol_p symbolKey_isSymbol;
  51
  52 typedef struct symbolKey_performOperation_p symbolKey_performOperation;
  53
  54 typedef struct _T1_r _T1;
  55
  56 typedef _T1 *symbolKey_symbolTree;
  57
  58 typedef unsigned int (*symbolKey_isSymbol_t) (void *);
  59 struct symbolKey_isSymbol_p { symbolKey_isSymbol_t proc; };
  60
  61 typedef void (*symbolKey_performOperation_t) (void *);
  62 struct symbolKey_performOperation_p { symbolKey_performOperation_t proc; };
  63
  64 struct _T1_r {
  65                nameKey_Name name;
  66                void *key;
  67                symbolKey_symbolTree left;
  68                symbolKey_symbolTree right;
  69              };
  70
  71 extern "C" symbolKey_symbolTree symbolKey_initTree (void);
  72 extern "C" void symbolKey_killTree (symbolKey_symbolTree *t);
  73 extern "C" void * symbolKey_getSymKey (symbolKey_symbolTree t, nameKey_Name name);
  74 extern "C" void symbolKey_putSymKey (symbolKey_symbolTree t, nameKey_Name name, void * key);
  75
  76 /*
  77    delSymKey - deletes an entry in the binary tree.
  78
  79                NB in order for this to work we must ensure that the InitTree sets
  80                both left and right to NIL.
  81 */
  82
  83 extern "C" void symbolKey_delSymKey (symbolKey_symbolTree t, nameKey_Name name);
  84
  85 /*
  86    isEmptyTree - returns true if symbolTree, t, is empty.
  87 */
  88
  89 extern "C" unsigned int symbolKey_isEmptyTree (symbolKey_symbolTree t);
  90
  91 /*
  92    doesTreeContainAny - returns true if symbolTree, t, contains any
  93                         symbols which in turn return true when procedure,
  94                         p, is called with a symbol as its parameter.
  95                         The symbolTree root is empty apart from the field,
  96                         left, hence we need two procedures.
  97 */
  98
  99 extern "C" unsigned int symbolKey_doesTreeContainAny (symbolKey_symbolTree t, symbolKey_isSymbol p);
 100
 101 /*
 102    foreachNodeDo - for each node in symbolTree, t, a procedure, p,
 103                    is called with the node symbol as its parameter.
 104                    The tree root node only contains a legal left pointer,
 105                    therefore we need two procedures to examine this tree.
 106 */
 107
 108 extern "C" void symbolKey_foreachNodeDo (symbolKey_symbolTree t, symbolKey_performOperation p);
 109
 110 /*
 111    findNodeAndParentInTree - find a node, child, in a binary tree, t, with name equal to n.
 112                              if an entry is found, father is set to the node above child.
 113 */
 114
 115 static void findNodeAndParentInTree (symbolKey_symbolTree t, nameKey_Name n, symbolKey_symbolTree *child, symbolKey_symbolTree *father);
 116
 117 /*
 118    searchForAny - performs the search required for doesTreeContainAny.
 119                   The root node always contains a nul data value,
 120                   therefore we must skip over it.
 121 */
 122
 123 static unsigned int searchForAny (symbolKey_symbolTree t, symbolKey_isSymbol p);
 124
 125 /*
 126    searchAndDo - searches all the nodes in symbolTree, t, and
 127                  calls procedure, p, with a node as its parameter.
 128                  It traverse the tree in order.
 129 */
 130
 131 static void searchAndDo (symbolKey_symbolTree t, symbolKey_performOperation p);
 132
 133
 134 /*
 135    findNodeAndParentInTree - find a node, child, in a binary tree, t, with name equal to n.
 136                              if an entry is found, father is set to the node above child.
 137 */
 138
 139 static void findNodeAndParentInTree (symbolKey_symbolTree t, nameKey_Name n, symbolKey_symbolTree *child, symbolKey_symbolTree *father)
 140 {
 141   /* remember to skip the sentinal value and assign father and child  */
 142   (*father) = t;
 143   if (t == NULL)
 144     {
 145       Debug_Halt ((const char *) "parameter t should never be NIL", 31, 203, (const char *) "../../gcc-git-devel-modula2/gcc/m2/mc/symbolKey.mod", 51);
 146     }
 147   (*child) = t->left;
 148   if ((*child) != NULL)
 149     {
 150       do {
 151         if (n < (*child)->name)
 152           {
 153             (*father) = (*child);
 154             (*child) = (*child)->left;
 155           }
 156         else if (n > (*child)->name)
 157           {
 158             /* avoid dangling else.  */
 159             (*father) = (*child);
 160             (*child) = (*child)->right;
 161           }
 162       } while (! (((*child) == NULL) || (n == (*child)->name)));
 163     }
 164 }
 165
 166
 167 /*
 168    searchForAny - performs the search required for doesTreeContainAny.
 169                   The root node always contains a nul data value,
 170                   therefore we must skip over it.
 171 */
 172
 173 static unsigned int searchForAny (symbolKey_symbolTree t, symbolKey_isSymbol p)
 174 {
 175   if (t == NULL)
 176     {
 177       return FALSE;
 178     }
 179   else
 180     {
 181       return (((*p.proc) (t->key)) || (searchForAny (t->left, p))) || (searchForAny (t->right, p));
 182     }
 183   /* static analysis guarentees a RETURN statement will be used before here.  */
 184   __builtin_unreachable ();
 185 }
 186
 187
 188 /*
 189    searchAndDo - searches all the nodes in symbolTree, t, and
 190                  calls procedure, p, with a node as its parameter.
 191                  It traverse the tree in order.
 192 */
 193
 194 static void searchAndDo (symbolKey_symbolTree t, symbolKey_performOperation p)
 195 {
 196   if (t != NULL)
 197     {
 198       searchAndDo (t->right, p);
 199       (*p.proc) (t->key);
 200       searchAndDo (t->left, p);
 201     }
 202 }
 203
 204 extern "C" symbolKey_symbolTree symbolKey_initTree (void)
 205 {
 206   symbolKey_symbolTree t;
 207
 208   Storage_ALLOCATE ((void **) &t, sizeof (_T1));  /* The value entity  */
 209   t->left = NULL;
 210   t->right = NULL;
 211   return t;
 212   /* static analysis guarentees a RETURN statement will be used before here.  */
 213   __builtin_unreachable ();
 214 }
 215
 216 extern "C" void symbolKey_killTree (symbolKey_symbolTree *t)
 217 {
 218   if ((*t) != NULL)
 219     {
 220       symbolKey_killTree (&(*t)->left);
 221       symbolKey_killTree (&(*t)->right);
 222       Storage_DEALLOCATE ((void **) &(*t), sizeof (_T1));
 223       (*t) = NULL;
 224     }
 225 }
 226
 227 extern "C" void * symbolKey_getSymKey (symbolKey_symbolTree t, nameKey_Name name)
 228 {
 229   symbolKey_symbolTree father;
 230   symbolKey_symbolTree child;
 231
 232   if (t == NULL)
 233     {
 234       return symbolKey_NulKey;
 235     }
 236   else
 237     {
 238       findNodeAndParentInTree (t, name, &child, &father);
 239       if (child == NULL)
 240         {
 241           return symbolKey_NulKey;
 242         }
 243       else
 244         {
 245           return child->key;
 246         }
 247     }
 248   /* static analysis guarentees a RETURN statement will be used before here.  */
 249   __builtin_unreachable ();
 250 }
 251
 252 extern "C" void symbolKey_putSymKey (symbolKey_symbolTree t, nameKey_Name name, void * key)
 253 {
 254   symbolKey_symbolTree father;
 255   symbolKey_symbolTree child;
 256
 257   findNodeAndParentInTree (t, name, &child, &father);
 258   if (child == NULL)
 259     {
 260       /* no child found, now is name less than father or greater?  */
 261       if (father == t)
 262         {
 263           /* empty tree, add it to the left branch of t  */
 264           Storage_ALLOCATE ((void **) &child, sizeof (_T1));
 265           father->left = child;
 266         }
 267       else
 268         {
 269           if (name < father->name)
 270             {
 271               Storage_ALLOCATE ((void **) &child, sizeof (_T1));
 272               father->left = child;
 273             }
 274           else if (name > father->name)
 275             {
 276               /* avoid dangling else.  */
 277               Storage_ALLOCATE ((void **) &child, sizeof (_T1));
 278               father->right = child;
 279             }
 280         }
 281       child->right = NULL;
 282       child->left = NULL;
 283       child->key = key;
 284       child->name = name;
 285     }
 286   else
 287     {
 288       Debug_Halt ((const char *) "symbol already stored", 21, 119, (const char *) "../../gcc-git-devel-modula2/gcc/m2/mc/symbolKey.mod", 51);
 289     }
 290 }
 291
 292
 293 /*
 294    delSymKey - deletes an entry in the binary tree.
 295
 296                NB in order for this to work we must ensure that the InitTree sets
 297                both left and right to NIL.
 298 */
 299
 300 extern "C" void symbolKey_delSymKey (symbolKey_symbolTree t, nameKey_Name name)
 301 {
 302   symbolKey_symbolTree i;
 303   symbolKey_symbolTree child;
 304   symbolKey_symbolTree father;
 305
 306   findNodeAndParentInTree (t, name, &child, &father);  /* find father and child of the node  */
 307   if ((child != NULL) && (child->name == name))
 308     {
 309       /* Have found the node to be deleted  */
 310       if (father->right == child)
 311         {
 312           /* most branch of child^.left.  */
 313           if (child->left != NULL)
 314             {
 315               /* Scan for right most node of child^.left  */
 316               i = child->left;
 317               while (i->right != NULL)
 318                 {
 319                   i = i->right;
 320                 }
 321               i->right = child->right;
 322               father->right = child->left;
 323             }
 324           else
 325             {
 326               /* (as in a single linked list) to child^.right  */
 327               father->right = child->right;
 328             }
 329           Storage_DEALLOCATE ((void **) &child, sizeof (_T1));
 330         }
 331       else
 332         {
 333           /* branch of child^.right  */
 334           if (child->right != NULL)
 335             {
 336               /* Scan for left most node of child^.right  */
 337               i = child->right;
 338               while (i->left != NULL)
 339                 {
 340                   i = i->left;
 341                 }
 342               i->left = child->left;
 343               father->left = child->right;
 344             }
 345           else
 346             {
 347               /* (as in a single linked list) to child^.left.  */
 348               father->left = child->left;
 349             }
 350           Storage_DEALLOCATE ((void **) &child, sizeof (_T1));
 351         }
 352     }
 353   else
 354     {
 355       Debug_Halt ((const char *) "trying to delete a symbol that is not in the tree - the compiler never expects this to occur", 92, 186, (const char *) "../../gcc-git-devel-modula2/gcc/m2/mc/symbolKey.mod", 51);
 356     }
 357 }
 358
 359
 360 /*
 361    isEmptyTree - returns true if symbolTree, t, is empty.
 362 */
 363
 364 extern "C" unsigned int symbolKey_isEmptyTree (symbolKey_symbolTree t)
 365 {
 366   return t->left == NULL;
 367   /* static analysis guarentees a RETURN statement will be used before here.  */
 368   __builtin_unreachable ();
 369 }
 370
 371
 372 /*
 373    doesTreeContainAny - returns true if symbolTree, t, contains any
 374                         symbols which in turn return true when procedure,
 375                         p, is called with a symbol as its parameter.
 376                         The symbolTree root is empty apart from the field,
 377                         left, hence we need two procedures.
 378 */
 379
 380 extern "C" unsigned int symbolKey_doesTreeContainAny (symbolKey_symbolTree t, symbolKey_isSymbol p)
 381 {
 382   return searchForAny (t->left, p);
 383   /* static analysis guarentees a RETURN statement will be used before here.  */
 384   __builtin_unreachable ();
 385 }
 386
 387
 388 /*
 389    foreachNodeDo - for each node in symbolTree, t, a procedure, p,
 390                    is called with the node symbol as its parameter.
 391                    The tree root node only contains a legal left pointer,
 392                    therefore we need two procedures to examine this tree.
 393 */
 394
 395 extern "C" void symbolKey_foreachNodeDo (symbolKey_symbolTree t, symbolKey_performOperation p)
 396 {
 397   searchAndDo (t->left, p);
 398 }
 399
 400 extern "C" void _M2_symbolKey_init (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
 401 {
 402 }
 403
 404 extern "C" void _M2_symbolKey_finish (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
 405 {
 406 }