Fivestar Fivestar - 1 month ago 13
C++ Question

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

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;
}

Answer

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)))