Trying to implement a hash table using linked lists to solve collision's problem I'm facing some problems with my code for initializing the hash table. I get a segmentation fault. Trying to see where exactly the problem is I used the valgrind. With this tool i get the warning:
"Address 0x8 is not stack'd, malloc'd or (recently) free'd"
on almost every my try to 'edit' the hash table. eg for the size,to insert sth,to delete etc. I've looked again and again my code but I cant find what's wrong. I thought I had malloc'd and stack'd everything correctly. But with this message,clearly sth goes wrong. Any ideas on this?
My code:
//hash table structure
typedef struct HashTable
{
int size; //size of table with connections
struct List **table; //table elements
}HashTable;
typedef struct List
{
char* number;
struct List *next;
}List;
struct HashTable *initHashTable(int size)
{
struct HashTable *blankTable=(struct HashTable *)malloc(sizeof(struct HashTable));
if (size<1)
{
return NULL;
}
if ((blankTable=malloc(sizeof(HashTable)))==NULL)
{
return NULL;
}
if ( (blankTable->table=malloc(size*sizeof(List))) == NULL)
{
return NULL;
}
int i;
for (i=0; i<size; i++) //initializes hash table
{
blankTable->table[i]=malloc(sizeof(List));
blankTable->table[i]=NULL; //Valgrind :: Invalid write of size 8
}
blankTable->size = size;
//printf("blankTable size:%d\n",blankTable->size);
return blankTable;
}
MORE NOTES: Using the following code to search if a number already exists or not in the hash table. I get from valgrind this:
Invalid read of size 8 ==3773== at 0x40110E: lookup(360) ==3773== Address 0x8 is not stack'd, malloc'd or (recently) free'd
struct List *lookup(HashTable *hashtable,char *number)
{
struct List *list= (struct List *) malloc (sizeof(struct List )); ;
unsigned int hashval= hash(number);
if ( (hashtable->table[hashval])!=NULL)
{
for( list=hashtable->table[hashval]; list!=NULL; list=list->next)
{ if(strcmp(number,list->number)==0) //SEGMENTATION!
{
return list;
}
}
}
return NULL;
}
The fact that i get also a segmentation if i call to see the table's size it's sth that worries me even more. Calling this:
unsigned int size = Array[pos].TableHead->size;
Array[pos].TableHead is a pointer to the struct of the hashTable.
EDIT:
Running the valgring I get this report:
Invalid write of size 8
==8724== at 0x4016D2: initHashTable (hash.c:524)
==8724== by 0x4019CE: main (hash.c:792)
==8724== Address 0x5199180 is 8 bytes after a block of size 8 alloc'd
==8724== at 0x4C25153: malloc (vg_replace_malloc.c:195)
==8724== by 0x4016B6: initHashTable (hash.c:522)
==8724== by 0x4019CE: main (hash.c:792)
==8724== Use of uninitialised value of size 8
==8724== at 0x4C264C4: strcmp (mc_replace_strmem.c:412)
==8724== by 0x4017A0: lookup (hash.c:551)
==8724== by 0x401820: add(hash.c:566)
==8724== by 0x401AAB: main (hash.c:817)
==8724==
==8724== Invalid read of size 1
==8724== at 0x4C264C4: strcmp (mc_replace_strmem.c:412)
==8724== by 0x4017A0: lookup (hash.c:551)
==8724== by 0x401820: add (hash.c:566)
==8724== by 0x401AAB: main (hash.c:817)
==8724== Address 0x0 is not stack'd, malloc'd or (recently) free'd
==8724==
==8724==
==8724== Process terminating with default action of signal 11 (SIGSEGV)
==8724== Access not within mapped region at address 0x0
==8724== at 0x4C264C4: strcmp (mc_replace_strmem.c:412)
==8724== by 0x4017A0: lookup (hash.c:551)
==8724== by 0x401820: add (hash.c:566)
==8724== by 0x401AAB: main (hash.c:817)
==8724== If you believe this happened as a result of a stack
==8724== overflow in your program's main thread (unlikely but
==8724== possible), you can try to increase the size of the
==8724== main thread stack using the --main-stacksize= flag.
==8724== The main thread stack size used in this run was 8388608.
Reading this my first thought that my number didnt have a null terminator. So,i re-initialize it and on its last index i added the null. Unfortunately,problem as you can see remains. On its first run (the lookup function) it compares the number with the list;s number which is null. There is the segmentation. But im wandering why. Can't it just return NULL ?
Thank you.
--leak-check=full
and--track-origins=yes
– ChristofferArray
? – Christoffer-g
then Valgrind will give better error reports (with source code line numbers). – caf