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     }
 213
 214     if (y != NULL) {
 215         symtab_entry_finalize(y);
 216     }
 217 }
 218
 219 /**
 220  * Searches for an entry in a binary tree.
 221  * @param p Root node
 222  * @param id Identifier (search key)
 223  */
 224 static symtab_entry *binary_search(symtab_entry *p, const char *id)
 225 {
 226     int r;
 227     while ((p != NULL) && ((r = strcmp(p->id, id)) != 0)) {
 228         p = (r < 0) ? p->left : p->right;
 229     }
 230     return p;
 231 }
 232
 233 /*---------------------------------------------------------------------------*/
 234
 235 static symtab_entry *lookup(symtab *st, const char *id, int recurse)
 236 {
 237     symtab_entry *e;
 238     do {
 239         e = binary_search(st->root, id);
 240         if (e != NULL) { return e; }
 241         st = st->parent;
 242     } while (recurse && st);
 243     return NULL;
 244 }
 245
 246 /**
 247  * Looks up the specified id in the current symbol table.
 248  */
 249 symtab_entry *symtab_lookup(const char *id)
 250 {
 251     return lookup(symtab_tos(), id, 0);
 252 }
 253
 254 /**
 255  * Looks up the specified id in the current symbol table.
 256  */
 257 symtab_entry *symtab_lookup_recursive(const char *id)
 258 {
 259     return lookup(symtab_tos(), id, 1);
 260 }
 261
 262 /**
 263  * Looks up the specified id in the global symbol table.
 264  */
 265 symtab_entry *symtab_global_lookup(const char *id)
 266 {
 267     return lookup(symtab_stack[0], id, 0);
 268 }
 269
 270 /**
 271  * Enters something into a symbol table.
 272  * @param id Identifier
 273  * @param type Type of symbol (*_SYMBOL)
 274  * @param def External definition (may be <code>NULL</code>)
 275  * @param flags Initial flags
 276  */
 277 symtab_entry *symtab_enter(const char *id, symbol_type type, astnode *def, int flags)
 278 {
 279     symtab *st = symtab_tos();
 280     /* See if this id already exists */
 281     symtab_entry *e = symtab_lookup(id);
 282     if (e != NULL) {
 283         /* Duplicate symbol. */
 284 //      printf("error: symtab_enter(): `%s' already exists\n", id);
 285         return NULL;
 286     }
 287 //  printf("symtab_enter(): '%s' @ %.8X\n", id, st);
 288     /* Allocate new entry */
 289     e = (symtab_entry *)malloc(sizeof(symtab_entry));
 290     if (e != NULL) {
 291         /* Set its fields */
 292         e->id = (char *)malloc(strlen(id)+1);
 293         if (e->id != NULL) {
 294             strcpy(e->id, id);
 295         }
 296         e->type = type;
 297         e->flags = flags;
 298         e->ref_count = 0;
 299         e->def = def;
 300         /* Zap! */
 301         e->struc.size = NULL;
 302         e->struc.fields = NULL;
 303         e->field.offset = NULL;
 304         e->field.size = NULL;
 305         e->left = NULL;
 306         e->right = NULL;
 307         e->parent = NULL;
 308         e->symtab = NULL;
 309         /* Put it into symbol table */
 310         if (st->root == NULL) {
 311             st->root = e;   /* This is the root element */
 312         }
 313         else {
 314         /* Insert entry in binary tree */
 315             binary_insert(st->root, e);
 316         }
 317     }
 318     /* Return the newly created symbol table entry */
 319     return e;
 320 }
 321
 322 /*---------------------------------------------------------------------------*/
 323
 324 /**
 325  * Finalizes a single symbol table entry.
 326  */
 327 static void symtab_entry_finalize(symtab_entry *e)
 328 {
 329     ordered_field_list *list;
 330     ordered_field_list *next;
 331 //  printf("symtab_finalize(): `%s'\n", e->id);
 332     /* Special finalizing */
 333     switch (e->type) {
 334         case LABEL_SYMBOL:
 335         break;
 336
 337         case CONSTANT_SYMBOL:
 338         astnode_finalize(e->def);
 339         break;
 340
 341         case MACRO_SYMBOL:
 342         astnode_finalize(e->def);
 343         break;
 344
 345         case STRUC_SYMBOL:
 346         case UNION_SYMBOL:
 347         case RECORD_SYMBOL:
 348         /* Free list of in-order field identifiers */
 349         for (list = e->struc.fields; list != NULL; list = next) {
 350             next = list->next;
 351             free(list);
 352         }
 353         symtab_finalize(e->symtab);
 354         astnode_finalize(e->struc.size);
 355         break;
 356
 357         case ENUM_SYMBOL:
 358         symtab_finalize(e->symtab);
 359         break;
 360
 361         case VAR_SYMBOL:
 362         astnode_finalize(e->def);
 363         astnode_finalize(e->field.offset);
 364         astnode_finalize(e->field.size);
 365         break;
 366
 367         case PROC_SYMBOL:
 368         break;
 369
 370         default:
 371         /* Nada */
 372         break;
 373     }
 374     /* Common finalizing */
 375     SAFE_FREE(e->id);
 376     SAFE_FREE(e);
 377 }
 378
 379 /**
 380  * Finalizes a symbol table entry recursively,
 381  * by first finalizing its children before finalizing itself.
 382  */
 383 static void symtab_entry_finalize_recursive(symtab_entry *e)
 384 {
 385     if (e == NULL) return;
 386     symtab_entry_finalize_recursive(e->left);
 387     symtab_entry_finalize_recursive(e->right);
 388     symtab_entry_finalize(e);
 389 }
 390
 391 /**
 392  * Finalizes a symbol table.
 393  * @param st The symbol table to finalize
 394  */
 395 void symtab_finalize(symtab *st)
 396 {
 397     if (st == NULL) return;
 398     symtab_entry_finalize_recursive(st->root);
 399     SAFE_FREE(st);
 400 }
 401
 402 /*---------------------------------------------------------------------------*/
 403
 404 /**
 405  * Gets top of symbol table stack.
 406  */
 407 symtab *symtab_tos()
 408 {
 409     if (stack_index == 0) { return NULL; }
 410     return symtab_stack[stack_index-1];
 411 }
 412
 413 /**
 414  * Creates a symbol table and pushes it on the symbol table stack.
 415  */
 416 symtab *symtab_create()
 417 {
 418     symtab *st = (symtab *)malloc(sizeof(symtab));
 419     if (st != NULL) {
 420         st->root = NULL;
 421         st->parent = symtab_tos();
 422         symtab_push(st);
 423     }
 424     return st;
 425 }
 426
 427 /**
 428  * Pushes a symbol table onto the stack.
 429  */
 430 void symtab_push(symtab *st)
 431 {
 432     symtab_stack[stack_index++] = st;
 433 }
 434
 435 /**
 436  * Pops a symbol table from the stack.
 437  */
 438 symtab *symtab_pop()
 439 {
 440     return symtab_stack[--stack_index];
 441 }
 442
 443 /**
 444  * Removes an entry from the symbol table.
 445  * The memory associated with the entry is freed.
 446  * @param id Identifier of the entry to remove
 447  */
 448 void symtab_remove(const char *id)
 449 {
 450     symtab *st = symtab_tos();
 451     symtab_entry * e = symtab_lookup(id);
 452     if (e == NULL) { return; }  /* Nothing to remove */
 453     binary_delete(st, e);
 454 }
 455
 456 /*---------------------------------------------------------------------------*/
 457
 458 /**
 459  * Gets the number of entries of the given type.
 460  */
 461 int symtab_type_count(symbol_type type)
 462 {
 463     symtab *st = symtab_tos();
 464     int count = 0;
 465     symtab_entry *e = binary_min(st->root);
 466     while (e != NULL) {
 467         if ((type == ANY_SYMBOL) || (e->type == type)) {
 468             count++;
 469         }
 470         e = binary_succ(e);
 471     }
 472     return count;
 473 }
 474
 475 /**
 476  * Removes all entries of a given type from the symbol table.
 477  * The memory associated with the entries is freed.
 478  * @param type Type of symbols to remove
 479  */
 480 void symtab_remove_by_type(symbol_type type)
 481 {
 482     int i;
 483     /* Declare array to hold identifiers */
 484     symbol_ident_list list;
 485     /* List the entry identifiers */
 486     int count = symtab_list_type(type, &list);
 487     /* Remove the entries one by one */
 488     for (i=0; i<count; i++) {
 489         symtab_remove(list.idents[i]);
 490     }
 491     /* Finalize the array of identifiers */
 492     symtab_list_finalize(&list);
 493 }
 494
 495 /*---------------------------------------------------------------------------*/
 496 /*
 497 static void indent(int n)
 498 {
 499     int i;
 500     for (i=0; i<n; i++) {
 501         printf(" ");
 502     }
 503 }
 504 */
 505 /**
 506  *
 507  */
 508 static void symtab_entry_print_recursive(symtab_entry *e, int level)
 509 {
 510     if (e == NULL) { return; }
 511     //indent(level*2);
 512     symtab_entry_print_recursive(e->left, level+1);
 513     printf("%s\n", e->id);
 514     symtab_entry_print_recursive(e->right, level+1);
 515 }
 516
 517 /**
 518  *
 519  */
 520 void symtab_print()
 521 {
 522     symtab *st = symtab_tos();
 523     symtab_entry_print_recursive(st->root, 0);
 524 }
 525
 526 /*---------------------------------------------------------------------------*/
 527
 528 /**
 529  * Gets the number of entries in the symbol table.
 530  */
 531 int symtab_size()
 532 {
 533     return symtab_type_count(ANY_SYMBOL);
 534 }
 535
 536 /**
 537  * Lists the entries in a symbol table that are of a certain type.
 538  * @param type The symbol type (*_SYMBOL)
 539  * @param list List which will receive the array of identifiers
 540  */
 541 int symtab_list_type(symbol_type type, symbol_ident_list *list)
 542 {
 543     symtab *st = symtab_tos();
 544     int i = 0;
 545     list->size = symtab_type_count(type);
 546     list->idents = (char **)malloc(list->size * sizeof(char *) );
 547     if (list->idents != NULL) {
 548         symtab_entry *e = binary_min(st->root);
 549         while (e != NULL) {
 550             if ((type == ANY_SYMBOL) || (e->type == type)) {
 551                 /* Add to list */
 552                 list->idents[i] = (char *)malloc(strlen(e->id)+1);
 553                 if (list->idents[i] != NULL) {
 554                     strcpy(list->idents[i], e->id);
 555                     i++;
 556                 }
 557             }
 558             e = binary_succ(e);
 559         }
 560     }
 561     /* Return the number of entries listed */
 562     return i;
 563 }
 564
 565 /**
 566  * Lists all identifiers in the symbol table.
 567  */
 568 int symtab_list(symbol_ident_list *list)
 569 {
 570     return symtab_list_type(ANY_SYMBOL, list);
 571 }
 572
 573 /**
 574  * Lists all identifiers in the symbol table which has ONE OR MORE of the
 575  * given flags set.
 576  * If flag is zero it is ignored.
 577  */
 578 int symtab_list_flag(int flag, symbol_ident_list *list)
 579 {
 580     // TODO
 581     return 0;
 582 }
 583
 584 /**
 585  * Lists all identifiers in the symbol table of a given type which has
 586  * ONE OR MORE of the given flags set.
 587  * If flag is zero it is ignored.
 588  */
 589 int symtab_list_type_flag(symbol_type type, int flag, symbol_ident_list *list)
 590 {
 591     // TODO
 592     return 0;
 593 }
 594
 595 /**
 596  * Finalizes a list of identifiers.
 597  */
 598 void symtab_list_finalize(symbol_ident_list *list)
 599 {
 600     int i;
 601     for (i=0; i<list->size; i++) {
 602         SAFE_FREE(list->idents[i]);
 603     }
 604     SAFE_FREE(list->idents);
 605 }