C++ Segmentation fault in while loop when looking up values for a hash table

Question

I've been working on this on and off all weekend - trying to find where my seg fault occurred. I have narrowed it down to this function and think I know "why" it happens. The seg fault ONLY occurs when it runs into a NULL field in the hash table when performing a lookup.

The only time the @@@ null value in table @@@ outputs is just before a seg fault - never anywhere else. I have a continue statement after it - and even put the case in the while loop. How come it is still faulting? The "next..." never shows up either. It just ends at the @@ null value @@ error and seg faults right after.

Any help? Code provided below

record *hashtable::lookup(keytype k)
{
    if (!table) return NULL;
    int i;
    int pos = hash(k, i = 0);
    if ((pos < 0) || (pos >= tsize)) return NULL;
    i = 0;
    while ((table[pos]->key != k && i < tsize) || (table[pos] == NULL && i < tsize))
    {
        cout << "next.." << endl;
        i++;
        pos = (hash(k, 0) + i*secondhash(k)) % tsize;
        if (table[pos] == NULL)
        {
            cout << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@null value in table@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@" << endl;
            continue;
        }
        else {

        }
    }
    cout << "Got out of loop..." << endl;

    if (table[pos]->key == k) return table[pos];

    return NULL;
}

Your while condition first execute table[pos]->key before verifying that table[pos] != NULL). This creates a segmentation fault if table[pos] == NULL. — Franck
@Franck Oh my. You're right by the looks of it. Thank you I can't believe I've been working at this for hours and didn't see that. If you would like to submit that as an answer I could set this question to answered. — Fivestar

Franck Franck · Accepted Answer · 2016-10-30T21:03:15

The problem is likely to be in the condition of your while loop.

The condition first accesses to table[pos]->key even if table[pos] == NULL can be true as suggested by the second part of your condition. This creates a segmentation fault each time table[pos] == NULL. A simple solution consists in swapping both parts of the logical or.

You could replace

while ((table[pos]->key != k && i < tsize) || (table[pos] == NULL && i < tsize))

by

while ((i < tsize) && ((table[pos] == NULL) || (table[pos]->key != k)))

C++ Segmentation fault in while loop when looking up values for a hash table

1 Answers