Homework 5, CSc 3320, Fall 2000, Due: 29 November 2000 (Wednesday)

CSc 3320 System-Level Programming
Summer 1999
Homework #5
Due: 29 November 2000 (Wednesday)

Write a C program that implements a menu-based application to manipulate a set of suppliers. Each supplier is a fixed length record defined as follows:

#define MAXNUM  11    /* Size of sno field */
#define MAXNAME 31    /* Size of sname field */
struct supp_element_type {         /* supplier element type */
  char sno[MAXNUM];
  char sname[MAXNAME];
};

This time, you need to implement the set using a CLOSED HASH table stored in a file.

A closed hash table is basically a file of supplier records. A hash function is used to determine the location in the file where a supplier record should be stored. In case of a collision (i.e. two supplier records hash to the same location), the second record is stored in the nearest VACANT location starting from the next location.
The file is of fixed size and is capable of holding MAXSIZE records. So, the closed hash table mechanism treats the file to be circular, i.e. the next record to the last record is the first record.
In a closed hash table, there are three types of entries: OCCUPIED, VACANT, and DELETED. Initially all the entries are marked VACANT. When an entry is inserted into the hash table, the entry is OCCUPIED. Due to the possibility of collisions, some entries will not be stored in the bucket they hash to, but a few entries further down.
When an entry is to be deleted, it is marked DELETED in the hash table; This way, when searching for other entries, we can skip over entries marked DELETED.

Algorithm for Member:

  1. Use hash function to locate bucket
  2. Starting from the bucket, search for the supplier
     until is is found or a VACANT location is found
     (skipping over DELETED entries)

Algorithm for Insert:

  1. Use hash function to locate bucket
  2. Starting from the bucket, search for the supplier
     until is is found or a VACANT location is found
     (skipping over DELETED entries)
  3. if (not found) then 
       3.1 Start all over again from the initial bucket and
           search for a DELETED or VACANT entry;
       3.2 if a DELETED or VACANT entry is found, then
           insert the new supplier here

Algorithm for Delete:

  1. Use hash function to locate bucket
  2. Starting from the bucket, search for the supplier
     until is is found or a VACANT location is found
     (skipping over DELETED entries)
  2. if found then mark the entry DELETED

You will need to download the tarred/gzipped archive hw5.tar.gz into your hydra account. This file is also available in the c3320 account home directory, both on zeus and hydra.