Princeton University
COS 217: Introduction to Programming Systems

Assignment 1: 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 experience with the GNU/UNIX programming tools, especially Emacs 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.

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.

For this assignment your SymTable ADT should have a simple (but inefficient) implementation, as described below. The next assignment will ask you to create a more efficient SymTable implementation. Other 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_put(SymTable_T oSymTable, const char *pcKey, void *pvValue);
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),
                        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. You need not implement the SymTable_free function for this assignment; the next assignment will ask you to do so.

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_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. It should be a checked runtime error for oSymTable or pfApply to be NULL. You need not implement the SymTable_map function for this assignment; the next assignment will ask you to do so.

The SymTable Implementation

You should implement your SymTable ADT as a linked list, each of whose nodes contains one binding.

Your implementation should enforce checked runtime errors by calling the standard assert function.

A SymTable should "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 malloc and strlen to be useful for making the copy.

A SymTable should 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.

As noted above, you need not implement the SymTable_free or SymTable_map functions for this assignment. A subsequent assignment will ask you to implement them.

Your SymTable ADT need not free the memory that it previously dynamically allocated. That is, your ADT need not call the free function.

Logistics

We encourage you to develop on arizona using Emacs and gcc.

You should follow these steps:

Step 1: Create Source Code

First create a C header file named symtable.h containing the interface to your SymTable ADT. The interface should consist of typedef and a set of function declarations. Make sure you encapsulate the function declarations with "#ifndef ... #define ... #endif" macros to prevent double inclusion into a compilation unit. Then create a file named symtable.c containing the implementation of your ADT, that is, a set of function definitions. It should "#include" the interface file to insure that each function definition is consistent with its declaration.

Step 2: Compile, Assemble, and Link

A minimal test program is available in the file /u/cs217/Assignment1/testsymtable.c. You may use it as a starting point for creating your own test programs. Note that the program reports the CPU time consumed. Compile, assemble, and link symtable.c and testsymtable.c. Repeat step 1 if necessary.

Step 3: Execute

Execute the main function in testsymtable.c to test your SymTable ADT. Make sure your ADT passes all of the tests defined in testsymtable.c. Create and execute additional tests if necessary. Repeat steps 1 and 2 if necessary.

Step 4: Submit

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."
(Optionally) An indication of how much time you spent doing the assignment.
(Optionally) Your assessment of the assignment: Did it help you to learn? What did it help you to learn? Do you have any suggestions for improvement? Etc.
(Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.

Note that comments describing your code should not be in the readme file. Rather they should be integrated into the code itself.

Submit your work electronically on arizona via the command:

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

Grading

We will grade your work on functionality and design. We will consider understandability to be an important aspect of good design. See the Program Understandability document for some suggestions concerning program understandability. To encourage good coding practices, we will compile using "gcc -Wall -ansi -pedantic" and take off points based on warning messages during compilation.

Princeton University COS 217: Introduction to Programming Systems