Answer Happy

Please help with the following C program, please do not
repost other solutions and please leave comments, will
upvote!
Your task for this assignment is to implement a hash table (HT).
You must build your HT using either a dynamic array or an array of
linked list. A dynamic array-based HT resolves collisions using
open addressing whereas array of linked list based HT resolves
collisions using chaining
The interface for the HT you'll implement ) is already
defined for you in the file hash_table.h. Your job is to implement
definitions for the functions that comprise this interface in
hash_table.c. Note that you may not modify the interface
definition with which you are provided. Specifically, do not modify
any of the already-defined HT function prototypes.
You are provided with a dynamic array implementation in
dynarray.c and dynarray.h as well as a linked list implementation
in list.c and list.h that you can use to implement your hash table,
if you'd like
--------------------------------------------------------------------------------------------------------------------------------
//hash_table.c
// In this file, you will write the structures and functions
needed to implement a hash table.
#include <stdlib.h>
#include "dynarray.h"
#include "list.h"
#include "hash_table.h"
/* This is the structure that represents a hash table.
You must define
* this struct to contain the data needed to implement a
hash table.*/
struct ht;
/* This function should allocate and initialize an empty
hash table and
* return a pointer to it.
*/
struct ht* ht_create(){
// FIXME:
return NULL;
}
/* This function should free the memory allocated to a
given hash table.
* Note that this function SHOULD NOT free the individual
elements stored in
* the hash table. That is the responsibility of the
caller.
*
* Params: ht - the hash table to be destroyed.
May not be NULL.
*/
void ht_free(struct ht* ht){
// FIXME:
return;
}
/* This function should return 1 if the specified hash
table is empty and
* 0 otherwise.
* Params: ht - the hash table whose emptiness is to
be checked. May not be
* NULL.
* Return: Should return 1 if ht is empty and 0
otherwise.
*/
int ht_isempty(struct ht* ht){
// FIXME:
return -1;
}
/* This function returns the size of a given hash table
(i.e. the number of
* elements stored in it, not the capacity).
*/
int ht_size(struct ht* ht){
// FIXME:
return -1;
}
/* This function takes a key, maps it to an integer index
value in the hash table,
* and returns it. The hash algorithm is totally up to you.
Make sure to consider
* Determinism, Uniformity, and Speed when design the hash
algorithm
* Params: ht - the hash table into which to store the
element. May not be NULL.
* key - the key of the element to be stored
* convert - pointer to a function that can be
passed the void* key from
* to convert it to a unique integer
hashcode
*/
int ht_hash_func(struct ht* ht, void* key, int
(*convert)(void*)){
// FIXME:
return -1;
}
/* This function should insert a given element into a hash
table with a
* specified key. Note that you cannot have two same
keys in one hash table.
* If the key already exists, update the value associated
with the key.
* This function is passed a function pointer that is used
to convert the key (void*)
* to a unique hashcode (int).
* Resolution of collisions is requried, use either
chaining or open addressing.
* If using chaining, double the number of buckets when the
load factor is >= 4
* If using open addressing, double the array capacity when
the load factor is >= 0.75
* load factor = (number of elements) / (hash table
capacity)
* Params: ht - the hash table into which to insert an
element. May not be NULL.
* key - the key of the element
* value - the value to be inserted into ht.
* convert - pointer to a function that can be
passed the void* key from
* to convert it to a unique integer
hashcode*/
void ht_insert(struct ht* ht, void* key, void* value, int
(*convert)(void*)){
// FIXME:
return;
}
/* This function should search for a given element in a
hash table with a
* specified key provided.
* This function is passed a function pointer that is used
to convert the key (void*)
* to a unique hashcode (int).
* If the key is found, return the corresponding value
(void*) of the element,
* otherwise, return NULL
* Params: ht - the hash table into which to loop up
for an element. May not be NULL.
* key - the key of the element to search for
* convert - pointer to a function that can be
passed the void* key from
* to convert it to a unique integer
hashcode*/
void* ht_lookup(struct ht* ht, void* key, int
(*convert)(void*)){
// FIXME:
return NULL;
}
/* This function should remove a given element in a hash
table with a
* specified key provided.
* This function is passed a function pointer that is used
to convert the key (void*)
* to a unique hashcode (int).
* If the key is found, remove the element and return,
otherwise, do nothing and return
* Params: ht - the hash table into which to remove an
element. May not be NULL.
* key - the key of the element to remove
* convert - pointer to a function that can be
passed the void* key from
* to convert it to a unique integer
hashcode*/
void ht_remove(struct ht* ht, void* key, int
(*convert)(void*)){
// FIXME:
return;
}
-------------------------------------------------------------------------------------------------------------------------------------------
//list.c
//File contains implementation of singly linked list
#include <stdlib.h>
#include <assert.h>
#include "list.h"
// This structure is used to represent a single node in a
singly-linked list
struct node {
void* val;
struct node* next;
};
//This structure is used to represent an entire singly-linked
list
struct list {
struct node* head;
};
//This function allocates and initializes a new, empty linked
list
struct list* list_create() {
struct list* list = malloc(sizeof(struct list));
list->head = NULL;
return list;
}
//This function frees the memory associated with a linked
list
void list_free(struct list* list) {
assert(list);
// Free all individual nodes.
struct node* next, * curr = list->head;
while (curr != NULL) {
next = curr->next;
free(curr);
curr = next;
}
free(list);
}
void list_insert(struct list* list, void* val) {
assert(list);
// Create new node and insert at head.
struct node* temp = malloc(sizeof(struct node));
temp->val = val;
temp->next = list->head;
list->head = temp;
}
void list_remove(struct list* list, void* val, int (*cmp)(void*
a, void* b)) {
assert(list);
struct node* prev = NULL, * curr = list->head;
while (curr) {
/* If current node's value matches query
value, update node prior to curr
* to point around curr, then free curr and
return. This removes curr from the list.*/
if (cmp(val, curr->val) == 0) {
if (prev) {
prev->next = curr->next;
} else {
list->head = curr->next;
}
free(curr);
return;
}
prev = curr;
curr = curr->next;
}
}
int list_position(struct list* list, void* val, int (*cmp)(void*
a, void* b)) {
assert(list);
struct node* curr = list->head;
int i = 0;
while (curr) {
// If curr's value matches the query
value, return the position of curr.
if (cmp(val, curr->val) == 0) {
return i;
}
curr = curr->next;
i++;
}
/* If we got all the way through the list and no
element matched `val`, then
* `val` didn't exist in the list, so return
-1.*/
return -1;
}
void list_reverse(struct list* list) {
assert(list);
struct node* next, * curr = list->head, * prev =
NULL;
while (curr) {
next = curr->next;
curr->next = prev;
list->head = prev = curr;
curr = next;
}
}
----------------------------------------------------------------------------------------------------------
//dynarray.c
/* This file contains a simple implementation of a dynamic
array. See the
* documentation below for more information on the
individual functions in
* this implementation.*/
#include <stdlib.h>
#include <assert.h>
#include "dynarray.h"
// This structure is used to represent a single dynamic
array.
struct dynarray {
void** data;
int size;
int capacity;
};
// You cannot modify the initial capacity
#define DYNARRAY_INIT_CAPACITY 2
// This function allocates and initializes a new, empty
dynamic array and returns a pointer to it.
struct dynarray* dynarray_create() {
struct dynarray* da = malloc(sizeof(struct
dynarray));
assert(da);
da->data = malloc(DYNARRAY_INIT_CAPACITY *
sizeof(void*));
assert(da->data);
da->size = 0;
da->capacity = DYNARRAY_INIT_CAPACITY;
return da;
}
//This function frees the memory associated with a dynamic
array.
void dynarray_free(struct dynarray* da) {
assert(da);
free(da->data);
free(da);
}
// This function returns the size of a given dynamic array (i.e.
the number of elements stored in it, not the capacity).
int dynarray_size(struct dynarray* da) {
assert(da);
return da->size;
}
// Auxilliary function to perform a resize on a dynamic
array's underlying storage array.
void _dynarray_resize(struct dynarray* da, int new_capacity)
{
assert(new_capacity > da->size);
// Allocate space for the new array.
void** new_data = malloc(new_capacity *
sizeof(void*));
assert(new_data);
// Copy data from the old array to the new one.
for (int i = 0; i < da->size; i++) {
new_data = da->data;
}
// Put the new array into the dynarray struct.
free(da->data);
da->data = new_data;
da->capacity = new_capacity;
}
// This function inserts a new value to a given dynamic
array.
void dynarray_insert(struct dynarray* da, void* val) {
assert(da);
// Make sure we have enough space for the new
element. Resize if needed.
if (da->size == da->capacity) {
_dynarray_resize(da, 2 * da->capacity);
}
// Put the new element at the end of the
array.
da->data[da->size] = val;
da->size++;
}
void dynarray_remove(struct dynarray* da, int idx) {
assert(da);
assert(idx < da->size && idx >= 0);
// Move all elements behind the one being removed
forward one index, overwriting the element to be removed
for (int i = idx; i < da->size - 1; i++) {
da->data = da->data[i+1];
}
da->size--;
}
// This function returns the value of an existing element in a
dynamic array.
void* dynarray_get(struct dynarray* da, int idx) {
assert(da);
assert(idx < da->size && idx >= 0);
return da->data[idx];
}
// This function updates (i.e. overwrites) the value of an
existing element in a dynamic array.
void dynarray_set(struct dynarray* da, int idx, void* val) {
assert(da);
assert(idx < da->size && idx >= 0);
da->data[idx] = val;
}