I'm trying to implement a hashtable with linked list and there is one thing not working properly. First i made the linked list code and made sure it worked just as it is supposed to, so I figured out it got to be something with the hashtable implementation or the interaction between them both.
What happens is i can add several objects and find them again with no problem. But if two or more objects are hashed with the same key they are supposed to create a linked list but for some reason i can only find the latest added object in the linked list.
The previously added object is there though because i can successfully delete the object that i cannot find with my "lookup_string" function, so therefor i know the object is stored at that spot.
So the function "lookup_string" is supposed to deliver the object i search for in the hash table and the "Search" function is the one i used when I only implemented the linked list. Worth mentioning is that the "Search" function is used in the delete-process but not in the process where i just want to find an object, I'm not sure if this matters because i believe the "lookup_string" should be able to find an object without the "Search" function.
So to make this simple, I store two objects:
Object 1:
name(key) = bcd
telephone number = 123
Object 2:
name(key) = ace
telephone number = 910
Now both object 1 and 2 will get the same hash-key value and therefor they will be stored in the same slot in the hash-table. They are supposed to create a linked list but when i search for the objects (choice number 3 in the menu) i can only find the latest added object, which is Object 2. But i can still delete Object 1 and it will tell me that Object 1 was deleted successfully.
Code:
struct post
{
char name[30];
int tel;
struct post *next;
};
typedef struct post Post;
Post *head = NULL;
Post *current;
struct hash_table
{
Post **table;
int size;
};
typedef struct hash_table Post_table;
unsigned int Hash(Post_table *hash_table, char tempname[30])
{
int i;
int sum;
int key;
for(i = 0; i < strlen(tempname); i++)
{
sum += (int)tempname[i];
}
key = sum % hash_table->size;
return key;
}
Post_table *create_hash_table(int size)
{
int i;
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
if ((new_table->table = malloc(sizeof(Post *) * size)) == NULL)
{
return NULL;
}
//Initialize the elements of the table
for(i = 0; i < size; i++)
{
new_table->table[i] = 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);
for(list = hash_table->table[hashkey]; list != NULL; list = list->next)
{
if (strcmp(tempname, list->name) == 0)
{
return list;
}
}
return NULL;
}
int add_string(Post_table *hash_table, char tempname[30], int temptel)
{
Post *new_list;
Post *current_list;
unsigned int hashkey = Hash(hash_table, tempname);
/* Attempt to allocate memory for list */
if ((new_list = malloc(sizeof(Post))) == NULL)
{
return 1;
}
/* Does item already exist? */
current_list = lookup_string(hash_table, tempname);
/* item already exists, don't insert it again. */
if (current_list != NULL)
{
return 2;
}
/* Insert into list */
printf("\nHash-key: %d\n", hashkey);
hash_table->table[hashkey] = AddList(tempname, temptel);
return 0;
}
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);
head = current = ptr;
return ptr;
}
Post* AddList(char tempname[30], int temptel)
{
if (NULL == head)
{
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;
current = ptr;
return ptr;
}
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(char tempname[30], Post **prev)
{
Post *ptr = 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;
}
}
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(tempname);
if(ret != 0)
{
printf("\n delete [name = %s] failed, no such element found\n",tempname);
}
else
{
printf("\n delete [name = %s] passed \n",tempname);
}
}
int Delete(char tempname[30])
{
Post *prev = NULL;
Post *del = NULL;
printf("\n Deleting value [%s] from list\n",tempname);
del = Search(tempname,&prev);
if(del == NULL)
{
return -1;
}
else
{
if(prev != NULL)
{
prev->next = del->next;
}
if(del == current && del != head)
{
current = prev;
}
else if(del == head)
{
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;
int 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);//inmatning
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;
}
I appreciate all help or tips toward solving my problem!
EDIT: This is how my code looks like right now, I divided my file into two files; hash.c and lista.h where i included the header file in the c-file.
lista.h:
struct post
{
char name[30];
int tel;
struct post *next;
};
typedef struct post Post;
struct list
{
Post *head = NULL;
Post *current;
};
typedef struct list List;
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, int emptyElement)
{
if (emptyElement == 1)
{
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;
return ptr;
}
int Delete(Post_table *hash_table, char tempname[30])
{
Post *prev = NULL;
Post *del = NULL;
printf("\n Deleting value [%s] from list\n",tempname);
del = Search(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;
}
hash.c:
struct hash_table
{
List *table;
int size;
};
typedef struct hash_table Post_table;
unsigned int Hash(Post_table *hash_table, char tempname[30])
{
int i;
int sum;
int key;
for(i = 0; i < strlen(tempname); i++)
{
sum += (int)tempname[i];
}
key = sum % hash_table->size;
return key;
}
Post_table *create_hash_table(int size)
{
int i;
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
if ((new_table->table = malloc(sizeof(Post *) * size)) == NULL)
{
return NULL;
}
//Initialize the elements of the table
for(i = 0; i < size; i++)
{
new_table->table[i] = 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);
for(list = hash_table->table[hashkey]; list != NULL; list = list->next)
{
if (strcmp(tempname, list->name) == 0)
{
return list;
}
}
return NULL;
}
int add_string(Post_table *hash_table, char tempname[30], int temptel)
{
int emptyElement = 0;
Post *new_list;
Post *current_list;
unsigned int hashkey = Hash(hash_table, tempname);
/* Attempt to allocate memory for list */
if ((new_list = malloc(sizeof(Post))) == NULL)
{
return 1;
}
/* Does item already exist? */
current_list = lookup_string(hash_table, tempname);
/* item already exists, don't insert it again. */
if (current_list != NULL)
{
return 2;
}
/* Insert into list */
if (hash_table->table[hashkey] == NULL)
{
emptyElement = 1;
}
printf("\nHash-key: %d\n", hashkey);
hash_table->table[hashkey] = AddList(tempname, temptel);
if (emptyElement == 1)
{
hash_table->table[hashkey].head = hash_table->table[hashkey];
hash_table->table[hashkey].current = hash_table->table[hashkey];
}
if (emptyElement == 0)
{
hash_table->table[hashkey].current = hash_table->table[hashkey];
}
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(tempname);
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(char tempname[30], Post **prev)
{
Post *ptr = 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 main()
{
printf("\nHej och välkommen till hashlistan\n\n");
int menyval = 1;
char tempname[30];
int temptel;
int 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);//inmatning
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;
}
But as I said there seems to be something wrong with this part:
struct list
{
Post *head = NULL;
Post *current;
};
And since this is not correct it causes several other errors so I'm trying to see what is wrong with this part first.