symtab.cpp

/*
**  symtab.cpp
**
**  binary tree symbol table class definitions
**
**  By: Stephen R. Schmitt
*/

#include "stdafx.h"                             // generated by Visual C++ ver.6
#include "symtab.h"
 
/*---------------------------------------------------------------------------*
**  "search" searches for an entry in the symbol table.
**
**  returns:  a pointer to the entry if one is found, else
**            a NULL pointer is returned
*/
node *symtab::search( char *name,               // identifier
                      node *np )                // starting point
{
    int cmp;                                    // result of strcmp

    while( np != NULL )
    {
        cmp = strcmp( name, np->name );
        if( cmp == 0 )
            return np ;                         // found entry

        if( cmp < 0 )
            np = np->left;                      // try again
        else
            np = np->right;
   }
   return NULL;                                 // no entry found
}

/*---------------------------------------------------------------------------*
 *  "enter" adds a name to the symbol table.
 *
 *  returns:  a pointer to the entry just made
 */
node *symtab::enter( char *name,                // identifier
                     node **npp )               // starting point
{
    int cmp;                                    // result of strcmp
    node *new_nodep;                            // ptr to new entry
    node *np;                                   // ptr to node to test

    /*
    ** create the new node
    */
    new_nodep = new struct node;
    if( new_nodep == NULL )
    {
        cout << "Out of memory" << endl;
        return NULL;
    }

    new_nodep->name = new char[strlen( name ) + 1];
    if( new_nodep->name == NULL )
    {
        cout << "Out of memory" << endl;
        return NULL;
    }

    strcpy( new_nodep->name, name );
    new_nodep->left  = NULL;
    new_nodep->right = NULL;
    new_nodep->files = NULL;
    new_nodep->lines = NULL;

    /*
    ** search for insertion point
    */
    np = *npp;                                  // save start
    while( np != NULL )
    {
        cmp = strcmp( name, np->name );         // match?
        if( cmp == 0 )                          // yes
            return np;                          // no entry

        if( cmp < 0 )                           // try again
            npp = &(np->left);
        else
            npp = &(np->right);

        np = *npp;                              // next node
    }

    *npp = new_nodep;                           // save 
    return new_nodep;                           // pointer to new entry
}

/*---------------------------------------------------------------------------*
**  "add_instance" enters a line number to the list for the file name.
**
**  returns:  a pointer to list origin
**/
void symtab::add_instance( int line_no,          // of identifier
                           instance **orgpp )    // starting point 
{
    instance *new_ip, *ip;

    new_ip = new struct instance;
    if( new_ip == NULL )
    {
        cout << "Out of memory" << endl;
        return;
    }
    else
    {
        new_ip->line = line_no;
        new_ip->next = NULL;
    }

    ip = *orgpp;
    while( ip != NULL )                         // fine end of list
    {
        orgpp = &(ip->next);
        ip = *orgpp;
    }

    *orgpp = new_ip;
}

/*---------------------------------------------------------------------------*
**  "output" opens the output file and sends sorted table data.
**
**  returns:  nothing
*/
void symtab::output()
{
    outf.open( "xref.out" );
    if( !outf.is_open() )
    {
        cout << "\nCan't open output file." << endl;
        return;
    }

    print( Symbol_root );
    outf.close();
    cout << "\nDone - output in xref.out" << endl;
}

/*---------------------------------------------------------------------------*
**  "print" list cross reference table to stdout in alphabetical order.
**
**  returns:  nothing
*/
void symtab::print( node *np )                  // start here
{
    if( np == NULL )
        return;

    print( np->left );                          // do left sub-tree

    outf << np->name << "\n\n";                 // do this node
    print_file( np->files );

    print( np->right );                         // do right sub-tree
}

/*---------------------------------------------------------------------------*
**  "print_file" prints line numbers where an identifier was in a file.
**
**  returns:  nothing
*/
void symtab::print_file( node *fp )             // file node
{
    if( fp == NULL )                            // no more files
        return;

    print_file( fp->left );                     // do left sub-tree

    outf << "  " << fp->name                    // do this node 
         << "  lines:\n\n";
    print_instances( fp->lines );

    print_file( fp->right );                    // do right sub-tree
}

/*---------------------------------------------------------------------------*
**  "print_instances" prints line numbers for occurrences of identifier.
**
**  returns:  nothing
*/
void symtab::print_instances( instance *ip )    // start of list
{
    int i = 0;

    while( ip != NULL )                         // print line numbers
    {
        outf << setw( 8 ) << ip->line;
        ip = ip->next;
        i++;

        if( i >= 8 )                            // go to next line
        {
            outf <<  "\n";
            i = 0;
        }
    }

    outf << "\n" << endl;
}