A hashtable of pointers in C?

Question

I am trying to build an initialize a hashtable whose pointers point to another struct in my program. But it seems to give me a segfault when I try to initialize(H). I think I may be allocating memory incorrectly, but I'm not sure if that's what a segmentation fault actually means. The way it is set up, H->hashtable should be an array of hashnodes, right? hashnodes themselves are the pointers to my other structs. Why am I only getting a seg fault at initialize?

    #include <stdio.h>
    #include <stdlib.h>

    typedef struct Position{
        char data[12];
        struct Hashnode *previous;
        struct Position *next;
        char letter;
        char direction[5];
    } *position;

    typedef struct Hashnode{
       struct Position *INSIDE;
    } *hashnode;

    typedef struct hash_table{
       hashnode *hashtable
    } *HTABLE;


    HTABLE NewHashtable(){
     HTABLE H = (HTABLE) malloc(sizeof(struct hash_table));
     if(H == NULL){ printf("Malloc for new hashtable failed."); exit(1);}
     return H;
    }



    void initialize(HTABLE H){

        H->hashtable = (hashnode*) malloc(100003*sizeof(hashnode));

        int toofer;
        for(toofer = 0; toofer<100003; toofer++){
                 H->hashtable[toofer]->INSIDE = NULL;
                 }
            }

   int main(){
       HTABLE H = NewHashtable();
       initialize(H);

       return 0;
   }

ugly: struct Position; *position; struct hash_table; *HTABLE. uppercase, lowercase, underscore, maybe camelCase. — Peter Miehle, Dec 17 '12 at 14:56
@PeterMiehle, It looks like the microsoft naming convention: HANDLE, something->MEMBER etc. Why is microsoft still in business is beyond my understanding. — Shahbaz, Dec 17 '12 at 15:03

score 3 · Answer 1 · edited May 23 '17 at 11:57

This:

HTABLE H = (HTABLE) malloc(sizeof(struct hash_table));

is just horrible. It mixes a typedef:ed pointer (why do people still do this?) with the underlying struct name, making it the reader's job to make sure they match. Plus, that cast is a bad idea, too.

It should be:

HTABLE H = malloc(sizeof *H);

if you insist on keeping the typedef.

That said, the code in initialize() is probably failing its malloc() call, which is not checked before being relied on. This is a very bad idea.

Further, there's confusion about what exactly is being allocated. The malloc() code allocates 100003*sizeof(hashnode), but hashnode is (again) typedef:ed as a pointer, not a struct. Then the pointers are dereferenced in the loop, causing mayhem.

score 1 · Answer 2 · answered Dec 17 '12 at 14:56

    H->hashtable = (hashnode*) malloc(100003*sizeof(hashnode));

    int toofer;
    for(toofer = 0; toofer<100003; toofer++){
             H->hashtable[toofer]->INSIDE = NULL;
             }
        }

The first line allocates a bunch of memory for H->hashtable. It contains random garbage.

Thus, when you enter the loop, H->hashtable[0] is random garbage (because all of H->hashtable is random garbage). But you attempt to follow that random garbage pointer in in your loop. Dereferencing an uninitialized pointer is the fastest way to get a segmentation fault.

Here's a way to help you see it. Say you decided to zero that memory to be safe. Your code would be:

    H->hashtable = (hashnode*) malloc(100003*sizeof(hashnode));
    memset(H->hashtable, 0, 100003 * sizeof(hashnode));

    int toofer;
    for(toofer = 0; toofer<100003; toofer++){
             H->hashtable[toofer]->INSIDE = NULL;
             }
        }

Clearly, after that memset, *(H->hashtable) is 0 since that sets all of H->hashtable to 0. So H->hashtable[0] is 0 too and thus H->hashtable[toofer]->INSIDE dereferences a null pointer.

score 0 · Answer 3 · edited Dec 17 '12 at 14:59

0

H->hashtable = (hashnode*) malloc(100003*sizeof(hashnode));

should better be

...sizeof(struct Hashnode)...

edited Dec 17 '12 at 14:59

Shahbaz

46,337
19
116
182

answered Dec 17 '12 at 14:59

Peter Miehle

5,984
2
38
55

In fact, it best be `H->hashtable = malloc(... * sizeof(*H->hashtable));`. – Shahbaz Dec 17 '12 at 15:00
or even `H->hashtable = malloc(... * sizeof *H->hashtable);` in particular don't cast the return of `malloc`: http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc – Jens Gustedt Dec 17 '12 at 15:35

A hashtable of pointers in C?

3 Answers3