Heap corruption in my skip list

Question

I'm having this problem with my skip list implementation, where I get a heap corruption, when I return 0; in my int main(). That's atleast where I debugged to, until it crashed.

Debug error

enter image description here

This is my code:

skipnode.h

template <typename T>
class SkipNode
{
public:
    T data;
    SkipNode<T> **next;
    SkipNode(T d, int level);
    ~SkipNode();
};

skipnode.cpp

#include "skipnode.h"

template<typename T>
SkipNode<T>::SkipNode(T d, int level)
{
    data = d;
    next = new SkipNode<T>*[level];

    for (int i = 0; i < level; i++)
        next[i] = 0;
}

template<typename T>
SkipNode<T>::~SkipNode()
{
    delete [] next;
}

skiplist.h

#include "skipnode.cpp"

#define MAXLEVEL 4

template<typename T>
class SkipList
{
public:
    SkipList();
    ~SkipList();
    int randLvl(int max);
    T search(T);
    void insert(T);
private:
    SkipNode<T> *root; 
};

skiplist.cpp

#include "skiplist.h"
#include <stdlib.h>
#include <time.h>

template<typename T>
SkipList<T>::SkipList()
{
    root = new SkipNode<T>(0,MAXLEVEL);
}

template<typename T>
SkipList<T>::~SkipList()
{
    delete root;
}

template<typename T>
int SkipList<T>::randLvl(int max)
{
    srand(time(NULL));
    return rand() % max + 1; //+ 1, så værdien ikke bliver 0
}

template<typename T>
void SkipList<T>::insert(T value)
{
    int level = randLvl(MAXLEVEL);

    SkipNode<T> *insertNode = new SkipNode<T>(value,level);
    SkipNode<T> *currentNode = root;

    for (int i = level; i > 0; i--)
    {
        for (; currentNode->next[i] != 0; currentNode = currentNode->next[i])
        {
            if (currentNode->next[i]->data > value)
                break;
        }
        if (i <= level)
        {
            insertNode->next[i] = currentNode->next[i];
            currentNode->next[i] = insertNode;
        }
    }
}

main.cpp

#include "skiplist.cpp"

int main()
{
    SkipList<int> SList;
    SList.insert(3);
    return 0;
}

I have a theory, that the error could be happening in this line in skiplist.cpp:

if (currentNode->next[i]->data > value)

because it seems like it can't access next->data, but I don't know why.

Can anyone help me out? And sorry, if I ask the question wrong, I'm kinda new to Stack Overflow. Thanks in advance!

Not to do with the crash, but constantly seeding your RNG with the time will mean that it returns the same number over and over until the time changes, which is probably not what you intended. — Gareth Davidson, Dec 03 '14 at 15:59
Hmm, it produces different outputs. Maybe I dont quite understand what you mean? — Thisen, Dec 03 '14 at 16:03
Are you sure? `time` returns a `time_t` which, on most platforms is the number of seconds since the epoch. You're seeding a pseudo random number generator with that, so it ought to return the same number until the clock changes to the next second. — Gareth Davidson, Dec 03 '14 at 16:16
Just tested it. Outputs: 4, 3, 3, 1, 2, 4, 1. Looks like it works :) — Thisen, Dec 03 '14 at 16:23
Try using Microsoft's [Application Verifier](http://www.microsoft.com/en-us/download/details.aspx?id=20028) to trap the corruption. It will invoke a debug stop if one is found. — rrirower, Dec 03 '14 at 19:51

score 3 · Accepted Answer · answered Dec 04 '14 at 12:28

3

You have an off-by-one error in the for loop in insert(T), it probably should be

for (int i = level-1; i >= 0; i--)

Also insert() leaks memory, delete insertNode

answered Dec 04 '14 at 12:28

Tatu Lahtela

4,514
30
29

score 1 · Answer 2 · edited May 23 '17 at 11:57

1

perhaps try gflags, see this answer :

https://stackoverflow.com/a/2476077/3986139

after enabling gflags you can get the exception in VS right at the time of heap corruption instead of the exception after the event

edited May 23 '17 at 11:57

Community

1
1

answered Dec 04 '14 at 09:19

apapa

669
13
22

Heap corruption in my skip list

2 Answers2