symtab.c

   1 /*
   2  * $Id: symtab.c,v 1.7 2007/11/11 22:35:22 khansen Exp $
   3  * $Log: symtab.c,v $
   4  * Revision 1.7  2007/11/11 22:35:22  khansen
   5  * compile on mac
   6  *
   7  * Revision 1.6  2007/08/09 20:33:57  khansen
   8  * progress
   9  *
  10  * Revision 1.5  2007/08/08 22:40:43  khansen
  11  * recursive symbol table lookup
  12  *
  13  * Revision 1.4  2007/07/22 13:33:26  khansen
  14  * convert tabs to whitespaces
  15  *
  16  * Revision 1.3  2004/12/14 01:50:05  kenth
  17  * xorcyst 1.3.0
  18  *
  19  * Revision 1.2  2004/12/06 04:52:53  kenth
  20  * xorcyst 1.1.0
  21  *
  22  * Revision 1.1  2004/06/30 07:55:57  kenth
  23  * Initial revision
  24  *
  25  */
  26
  27 /**
  28  *    (C) 2004 Kent Hansen
  29  *
  30  *    The XORcyst is free software; you can redistribute it and/or modify
  31  *    it under the terms of the GNU General Public License as published by
  32  *    the Free Software Foundation; either version 2 of the License, or
  33  *    (at your option) any later version.
  34  *
  35  *    The XORcyst is distributed in the hope that it will be useful,
  36  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  37  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  38  *    GNU General Public License for more details.
  39  *
  40  *    You should have received a copy of the GNU General Public License
  41  *    along with The XORcyst; if not, write to the Free Software
  42  *    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  43  */
  44
  45 /**
  46  * This file contains functions for symbol table management.
  47  */
  48
  49 #include "symtab.h"
  50 #include <stdlib.h>
  51 #include <string.h>
  52 #include <stdio.h>
  53
  54 #define SAFE_FREE(a) if (a) { free(a); a = NULL; }
  55
  56 /* Stack of symbol tables */
  57 static symtab *symtab_stack[32] = { NULL };
  58 static int stack_index = 0;
  59
  60 static void symtab_entry_finalize(symtab_entry *);
  61
  62 /*---------------------------------------------------------------------------*/
  63
  64 /**
  65  * Gets the entry in the tree with minimum key.
  66  */
  67 static symtab_entry *binary_min(symtab_entry *p)
  68 {
  69     if (p == NULL) { return NULL; }
  70     while (p->left != NULL) {
  71         p = p->left;
  72     }
  73     return p;
  74 }
  75
  76 #if 0
  77 /**
  78  * Gets the entry in the tree with maximum key.
  79  */
  80 static symtab_entry *binary_max(symtab_entry *p)
  81 {
  82     if (p == NULL) { return NULL; }
  83     while (p->right != NULL) {
  84         p = p->right;
  85     }
  86     return p;
  87 }
  88 #endif
  89
  90 /**
  91  * Gets the successor of an entry.
  92  */
  93 static symtab_entry *binary_succ(symtab_entry *p)
  94 {
  95     symtab_entry *e;
  96     if (p == NULL) { return NULL; }
  97     if (p->right != NULL) { return binary_min(p->right); }
  98     e = p->parent;
  99     while ((e != NULL) && (p == e->right)) {
 100         p = e;
 101         e = e->parent;
 102     }
 103     return e;
 104 }
 105
 106 #if 0
 107 /**
 108  * Gets the predecessor of an entry.
 109  */
 110 static symtab_entry *binary_pred(symtab_entry *p)
 111 {
 112     symtab_entry *e;
 113     if (p == NULL) { return NULL; }
 114     if (p->left != NULL) { return binary_max(p->left); }
 115     e = p->parent;
 116     while ((e != NULL) && (p == e->left)) {
 117         p = e;
 118         e = e->parent;
 119     }
 120     return e;
 121 }
 122 #endif
 123
 124 /**
 125  * Inserts a new entry in a binary tree.
 126  * It's implemented recursively although that's a bad thing.
 127  * @param p The root of the tree
 128  * @param e A new entry to be inserted
 129  */
 130 static void binary_insert(symtab_entry *p, symtab_entry *e)
 131 {
 132     int r = strcmp(p->id, e->id);
 133     if (r < 0) {
 134         /* Follow left branch */
 135         if (p->left == NULL) {
 136             p->left = e;    /* Entry inserted successfully */
 137             e->parent = p;
 138         }
 139         else {
 140             binary_insert(p->left, e);   /* Call recursively */
 141         }
 142     }
 143     else if (r > 0) {
 144         /* Follow right branch */
 145         if (p->right == NULL) {
 146             p->right = e;   /* Entry inserted successfully */
 147             e->parent = p;
 148         }
 149         else {
 150             binary_insert(p->right, e);  /* Call recursively */
 151         }
 152     }
 153     else {
 154         /* Symbol already present */
 155     }
 156 }
 157
 158 /**
 159  * Deletes an entry from a binary tree.
 160  * @param p Root node
 161  * @param z Entry to delete
 162  */
 163 static void binary_delete(symtab *st, symtab_entry *z)
 164 {
 165     symtab_entry *y;
 166     symtab_entry *x;
 167     symtab_entry *p;
 168     if ((st == NULL) || (z == NULL)) { return; }
 169
 170     if ((z->left == NULL) || (z->right == NULL)) {
 171         y = z;
 172     }
 173     else {
 174         y = binary_succ(z);
 175     }
 176
 177     if (y->left != NULL) {
 178         x = y->left;
 179     }
 180     else {
 181         x = y->right;
 182     }
 183
 184     p = y->parent;
 185     if (x != NULL) {
 186         x->parent = p;
 187     }
 188
 189     if (p == NULL) {
 190         st->root = x;
 191     }
 192     else if (y == p->left) {
 193         p->left = x;
 194     }
 195     else {
 196         p->right = x;
 197     }
 198
 199     if (y != z) {
 200         symtab_finalize(z->symtab);
 201         SAFE_FREE(z->id);
 202         z->id = (char *)malloc(strlen(y->id)+1);
 203         if (z->id != NULL) {
 204             strcpy(z->id, y->id);
 205         }
 206         z->type = y->type;
 207         z->flags = y->flags;
 208         z->ref_count = y->ref_count;
 209         z->def = y->def;
 210         z->symtab = y->symtab;
 211         z->tag = y->tag;
 212     } else {
 213         symtab_entry_finalize(y);
 214     }
 215 }
 216
 217 /**
 218  * Searches for an entry in a binary tree.
 219  * @param p Root node
 220  * @param id Identifier (search key)
 221  */
 222 static symtab_entry *binary_search(symtab_entry *p, const char *id)
 223 {
 224     int r;
 225     while ((p != NULL) && ((r = strcmp(p->id, id)) != 0)) {
 226         p = (r < 0) ? p->left : p->right;
 227     }
 228     return p;
 229 }
 230
 231 /*---------------------------------------------------------------------------*/
 232
 233 static symtab_entry *lookup(symtab *st, const char *id, int recurse)
 234 {
 235     symtab_entry *e;
 236     do {
 237         e = binary_search(st->root, id);
 238         if (e != NULL) { return e; }
 239         st = st->parent;
 240     } while (recurse && st);
 241     return NULL;
 242 }
 243
 244 /**
 245  * Looks up the specified id in the current symbol table.
 246  */
 247 symtab_entry *symtab_lookup(const char *id)
 248 {
 249     return lookup(symtab_tos(), id, 0);
 250 }
 251
 252 /**
 253  * Looks up the specified id in the current symbol table.
 254  */
 255 symtab_entry *symtab_lookup_recursive(const char *id)
 256 {
 257     return lookup(symtab_tos(), id, 1);
 258 }
 259
 260 /**
 261  * Looks up the specified id in the global symbol table.
 262  */
 263 symtab_entry *symtab_global_lookup(const char *id)
 264 {
 265     return lookup(symtab_stack[0], id, 0);
 266 }
 267
 268 /**
 269  * Enters something into a symbol table.
 270  * @param id Identifier
 271  * @param type Type of symbol (*_SYMBOL)
 272  * @param def External definition (may be <code>NULL</code>)
 273  * @param flags Initial flags
 274  */
 275 symtab_entry *symtab_enter(const char *id, symbol_type type, astnode *def, int flags)
 276 {
 277     symtab *st = symtab_tos();
 278     /* See if this id already exists */
 279     symtab_entry *e = symtab_lookup(id);
 280     if (e != NULL) {
 281         /* Duplicate symbol. */
 282 //      printf("error: symtab_enter(): `%s' already exists\n", id);
 283         return NULL;
 284     }
 285 //  printf("symtab_enter(): '%s' @ %.8X\n", id, st);
 286     /* Allocate new entry */
 287     e = (symtab_entry *)malloc(sizeof(symtab_entry));
 288     if (e != NULL) {
 289         /* Set its fields */
 290         e->id = (char *)malloc(strlen(id)+1);
 291         if (e->id != NULL) {
 292             strcpy(e->id, id);
 293         }
 294         e->type = type;
 295         e->flags = flags;
 296         e->ref_count = 0;
 297         e->def = def;
 298         /* Zap! */
 299         e->struc.size = NULL;
 300         e->struc.fields = NULL;
 301         e->field.offset = NULL;
 302         e->field.size = NULL;
 303         e->left = NULL;
 304         e->right = NULL;
 305         e->parent = NULL;
 306         e->symtab = NULL;
 307         /* Put it into symbol table */
 308         if (st->root == NULL) {
 309             st->root = e;   /* This is the root element */
 310         }
 311         else {
 312         /* Insert entry in binary tree */
 313             binary_insert(st->root, e);
 314         }
 315     }
 316     /* Return the newly created symbol table entry */
 317     return e;
 318 }
 319
 320 /*---------------------------------------------------------------------------*/
 321
 322 /**
 323  * Finalizes a single symbol table entry.
 324  */
 325 static void symtab_entry_finalize(symtab_entry *e)
 326 {
 327     ordered_field_list *list;
 328     ordered_field_list *next;
 329 //  printf("symtab_finalize(): `%s'\n", e->id);
 330     /* Special finalizing */
 331     switch (e->type) {
 332         case LABEL_SYMBOL:
 333         break;
 334
 335         case CONSTANT_SYMBOL:
 336         astnode_finalize(e->def);
 337         break;
 338
 339         case MACRO_SYMBOL:
 340         astnode_finalize(e->def);
 341         break;
 342
 343         case STRUC_SYMBOL:
 344         case UNION_SYMBOL:
 345         case RECORD_SYMBOL:
 346         /* Free list of in-order field identifiers */
 347         for (list = e->struc.fields; list != NULL; list = next) {
 348             next = list->next;
 349             free(list);
 350         }
 351         symtab_finalize(e->symtab);
 352         astnode_finalize(e->struc.size);
 353         break;
 354
 355         case ENUM_SYMBOL:
 356         symtab_finalize(e->symtab);
 357         break;
 358
 359         case VAR_SYMBOL:
 360         astnode_finalize(e->def);
 361         astnode_finalize(e->field.offset);
 362         astnode_finalize(e->field.size);
 363         break;
 364
 365         case PROC_SYMBOL:
 366         break;
 367
 368         default:
 369         /* Nada */
 370         break;
 371     }
 372     /* Common finalizing */
 373     SAFE_FREE(e->id);
 374     SAFE_FREE(e);
 375 }
 376
 377 /**
 378  * Finalizes a symbol table entry recursively,
 379  * by first finalizing its children before finalizing itself.
 380  */
 381 static void symtab_entry_finalize_recursive(symtab_entry *e)
 382 {
 383     if (e == NULL) return;
 384     symtab_entry_finalize_recursive(e->left);
 385     symtab_entry_finalize_recursive(e->right);
 386     symtab_entry_finalize(e);
 387 }
 388
 389 /**
 390  * Finalizes a symbol table.
 391  * @param st The symbol table to finalize
 392  */
 393 void symtab_finalize(symtab *st)
 394 {
 395     if (st == NULL) return;
 396     symtab_entry_finalize_recursive(st->root);
 397     SAFE_FREE(st);
 398 }
 399
 400 /*---------------------------------------------------------------------------*/
 401
 402 /**
 403  * Gets top of symbol table stack.
 404  */
 405 symtab *symtab_tos()
 406 {
 407     if (stack_index == 0) { return NULL; }
 408     return symtab_stack[stack_index-1];
 409 }
 410
 411 /**
 412  * Creates a symbol table and pushes it on the symbol table stack.
 413  */
 414 symtab *symtab_create()
 415 {
 416     symtab *st = (symtab *)malloc(sizeof(symtab));
 417     if (st != NULL) {
 418         st->root = NULL;
 419         st->parent = symtab_tos();
 420         symtab_push(st);
 421     }
 422     return st;
 423 }
 424
 425 /**
 426  * Pushes a symbol table onto the stack.
 427  */
 428 void symtab_push(symtab *st)
 429 {
 430     symtab_stack[stack_index++] = st;
 431 }
 432
 433 /**
 434  * Pops a symbol table from the stack.
 435  */
 436 symtab *symtab_pop()
 437 {
 438     return symtab_stack[--stack_index];
 439 }
 440
 441 /**
 442  * Removes an entry from the symbol table.
 443  * The memory associated with the entry is freed.
 444  * @param id Identifier of the entry to remove
 445  */
 446 void symtab_remove(const char *id)
 447 {
 448     symtab *st = symtab_tos();
 449     symtab_entry * e = symtab_lookup(id);
 450     if (e == NULL) { return; }  /* Nothing to remove */
 451     binary_delete(st, e);
 452 }
 453
 454 /*---------------------------------------------------------------------------*/
 455
 456 /**
 457  * Gets the number of entries of the given type.
 458  */
 459 int symtab_type_count(symbol_type type)
 460 {
 461     symtab *st = symtab_tos();
 462     int count = 0;
 463     symtab_entry *e = binary_min(st->root);
 464     while (e != NULL) {
 465         if ((type == ANY_SYMBOL) || (e->type == type)) {
 466             count++;
 467         }
 468         e = binary_succ(e);
 469     }
 470     return count;
 471 }
 472
 473 /**
 474  * Removes all entries of a given type from the symbol table.
 475  * The memory associated with the entries is freed.
 476  * @param type Type of symbols to remove
 477  */
 478 void symtab_remove_by_type(symbol_type type)
 479 {
 480     int i;
 481     /* Declare array to hold identifiers */
 482     symbol_ident_list list;
 483     /* List the entry identifiers */
 484     int count = symtab_list_type(type, &list);
 485     /* Remove the entries one by one */
 486     for (i=0; i<count; i++) {
 487         symtab_remove(list.idents[i]);
 488     }
 489     /* Finalize the array of identifiers */
 490     symtab_list_finalize(&list);
 491 }
 492
 493 /*---------------------------------------------------------------------------*/
 494 /*
 495 static void indent(int n)
 496 {
 497     int i;
 498     for (i=0; i<n; i++) {
 499         printf(" ");
 500     }
 501 }
 502 */
 503 /**
 504  *
 505  */
 506 static void symtab_entry_print_recursive(symtab_entry *e, int level)
 507 {
 508     if (e == NULL) { return; }
 509     //indent(level*2);
 510     symtab_entry_print_recursive(e->left, level+1);
 511     printf("%s\n", e->id);
 512     symtab_entry_print_recursive(e->right, level+1);
 513 }
 514
 515 /**
 516  *
 517  */
 518 void symtab_print()
 519 {
 520     symtab *st = symtab_tos();
 521     symtab_entry_print_recursive(st->root, 0);
 522 }
 523
 524 /*---------------------------------------------------------------------------*/
 525
 526 /**
 527  * Gets the number of entries in the symbol table.
 528  */
 529 int symtab_size()
 530 {
 531     return symtab_type_count(ANY_SYMBOL);
 532 }
 533
 534 /**
 535  * Lists the entries in a symbol table that are of a certain type.
 536  * @param type The symbol type (*_SYMBOL)
 537  * @param list List which will receive the array of identifiers
 538  */
 539 int symtab_list_type(symbol_type type, symbol_ident_list *list)
 540 {
 541     symtab *st = symtab_tos();
 542     int i = 0;
 543     list->size = symtab_type_count(type);
 544     list->idents = (char **)malloc(list->size * sizeof(char *) );
 545     if (list->idents != NULL) {
 546         symtab_entry *e = binary_min(st->root);
 547         while (e != NULL) {
 548             if ((type == ANY_SYMBOL) || (e->type == type)) {
 549                 /* Add to list */
 550                 list->idents[i] = (char *)malloc(strlen(e->id)+1);
 551                 if (list->idents[i] != NULL) {
 552                     strcpy(list->idents[i], e->id);
 553                     i++;
 554                 }
 555             }
 556             e = binary_succ(e);
 557         }
 558     }
 559     /* Return the number of entries listed */
 560     return i;
 561 }
 562
 563 /**
 564  * Lists all identifiers in the symbol table.
 565  */
 566 int symtab_list(symbol_ident_list *list)
 567 {
 568     return symtab_list_type(ANY_SYMBOL, list);
 569 }
 570
 571 /**
 572  * Lists all identifiers in the symbol table which has ONE OR MORE of the
 573  * given flags set.
 574  * If flag is zero it is ignored.
 575  */
 576 int symtab_list_flag(int flag, symbol_ident_list *list)
 577 {
 578     // TODO
 579     return 0;
 580 }
 581
 582 /**
 583  * Lists all identifiers in the symbol table of a given type which has
 584  * ONE OR MORE of the given flags set.
 585  * If flag is zero it is ignored.
 586  */
 587 int symtab_list_type_flag(symbol_type type, int flag, symbol_ident_list *list)
 588 {
 589     // TODO
 590     return 0;
 591 }
 592
 593 /**
 594  * Finalizes a list of identifiers.
 595  */
 596 void symtab_list_finalize(symbol_ident_list *list)
 597 {
 598     int i;
 599     for (i=0; i<list->size; i++) {
 600         SAFE_FREE(list->idents[i]);
 601     }
 602     SAFE_FREE(list->idents);
 603 }