problem with initializing a hash table

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.

blankTable->table[i]=malloc(sizeof(List));
blankTable->table[i]=NULL;

You allocate memory for List item and then set it to NULL (0x0).

The following toy program works correctly (well, does not segfault at least) with the struct definitions and functions you posted:

#include <stdlib.h>
#include <assert.h>

/* code from question omitted */

int main(void) 
{
    HashTable * hash = initHashTable(5);
    int i;

    assert(hash->size == 5);

    for ( i = 0; i < hash->size; i++ )
        assert(hash->table[i] == NULL);

    free(hash);

    return EXIT_SUCCESS;
}

I assume the above is correct, that you consider a NULL pointer to be an "empty" list, right? (The insert function would thus replace the appropriate NULL with the first element of a new list.)

If so, you can simplify things a great deal. It is possible to write an initializer that makes the above toy program run cleanly through valgrind. I don't want to cheat you of the discovery, but I can hint that you might want to look up what flexible arrays are and how they work.

Ignoring the problems in the initialization function (valgrind should tell you pretty precisely what is wrong once you have the application not segfaulting), what are the bounds for the function hash() in the lookup function?

You try to read the value of hashtable->table[hash(number)], so hashtable must be initialized with at least that many elements, otherwise you will read from memory you have not allocated (hence the segmentation fault).

Perhaps you meant

List * lookup(HashTable *hashtable, char *number)
{
    assert(hashtable != NULL);
    assert(number != NULL);

    unsigned int hashval = hash(number) % hashtable->size;
    List * list = hashtable->table[hashval];

    assert( list == NULL || list->number != NULL );

    while ( list != NULL && strcmp(number,list->number)!=0)
    {
        list = list->next;
        assert ( list == NULL || list->number != NULL );
    }

    return list;
}

Updates: You can not pass a null pointer to strcmp, from the valgrind log you posted that is the reason you get a segmentation fault. The lookup function above has been updated with some more asserts to make sure that this does not happen.

Also, the valgrind hints that you have passed an uninitialized value to strcmp, this might be the null pointer (if the uninitialized value happens to be zeroed). However, there is still some vital information lacking to properly answer this question, could you perhaps post the whole file hash.c somewhere?

After reading through the file: I have to be honest, you have some very serious problems in that code :-) I think you do not yet grasp the concept of manual memory handling and initialization -- is it perhaps possible that you learned Java first?

In any case, here are the problems I spot in no particular order:

1. In init_array_for_antennas(), you initialize the local variable MyArray, not the global. Just remove the local variable and you should be OK.
2. Static and global variables are implicitly initialized to zero, so almost everything in init_array_for_antennas() is just redundant.
3. In several places, you "initialize" pointers with malloc() and then set the pointer to its actual value. This is a classic memory leak; you will not be able to free such memory since you overwrite the reference to it.
4. The statement number[strlen(number)]='\0'; is, well, just redundant. Think about how strlen() works and you should see it yourself.
5. If you have not already, read up what asserts are and learn how you can use them to check your assumption. Commenting out assert(pointer_you_dereference_later != NULL); is just wrong.
6. When you already have a pointer to a string, you do not have to copy the contents to a local array and then pass that array to underlying functions - just pass the pointer!
7. You use the global constant bucket_size in some places, and the hashtable struct field size in others. This is an error just waiting to happen, either make the size field an actual compile-time constant, or use the runtime value properly.
8. A matter of style, really, but you typedef a lot of struct to nice, human-readable names, and yet consequently add the 'struct' keyword anyway.
9. If you use calloc() instead of malloc() you get zeroed memory. For instance, allocating an array of pointers with calloc() will make them initialized to NULL, and you do not need to do that explicitly.

Well, there's probably more but that's it for tonight. I'd guess the first point in the list is the cause of your actual problem :-)