/* symtab.c

  @@@@    @   @  @    @   @@@@@    @@    @@@@@            @@@@
 @         @ @   @@  @@     @     @  @   @    @          @    @
  @@@@      @    @ @@ @     @    @    @  @@@@@           @
      @     @    @    @     @    @@@@@@  @    @   @@@    @
 @    @     @    @    @     @    @    @  @    @   @@@    @    @
  @@@@      @    @    @     @    @    @  @@@@@    @@@     @@@@

 *
 *This file contains a simple implementation of a symbol table
 * based on binary search trees.
 *
 * WARNING: Before calling "Insert" the function "Lookup" must be called
 * and should have failed to find the identifier.  This makes "Insert"
 * more efficient, without significant loss of efficiency in "Lookup".
 *
 * 08/28/91 ks - removed calls to error.c - Harakiri */

#include <stdio.h>
#include <strings.h>

#define SYMTAB_LOCAL
#include "symtab.h"
#include "tracing.h"

static SYMTABPTR Parent; /* Static variable set by "Lookup" 
                            subsequently needed by "Insert" */

static void Convert(VARLIST *head, VARLIST *tail, SYMTABPTR tree);

/* -------------------------------------------------------------------------- */
/* ---------------- INITSYMTAB:  INITIALIZE THE SYMBOL TABLE ---------------- */
/* -------------------------------------------------------------------------- */
void InitSymtab(void)
{
     if (PtraceSymtab) Entering("INITSYMTAB");
     SymRoot = NULL;
     if (PtraceSymtab) Leaving("INITSYMTAB");
}


/* -------------------------------------------------------------------------- */
/* --------------- LOOKUP:  LOOKUP AN IDENTIFIER IN THE TABLE --------------- */
/* -------------------------------------------------------------------------- */
/* Lookup an identifier in the symbol table.  If the identifier is
 * found, return a pointer to its attributes; otherwise, return nil.
 */
ATTRPTR Lookup(IDNAME id)
{
     int dir;
     SYMTABPTR cur = SymRoot;

     if (PtraceSymtab) Entering("LOOKUP");
     /*printf("looking for %s\n",id);*/
     Parent = NULL;
     while(cur != NULL){
          if((dir=strcmp(id,cur->attrs->id))<0){
               Parent = cur;
               cur = cur->left;
          }
          else if( dir > 0 ){
               Parent = cur;
               cur = cur->right;
          }
          else{ /* if cur->attrs->id = id */
                if (PtraceSymtab) Leaving("LOOKUP");
               return(cur->attrs);
               }
      }
     if (PtraceSymtab) Leaving("LOOKUP");
      return(NULL);
} /* Lookup */



/* -------------------------------------------------------------------------- */
/* --------------- INSERT:  INSERT AN IDENTIFIER IN THE TABLE --------------- */
/* -------------------------------------------------------------------------- */
/* Insert an identifier into the symbol table and return apointer to it.
 * This routine avoids doing redoing the work of the earlier "Lookup"
 * operation, by having "Lookup" place the essential information in astatic
 * global variable.  It is assumed that the "Lookup" operation failed to
 * find the identifier.
 */
void Insert(ATTRPTR attrs)
{
     SYMTABPTR cur;

     if (PtraceSymtab) Entering("INSERT");
     cur = stab_alloc();
     cur->left = NULL;
     cur->right = NULL;
     cur->attrs = attrs;
     if(Parent != NULL){
          if(strcmp(attrs->id,Parent->attrs->id)<0){
               Parent->left = cur;
               /*printf("inserting %s below (left) %s\n",attrs->id,Parent->attrs->id);*/
          }
          else{
               Parent->right = cur;
               /*printf("inserting %s below (right) %s\n",attrs->id,Parent->attrs->id);*/
          }
     }
     else{
          SymRoot = cur;
          /*printf("inserting %s at root\n",attrs->id);*/
     }
     if (PtraceSymtab) Leaving("INSERT");
} /* Insert */


/* ----------- GETVARS:  COLLECT ALL VARIABLES IN THE SYMBOLTABLE ----------- */
/* -------------------------------------------------------------------------- */
/* Convert binary tree into an alphabetized singly linked list. */
VARLIST GetVars()
{    VARLIST first = NULL;
     VARLIST last = NULL;

     if (PtraceSymtab) Entering("GETVARS");
     if(SymRoot != NULL) Convert(&first,&last, SymRoot);
     else {
          fprintf(stderr,
          "Warning (GetVars) No entries in the symbol table!\n");
        /*  exit(1); */
          }
     if (PtraceSymtab) Leaving("GETVARS");
     return(first);
}

static void Convert(VARLIST *head,VARLIST *tail, SYMTABPTR tree)
{     /* Note : Since we are modifying the head and tail of the list as
       * we descend into the tree we have to pass pointers to them (they
       * inturn, are pointers to variable lists)        */
VARLIST new;

     if (PtraceSymtab) Entering("CONVERT");

     /* recursively descend tree along the left side */
     if(tree->left != NULL) 
		Convert(head,tail,tree->left);

     /* now there are no more left chidren so place this node in list*/
     new = var_alloc();
     new->next = NULL;
     new->cur = tree->attrs;
     /*printf("Convert: placing %s in list\n",new->cur->id);*/

     if(*tail == NULL){ /* ie. an empty list */
          *tail = new;
          *head = *tail;
     }
     else {
          /* this is normal processing - we place the new entry at
           * the tail of the list.  That is, the-content-of-tail's
           * next pointer is first set to new, then tail is set
           * to point to new.
           */
          (*tail)->next = new;
          *tail = new;
     }

     /* recursively descend the right side */
     if(tree->right != NULL ) Convert(head,tail,tree->right);

     if (PtraceSymtab) Leaving("CONVERT");
} /* Convert */

/* -------------------------------------------------------------------------- */
/* some symbol table debugging routines:                                      */
/* -------------------------------------------------------------------------- */

/* dumpstab - a dump of the symboltable */
void DumpSymTab(void)
{
     printf(" \n");
     printf("Symbol table dump:\n");
     if(SymRoot == NULL ) printf("SymRoot is NULL => symbol table is empty\n");
     else RecDumpSymTab(SymRoot);
}
/* rec_dumpstab - a recursive dump of symboltable */
void RecDumpSymTab(SYMTABPTR tree)
{
     if(tree->left != NULL) 
	RecDumpSymTab(tree->left);
     if(tree != NULL ) printf("  %s\n",tree->attrs->id);
	if(tree->right != NULL) RecDumpSymTab(tree->right); 
}