Introduction

Often software is written for one purpose and then it is discovered that is useful in a variety of other situations. In this case, the code is frequently generalized and put into a library so that many different applications can use the library.

One of the tricks of making libraries generic is C is how to represent the items to be stored. The way this is done is C is to use a generic pointer type, void *, to refer to items of an un-known type.

A second way to make software re-usable is to provide the same API, but to use different algorithms and data structures to implement them. For example, an API might be to store and lookup items, but the underlying implementation might be a linked list, a hash table, or a tree.

In this assignment, you will be given an implementation of a program (intCount) that reads through a file consisting of multiple lines each containing one or more numbers. It counts the number of times each number appears in the file. After reading the entire file, each number found in the file and the number of times that number appeared.

The key bit of software to be re-used is the representation that stores the numbers and their frequency. The data is stored in an AVL tree. AVL tress are a type of binary tree that is balanced so the depth of any two leaf nodes differ by at most one. You will convert the AVL implementation to be able to store any data type not just integers.

In addition, you will implement an API that allows multiple different ways to store the data including AVL trees and hash tables.

Table API

These functions should be defined in a file table.c that is linked into any application that wishes to use the table abstraction.

int defineImplementation(tableImplementation *funcs, char *name)

Define an implementation of the table abstraction. The funcs parameter is a structure containing the addresses of the functions to implementation the various features of the table API. The name parameter is the name of the implementation (i.e. hash table). Return is 0 for success and -1 for error (including re-defining the name of an implementation).

tableADT createTable(char *implemenationName, compareFunc)

Create a new instance of the table using the desired implementation (inplementationName). Supply a comparison function to be used when the implementations need to compare two values. Returns NULL if the table can not be created (due to malloc errors, or an undefined implementation name).

The compare function takes two parameters a, and b. It should return 0 if the passed items are the same, -1 if a is less than b and +1 is a is greater than b.

void *insertTable(tableADT t, void *key, void *item)

Insert a new item with key value key into the table. On success the function should return the values passed in as item. On failure it should return null.

void *lookupTable(tableADT t, void *key)

Look for the item key in the passed table. If found, return the corresponding item.

int visitTableItems(tableADT t, visitorFunc)

Invoke the passed visitorFunc on every instance of the items stored in the table. Returns -1 if the implementation does not define this function, and the return value of the implementation’s visit function if defined.

int deleteTableItem(tableADT t, void *key)

Delete the item with the passed key from the table. Return 0 on success and –1 on failure.

int deleteTable(tableADT t, visitorFunc cleanupItem)

Delete the passed table. Return 0 on success. cleanupItem is a visitor function that is called on every node of the table just before it is deleted. If NULL is passed for this parameter, your implementation should not call a cleanupItem function for that table deletion.

Table Implementation API

Any implementation of the table abstraction must provide the functions defined in the tableImplementation struct in table.h

AVL Table Implementation

Almost all of this code is already provided for you in the intCount implementation. Mostly you will need to re-factor it to operate on void * pointers and to put it into a separate file (avl.c).

The visit function will need to traverse the AVL tree in the order left sub-tree, current node, right sub-tree. This will ensure that the intCount program will produce output in the same order as the original program.

Hash Table Implementation

You will also create a chained hash table implementation of the table abstraction. A chained hash table has a fixed number of elements in the hash array. To handle collisions, a linked list of items is maintained for each hash location. Your implementation includes all of the functions of the table abstraction. You will need to create a hash function that hashes a pointer. An easy function to get started is simply take the pointer address, convert it to an unsigned int and uses the % operator to get a value between 0 and hashTableSize-1.

Shared Libraries

Both the AVL and hash table implementations of the table abstraction will be stored in their own shared libraries. Each library will also contain an _init() function that calls the defineImplementation table API function to register each implementation when it is loaded into the program.

Your avl tree implementation of the table API should be in a file called avl.c and the hash table implementation in a file called hashTable.c. The shared libraries should be called libavl.so and libhashTable.so

Since the implementations of the table abstraction are stored in shared libraries, there are two ways they can be linked into the application. First, they can be loaded via the

-l<library> option to the linker. Second, they can be loaded (like a plugin) at runtime using the dlopen system call. If a user program wishes to use a specific implementation of the table abstraction, they may use either of these approaches.

The interface routines (table.c) should not be in a shared library, but should be compiled into table.o and linked into each application that uses the table abstraction.

Int Count

You should also re-factor intCount to use the table abstraction (with the avl representation) and turn this in as part of your assignment. To do this you will also need to modify the supplied Makefile to link into the application the table.o abstraction and the libavl.so shared library.