Princeton University
COS 217: Introduction to Programming Systems

Assignment 2: A Symbol Table ADT

Purpose

The purpose of this assignment is to help you learn/review (1) aspects of advanced C programming, and (2) how to create abstract data types (ADTs) in C. It will also give you the opportunity to gain more experience with the GNU/UNIX programming tools, especially Emacs, gdb, and gcc.

Background

A symbol table is an unordered collection of bindings. A binding consists of a key and a value. A key is a string that uniquely identifies its binding; a value is data that is somehow pertinent to its key. A symbol table allows its client to insert (put) new bindings, to retrieve (get) the values of bindings with specified keys, and to remove bindings with specified keys. Symbol tables are used often in programming systems; compilers and assemblers use them extensively.

A hash table is a particularly efficient way to implement a symbol table. Section 2.9 of The Practice of Programming (Kernighan and Pike), chapter 8 of C Interfaces and Implementations (Hanson), and chapter 14 of Algorithms in C, Parts 1-4 (Sedgewick) describe hash tables.

Your Task

Your task in this assignment is to create an ADT named SymTable. Each instance of the SymTable ADT should be a symbol table. You should design your SymTable ADT so it is "generic." That is, you should design your SymTable so its values are void pointers, and thus can point to data of any type.

Subsequent assignments may ask you to create programs that are clients of your SymTable ADT.

The SymTable Interface

The SymTable interface should contain these function declarations:

SymTable_T SymTable_new(void);
void       SymTable_free(SymTable_T oSymTable);
int        SymTable_getLength(SymTable_T oSymTable);
int        SymTable_put(SymTable_T oSymTable, const char *pcKey, const void *pvValue);
int        SymTable_contains(SymTable_T oSymTable, const char *pcKey);
void      *SymTable_get(SymTable_T oSymTable, const char *pcKey);
int        SymTable_remove(SymTable_T oSymTable, const char *pcKey);
void       SymTable_map(SymTable_T oSymTable, 
                        void (*pfApply)(const char *pcKey, void *pvValue, void *pvExtra),
                        const void *pvExtra);

The SymTable_new function should return a new SymTable_T that contains no bindings.

The SymTable_free function should free all memory occupied by oSymTable.

The SymTable_getLength function should return the number of bindings in oSymTable. It should be a checked runtime error for oSymTable to be NULL.

The SymTable_put function should add a new binding to oSymTable consisting of key pcKey and value pvValue. It should return 1 (TRUE) if successful, and 0 (FALSE) otherwise. It should be a checked runtime error for oSymTable or pcKey to be NULL.

The SymTable_contains function should return 1 (TRUE) if oSymTable contains a binding whose key is pcKey, and 0 (FALSE) otherwise. It should be a checked runtime error for oSymTable or pcKey to be NULL.

The SymTable_get function should return the value of the binding within oSymTable whose key is pcKey, or NULL if no such binding exists. It should be a checked runtime error for oSymTable or pcKey to be NULL.

The SymTable_remove function should remove from oSymTable the binding whose key is pcKey. It should return 1 (TRUE) if successful, and 0 (FALSE) otherwise. It should be a checked runtime error for oSymTable or pcKey to be NULL.

The SymTable_map function should apply function *pfApply to each binding in oSymTable, passing pvExtra as an extra parameter. It should be a checked runtime error for oSymTable or pfApply to be NULL.

The SymTable Implementation

Your SymTable implementation should:

Be a hash table.
Contain 509 buckets initially.
Use a reasonable hash function. You are welcome to use this one:

unsigned int hash(const char *pcKey)
/* Return a hash code for pcKey.  Adapted from the Fall 2002 COS 217 
   lecture notes. */
{
   int i;
   unsigned int uiHash = 0U;
   for (i = 0; pcKey[i] != NULL; i++)
      uiHash = uiHash * 65599 + pcKey[i];
   return uiHash;
}

See page 578 of the Sedgewick textbook for an alternative.

Enforce checked runtime errors by calling the standard assert function.
Contain no "memory leaks." That is, your SymTable ADT should, when appropriate, free the memory that it previously dynamically allocated.
"Own" its keys. That is, the SymTable_put function should not simply store the value of pcKey within the binding that it creates. Rather, the SymTable_put function should make a copy of string pcKey, and store the address of that copy within the new binding. You will find the standard C functions strlen and malloc to be useful for making the copy.
Not "own" its values. Indeed it cannot own its values: since is cannot determine the size of its values, it cannot create copies of them.

Implementing those features is worth 90% of the assignment. To receive full credit for the assignment, your SymTable implementation should also:

Expand. That is, for efficiency your implementation should dynamically increase the number of buckets (and, necessarily, reposition all bindings) whenever the number of bindings becomes too large.

More precisely, page 126 of the Hanson textbook provides a sequence of integers that are appropriate bucket counts: 509, 1021, 2053, 4093, 8191, 16381, 32771, and 65521. When the SymTable_put function detects that the new binding count exceeds 509, it should increase the bucket count to 1021. When the function detects that the new binding count exceeds 1021, it should increase the bucket count to 2053. Etc. When SymTable_put detects that the new binding count exceeds 65521, it should not increase the bucket count. Thus 65521 is the maximum number of buckets that the SymTable should contain.

Logistics

You should develop on arizona, using Emacs to create source code and gdb to debug.

A minimal test program is available in the file /u/cs217/Assignment2/testsymtable.c. You may use it as a starting point for creating your own test programs.

Create a "readme" text file that contains:

Your name.
A description of whatever help (if any) you received from others while doing the assignment, and the names of any individuals with whom you collaborated, as prescribed by the course "Policies" web page.
The CPU times consumed by testsymtable.c when the given binding count is 100, 1000, 10000, and 100000. If the time consumed is more than 5 minutes, you may abort execution and report "Greater than 5 minutes."
The CPU times consumed by testsymtable.c when the given binding count is 100, 1000, 10000, and 100000 and your SymTable ADT does not dynamically increase the number of buckets. You can determine those times by temporarily commenting-out your expansion code. If the time consumed is more than 5 minutes, you may abort execution and report "Greater than 5 minutes."
(If you are submitting your work late) An indication of how many "free late days" you wish to apply to this assignment.
(Optionally) An indication of how much time you spent doing the assignment.
(Optionally) Your assessment of the assignment.
(Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.

Submit your work electronically on arizona via the command:

/u/cs217/bin/submit 2 symtable.h symtable.c readme

Grading

As always, we will grade your work on correctness and design, and will consider understandability to be an important aspect of good design. To encourage good coding practices, we will compile using "gcc -Wall -ansi -pedantic" and take off points based on warning messages during compilation.

Note: You will receive a better grade if you submit a working non-expanding SymTable ADT instead of a non-working expanding SymTable ADT. If your attempts to develop the expansion code fail, then leave the expansion code in your symtable.c file as comments, and describe your attempts in your readme file.

Princeton University COS 217: Introduction to Programming Systems