CMSC 15200 - Summer 2016

Homework #8: Due: Wednesday August 24th, 2016 @ 11:59pm

In this assignment you will handle the transactions for Tiny Savings and Loan, a small bank that saves and loans money out to customers. The bank tellers generate a stream of inputs like the following


  Alice joins trusted
  Alice deposits 100
  Bob joins untrusted
  Bob deposits 300
  Alice withdraws 50
  Alice withdraws 100
  Bob withdraws 100
  Charlie joins trusted
  Alice print
  Bob print
  Charlie print

You will take this stream of inputs, maintain the balance of each customer, and ensure that they do not withdraw too much money.

You will also save the state of the loan system when the program exits. When the program relaunches, all previous account information should be loaded again.

In order to do this you will have to write a lookup-table (i.e. a hashtable). You will then use that lookup table to build the banking application.

Hash Table

It will be easy to build the banking application if we have the right data structure.

A hash table is a collection of key/value pairs. We insert a new key/value pair with set. We retrieve the value with get. In this case we will use the customer’s name as the key to be hashed and their full Account as the value. To support clashes on hash values, we will implement a hash table with a linked list of entries. However, the keys must remain unique, even though the hash values might not be.

In this assignment, you will first build a hash table to store the accounts by name. The linked list entries for values are defined as:


  typdef struct entry {
    char* key;
    ValueType* value;
    struct entry* next;
  } Entry;

You will need to implement the Table struct. The hashtable library will be implemented in hashtable.h and hashtable.c. You must have at least the following functions:


  /*
   * Allocates and initializes a new hash table.
   * You can assume the table has 100 buckets.
   */
  Table* hashtable_mkTable();
  
  /*
   * Returns a newly allocated list of all the entries inside the hashtable.
   */
  Entry* hashtable_entriesSet(const Table* t); 
  
  /*
   * Does the table contain this key?
   */
  bool hashtable_contains(const Table* t, const char* key);
  
  /*
   * Returns the hash code for a key.
   * (See hashing algorithm below.)
   */
  int hashtable_hash(const char* key); 
  
  /*
   * Get the value associated to key.
   */
  ValueType* hashtable_get(const Table* t, const char* key); 
  
  /* 
   * Adds new key/value pair if the key doesn't exist yet.
   * If the key already exists, update the old value to the new value.
   * Returns a pointer to the old value if one existed, NULL otherwise.
   */
  ValueType* hashtable_set(Table* t, const char* key, ValueType* value); 
  
  /*
   * How many entries (key/value pairs) are in the table?
   * This is NOT how many buckets are in the table.
   */
  int hashtable_size(const Table* t);

Implementation

Your hash table must have the return type ValueType. The hash table code should know nothing about Accounts. You can typedef any type to ValueType at compile-time. For testing, you might want to typedef ValueType to be an int so that your hash table maps strings to int values:

typedef int ValueType;  // place this inside the hashtable.h file

This will make it easy to write tests (you won't have to make accounts to test your hash table). Write these test cases inside the test_hashtable.c file. Once you have tested your hashtable you can then change ValueType typedef to an Account (Yes, this will make your test_hashtable.c unable to compile, but that's fine once you are done testing). We will just check to make sure your hashtable was correctly tested inside test_hashtable.c. You will just submit this file along with the rest of your files. When you move to the next section you can typedef Accounts to ValueType and your code should work just the same. This is because hashtable.c doesn't actually need to know anything about the values that it stores. It will just need to find and return pointers them.

typedef Account ValueType;

You should create a header file called account.h that includes your struct and associated type definition. You then can include the header file inside your account.h file and your main source files. You should also have an account.c file that contains functions related to Accounts (e.g., mkAccount). You should decide what functions should go inside this library.

Note: Account should be typedef'd to struct account.

Testing

Testing each function in your hash table in this case may be annoying because each test will necessarily require the use of several functions (e.g. you will have to set many times to test size). Feel free to just have one or two large tests.

Hashing

Follow this recipe for computing the hash code for a string:

  • Initialize an unsigned long int result to 17 (unsigned long res = 17;).
  • Loop over the characters in the string. For every character, set the result to be 37 times itself plus the ASCII numeric value of the character.
(This hashing algorithm recipe is from Effective Java by Joshua Bloch.)

For example, the hash code for the word FORK, given that the ASCII values of the characters in FORK are 70, 79, 82 and 75, is as follows: 

res = 17
res = 37*17+70     = 699
res = 37*699+79    = 25942
res = 37*25942+82  = 959936
res = 37*959936+75 = 35517707
(As you can see, these hash codes get large rather quickly.)

To identify the bucket of FORK in a hash table of size, say, 33, you compute the remainder of the hash code when divided by 33. In this case 35517707%33 is 5, so FORK would be inserted into and/or located in the bucket with index 5 (the sixth bucket in the table).

You can assume that the table in this assignment has 100 buckets inside.

Tiny Savings and Loan

Now that we have a hash table, writing this application should be much easier. We strongly recommend that you don’t start writing this part of the homework until you are confident that your hash table works.

The input stream from Tiny Savings and Loan works can have the actions:
joins, deposits, withdraws, print.
In each case the action is preceded by the name of the account holder and optionally followed by some extra information (such as a balance). These actions have the following rules.

  • Anyone may open an account. When they open an account a credit check is performed. If they pass the credit check then they are marked as “trusted”, otherwise they are “untrusted”.

    Name joins trusted/untrusted

  • Anyone may deposit funds. This increases their balance by the amount listed.

    Name deposits amount

  • Anyone may withdraw their own funds. This decreases their balance by the amount listed.

    Name withdraws amount

  • Trusted members may withdraw an additional $1000. That is to say, if a member is trusted, their balance can go as low as -$1000 (they owe money to the bank). Any transaction which incurs more debt to the bank than this fails.

  • Anyone may ask to see their current balance

    Name print

If a withdrawal transaction fails your program should print a short fail message.

Transaction for Name fails

Saving Hash Table State

You will need to save the state of your hashtable when the program exits. You can make the file a comma-delimited file, where there are commas between your keys and values, with each key/value pair on a new line. You will write three function prototypes inside the tsl.h file and implement them in tsl.c: 


  /*
   * Saves the hashtable state to the filename given.
   * Returns true on a successful save, false otherwise.
   */
  bool tsl_save(const Table* t, const char* filename); 
  
  /*
   * Loads the hashtable from the file given.
   * The table obviously must be allocated before using this function.
   * Presumably the table is empty beforehand, but it's not necessarily required.
   * Returns true on a successful load, false otherwise.
   */
  bool tsl_load(Table* t, const char* filename); 
  
  /*
   * Nicely prints the table to standard output.
   * This has no correlation to saving, but allows you to see the hashtable contents.
   */
  void tsl_printTable(const Table* t);

Handling inputs

The main function will need to take inputs from the command line and open up a pointer to a file FILE* inputFile. You will need to write the function

char* nextMessage(FILE* inputStream)

with the input file as an input to obtain the next line in the file. Your program should call this function many times. Each time it's called, it will return the next line in the file. When there are no more lines in the file it will return NULL.

The program should have two modes. If given a text file as a command line input

./tsl input.txt

It will read lines from that file. At the end of reading in the file, make sure to save the state of the program.

If you do not supply an argument

./tsl

It will expect you type in lines by hand at the terminal. This can be useful for testing. Of course, if you forget about this you will wonder why your program isn’t doing anything. It’s waiting for you. You can specify end-of-input by entering QUIT . At this point the program should save its state and exit.

Program Flow

First create an input file stream and a hash table for the accounts. Then read in and handle messages, one at a time, affecting the account book at each step until all input is processed. Finally, save the state of the account book (table) to a file and exit. You may decide what to name the output file that saves the state.

Example Input/Output

Input:


  Alice joins trusted
  Alice deposits 100
  Alice print
  Bob joins untrusted
  Bob deposits 300
  Bob print
  
  Alice withdraws 10
  Alice withdraws 10
  Alice print
  Bob withdraws 250
  Bob print
  
  Alice withdraws 100
  Alice print
  Bob withdraws 200
  Bob print

Output:


  Alice:      $ 100
  Bob:        $ 300
  Alice:      $  80
  Bob:        $  50
  Alice:      $ -20
  Transaction for Bob fails
  Bob:        $  50

Submission

You should submit at least the following files:

  • hashtable.h, hashtable.c, and test_hashtable.c (tests for your hashtable functions for ints)

  • account.h, account.c

  • tsl.h, tsl.c

  • Makefile

If you write more files please remember to both add and commit them to your repository.

Style

At the top of your tsl.c file, write a comment with your name, etc., in the following form: 

              /* Jane Doe, jdoe */
              /* CS152, Summer 2016 */
              /* Homework 8: Tiny Savings Loan */
This information is not strictly necessary, since your files are already identified by their names and the repository they reside in. Nevertheless, the redundancy is a helpful convenience for us when we are browsing and/or grading your work.

Comments, where they occur, should be helpful and precise. Omit superfluous comments: 

              int a = b + c; /* I'm adding b and c and naming it a! */
Yes, we can see that.

Your code should be no more than 80 columns wide.

Do not write more than one statement on a line.

Do not submit code that does not compile. If a function is broken, and makes compilation impossible, comment out that function and submit the rest. Non-compiling code will receive little to no credit.

Submitting Your Work

Save and commit your files in YOUR-REPOSITORY/hw8. Recall that you will need to add your work before you commit it. (Also, notice that in the -m message you include at commit time, -m is simply a command-line option.)

Commit your work early and often. We do not grade intermediate commits, only the work as it stands at the deadline. If you have any issues with subversion, not only your instructors but your classmates can help you. Most of the students in this class have at least one full quarter of experience running subversion.

If, for any reason, perhaps due to a late add, you do not have a CS repository, save your work somewhere you can easily get it and send mail to the lecturer. We'll get you set up with a repository in time to make the deadline.