CS 270, Fall 2014
Programming Assignment PA9B
Symbol Table

PA9B due Thursday, Nov. 20 at 11:59pm, no late submissions.

Goals of Assignment

• Learn about C structures (struct) and how to embed one structure within another.
• Learn how to use C pointers and the address-of operator &
• Learn how to allocate and free memory using malloc()/calloc()/free()
• Learn a little bit about hash tables
• Build a module that will be reused in future assignment(s).

Overview

In this assignment, you will use a hash table with chaining. You will learn more about hash tables in your Data Structures course. The data structures you use are already defined for you in symbol.h and symbol.c.

The hash function you will use computes an integer value from a string. More than one string may hash to the same value. However, a good hash function will minimize this. You can think of the hash value as an "alias" for the string. Thus, when searching for a string, you first search for the hash value (using integer comparison, which is fast) and only when you find an equal hash value, use strcasecmp() (much slower than integer comparison) to verify you have found the string of interest.

The symbol table contains a hash_table which is an array. The index into this array is calculated as index = hash-value % size-of-hash-table. A given index in the hash table contains a pointer to the head of a singly linked list of nodes containing symbols whose hash values share the same index.

There is a second, optional, table in the symbol table structure. It is a dynamically allocated arrayof of char* (C's version of strings), that allow a fast lookup of a symbols name given its address.

Getting Started

1. Create a directory for this assignment and cd to it
2. Copy the following files to the directory you created. It is easiest to right click on the link, and do a Save Target As.. for each of the files.
   • symbol.h (do no modify)
   • symbol.c (complete this file)
   • testSymbol.c (do not modify)
   • Makefile (do not modify)
3. Build the excutable by typing make
4. You now have a functional program, but it will not produce the corrrect results
5. Enter ./testSymbol. You will see a usage message which tells you how to use the program. You may also use help within the program to reprint the message
6. You are now ready to begin implementation. You have seven functions to implement. In the reference implmentation, approximately 90 line of code were added. Implement functions one at a time and test as you go.

Implementing symbol_init()

Implementing symbol_search()

1. compute the hash value for the name using symbol_hash()
2. compute the index based on (hash-value % table-size)
3. search the linked list to find the symbol. To speed thing up search first for the hash value. Only when the hash values match do you need to do a case independent string comparison.
4. return the information if the name is found, or NULL otherwise

Implementing symbol_add()

A hash table is designed to spread out the entries, often sacrificing space for speed. To thoroughtly test your function, you will need to force multiple names to occupy the same index in the hash table. Think about the pigeon hole princple from CS161, study the code and you should understand which CONSTANT to modify to test your code. Your code will be tested with a different value than the default. Hint: the change is in a file we told you not to modify. You may change that file for the purpose of testing.

Implementing the remaining functions

1. The function symbol_find_by_name() is only a few lines of code. Most of the work is done by symbol_search(). Test by using the command get in the test driver.
2. The function symbol_iterate() is only a few (10) lines of code. It consists of nested loops with the outer loop varying over the symbol table and the inner loop varying over the linked list at the current index. Using a function pointer is really straight forward. The actual line of code you will use is:

   
       (*fnc)(symbol, data);
       
       This is almost identical to calling a normal function named fnc() except
       that you would write: 
   
       fnc(symbol, data);
       
       You can test your function using the commands count/list in the test
       driver

3. The function symbol_reset() consist of two nested loops as you wrote for symbol_iterate(). For each node you will need to free any allocated memory. Test it with the command reset in the test driver.
4. The function symbol_term() may use symbol_reset to do most of the work. Be sure and deallocate the main symbol table as well. This will be tested when the test driver terminates.
5. Implement the remaining functions defined in the TODO list.

   ./testSymbol 0/1 < testFile