2

I have a lengthy program that basically manages a hash table; adds, deletes, etc. I'm hitting an extremely bizarre bug in my program, though.

Basically I have a delete function that hashes a values, checks a linked list stored in an array given by a hash value for the appropriate object, and, if found, deletes it and exits the function. It looks essentially like this:

template<typename T>
void HashTable<T>::remove(T* t){
    LinkedList<T> list= data[(hash(t))];
    Node<T>* prev = NULL;
    Node<T>* cur = list.head;
    bool running = cur != NULL;
    while(running){
      T key = cur->getKey();
      if(t == key){
          if(prev == NULL){ 
              cur = cur->getNext();
              running = false;
          }else{
              prev->setNext(cur->getNext());
              cout << &key << '\n';
              cur = NULL;
              running = false;
          }
      }
      prev = cur;
      cur = cur->getNext();
    }
    cout << "Are we getting here?"; //yes
}

I'm calling this function in this way:

Type* b = buildType(); //produces a Type* from CL arguments
hash.remove(b);
cout << "Are we getting to THIS SPOT?"; //no

Basically, the above program outputs "Are we getting here?" but not "Are we getting to THIS SPOT?"

I have no clue what could be the problem in this case, and it took me quite a while to even realize that there could possibly be a problem here. Does anyone know what the issue could possibly be?

Kara
  • 6,115
  • 16
  • 50
  • 57
Benjamin Kovach
  • 3,190
  • 1
  • 24
  • 38
  • 7
    Try `cerr` instead. If still a problem, check for a possible bug in `LinkedList<>` destructor. – jxh Apr 24 '13 at 20:22
  • 2
    Run it under the debugger and hit the pause button. You'll see why it's hung. – Mike Dunlavey Apr 24 '13 at 20:23
  • It seems there is an unintentional copy of LinkedList instance. Does it go away if you change the first line in remove() to LinkedList& list = data[...] ? – alexm Apr 24 '13 at 20:25
  • @user315052 When I replace both `cout`s with `cerr`, the program actually stops hanging and starts breaking after outputting "Are we getting here?" What does this mean? – Benjamin Kovach Apr 24 '13 at 20:26
  • 2
    @BenjaminKovach: Define *breaking*. – jxh Apr 24 '13 at 20:27
  • Possible memory corruption, run under valgrind. – Pete Fordham Apr 24 '13 at 20:28
  • @user315052 Sorry -- I'm not great with C++ yet. I'm on Windows and getting an error box saying that the program has stopped working. Though, I might have found a solution with all of this help -- making the changing the linked list to a pointer to one may have actually fixed everything. – Benjamin Kovach Apr 24 '13 at 20:29
  • 1
    You probably would not have observed this particular problem if you had obeyed the [Rule of Three/Five](http://stackoverflow.com/questions/4782757/rule-of-three-becomes-rule-of-five-with-c11) with respect to `LinkedList<>`. But, you would have experienced a different bug instead (remove not removing). – jxh Apr 24 '13 at 20:32
  • @user315052 Thanks; I'll keep that in mind for the future! – Benjamin Kovach Apr 24 '13 at 20:45

1 Answers1

4

In this line

LinkedList<T> list= data[(hash(t))]

you are creating a copy of the LinkedList you are obtaining from data. I bet you do not mean to be making a copy, but mean to be using a reference. Furthermore, I'd guess it is using the default copy constructor rather than one you intentionally created. Then when the destructor for that copy of the LinkedList is called, it is deleting heap entries that are still held by the original LinkedList, resulting in heap corruption and eventually a hang.

antlersoft
  • 14,636
  • 4
  • 35
  • 55