#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include "GenericHashTable.h"
#define INT_TYPE 0
#define STR_TYPE 1
void duplicateTable(Table *table)
{
int prev_size = table->currentSize; // A variable to hold the old size, before duplicatoin.
table
->arr
= (Object
**)realloc(table
->arr
, table
->currentSize
* 2 * sizeof(Object
*)); // Reallocate the array, making it twice bigger.
if(table->arr == NULL)
{
printf("Error occured while duplicating the array. \n");
return;
}
table->currentSize = table->currentSize * 2; // Update the size.
table->ratio = table->currentSize / table->originalSize; // Update the rate of currentSize/originalSize.
for (int i = prev_size; i < table->currentSize; i++) // Initialize new cells of the array with NULLs.
{
table->arr[i] = NULL;
}
for (int i = table->currentSize - 1; i > 0; i--) // Loop to move all old data to thier new location, for i'th cell it would be: 2*i.
{
if (table->arr[i] != NULL)
{
table->arr[2 * i] = table->arr[i];
table->arr[i] = NULL; // Initialize old index.
}
}
}
int listLength(Object *obj)
{
int count = 1;
if (obj == NULL)
return 0;
while (obj->nextObj != NULL)
{
count++;
obj = obj->nextObj;
}
return count;
}
int intHashFun(int *key, int origSize)
{
int toReturn = 0;
toReturn = *key % origSize;
return toReturn;
}
int strHashFun(char *key, int origSize)
{
int ascii_val = 0;
int toReturn = 0;
for (int i
= 0; i
< strlen(key
); key
++)
{
ascii_val += key[i];
}
toReturn = ascii_val % origSize;
return toReturn;
}
Object *createObject(void *data)
{
Object
*new_obj
= (Object
*)calloc(1, sizeof(Object
)); // Allocate the memory for the new object.
if (new_obj == NULL)
{
printf("An error occured creating an object. \n");
return NULL;
}
new_obj->data = data;
if (new_obj->data == NULL)
{
printf("An error occured creating an object. \n");
return NULL;
}
else
{
new_obj->nextObj = NULL;
return new_obj;
}
}
Table *createTable(int size, int dType, int listLength)
{
Table
*new_table
= (Table
*)calloc(1, sizeof(Table
)); // Allocate memory for the table.
if (new_table == NULL)
{
printf("An error occured while allocating the table.\n");
return NULL;
}
//------Variables Initialization--------///
new_table->listLen = listLength;
new_table->dataType = dType;
new_table->originalSize = size;
new_table->ratio = 1;
new_table->currentSize = size;
new_table
->arr
= (Object
**)calloc(size
, sizeof(Object
*));
if (new_table->arr == NULL)
{
printf("An error occured while allocating the table.\n");
return NULL;
}
else
{
return new_table;
}
}
void printTable(Table *table)
{
Object *current_object;
int data_int = 0;
char *data_string = NULL;
if (table->dataType == INT_TYPE)
{
for (int i = 0; i < table->currentSize; i++)
{
current_object = table->arr[i];
while (current_object != NULL)
{
data_int = *((int *)(current_object->data));
if (current_object->nextObj == NULL)
{
}
else
printf("%d \t --> \t", data_int
);
current_object = current_object->nextObj;
}
}
printf("--------------------------------------------------\n");
}
else if (table->dataType == STR_TYPE)
{
for (int i = 0; i < table->currentSize; i++)
{
current_object = table->arr[i];
while (current_object != NULL)
{
data_string = (char *)current_object->data;
if (current_object->nextObj == NULL)
{
}
else
printf("%s \t --> \t", data_string
);
current_object = current_object->nextObj;
}
}
printf("--------------------------------------------------\n");
}
}
int add(Table *table, void *data)
{
int location = -1; // A variable to save the location of the hash value.
int *data_int; // A pointer in-case the data-type is integer.
char *data_str; // A pointer in-case the data-type is string.
Object *current_object; // A pointer to the current object.
Object *new_object; // A pointer to the new object creeated.
if (table->dataType == INT_TYPE) // In-case the data-type is integer, allocate memory for data_int, and calculate the hash value.
{
data_int
= (int *)calloc(1, sizeof(int));
if (data_int == NULL)
{
printf("Error: failure in memory allocation.\n");
return -1;
}
*data_int = *((int *)(data));
location = table->ratio * intHashFun(data_int, table->originalSize);
}
else if (table->dataType == STR_TYPE) // In-case the data-type is string, allocate memory for data_str, and calculate the hash value.
{
data_str
= (char *)calloc(strlen((char*)data
)+1, sizeof(char));
if (data_str == NULL)
{
printf("Error: failure in memory allocation.\n");
return -1;
}
strcpy(data_str
, ((char *)(data
)));
location = table->ratio * strHashFun(data_str, table->originalSize);
}
else
{
printf("Error: Invalid data type. \n");
return -1;
}
for (int i = location; i < location + table->ratio; i++) // Scan the array through the indexes given by the ratio variable and the hash variable.
{
current_object = table->arr[i];
if (current_object == NULL) // If there's an empty list, figure out what is the data-type and accordingly add the object to the array as the list's head.
{
if (table->dataType == INT_TYPE)
{
new_object = createObject(data_int);
table->arr[i] = new_object;
return i;
}
else
{
new_object = createObject(data_str);
table->arr[i] = new_object;
return i;
}
}
else if (listLength(current_object) < table->listLen) // If there is a list and it's not filled yet, go down the list and add the new object as the last element.
{
if (table->dataType == INT_TYPE)
{
new_object = createObject(data_int);
while (current_object->nextObj != NULL)
current_object = current_object->nextObj;
current_object->nextObj = new_object;
return i;
}
else
{
new_object = createObject(data_str);
while (current_object->nextObj != NULL)
current_object = current_object->nextObj;
current_object->nextObj = new_object;
return i;
}
}
} // If reached this area
duplicateTable(table);
if (table->dataType == INT_TYPE)
{
location = table->ratio * intHashFun(data_int, table->originalSize);
new_object = createObject(data_int);
table->arr[location + 1] = new_object;
return location + 1;
}
else
{
location = table->ratio * strHashFun(data_str, table->originalSize);
new_object = createObject(data_str);
table->arr[location + 1] = new_object;
return location + 1;
}
}
int isEqual(int type, void *data1, void *data2)
{
if (type == STR_TYPE)
{
return strcmp((char *)data1
, (char *)data2
);
}
else if (type == INT_TYPE)
{
if (*((int *)(data1)) == *((int *)(data2)))
return 0;
else
return 1;
}
else
{
printf("Error: Invalid data type. \n");
return -1;
}
}
Object *search(Table *table, void *data)
{
int location = -1;
Object *current_object;
if (table->dataType == INT_TYPE)
location = table->ratio * intHashFun(((int *)(data)), table->originalSize);
else
location = table->ratio * strHashFun((char *)(data), table->originalSize);
for (int i = location; i < location + table->ratio; i++)
{
current_object = table->arr[i];
if (listLength(table->arr[i]) > 0)
{
while (current_object != NULL)
{
if (table->dataType == INT_TYPE)
{
if (isEqual(table->dataType, (int *)(data), current_object->data) == 0)
return current_object;
}
else
{
if (isEqual(table->dataType, (char *)(data), current_object->data) == 0)
return current_object;
}
current_object = current_object->nextObj;
}
}
}
return NULL;
}
int removeObj(Table *table, void *data)
{
int location = -1;
Object *temp_object;
Object *temp_next;
if (table->dataType == INT_TYPE)
location = table->ratio * intHashFun(data, table->originalSize);
else
location = table->ratio * strHashFun(data, table->originalSize);
for (int i = location; i < location + table->ratio; i++)
{
temp_object = table->arr[i];
if (temp_object == NULL)
continue;
else if(table->dataType == INT_TYPE && isEqual(INT_TYPE,temp_object->data,data)==0 && temp_object->nextObj!=NULL)
{
table->arr[i]= temp_object->nextObj;
freeObject(temp_object,INT_TYPE);
return i;
}
else if(table->dataType == STR_TYPE && isEqual(STR_TYPE,temp_object->data,data)==0 && temp_object->nextObj!=NULL)
{
table->arr[i]= temp_object->nextObj;
freeObject(temp_object,STR_TYPE);
return i;
}
else if (temp_object->nextObj == NULL)
{
if (table->dataType == INT_TYPE)
{
if (isEqual(INT_TYPE, temp_object->data, data) == 0)
{
freeObject(table->arr[i], INT_TYPE);
table->arr[i] = NULL;
return i;
}
}
else
{
if (isEqual(STR_TYPE, temp_object->data, data) == 0)
{
freeObject(table->arr[i], STR_TYPE);
table->arr[i] = NULL;
return i;
}
}
}
else
{
while (temp_object->nextObj != NULL)
{
if (table->dataType == INT_TYPE)
{
if (isEqual(INT_TYPE, temp_object->nextObj->data, data) == 0)
{
temp_next=temp_object->nextObj->nextObj;
freeObject(temp_object->nextObj,INT_TYPE);
temp_object->nextObj = temp_next;
return i;
}
}
else
{
if (isEqual(STR_TYPE, temp_object->nextObj->data, data) == 0)
{
temp_next=temp_object->nextObj->nextObj;
freeObject(temp_object->nextObj,STR_TYPE);
temp_object->nextObj = temp_next;
return i;
}
}
temp_object = temp_object->nextObj;
}
}
}
return -1;
}
void freeObject(Object *obj, int type)
{
if(obj!=NULL)
{
}
}
void freeTable(Table* table)
{
Object* temp;
Object* current_object;
for(int i = 0; i < table->currentSize; i++)
{
if(table->arr[i] != NULL)
{
current_object = table->arr[i];
if(listLength(table->arr[i])==1)
{
freeObject(table->arr[i],table->dataType);
continue;
}
else if(listLength(table->arr[i]) > 1)
{
for(int j = 0; j < listLength(table->arr[i]);j++)
{
temp = current_object->nextObj;
freeObject(current_object,table->dataType);
current_object=temp;
}
//freeObject(table->arr[i],table->dataType);
}
}
}
}
int main()
{
int a = 8;
int b = 16;
int c = 24;
int d = 5;
int e = 9;
int f = 13;
int g = 6;
int h = 10;
int i = 14;
int j = 104;
char *str1 = "aaaaaaaaaa";
char *str2 = "b r r r r e ";
char *str3 = "cwjxcn cwnjcwj";
char *str4 = "dwcnjwc njcwnjwc";
char *str5 = "ecwwc wcwc cwcw";
char *str6 = "f";
char *str7 = "ew33f";
Table *temp = createTable(8, 0, 2);
add(temp, (void *)&a);
add(temp, (void *)&b);
add(temp, (void *)&c);
add(temp, (void *)&d);
add(temp, (void *)&e);
add(temp, (void *)&f);
add(temp, (void *)&g);
add(temp, (void *)&h);
add(temp, (void *)&i);
printTable(temp);
Object *xyz = search(temp, (void *)&a);
if(xyz != NULL){
printf("a = %d\n", *(int*)xyz
->data
);
}
xyz = search(temp, (void *)&c);
if(xyz != NULL){
printf("c = %d\n", *(int*)xyz
->data
);
}
xyz = search(temp, (void *)&j);
if(xyz != NULL){
printf("j = %d\n", *(int*)xyz
->data
);
}
xyz = search(temp, (void *)&f);
if(xyz != NULL){
printf("f = %d\n", *(int*)xyz
->data
);
}
int x =removeObj(temp,(void*)&a);
int xx =removeObj(temp,(void*)&j);
int xxx =removeObj(temp,(void*)&a);
int y = removeObj(temp,(void*)&c);
int z = removeObj(temp,(void*)&i);
xyz = search(temp, (void *)&a);
printTable(temp);
if(xyz != NULL){
printf("a = %d\n", *(int*)xyz
->data
);
}
xyz = search(temp, (void *)&f);
if(xyz != NULL){
printf("f = %d\n", *(int*)xyz
->data
);
}
xyz = search(temp, (void *)&b);
if(xyz != NULL){
printf("b = %d\n", *(int*)xyz
->data
);
}
printf("\n%d %d %d %d %d\n\n",x
,xx
,xxx
,y
,z
);
Table *tempO = createTable(4, 1, 3);
add(tempO, (void *)str1);
add(tempO, (void *)str2);
add(tempO, (void *)str3);
add(tempO, (void *)str4);
add(tempO, (void *)str5);
add(tempO, (void *)str6);
printTable(tempO);
xyz = search(tempO, (void *)str1);
if(xyz != NULL){
printf("str1 = %s\n", (char*)xyz
->data
);
}
xyz = search(tempO, (void *)str2);
if(xyz != NULL){
printf("str2 = %s\n", (char*)xyz
->data
);
}
xyz = search(tempO, (void *)str3);
if(xyz != NULL){
printf("str3 = %s\n", (char*)xyz
->data
);
}
add(tempO, (void *)str1);
add(tempO, (void *)str2);
add(tempO, (void *)str3);
add(tempO, (void *)str4);
add(tempO, (void *)str5);
add(tempO, (void *)str6);
printTable(tempO);
int x1 =removeObj(tempO,(void*)str6);
int xx1 =removeObj(tempO,(void*)str3);
int xxx1 =removeObj(tempO,(void*)str6);
int y1 = removeObj(tempO,(void*)str1);
int z1 = removeObj(tempO,(void*)str7);
printTable(tempO);
printf("\n%d %d %d %d %d\n\n",x1
,xx1
,xxx1
,y1
,z1
);
xyz = search(tempO, (void *)str1);
if(xyz != NULL){
printf("str1 = %s\n", (char*)xyz
->data
);
}
xyz = search(tempO, (void *)str2);
if(xyz != NULL){
printf("str2 = %s\n", (char*)xyz
->data
);
}
xyz = search(tempO, (void *)str3);
if(xyz != NULL){
printf("str3 = %s\n", (char*)xyz
->data
);
}
freeTable(temp);
freeTable(tempO);
return 0;
}
/*int main()
{
Table *t = createTable(4, STR_TYPE, 2);
char *c1 = "a";
char *c2 = "b";
char *c3 = "c";
char *c4 = "d";
add(t, (void *)c1);
add(t, (void *)c1);
add(t, (void *)c1);
add(t, (void *)c1);
//printTable(t);
add(t, (void *)c2);
add(t, (void *)c2);
add(t, (void *)c2);
add(t, (void *)c2);
//printTable(t);
add(t, (void *)c3);
add(t, (void *)c3);
add(t, (void *)c3);
add(t, (void *)c3);
//printTable(t);
add(t, (void *)c4);
add(t, (void *)c4);
add(t, (void *)c4);
add(t, (void *)c4);
printTable(t);
// printf("%s\n", ((char *)(search(t, c4)->data)));
removeObj(t,c4);
// printTable(t);
//removeObj(t,(char *)(search(t, c4)->data));
//removeObj(t,(char *)(search(t, c4)->data));
//removeObj(t,(char *)(search(t, c4)->data));
// removeObj(t,(char *)(search(t, c4)->data));
//printTable(t);
freeTable(t);
}
*/