KAIST
EE 209: Programming Structures for EE

Assignment 3: Customer Management Table


Purpose

The purpose of this assignment is to help you learn how to implement common data structures in C and how to exploit them to achieve modularity in a real-world application. It also will give you the opportunity to gain more experience with the GNU/Linux programming tools, especially bash, emacs, and gdb.


Rules

Dynamic resizing of an array in task 1 is "on your own" part of this assignment. This part is worth 15% of this assignment.


Background

A data structure is a way of organizing data for efficient operation. In this assignment, you will implement the required functionalities (register, unregister, and find) of a customer management program using the following data structures.


Your Task

You will implement and improve the customer data management API using various data structures. Your task in this assignment is threefold:


The customer_manager Interface

customer_manager is an API library for the customer data management, where the users can register the customer information and perform lookup operations to retrieve the purchase amount information.

The customer_manager interface introduces a structure type definition, DB_T:

The customer_manager interface is described in a file named customer_manager.h, and it contains these function declarations:

DB_T CreateCustomerDB(void);
void DestroyCustomerDB(DB_T d);
int RegisterCustomer(DB_T d, const char *id, const char *name, const int purchase);
int UnregisterCustomerByID(DB_T d, const char *id);
int UnregisterCustomerByName(DB_T d, const char *name);
int GetPurchaseByID(DB_T d, const char *id);
int GetPurchaseByName(DB_T d, const char *name);
typedef int (*FUNCPTR_T)(const char* id, const char* name, const int purchase);
int GetSumCustomerPurchase(DB_T d, FUNCPTR_T fp);

What each function does is as follows:


[Task 1] The customer_manager Array Implementation

The goal of the first task is to implement the customer_manager API using a dynamically resizable array. Array is the simplest data structure that works well for a small number of user items.

Your first customer_manager implementation should be as follows:

Implementation tips:

[Task 2] The customer_manager Hash Table Implementation

Unfortunately, using an array is slow when you deal with a large number of user items. Frequent reqistration and unregisteration of a user item creates many holes (empty elements) scattered across the array, which, in turn, makes these operations slow. Adding, deleting, and searching of a user item would eventually depend on linear search (unless you take extra measures to manage the holes separately).

We improve the performance of customer_manager operations with a hash table in this task. Actually, you would need two hash tables. One is for looking up a user item with ID as a key, and the other is for a lookup with a name as a key.

Your hash table-based customer_manager implementation should:

enum {HASH_MULTIPLIER = 65599};
...
static int hash_function(const char *pcKey, int iBucketCount)

/* Return a hash code for pcKey that is between 0 and iBucketCount-1,
   inclusive. Adapted from the EE209 lecture notes. */
{
   int i;
   unsigned int uiHash = 0U;
   for (i = 0; pcKey[i] != '\0'; i++)
      uiHash = uiHash * (unsigned int)HASH_MULTIPLIER
               + (unsigned int)pcKey[i];
   return (int)(uiHash % (unsigned int)iBucketCount);
}
Implementation tips: The following figure represents an example hash table-based customer_manager implementation (it uses the hash_function mentioned above).

[Task 3] Testing Your Library and Measuring the Performance

We provide testclient.c to test your implementations. It first checks the correctness of your library functions and measures the performance over various user items. Note that we may use other programs for grading.

To compile your code, do the following:

// test your array-based implementation
$ gcc209 -o testclient1 testclient.c customer_manager1.c
$ ./testclient1

// test your hash table-based implementation
$ gcc209 -o testclient2 testclient.c customer_manager2.c
$ ./testclient2

(Extra credit: 15% ) We will give an extra credit to the student whose implementation is the fastest among all students. We may use our own program to measure the performance.


Logistics

Develop in your own environment using emacs to create source code and gdb to debug. Make sure to compile with gcc209 and test your code on lab machine before submission.

Please follow the steps through Task 1 to Task 3 to complete the customer_manager API, and test your libraries.

We give two opportunities for getting an extra credit (each 15%).

Create a readme text file that contains:


Submission

Use KAIST KLMS to submit your assignments. Your submission should be one gzipped tar file whose name is

YourStudentID_assign3.tar.gz

Your submission need to include the following files:


Grading

We will grade your work on quality from the user's point of view and from the programmer's point of view. To encourage good coding practices, we will deduct points if gcc209 generates warning messages.

From the user's point of view, your module has quality if it behaves as it should.

In part, style is defined by the rules given in The Practice of Programming (Kernighan and Pike), as summarized by the Rules of Programming Style document. These additional rules apply:

Names: You should use a clear and consistent style for variable and function names. One example of such a style is to prefix each variable name with characters that indicate its type. For example, the prefix c might indicate that the variable is of type char, i might indicate int, pc might mean char*, ui might mean unsigned int, etc. But it is fine to use another style -- a style which does not include the type of a variable in its name -- as long as the result is a readable program.

Line lengths: Limit line lengths in your source code to 72 characters. Doing so allows us to print your work in two columns, thus saving paper.

Comments: Each source code file should begin with a comment that includes your name, the number of the assignment, and the name of the file.

Comments: Each function should begin with a comment that describes what the function does from the caller's point of view. The function comment should:

Comments: Each structure type definition and each structure field definition should have a comment that describes it.

Comments: The interface of each data structure should contain a comment that describes what an object of that type is. It would be reasonable to place that comment adjacent to the definition of the opaque pointer.