Segmentation fault when installing key value in hash table

Question

EDIT: I have updated the init function(code updated) to use malloc and the segmentation fault is gone. However I get no output from the print table function now. Further updated the code as per suggestions. It seems to work now.

I've been following K&R (beginner in C) for C and tried writing a hashtable using their example in section 6.7 (with few modifications)

The code is below-

#include <stdio.h>
#include <string.h>
#include "hashtable.h"

#define HASHSIZE 101


listptr * init_table()
{
    listptr *hashtab = (listptr *) calloc(HASHSIZE, sizeof(*hashtab));
    return hashtab;
}

unsigned hash (char *s)
{
    unsigned hashval;

    for (hashval=0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;

    return hashval % HASHSIZE;
}

listptr lookup (listptr * hashtab, char *s)
{
    listptr np;

    for (np = hashtab[hash(s)]; np!=NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np;
    return NULL;
}

listptr install(listptr * hashtab, char *name, char * defn)
{
    listptr np;

    unsigned hashval;

    if((np = lookup(hashtab, name)) == NULL) {
        np = (listptr) malloc(sizeof(*np));
        if (np==NULL || (np->name = strdup(name))==NULL)
            return NULL;

        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    }
    else
    {
        free((void*) np->defn);
    }
    if ((np->defn = strdup(defn)) == NULL)
        return NULL;

    return np;
}

void printtable(listptr * table, int len)
{
    listptr p;
    int i =0;
    while (i < len) {
        if (table[i] != NULL) {
            for (p = table[i];p!=NULL;p=p->next) {
                printf("%s\t%s\n", p->name, p->defn);
            }
        }
        i++;
    }
}

hashtable.h contains -

#ifndef HDR
#define HDR

#include <stdlib.h>

typedef struct nlist *listptr;

typedef struct nlist {
    listptr next;
    char *name;
    char *defn;
} Hashtablebucket;

listptr * init_table();
listptr lookup(listptr *, char *);
listptr install (listptr *, char *, char *);
void printtable(listptr *, int );

#endif

In main.c I have -

#include <stdio.h>
#include <string.h>
#include "hashtable.h"

int main()
{
    listptr * table = init_table();


    install(table, "key1", "value1");
    install(table, "key2", "value2");
    install(table, "key3", "value3");

    printtable(table, 101);

    return 0;
}

This results in a segmentation fault and I have no idea what could be wrong as the hashtable has 101 elements of space.

Would appreciate any help in debugging the problem...

EDIT: With the above code there is no output at all. Could someone please help with the debug?

Thanks in advance

Answer 1

The original K&R code assumes a global table. In your case you try to allocate it locally, but you cannot return a pointer to local variable (well, you can, but the behaviour is undefined). Instead you need to allocate the memory using malloc/or even better, calloc in this case:

listptr * init_table()
{
    listptr *table = calloc(HASHSIZE, sizeof *table);
    return table;
}

It would be preferable to make a struct for the hash table, so that you can have tables of different sizes:

struct hashtable {
    size_t n_slots;
    listptr *slots;
};

struct hashtable *init_table(size_t n_slots) {
    struct hashtable *tbl = malloc(sizeof *tbl);
    tbl->n_slots = n_slots;
    tbl->slots = calloc(n_slots, sizeof *(tbl->slots));
    return tbl;
}

---

For hash function, it is better to keep it so that it returns an unsigned int (or size_t!) always, and do the modulo outside that function. Also, char can be signed or unsigned; you'd most probably want to use unsigned chars.

I.e.

size_t hash (char *s)
{
    size_t hashval;

    for (hashval=0; *s != '\0'; s++)
        hashval = *(unsigned char*)s + 31 * hashval;

    return hashval;
}

and

hashval = hash(name) % tbl->n_slots;