CODEWITHSUNDEEP
chashtable
Arwaa Rasool
Arwaa Rasool

Reputation: 49

Hash Tables- Segmentation Fault

Not sure why I'm getting a segmentation fault here. I'm trying to create a hash table that would have collisions and the data should be string. So I'm using a char array for the data. Need to detect collisions at the end. 

#define SIZE 20    
struct DataItem
{
    char data[50];
    int key;
};

struct DataItem* hashArray[SIZE];
struct DataItem* dummyItem;
struct DataItem* item;

int hashCode(int key)
{
    return key % SIZE;
}
void insert(int key, char data[50])
{

    struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
    strcpy(item->data, data);
    item->key = key;

//get the hash 
    int hashIndex = hashCode(key);

//move in array until an empty or deleted cell
    while (hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1)
    {
        //go to next cell
        ++hashIndex;

        //wrap around the table
        hashIndex %= SIZE;
    }

    hashArray[hashIndex] = item;
}

struct DataItem* delete(struct DataItem* item)
{
    int key = item->key;

    //get the hash 
    int hashIndex = hashCode(key);

    //move in array until an empty
    while (hashArray[hashIndex] != NULL)
    {

        if (hashArray[hashIndex]->key == key)
        {
            struct DataItem* temp = hashArray[hashIndex];

            //assign a dummy item at deleted position
            hashArray[hashIndex] = dummyItem;
            return temp;
        }

        //go to next cell
        ++hashIndex;

        //wrap around the table
        hashIndex %= SIZE;
    }

    return NULL;
}

int detect_collisions()
{
    int i = 0;
    int collision = 0;
    for (i = 0; i < SIZE; i++)
    {
        if (hashArray[i] != NULL)
        {
            if (hashArray[i]->key == hashArray[i + 1]->key)
                ;
            collision++;
        }

    }
    return collision;
}

void display()
{
    int i = 0;

    for (i = 0; i < SIZE; i++)
    {
        if (hashArray[i] != NULL)
        {
            printf("Phli dafa: %d\n", i);
            printf(" (%d,%s)", hashArray[i]->key, hashArray[i]->data);
        }
        else
            printf(" ~~ ");
    }

    printf("\n");
}
int main()
{
    dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
    strcpy(dummyItem->data, NULL);
    dummyItem->key = -1;

    insert(1, "check");
    display();
    delete(item);
}

Upvotes: 1

Views: 1832

Answers (3)

4386427
4386427

Reputation: 44274

You have a problem here:

strcpy(dummyItem->data,NULL);

as strcpy will dereference a NULL pointer.

To put in an empty string use:

strcpy(dummyItem->data, "");

Your second problem is:

delete(item);

item is NULL at this point. So here:

struct DataItem* delete(struct DataItem* item)
{
    int key = item->key;
              ^^^^^^

you dereference a NULL pointer.

Maybe your delete function should rather be:

struct DataItem* delete(int key)
{

The third problem is here (there are actually 3 problems here):

for (i = 0; i < SIZE; i++)
{
    if (hashArray[i] != NULL)
    {
        if (hashArray[i]->key == hashArray[i + 1]->key)
                                 ^^^^^^^^^^^^^^^^
                                 a) May be NULL
                                 b) Out of range when i == size-1
            ;
           ^^^
           c) Delete this
        collision++;
    }

}

My guess is that you want:

for (i = 0; i < SIZE-1; i++)        // Notice
{
    if (hashArray[i] != NULL && hashArray[i + 1] != NULL)   // Notice
    {
        if (hashArray[i]->key == hashArray[i + 1]->key)
        {
            collision++;
        }
    }
}

Upvotes: 3

LPs
LPs

Reputation: 16223

The problem is 

strcpy(dummyItem->data, NULL);

It will try to copy a string pointed by NULL (that is not pointing a string..) to your array. So it invokes Undefined Behavior

What you want (I guess) is

memset(dummyItem->data, 0x00, sizeof(dummyItem->data));

or

dummyItem->data[0] = 0x00;

or

dummyItem->data[0] = '\0';

Take also note that you must always check malloc return value: it can fail returning NULL

dummyItem = malloc(sizeof(struct DataItem));
if ( dummyItem != NULL)
{
   // YOUR STUFF
}

You have also a ; just after

if (hashArray[i]->key == hashArray[i + 1]->key)

remove it.

Last thing I can see

delete(item);

is UB because of item is not initialized because the code in insert function uses a local variable, maybe you want change

struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));

to

item = malloc(sizeof(struct DataItem));

EDIT 1

You are also accessing the array out of bounds with

if (hashArray[i]->key == hashArray[i + 1]->key)

hashArray[i + 1] is out of bounds when i = SIZE-1 Moreover hashArray[i + 1] can be NULL or not initialized.

Upvotes: 2

Chris Turner
Chris Turner

Reputation: 8142

If you compile your code with debugging turned on ( ie -g option with gcc ) and then run it in a debugger it will tell you what lines the seg faults are happen on. There are two places that are causing a seg fault that I can see - the strcpy being passed a NULL and also the call to delete(item) where item is still NULL. Presumably because you think you're using the one defined in insert rather than the globally defined one.

Upvotes: 0

Related Questions