symtab.c

Go to the documentation of this file.

/*****************************************************************************
 * @file                                                                     *
 *                                                                           *
 * Contains routines for creating and manipulating symbol tables.            *
 *                                                                           *
 *****************************************************************************/
/* $Id: symtab.c,v 1.4 2005/04/27 22:44:10 seymour Exp $ */
/* $UTK_Copyright: $ */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#include"symtab.h"

/*****************************************************************************
 * Globals and Function prototypes:                                          *
 *****************************************************************************/

/* define which of the possible hashing functions to use.  */

#define HASH(x) hash(x)

unsigned int HashPJW(const char *);
unsigned int hash(const char *);

/*****************************************************************************
 *                                                                           *
 * Create a new symbol table with the given number of entries.  Return a     *
 * pointer to the table.                                                     *
 *                                                                           *
 * @param numentries -- the number of entries in the symbol table.  this     *
 *   does not limit the number of items the symbol table can hold since each *
 *   entry has a linked list of items that hash to that location.            *
 *                                                                           *
 * @returns a pointer to the new symbol table                                *
 *****************************************************************************/

SYMTABLE *
new_symtable(unsigned int numentries)
{
  SYMTABLE *newtable;
  newtable = (SYMTABLE *) malloc(sizeof(SYMTABLE));
  if (!newtable)
    return NULL;

  newtable->num_entries = numentries;
  newtable->num_items = 0;
  newtable->entry = (HASHNODE **) calloc(numentries, sizeof(HASHNODE *));

  if (!newtable->entry) {
    free(newtable);
    return NULL;
  }

  return (newtable);
}

/*****************************************************************************
 *                                                                           *
 * Insert a node into the given table.                                       *
 *                                                                           *
 * now accepts entire symbol table as argument instead of just one entry.    *
 * this allows removing a lot of redundant code throughout the parser...     *
 * e.g. computing the hash index.  kgs 3/30/00                               *
 *                                                                           *
 * @param table -- the table into which the item should be stored            *
 * @param node_val -- pointer to the item to be inserted                     *
 * @param tag -- string key used to identify this item                       *
 *                                                                           *
 * @returns 0 on success, -1 on failure                                      *
 *                                                                           *
 *****************************************************************************/

int 
hash_insert(SYMTABLE * table, void *node_val, char *tag)
{
  HASHNODE *newnode;
  int idx;

  if ((table == NULL) || (tag == NULL))
    return -1;

  idx = HASH(tag) % table->num_entries;

  newnode = (HASHNODE *) malloc(sizeof(HASHNODE));
  if (!newnode)
    return -1;

  newnode->tag = tag;
  newnode->item = node_val;
  newnode->next = table->entry[idx];
  table->entry[idx] = newnode;

  table->num_items++;

  return 0;
}

/*****************************************************************************
 *                                                                           *
 * This function removes the entry corresponding to the given tag.           *
 *                                                                           *
 * @param table -- the table from which the entry should be deleted          *
 * @param tag -- the key corresponding to the item to be deleted             *
 *                                                                           *
 * @returns the deleted node if found, otherwise returns NULL                *
 *                                                                           *
 *****************************************************************************/

HASHNODE *
hash_delete(SYMTABLE * table, char *tag)
{
  HASHNODE *list, *prev;
  int idx;

  if ((table == NULL) || (tag == NULL))
    return NULL;

  idx = HASH(tag) % table->num_entries;
  list = table->entry[idx];

  for (prev = NULL; list; list = list->next) {
    if (list->tag == NULL)
      prev = list;
    else if (!strcmp(list->tag, tag)) {
      if (prev)
    prev->next = list->next;
      else
    table->entry[idx] = list->next;

      table->num_items--;
      return (list);
    }

    prev = list;
  }

  return NULL;          /* Not in list. */
}

/*****************************************************************************
 *                                                                           *
 * This is a specific lookup routine to match an id with                     *
 * its associated type.  I will need others for matching                     *
 * externals, intrinsics, etc.                                               *
 *                                                                           *
 * @param table -- the table to be searched for the given key                *
 * @param id -- the key to search for                                        *
 *                                                                           *
 * @returns a pointer to the item or NULL if not found                       *
 *                                                                           *
 *****************************************************************************/

HASHNODE *
hash_lookup(SYMTABLE * table, char *id)
{
  int index;
  HASHNODE *hash_entry;

  if ((table == NULL) || (id == NULL))
    return NULL;

  index = HASH(id) % table->num_entries;

  hash_entry = search_hashlist(table->entry[index], id);
  if (hash_entry == NULL) {
#ifdef SYM_DEBUG
    printf("Not in table.\n");
#endif
    return NULL;
  } else {  /* Attempt to return the value pointed to by "type". */

#ifdef SYM_DEBUG
    printf("In table.\n");
#endif
    return (hash_entry);
  }
}

/*****************************************************************************
 *                                                                           *
 * If there is an entry corresponding to the given id in this list, return   *
 * a pointer to it.  otherwise return NULL.                                  *
 *                                                                           *
 * @param list -- the list to be searched for the given key                  *
 * @param id -- the key to search for                                        *
 *                                                                           *
 * @returns a pointer to the item or NULL if not found                       *
 *                                                                           *
 *****************************************************************************/

HASHNODE *
search_hashlist(HASHNODE * list, char *id)
{

  if (id == NULL)
    return NULL;

  for (; list; list = list->next) {
    if (list->tag == NULL)
      continue;
    if (!strcmp(list->tag, id))
      return (list);
  }

  return NULL;          /* Not in list. */
}

/*****************************************************************************
 *                                                                           *
 * hash_dump                                                                 *
 *                                                                           *
 * dumps the contents of the hash table.                                     *
 *                                                                           *
 *****************************************************************************/

void
hash_dump(SYMTABLE *table, void (*dump_function)(char *, void*))
{
  HASHNODE *tmp;
  int i;

  for(i=0;i<table->num_entries;i++) {
    for(tmp = table->entry[i]; tmp != NULL; tmp = tmp->next) {
      dump_function(tmp->tag, tmp->item);
    }
  }

  return;
}

/*****************************************************************************
 *                                                                           *
 *  Simple hash function: just add the ascii integer                         *
 *  values of each character in the string.                                  *
 *                                                                           *
 *  Added error check for null string and made some                          *
 *  other minor changes.  12/5/97  --Keith                                   *
 *                                                                           *
 * @param str -- the string to be hashed                                     *
 *                                                                           *
 * @returns the hashed value                                                 *
 *                                                                           *
 *****************************************************************************/

unsigned int 
hash(const char *str)
{
  int sum = 0;

  if (str == NULL)
    return 0;

  while (*str)
    sum += *str++;

  return sum;
}

/*****************************************************************************
 *                                                                           *
 * An adaptation of Peter Weinberger's (PJW) generic hashing                 *
 * algorithm based on Allen Holub's version. Accepts a pointer               *
 * to a datum to be hashed and returns an unsigned integer.                  *
 *                                                                           *
 * @param datum -- the string to be hashed                                   *
 *                                                                           *
 * @returns the hashed value                                                 *
 *                                                                           *
 *****************************************************************************/
#include <limits.h>
#define BITS_IN_int     ( sizeof(int) * CHAR_BIT )
#define THREE_QUARTERS  ((int) ((BITS_IN_int * 3) / 4))
#define ONE_EIGHTH      ((int) (BITS_IN_int / 8))
#define HIGH_BITS       ( ~((unsigned int)(~0) >> ONE_EIGHTH ))

unsigned int 
HashPJW(const char *datum)
{
  unsigned int hash_value, i;
  for (hash_value = 0; *datum; ++datum) {
    hash_value = (hash_value << ONE_EIGHTH) + *datum;
    if ((i = hash_value & HIGH_BITS) != 0)
      hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
  }
  return (hash_value);
}