symtab.c

Go to the documentation of this file.
00001 /*****************************************************************************
00002  * @file                                                                     *
00003  *                                                                           *
00004  * Contains routines for creating and manipulating symbol tables.            *
00005  *                                                                           *
00006  *****************************************************************************/
00007 /* $Id: symtab.c,v 1.4 2005/04/27 22:44:10 seymour Exp $ */
00008 /* $UTK_Copyright: $ */
00009 
00010 #include<stdio.h>
00011 #include<stdlib.h>
00012 #include<string.h>
00013 
00014 #include"symtab.h"
00015 
00016 /*****************************************************************************
00017  * Globals and Function prototypes:                                          *
00018  *****************************************************************************/
00019 
00020 /* define which of the possible hashing functions to use.  */
00021 
00022 #define HASH(x) hash(x)
00023 
00024 unsigned int HashPJW(const char *);
00025 unsigned int hash(const char *);
00026 
00027 /*****************************************************************************
00028  *                                                                           *
00029  * Create a new symbol table with the given number of entries.  Return a     *
00030  * pointer to the table.                                                     *
00031  *                                                                           *
00032  * @param numentries -- the number of entries in the symbol table.  this     *
00033  *   does not limit the number of items the symbol table can hold since each *
00034  *   entry has a linked list of items that hash to that location.            *
00035  *                                                                           *
00036  * @returns a pointer to the new symbol table                                *
00037  *****************************************************************************/
00038 
00039 SYMTABLE *
00040 new_symtable(unsigned int numentries)
00041 {
00042   SYMTABLE *newtable;
00043   newtable = (SYMTABLE *) malloc(sizeof(SYMTABLE));
00044   if (!newtable)
00045     return NULL;
00046 
00047   newtable->num_entries = numentries;
00048   newtable->num_items = 0;
00049   newtable->entry = (HASHNODE **) calloc(numentries, sizeof(HASHNODE *));
00050 
00051   if (!newtable->entry) {
00052     free(newtable);
00053     return NULL;
00054   }
00055 
00056   return (newtable);
00057 }
00058 
00059 /*****************************************************************************
00060  *                                                                           *
00061  * Insert a node into the given table.                                       *
00062  *                                                                           *
00063  * now accepts entire symbol table as argument instead of just one entry.    *
00064  * this allows removing a lot of redundant code throughout the parser...     *
00065  * e.g. computing the hash index.  kgs 3/30/00                               *
00066  *                                                                           *
00067  * @param table -- the table into which the item should be stored            *
00068  * @param node_val -- pointer to the item to be inserted                     *
00069  * @param tag -- string key used to identify this item                       *
00070  *                                                                           *
00071  * @returns 0 on success, -1 on failure                                      *
00072  *                                                                           *
00073  *****************************************************************************/
00074 
00075 int 
00076 hash_insert(SYMTABLE * table, void *node_val, char *tag)
00077 {
00078   HASHNODE *newnode;
00079   int idx;
00080 
00081   if ((table == NULL) || (tag == NULL))
00082     return -1;
00083 
00084   idx = HASH(tag) % table->num_entries;
00085 
00086   newnode = (HASHNODE *) malloc(sizeof(HASHNODE));
00087   if (!newnode)
00088     return -1;
00089 
00090   newnode->tag = tag;
00091   newnode->item = node_val;
00092   newnode->next = table->entry[idx];
00093   table->entry[idx] = newnode;
00094 
00095   table->num_items++;
00096 
00097   return 0;
00098 }
00099 
00100 /*****************************************************************************
00101  *                                                                           *
00102  * This function removes the entry corresponding to the given tag.           *
00103  *                                                                           *
00104  * @param table -- the table from which the entry should be deleted          *
00105  * @param tag -- the key corresponding to the item to be deleted             *
00106  *                                                                           *
00107  * @returns the deleted node if found, otherwise returns NULL                *
00108  *                                                                           *
00109  *****************************************************************************/
00110 
00111 HASHNODE *
00112 hash_delete(SYMTABLE * table, char *tag)
00113 {
00114   HASHNODE *list, *prev;
00115   int idx;
00116 
00117   if ((table == NULL) || (tag == NULL))
00118     return NULL;
00119 
00120   idx = HASH(tag) % table->num_entries;
00121   list = table->entry[idx];
00122 
00123   for (prev = NULL; list; list = list->next) {
00124     if (list->tag == NULL)
00125       prev = list;
00126     else if (!strcmp(list->tag, tag)) {
00127       if (prev)
00128     prev->next = list->next;
00129       else
00130     table->entry[idx] = list->next;
00131 
00132       table->num_items--;
00133       return (list);
00134     }
00135 
00136     prev = list;
00137   }
00138 
00139   return NULL;          /* Not in list. */
00140 }
00141 
00142 /*****************************************************************************
00143  *                                                                           *
00144  * This is a specific lookup routine to match an id with                     *
00145  * its associated type.  I will need others for matching                     *
00146  * externals, intrinsics, etc.                                               *
00147  *                                                                           *
00148  * @param table -- the table to be searched for the given key                *
00149  * @param id -- the key to search for                                        *
00150  *                                                                           *
00151  * @returns a pointer to the item or NULL if not found                       *
00152  *                                                                           *
00153  *****************************************************************************/
00154 
00155 HASHNODE *
00156 hash_lookup(SYMTABLE * table, char *id)
00157 {
00158   int index;
00159   HASHNODE *hash_entry;
00160 
00161   if ((table == NULL) || (id == NULL))
00162     return NULL;
00163 
00164   index = HASH(id) % table->num_entries;
00165 
00166   hash_entry = search_hashlist(table->entry[index], id);
00167   if (hash_entry == NULL) {
00168 #ifdef SYM_DEBUG
00169     printf("Not in table.\n");
00170 #endif
00171     return NULL;
00172   } else {  /* Attempt to return the value pointed to by "type". */
00173 
00174 #ifdef SYM_DEBUG
00175     printf("In table.\n");
00176 #endif
00177     return (hash_entry);
00178   }
00179 }
00180 
00181 /*****************************************************************************
00182  *                                                                           *
00183  * If there is an entry corresponding to the given id in this list, return   *
00184  * a pointer to it.  otherwise return NULL.                                  *
00185  *                                                                           *
00186  * @param list -- the list to be searched for the given key                  *
00187  * @param id -- the key to search for                                        *
00188  *                                                                           *
00189  * @returns a pointer to the item or NULL if not found                       *
00190  *                                                                           *
00191  *****************************************************************************/
00192 
00193 HASHNODE *
00194 search_hashlist(HASHNODE * list, char *id)
00195 {
00196 
00197   if (id == NULL)
00198     return NULL;
00199 
00200   for (; list; list = list->next) {
00201     if (list->tag == NULL)
00202       continue;
00203     if (!strcmp(list->tag, id))
00204       return (list);
00205   }
00206 
00207   return NULL;          /* Not in list. */
00208 }
00209 
00210 /*****************************************************************************
00211  *                                                                           *
00212  * hash_dump                                                                 *
00213  *                                                                           *
00214  * dumps the contents of the hash table.                                     *
00215  *                                                                           *
00216  *****************************************************************************/
00217 
00218 void
00219 hash_dump(SYMTABLE *table, void (*dump_function)(char *, void*))
00220 {
00221   HASHNODE *tmp;
00222   int i;
00223 
00224   for(i=0;i<table->num_entries;i++) {
00225     for(tmp = table->entry[i]; tmp != NULL; tmp = tmp->next) {
00226       dump_function(tmp->tag, tmp->item);
00227     }
00228   }
00229 
00230   return;
00231 }
00232 
00233 /*****************************************************************************
00234  *                                                                           *
00235  *  Simple hash function: just add the ascii integer                         *
00236  *  values of each character in the string.                                  *
00237  *                                                                           *
00238  *  Added error check for null string and made some                          *
00239  *  other minor changes.  12/5/97  --Keith                                   *
00240  *                                                                           *
00241  * @param str -- the string to be hashed                                     *
00242  *                                                                           *
00243  * @returns the hashed value                                                 *
00244  *                                                                           *
00245  *****************************************************************************/
00246 
00247 unsigned int 
00248 hash(const char *str)
00249 {
00250   int sum = 0;
00251 
00252   if (str == NULL)
00253     return 0;
00254 
00255   while (*str)
00256     sum += *str++;
00257 
00258   return sum;
00259 }
00260 
00261 /*****************************************************************************
00262  *                                                                           *
00263  * An adaptation of Peter Weinberger's (PJW) generic hashing                 *
00264  * algorithm based on Allen Holub's version. Accepts a pointer               *
00265  * to a datum to be hashed and returns an unsigned integer.                  *
00266  *                                                                           *
00267  * @param datum -- the string to be hashed                                   *
00268  *                                                                           *
00269  * @returns the hashed value                                                 *
00270  *                                                                           *
00271  *****************************************************************************/
00272 #include <limits.h>
00273 #define BITS_IN_int     ( sizeof(int) * CHAR_BIT )
00274 #define THREE_QUARTERS  ((int) ((BITS_IN_int * 3) / 4))
00275 #define ONE_EIGHTH      ((int) (BITS_IN_int / 8))
00276 #define HIGH_BITS       ( ~((unsigned int)(~0) >> ONE_EIGHTH ))
00277 
00278 unsigned int 
00279 HashPJW(const char *datum)
00280 {
00281   unsigned int hash_value, i;
00282   for (hash_value = 0; *datum; ++datum) {
00283     hash_value = (hash_value << ONE_EIGHTH) + *datum;
00284     if ((i = hash_value & HIGH_BITS) != 0)
00285       hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
00286   }
00287   return (hash_value);
00288 }