Double hashing closed hashing hash table issue

Question

I don't understand what's wrong. I went through the program multiple times using the rubber ducky technique. What's the issue please?

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

enum state {legitimate, empty, deleted};

typedef struct 
{

    enum state info;
    char *key;
    char *value;

}cell;

typedef struct 
{

    cell *cells;
    unsigned int size;

}hash_table;

 
unsigned int
hash1(const char *key, unsigned int size)
{
    unsigned int hash = 0;
    
    for(unsigned int i = 0; key[i]; i++)
    {
        hash = (hash << 5) + key[i];
    }

    return (hash%size);

}

unsigned int
hash2(const char *key)
{
    unsigned int hash = 0;
    unsigned int prime = 3;
    
    for(unsigned int i = 0; key[i]; i++)
    {
        hash = prime - (key[i] % prime);
    }

    return (hash);

}


hash_table*
initialize(unsigned int size)
{
    hash_table *H = malloc(sizeof(*H));
    H->cells = malloc(sizeof(*H->cells)*size);

    for(unsigned int i = 0; i<size; i++)
    {
        H->cells[i].info = empty;
    }

    return H;

}

unsigned int
find(hash_table *H, const char *key)
{
    unsigned int index = hash1(key, H->size);
    unsigned int hash = hash2(key);
    unsigned max = index;

    while(H->cells[index].key!=key && H->cells[index].info!=empty)
    {
        index = (index+hash)%H->size;

        if(index==max){printf("Not found!"); return -1;}
        if(index>=H->size){index-=H->size;}

    }

    return index;
    

}

void
insert(hash_table *H, const char *key, const char *value)
{
    unsigned int index = find(H, key);

    if(H->cells[index].info!=legitimate)
    {

        H->cells[index].key= malloc(strlen(key)+1);
        H->cells[index].value = malloc(strlen(value)+1);


        strcpy(H->cells[index].key,key);
        strcpy(H->cells[index].value,value);

        H->cells[index].info = legitimate;

    }
}

void
dump(hash_table *H)
{
    for(unsigned int i = 0; i<H->size; i++)
    {   
        if(H->cells[i].info!=legitimate){continue;}

        printf("Index[%d]: %s\n", i, H->cells[i].value);
    }
}


int main()
{
    hash_table *H = initialize(10);
    insert(H,"name1","David");
    insert(H, "name2", "Radka");
    dump(H);
    return 0;
}

OUTPUT:

NO OUTPUT

I checked if hash1(), hash2(), and find() functions work, and they do, checked with multiple inputs everything seemed to work as it should. I am not sure what is missing or what I did wrong. Please help.

Answer 1

Since your program generates a core dump, you can take advantage of that

Run your program, you get

Floating point exception (core dumped)

When a process terminates unexpectedly it generates a file with the process memory contents (a snapshot of the program at the time of the crash). Since core file creation is disabled by default, we use the ulimit command to enable writing core files:

Open a console and set the process resources limit to unlimited

ulimit -c unlimited

Run again your program to generate the core file

Launch the debugger using the generated core file

> gdb demo core

Program terminated with signal SIGFPE, Arithmetic exception.
#0  0x000055cd5fe03202 in hash1 (key=0x55cd5fe04024 "name1", size=0) at demo.c:35
35      return (hash%size);

It crashes at hash1(), lets see why:

(gdb) print hash
$1 = 118636753
(gdb) print size
$2 = 0

You got it! dividing by zero in return (hash%size);

The prototype of hash1 is

unsigned int hash1(const char *key, unsigned int size);

Check who is calling hash1() with size set to 0:

(gdb) frame 1
#1  0x0000555555555309 in find (H=0x5555555592a0, key=0x555555556024 "name1") at demo.c:73
73      unsigned int index = hash1(key, H->size);

H->size is the culprit, it is used uninitialized.

hash_table*
initialize(unsigned int size)
{
    hash_table *H = malloc(sizeof(*H));
    H->cells = malloc(sizeof(*H->cells)*size);

    for(unsigned int i = 0; i<size; i++)
    {
        H->cells[i].info = empty;
    }
    H->size = size; // Initialize it here
    return H;
}