COS 217 Spring 1996. Implementing an ADT: Associative Tables

COS 217. Introduction to Programming Systems. Spring 1996.

Implementing an ADT: Associative Tables

Implement a slightly modified version of associative table abstract datatype that you used in the previous assignment.

/u/cs217/4new/newtable.h is the interface specification; you are to provide an implementation that conforms to this specification in an RCS file for table.c. The difference between newtable.h and table.h, which you used for your last assignment, is that Table_new requires two function arguments instead of one. The new argument,

int hash(const char *x)
is a hash function.

Your implementation must work with wf. It must also work with cw the variant of wf implemented by /u/cs217/4new/main.o. cw is built by linking /u/cs217/4new/main.o with /u/cs217/3/getword.o and a correct table.o; that is, by the command

lcc -o cw /u/cs217/4new/main.o /u/cs217/3/getword.o table.o
where table.o is your implementation. /u/cs217/4new/cw is the program built using Hanson's implementation, which is available in /u/cs217/4new/table.o. The only C source-code file you need to write for this assignment is table.c, derived from its RCS file, table.c,v. Use RCS to track the history of your code. During development, use a makefile that uses your table.o, /u/cs217/4new/main.o, and /u/cs217/3/getword.o as suggested above to build cw. You may, of course, use your own version of getword.o while you are developing your program, but the program you submit must work with Hanson's version.

Your table.c must not use any global or static variables. All variables must be locals or parameters. In addition, only casts between pointer types are permitted.

Your implementation must have no storage leaks. A storage leak is storage that you have allocated that is no longer accessible via some pointer or chain of pointers visible in your program. If your implementation of Table_free deallocates all of the storage that your other table functions allocate, you will have no leaks. Hanson's client, /u/cs217/4new/main.o, calls Table_free for every table it creates via Table_new, and it deallocates everything it allocates. Thus, there should be no storage allocated just before the program terminates, except for I/O buffers allocated by the functions in the standard I/O library.

Your implementation should not crash. We will deduct a substantial number of points for unannounced core dumps that can be blamed on your table.c. You must implement all of the checked runtime errors specified in /u/cs217/4new/newtable.h.

Submission

Submit your program electronically with a command like
/u/cs217/bin/submit 4 table.c,v
where the table.c,v is the RCS file for your your implementation of table. Do not submit a readme file; it is unnecessary because the RCS file gives table.c's author and modification history. Make sure your RCS file holds the latest revision when you submit it.

Due: submitted by 11:59pm, Mon. 3/4.

Copyright (c) 1994,1996 by David R. Hanson
Tue Feb 27 11:32:02 EST 1996