I have a hashtable with separetaly linked lists. I Successfully store my elements in the hashtable but it fails when I try to search for my stored elements. My function lookup_string is supposed to find the right list in the hashtable and go through the linked list with the for-loop if more than one element is stored with the same hash-key.
Inside the lookup_string function I found out that the for-loop never executes (I used prints to check that) and the function skips that for-loop and returns NULL directly. This behaviour is really odd and I don't know why it skips that loop, but this is the reason why I can't find my elements after I have stored them, atleast what I think.
If someone can shed some light on this problem that would be much appreciated!
I have functions to delete elements in the hashtable but those are not necessary to consider, I just uploaded them for understanding purpose. I choose alternative 1 in the menu to add one element and then alternative 3 in the menu and that is when I can't find my stored element.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct post // structure of node
{
char name[30]; // stored data
int tel; // stored data
struct post *next; // reference to next node
};
typedef struct post Post; // Post = struct post
struct list
{
Post *head;
Post *current;
};
typedef struct list List;
struct hash_table
{
List *table;
int size;
};
typedef struct hash_table Post_table;
Post* CreateList(char tempname[30], int temptel)
{
Post *ptr = (Post*)malloc(sizeof(Post));
strcpy(ptr->name, tempname);
ptr->tel = temptel;
ptr->next = NULL;
printf("\n creating list with headnode as [%s]\n",tempname);
return ptr;
}
Post* AddList(char tempname[30], int temptel, Post *current)
{
if( current == NULL )
{
return (CreateList(tempname, temptel));
}
printf("\n Adding node to end of list with value [%s]\n",tempname);
Post *ptr = (Post*)malloc(sizeof(Post));
strcpy(ptr->name, tempname);
ptr->tel = temptel;
ptr->next = NULL;
current->next = ptr;
return ptr;
}
unsigned int Hash(Post_table *hash_table, char tempname[30])
{
int i, sum, key;
for(i = 0; i < strlen(tempname); i++)
{
sum += (int)tempname[i];
}
key = abs(sum % hash_table->size);
return key;
}
Post_table *create_hash_table(int size)
{
Post_table *new_table;
if (size < 1)
{return NULL;}
// attempt to allocate memory for the table structure
if ((new_table = malloc(sizeof(Post_table))) == NULL)
{return NULL;}
// attempt to allocate memory for the table itself
// calloc() = all head and current are initialized with NULL
if ((new_table->table = calloc(size,sizeof(List *) * size)) == NULL)
{return NULL;}
new_table->size = size;
return new_table;
}
Post *lookup_string(Post_table *hash_table, char tempname[30])
{
Post *list;
unsigned int hashkey = Hash(hash_table, tempname);
printf("testprint-1");
// Go to the correct list based on the hash value and see if str is
// in the list. If it is, return return a pointer to the list element.
// If it isn't, the item isn't in the table, so return NULL.
for(list = hash_table->table[hashkey].head; list != NULL; list = list->next)
{
printf("testprint-2");
if (strcmp(tempname, list->name) == 0)
{
return list;
}
}
return NULL;
}
int add_string(Post_table *hash_table, char tempname[30], int temptel)
{
Post *current_list;
unsigned int hashkey = Hash(hash_table, tempname);
printf("\nHash-key: %d\n", hashkey);
// if item already exists, don't insert it again
current_list = lookup_string(hash_table, tempname);
if (current_list != NULL)
{
return 2;
}
hash_table->table[hashkey].current = AddList(tempname, temptel, hash_table->table[hashkey].current);
// if the list has been created just now, then both head and current must point to the only list element
if( hash_table->table[hashkey].head == NULL )
{
hash_table->table[hashkey].head = hash_table->table[hashkey].current;
}
return 0;
}
void free_entry(Post_table *hash_table, char tempname[30])
{
Post *del_list;
Post *temp;
int ret = 0;
unsigned int hashkey = Hash(hash_table, tempname);
del_list = lookup_string(hash_table, tempname);
ret = Delete(hash_table, tempname, hashkey);
if(ret != 0)
{
printf("\n delete [name = %s] failed, no such element found\n",tempname);
}
else
{
printf("\n delete [name = %s] passed \n",tempname);
}
}
void skrivMeny(void)
{
printf("\n1: Register name and telephone number\n");
printf("2: Remove name and telephone number\n");
printf("3: Search for name\n");
printf("5: Exit\n");
}
Post* Search(Post_table *hash_table, unsigned int hashkey, char tempname[30], Post **prev)
{
Post *ptr = hash_table->table[hashkey].head;
Post *tmp = NULL;
int found = 0;
char structname[sizeof(tempname)];
printf("\n Searching the list for value [%s] \n",tempname);
while(ptr != NULL)
{
if (strcmp(ptr->name, tempname) == 0)
{
found = 1;
break;
}
else
{
tmp = ptr;
ptr = ptr->next;
}
}
if(found == 1)
{
if(prev)
{
*prev = tmp;
}
return ptr;
}
else
{
return NULL;
}
}
int Delete(Post_table *hash_table, char tempname[30], unsigned int hashkey)
{
Post *prev = NULL;
Post *del = NULL;
printf("\n Deleting value [%s] from list\n",tempname);
del = Search(hash_table, hashkey, tempname, &prev);
if(del == NULL)
{
return -1;
}
else
{
if(prev != NULL)
{
prev->next = del->next;
}
if(del == hash_table->table[hashkey].current && del != hash_table->table[hashkey].head)
{
hash_table->table[hashkey].current = prev;
}
else if(del == hash_table->table[hashkey].head)
{
hash_table->table[hashkey].head = del->next;
}
}
free(del);
del = NULL;
return 0;
}
int main()
{
printf("\nHej och välkommen till hashlistan\n\n");
int menyval = 1;
char tempname[30];
int temptel, key;
Post * ptr;
Post_table *hash_table;
int table_size = 10;
hash_table = create_hash_table(table_size);
while (menyval > 0 && menyval <= 5)
{
skrivMeny();
scanf("%d", &menyval);
if (menyval == 1)
{
printf("[Name] [Number] = ");
scanf("%s %d", &tempname[0], &temptel);
add_string(hash_table, tempname, temptel);
}
if (menyval == 2)
{
printf("[Name] = ");
scanf("%s", &tempname[0]);
free_entry(hash_table, tempname);
}
if (menyval == 3)
{
printf("[Name] = ");
scanf("%s", &tempname[0]);
ptr = lookup_string(hash_table, tempname);
if(ptr == NULL)
{
printf("\n Search [name = %s] failed, no such element found\n",tempname);
}
else
{
printf("\n Search passed [name = %s tel = %d]\n",ptr->name, ptr->tel);
}
}
if (menyval == 5)
{
break;
}
}
return 0;
}