COMPLETE THIS PROGRAM IN C USING THE TEMPLATE BELOW:

TEMPLATE:

hash.h:

#ifndef __HASH_H

#define __HASH_H

typedef struct HTNodeTag {

char* key;

char* value;

struct HTNodeTag * next;

} HTNode;

typedef struct HashTableTag {

unsigned int ne;

HTNode ** ht;

} HashTable;

unsigned int HashTable_hash(char* str);

HashTable * newHashTable(unsigned int mxs);

void HashTable_add(HashTable* t, char* key, char* value);

char * HashTable_get(HashTable* t, char* key);

void HashTable_remove(HashTable* t, char* key);

void deleteHashTable(HashTable* t);

unsigned int HashTable_max_length(HashTable* t);

char * HashTable_max_key(HashTable* t, char *s);

#endif

hash.c:

#define _POSIX_C_SOURCE 200809L

#include

#include

#include

#include

#include "hash.h"

#define HT_HASH_PRIME 41U

/* The function maps a string to an unsigned int */

unsigned int HashTable_hash(char* str)

{

if (str == NULL)

return 0;

// TODO

return 1;

}

HashTable* newHashTable(unsigned int mxs)

{

/* Implement a constructor that builds a hashtable relying

on auxiliary chaining (lists) and capable to hold up to

mxs lists in its primary structure. Write a hash function

that is suitable for strings. */

// TODO

if (mxs == 0)

return NULL;

return NULL;

}

/* Given a head of a list, return the node that has the key.

* return NULL if the key is not on the list */

static HTNode* findInList(HTNode * head, char * key)

{

// TODO

return NULL;

}

/* Add the pair key/value to the hash table t.

* Do nothing is the key is already in the hash table.

* */

void HashTable_add(HashTable* t, char* key, char* value)

{

if (t == NULL)

return;

// TODO

}

char* HashTable_get(HashTable* t, char* key)

{

/* Returns the value associated to key in t. If there is no

such value (key does not appear in t) simply return NULL */

// TODO

return NULL;

}

void HashTable_remove(HashTable* t, char* key)

{

/* Removes the pair identified by key from the hashtable t */

// TODO

}

void deleteHashTable(HashTable* t)

{

/* Deallocate all the memory needed for t and its auxiliary structures */

// TODO

}

/* Find the length of the longest list

* Return 0 if the hash table is empty.

* */

unsigned int HashTable_max_length(HashTable* t)

{

// TODO

return 0;

}

/* If s is NULL, return a pointer to the largest key in the hash table.

*

* If s not NULL, return the largest of the keys that are smaller than s.

*

* Do not clone the key.

*

* Return NULL if no key is found.

*

* Note that an empty string is the smallest. So pass NULL to

* find the max.

*/

char * HashTable_max_key(HashTable* t, char *s)

{

// TODO

if (t == NULL)

return NULL;

return NULL;

}

main.c:

#include

#include

#include

#include

#include

#include "hash.h"

static int g_opt_quiet = 0; // OK. Here is a global variable.

void sys_error(char *s)

{

fprintf(stderr, "Error: %s. ", s);

exit (-1);

}

void hash_test(unsigned int ne, char * filename)

{

char buf[256];

int done = 0;

HashTable * ht;

ht = newHashTable(ne);

while (!done && fgets(buf, 255, stdin) != NULL) {

char *s1, *s2, *s3;

s1 = buf;

while (*s1 && isspace(*s1)) /* skip space */

s1 ++;

if (! *s1)

continue; /* empty line*/

s2 = s1 + 1;

while (*s2 && ! isspace(*s2)) /* search the end of word1*/

s2 ++;

if (*s2) {

*s2 = 0;

s2 ++;

while (*s2 && isspace(*s2)) /* skip space */

s2 ++;

s3 = s2;

while (*s3 && *s3 != ' ')

s3 ++;

if (*s3 == ' ')

*s3 = 0;

}

switch (*s1) {

case '!': // info and control

if (! strcmp(s1+1, "exit"))

done = 1;

else if (! strcmp(s1+1, "hash")) {

unsigned h = HashTable_hash(s2);

printf("0x%08X %u ", h, h);

}

else if (! strcmp(s1+1, "maxlen")) {

printf("%u ", HashTable_max_length(ht));

}

else if (! strcmp(s1+1, "maxkey")) {

char *p = HashTable_max_key(ht, (*s2) ? s2 : NULL);

if (p == NULL)

printf("Not Found. ");

else

printf("%s ", p);

}

else

printf("Unknown command: %s ", s1);

break;

case '-': // remove a key

HashTable_remove(ht, s1+1);

break;

default : // add a key

if (*s2) {

HashTable_add(ht, s1, s2);

if (! g_opt_quiet)

printf("Add '%s' => '%s' ", s1, s2);

} else {

s2 = HashTable_get(ht, s1);

if (s2 == NULL)

printf("'%s' not found. ", s1);

else

printf("'%s' => '%s' ", s1, s2);

}

break;

}

}

deleteHashTable(ht);

}

int main(int argc, char* argv[])

{

unsigned int ne = 51;

char * filename;

for (int i = 1; i

if (argv[i][0] == '-') {

if (argv[i][1] == 'n' && argv[i][2]) {

int k = atoi(&argv[i][2]);

if (k

sys_error("Invalid number of entries");

ne = k;

}

else if (argv[i][1] == 'q') {

g_opt_quiet = 1;

}

else

sys_error("Invalid argument");

}

else

filename = argv[i];

}

hash_test(ne, filename);

}

Exercise 2. Hash Table (100 points) In this exercise, you complete the implementation of a hash table with string keys and string values. All hash related files are placed under directory hash The hash table API is provided in the git repository in file hash.h. Part of it is shown below in Figure 1. Some but not all API functions are implemented in hash.c. You will need to implement the missing functions The only file you need change is hash.c. Do not print anything in your code. 1 typedef struct HTNodeTag char char struct HTNodeTag* next; value; 5 HTNode; 6 7 typedef struct HashTableTag ( unsigned int ne; Number of buckets in the hash table HTNode ht 10 HashTable; 12 unsigned int HashTable_hash (char* str); 13 HashTableneHashTable (unsigned int mxs) 14 voicd 15 char * 16 voicd 17 void 18 char* 19 unsigned int HashTable_max_length (HashTable* t); HashTable add (HashTable* t, char* key, char* value); HashTable get (HashTable* t, char* key); HashTable_remove (HashTable* t, char* key); deleteHashTable (HashTable* t); HashTable_max_key (HashTable* t, char *s) Exercise 2. Hash Table (100 points) In this exercise, you complete the implementation of a hash table with string keys and string values. All hash related files are placed under directory hash The hash table API is provided in the git repository in file hash.h. Part of it is shown below in Figure 1. Some but not all API functions are implemented in hash.c. You will need to implement the missing functions The only file you need change is hash.c. Do not print anything in your code. 1 typedef struct HTNodeTag char char struct HTNodeTag* next; value; 5 HTNode; 6 7 typedef struct HashTableTag ( unsigned int ne; Number of buckets in the hash table HTNode ht 10 HashTable; 12 unsigned int HashTable_hash (char* str); 13 HashTableneHashTable (unsigned int mxs) 14 voicd 15 char * 16 voicd 17 void 18 char* 19 unsigned int HashTable_max_length (HashTable* t); HashTable add (HashTable* t, char* key, char* value); HashTable get (HashTable* t, char* key); HashTable_remove (HashTable* t, char* key); deleteHashTable (HashTable* t); HashTable_max_key (HashTable* t, char *s)