Hash Table - Conditional jump or move depends on uninitialised value(s)

0
votes

I am coding a HashTable using a Doubly Linked list for one of my classes, but I am running into an error when I run valgrind. It says: Conditional jump or move depends on uninitialised value(s). When I run --track-origins=yes, it says:

==11453== Conditional jump or move depends on uninitialised value(s)
==11453==    at 0x402904: LinkedList<std::string>::itemExists(std::string const&) (LinkedList.h:89)
==11453==    by 0x401FE6: HashSet<std::string>::find(std::string const&) (HashSet.h:85)
==11453==    by 0x401E42: HashSet<std::string>::add(std::string const&) (HashSet.h:39)
==11453==    by 0x4019D7: insert(std::string, std::basic_ifstream<char, std::char_traits<char> >&, std::basic_ofstream<char, std::char_traits<char> >&, std::string, HashSet<std::string>&) (main.cpp:64)
==11453==    by 0x4015B1: main (main.cpp:34)
==11453==  Uninitialised value was created by a heap allocation
==11453==    at 0x4C2B800: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11453==    by 0x4024D8: HashSet<std::string>::rehash() (HashSet.h:131)
==11453==    by 0x401E69: HashSet<std::string>::add(std::string const&) (HashSet.h:45)
==11453==    by 0x4019D7: insert(std::string, std::basic_ifstream<char, std::char_traits<char> >&, std::basic_ofstream<char, std::char_traits<char> >&, std::string, HashSet<std::string>&) (main.cpp:64)
==11453==    by 0x4015B1: main (main.cpp:34)

So I think the problem is in my rehash function, but I can't figure out where it is. Could you guys help me out? Here is my rehash function:

void rehash()
{
    int old_size = tableSize;
    if (tableSize == itemsStored) {
        tableSize = tableSize * 2 + 1;
    }

    else if (itemsStored <= tableSize/2) {
        tableSize = tableSize / 2;
    }
        LinkedList<string>* newTable = new LinkedList<string>[tableSize];    -------> line 131
        for (int i = 0; i < old_size; ++i)
        {
            int table_size = 0;
            table_size = table[i].getSize();
            if(table_size != 0) {
                for (int j = 0; j < table_size; ++j) {
                        unsigned index = hashFunction(table[i].getItem(j)) % tableSize;
                        newTable[index].insert(newTable[index].getSize(), table->getItem(i));

                }
            }
        }
        LinkedList<string>* temp = table;
        table = newTable;
        delete [] temp;

}

And this is my constructor for the Hash Set:

HashSet()
{
    int tableSize = 0;
    table = new LinkedList<string>[tableSize];
}

This is my constructor for the LinkedList:

LinkedList()
{
    size = 0;
}

Thank you!

2
c++hashtablevalgrind
The problem could equally well exist in the insert code-path. Why don't you step through with a debugger to see what's going on? - Oliver Charlesworth
Can you mark line 131? - Daniel Jour
And: Are all members of a linked list initialised in its constructors? - Daniel Jour
@OliverCharlesworth , thank you so much for answering. So, the problem is that my debugger won't complain about it. It runs perfectly fine, valgrind is the one that accuses the issue, and in order for me to get full credit for this assignment, valgrind must be happy. I will check the insert code again, though. - Victor Lazaro
@DanielJour, thank you for your help! I edited the question, marking line 131 and showing my constructors. - Victor Lazaro

2 Answers

1
votes

I'm going to take a lucky guess here: your LinkedList contains a head pointer and your itemExists function loads that pointer before checking if the size field is greater than zero.

Something like

Node* node = head;
for (size_t i = 0; i < size; i++)
{
    if (node->hash == ...)
    ...
    node = node->next;
}

Looks innocent because the pointer isn't dereferenced if size == 0, but reading an uninitialized pointer is UB in itself.

0
votes

Oh my, that's hard to spot. If it isn't what @PaulGroke already suggested, then there's also a potential problem here:

HashSet()
{
    /* */int/* */ tableSize = 0; // HERE!
    table = new LinkedList<string>[tableSize];
}

From your rehash member function I'd guess that your hash set class has a member named tableSize. The above constructor has a local variable with the same name that shadows this member. As consequence, the member field is never initialised, and you have undefined behaviour. Removing the marked int should solve this.

In general, you should use the initialiser list to write your constructors:

HashSet()
 : tableSize(0), 
   table(new LinkedList<string>[tableSize]); {
}

Though it's debatable whether this should be done for allocations as I did above, but then you normally shouldn't use raw new or new [] in code at all, better std::shared_pointer/std::unique_pointer or std::vector.