Table Lookup - hashtab - example program in C

By: Emiley J Emailed: 1673 times Printed: 2153 times    

Latest comments
By: rohit kumar - how this program is work
By: Kirti - Hi..thx for the hadoop in
By: Spijker - I have altered the code a
By: ali mohammed - why we use the java in ne
By: ali mohammed - why we use the java in ne
By: mizhelle - when I exported the data
By: raul - no output as well, i'm ge
By: Rajesh - thanx very much...
By: Suindu De - Suppose we are executing

In this tutorial we will write the innards of a table-lookup package, to illustrate more aspects of structures. This code is typical of what might be found in the symbol table management routines of a macro processor or a compiler. For example, consider the #define statement. When a line like
   #define  IN  1
is encountered, the name IN and the replacement text 1 are stored in a table. Later, when the name IN appears in a statement like
   state = IN;
it must be replaced by 1.

There are two routines that manipulate the names and replacement texts. install(s,t) records the name s and the replacement text t in a table; s and t are just character strings. lookup(s) searches for s in the table, and returns a pointer to the place where it was found, or NULL if it wasn't there.

The algorithm is a hash-search - the incoming name is converted into a small non-negative integer, which is then used to index into an array of pointers. An array element points to the beginning of a linked list of blocks describing names that have that hash value. It is NULL if no names have hashed to that value.

A block in the list is a structure containing pointers to the name, the replacement text, and the next block in the list. A null next-pointer marks the end of the list.

   struct nlist {       /* table entry: */
       struct nlist *next;   /* next entry in chain */
       char *name;           /* defined name */
       char *defn;           /* replacement text */
   };
The pointer array is just
   #define HASHSIZE 101

   static struct nlist *hashtab[HASHSIZE];  /* pointer table */
The hashing function, which is used by both lookup and install, adds each character value in the string to a scrambled combination of the previous ones and returns the remainder modulo the array size. This is not the best possible hash function, but it is short and effective.
   /* hash:  form hash value for string s */
   unsigned hash(char *s)
   {
       unsigned hashval;

       for (hashval = 0; *s != '\0'; s++)
           hashval = *s + 31 * hashval;
       return hashval % HASHSIZE;
   }
Unsigned arithmetic ensures that the hash value is non-negative.

The hashing process produces a starting index in the array hashtab; if the string is to be found anywhere, it will be in the list of blocks beginning there. The search is performed by lookup. If lookup finds the entry already present, it returns a pointer to it; if not, it returns NULL.

   /* lookup:  look for s in hashtab */
   struct nlist *lookup(char *s)
   {
       struct nlist *np;

       for (np = hashtab[hash(s)];  np != NULL; np = np->next)
           if (strcmp(s, np->name) == 0)
               return np;     /* found */
       return NULL;           /* not found */
   }
The for loop in lookup is the standard idiom for walking along a linked list:
   for (ptr = head; ptr != NULL; ptr = ptr->next)
   ...
install uses lookup to determine whether the name being installed is already present; if so, the new definition will supersede the old one. Otherwise, a new entry is created. install returns NULL if for any reason there is no room for a new entry.
   struct nlist *lookup(char *);
   char *strdup(char *);

   /* install:  put (name, defn) in hashtab */
   struct nlist *install(char *name, char *defn)
   {
       struct nlist *np;
       unsigned hashval;

       if ((np = lookup(name)) == NULL) { /* not found */
           np = (struct nlist *) malloc(sizeof(*np));
           if (np == NULL || (np->name = strdup(name)) == NULL)
               return NULL;
           hashval = hash(name);
           np->next = hashtab[hashval];
           hashtab[hashval] = np;
       } else       /* already there */
           free((void *) np->defn);   /*free previous defn */
       if ((np->defn = strdup(defn)) == NULL)
           return NULL;
       return np;
   }

C Home | All C Tutorials | Latest C Tutorials

Sponsored Links

If this tutorial doesn't answer your question, or you have a specific question, just ask an expert here. Post your question to get a direct answer.



Bookmark and Share

Comments(0)


Be the first one to add a comment

Your name (required):


Your email(required, will not be shown to the public):


Your sites URL (optional):


Your comments:



More Tutorials by Emiley J
Password must include both numeric and alphabetic characters - Magento
What is Hadoop?
Returning multiple values from a web service
Tomcat and httpd configured in port 8080 and 80
Java Webservices using Netbeans and Tomcat
Java WebService connected to Database
How to Deploy a Java Web Service
Call a webservice in Java
Java WebService - Create your first web service in Java
package javax.jws does not exist
Getting Started with Android
HTML5 Location - getCurrentPosition() in HTML5
HTML5 Canvas - Using Canvas in HTML5
HTML5 - Introduction
HTML5 Video - Handling video in HTML5

More Tutorials in C
Sum of the elements of an array in C
Printing a simple histogram in C
Sorting an integer array in C
Find square and square root for a given number in C
Simple arithmetic calculations in C
Command-line arguments in C
Calculator in C
Passing double value to a function in C
Passing pointer to a function in C
Infix to Prefix And Postfix in C
while, do while and for loops in C
Unicode and UTF-8 in C
Formatting with printf in C
if, if...else and switch statements in C with samples
Statements in C

More Latest News
Most Viewed Articles (in C )
Listing Files and Directories sample program in C
Using realloc() Function in C
Open, Creat, Close, Unlink system calls sample program in C
lseek() sample program in C
Fopen and Getc implementation program in C
Using Shift Operators in C
assert() Function Example program in C
perror() Function - example program in C
Find square and square root for a given number in C
Line Counting sample program in C
Conditional Expressions in C
goto and labels in C
Example Calculator program in C - describing use of External Variables in C
Initialization of Variables in C
Character Pointers and Functions in C
Most Emailed Articles (in C)
Passing pointer to a function in C
File Copying in C
Arithmetic Operators in C
scanf and sscanf sample program in C
assert() Function Example program in C
perror() Function - example program in C
Infix to Prefix And Postfix in C
External Variables and Scope in C
Constants and escape sequences in C
register Variables in C
Tutorial on Complicated Declarations in C
Standard Input and Output in C
lseek() sample program in C
Listing Files and Directories sample program in C
Using memset(), memcpy(), and memmove() in C