Princeton University
COS 217: Introduction to Programming Systems

Assignment 3: A "TableFixed" ADT

Purpose

The purpose of this assignment is to help you learn how to create Abstract Data Types (ADTs) via the C programming language. It will also give you the opportunity to learn more about the GNU/UNIX programming tools, especially bash, Emacs, gcc, gdb, and make.

Background

A table is a set of bindings. Each binding consists of a key and a value. A key uniquely identifies its binding; a value is data that is somehow pertinent to its key. Programming systems use tables often. For example, compilers and assemblers use tables to relate symbols to their meanings.

Chapter 8 of the Hanson textbook describes the interface and implementation of a "Table" ADT, and also shows an example program that uses it. For this assignment you should create two ADTs that (collectively) are similar to Hanson's Table ADT, but are more specialized in the manner described below.

Part 1: The TableFixed ADT

In Part 1 of this assignment your task is to create an ADT named TableFixed. A TableFixed should be a table that considers all of its keys to be of the same fixed size.  The user should specify the size of a TableFixed's keys at the time the TableFixed is created.

A TableFixed should be able to handle keys of any fixed size. However, a TableFixed should be optimized so it can handle the most common key sizes particularly efficiently. Assume that the most common key sizes are 8, 12, and 16 bytes.

The Interface

The TableFixed interface should contain these function declarations: 

TableFixed_T  TableFixed_new(unsigned long ulEstLength, size_t uiKeySize);
void          TableFixed_free(TableFixed_T oTableFixed);
unsigned long TableFixed_length(TableFixed_T oTableFixed);
int           TableFixed_put(TableFixed_T oTableFixed, const void *pvKey, void *pvValue);
void         *TableFixed_getValue(TableFixed_T oTableFixed, const void *pvKey);
const void   *TableFixed_getKey(TableFixed_T oTableFixed, const void *pvKey);
int           TableFixed_remove(TableFixed_T oTableFixed, const void *pvKey);
void          TableFixed_toArrays(TableFixed_T oTableFixed, const void **ppvKeyArray, void **ppvValueArray);
void          TableFixed_map(TableFixed_T oTableFixed, 
                             void (*pfApply)(const void *pvKey, void **ppvValue, void *pvExtra),
                             void *pvExtra);

The TableFixed_new function should return a new TableFixed_T.  The parameter ulEstLength is an estimate of the maximum number of  bindings that the TableFixed_T will contain.  Each key of the TableFixed_T should contain uiKeySize bytes.

The TableFixed_free function should free the dynamically allocated memory in which oTableFixed is residing.  It should be a checked runtime error for oTableFixed to be NULL.

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

The TableFixed_put function should add a new binding to oTableFixed consisting of key *pvKey and value *pvValue.  It should reject the new binding if a binding whose key is *pvKey already exists in oTableFixed.  It should return 1 (TRUE) if successful, and 0 (FALSE) otherwise. It should be a checked runtime error for oTableFixed to be NULL.

The TableFixed_getValue function should return the address of the value of the binding within oTableFixed whose key is *pvKey, or NULL if no such binding exists. It should be a checked runtime error for oTableFixed to be NULL.

The TableFixed_getKey function should return the address of the key of the binding within oTableFixed whose key is *pvKey, or NULL if no such binding exists.

The TableFixed_remove function should remove from oTableFixed the binding whose key equals *pvKey.  It should return 1 (TRUE) if successful, and 0 (FALSE) otherwise.  It should be a checked runtime error for oTableFixed to be NULL.

The TableFixed_toArrays function should fill the array ppvKeyArray with oTableFixed's keys, and fill the array ppvValueArray with the corresponding values.  The arrays must contain at least TableFixed_length() elements. It should be a checked runtime error for oTableFixed, ppvKeyArray, or  ppvValueArray to be NULL.  It should be an unchecked runtime error for either ppvKeyArray or ppvValueArray to contain too little space.

The TableFixed_map function should apply function *pfApply to each binding in oTableFixed.  That is, for each binding in oTableFixed consisting of key pvKey and value pvValue, the function should call (*pfApply)(pvKey, &pvValue, pvExtra). It should be a checked runtime error for oTableFixed or pfApply to be NULL.

The Implementation

You should implement your TableFixed as a hash table. 

When using Hanson's Table ADT, the user typically supplies "hash" and "compare" functions via parameters to the Table_new function.  In contrast, when using the TableFixed ADT the user does not supply hash and compare functions.  Rather the TableFixed ADT supplies its own hash and compare functions based upon the specified key size.  More precisely...

You should define four hash functions: hashGeneric, hash8, hash12, and hash16. Given a key and its size, the hashGeneric function should loop through the bytes that comprise the key to form their sum, and should return the sum as the hash code for that key. The hash8 function should do the same, but should be optimized for keys of size 8. That optimization should consist of "unwinding the loop." Similarly the hash12 function should be optimized for keys of size 12, and the hash16 function should be optimized for keys of size 16.

You should also define four compare functions: compareGeneric, compare8, compare12, and compare16. The compareGeneric function should accept two keys and their size, and should loop through the bytes that comprise the keys to determine how they compare. It should return 0 if the keys are the same, and 1 if they are different. The compare8 function should do the same, but should be optimized for keys of size 8 by "unwinding the loop." Similarly compare12 should be optimized for keys consisting of 12 bytes, and compare16 should be optimized for keys of size 16.

The TableFixed_new function should should compute the number of buckets in the hash table based upon the specified estimated length; see the Hanson textbook for code that uses an estimated binding count to compute an appropriate number of buckets. Then, based upon the specified key size, the function should "install" the most appropriate hash and compare functions so they are available to the other functions of the TableFixed ADT.

Part 2: The TableFixedIter ADT

In Part 2 your task is to implement an ADT named TableFixedIter. TableFixedIter is an "iterator"; it should allow the user to iterate over the bindings of a specified TableFixed, while hiding the implementation of the TableFixed from the user.  At any given time, a TableFixedIter is either in an invalid state, or it has selected a particular binding of its TableFixed.

The Interface

The TableFixedIter interface should contain these function declarations:

TableFixedIter_T TableFixedIter_new(TableFixed_T oTableFixed); 
void             TableFixedIter_free(TableFixedIter_T oTableFixedIter); 
int              TableFixedIter_valid(TableFixedIter_T oTableFixedIter);
void             TableFixedIter_selectFirst(TableFixedIter_T oTableFixedIter);
void             TableFixedIter_selectNext(TableFixedIter_T oTableFixedIter);
const void      *TableFixedIter_selectedKey(TableFixedIter_T oTableFixedIter);

The TableFixedIter_new function should return a new TableFixedIter_T that can be used to iterate over oTableFixed's bindings.  After the function executes, the TableFixedIter should be in an invalid state.  It should be a checked runtime error for oTableFixed to be NULL.

The TableFixedIter_free function should free the dynamically allocated memory in which oTableFixedIter is residing.  It should be a checked runtime error for oTableFixedIter to be NULL.

The TableFixedIter_valid function should return 1 (TRUE) if oTableFixedIter is in a valid state, and 0 (FALSE) otherwise.  It should be a checked runtime error for oTableFixedIter to be NULL.

The TableFixedIter_selectFirst function should select the first binding of oTableFixedIter's TableFixed_T.  If there is indeed a first binding, then the function should place oTableFixedIter into a valid state; if the TableFixed_T is empty, the function should leave oTableFixedIter in an invalid state.  It should be a checked runtime error for oTableFixedIter to be NULL.

The TableFixedIter_selectNext function should select the next binding of oTableFixedIter's TableFixed_T.  If there is no next binding, then the function should place oTableFixedIter into an invalid state.  It should be a checked runtime error for oTableFixedIter to be NULL, or for oTableFixedIter to be in an invalid state when the function is called.

The TableFixedIter_selectedKey function should return the address of the key of oTableFixedIter's selected binding.  It should be a checked runtime error for oTableFixedIter to be NULL, or for oTableFixedIter to be in an invalid state.

The Implementation

A TableFixedIter may assume that no bindings will be added to or removed from its TableFixed during the "lifetime" of the TableFixedIter.

Logistics

You should develop on arizona using the bash shell. Use Emacs to create source code. Use the "make" tool to automate the build process. Use gdb to debug.

The file /u/cs217/Assignment3/testtablefixed.c contains a minimal test program that illustrates typical usage of the TableFixed and TableFixedIter ADTs.  You may use that test program as the basis for defining your own tests.

You should create four text files for submission: tablefixed.h, tablefixed.c, makefile, and readme. The tablefixed.h file should contain the interfaces of your TableFixed and TableFixedIter ADTs.  The tablefixed.c file should contain the implementations of the two ADTs.  The makefile file should contain commands to the "make" program indicating how it should build a program using the tablefixed.h, tablefixed.c, and testtablefixed.c files. The readme file should contain your name and any information that helps us to grade your work in the most favorable light.  You should include descriptions of any known bugs in your readme file.

Submit your work electronically via the command /u/cs217/bin/submit 3 tablefixed.h tablefixed.c makefile readme.

Grading

We will grade your work on correctness and understandability. Please see the statement of Assignment 1 for some guidelines concerning program understandability.  To encourage good coding practices, you will lose points for any warning messages generated by gcc during the compilation of your work.