Channing Moor
Channing Moor

Reputation: 1

Access violation reading with skip list

I am doing Stroustrup's PPP2 chapter 18 exercise 11: "Research and implement a skip list." This code gives the exception: Exception thrown at 0x00007FF61A3E656F in Skip List.exe: 0xC0000005: Access violation reading location 0x0000000000000020.

#include <iostream>
#include <vector>
#include <math.h>

// Error on lines 91 & 95: read-access violation: could be related to nullptr in constructors
// Only the first half is relevant to the exception
// 
const int maxLevel = 16;

class Node {
public:
    std::vector<Node*> next; // vector to hold next nodes at each level
    int value;

    Node(int value, int level) : value(value), next(level+1, nullptr) {}; // each node knows its position in the hierarchy, next vector is initialized to have level+1 elements, all set to 0

    void addNext(Node* node, int level) // add space for upcoming elements if next is not big enough
    {
        if (level >= next.size())
        {
            next.resize(level + 1, 0); 
        }
        next[level] = node;
    }

    ~Node() // destructor
    {
        for (auto& n : next)
        {
            delete n;
        }
    }
};

class skipList {
    int level;
    Node* head; // starting point of the skipList
    double P; // fraction/percentage of promotion
public:
    skipList() : level(1), head(), P(0.5) {}; // Default 
    skipList(int level, Node* head, double P) : level(level), head(head), P(P) // Constructor with parameters 
    {
        try {
            if (head == nullptr)
            {
                std::runtime_error("head can't be nullptr");
            }
        }
        catch (std::exception& e)
        {
            std::cerr << "Exception: " << e.what() << std::endl;
        }
        catch (...)
        {
            std::cerr << "Unkown Exception!" << std::endl;
        }
    }

    // main functions
    void insert(int value);
    void remove(int value);
    void search(int value);
    void display();

    // helper functions
    int randomNumber();
};

int skipList::randomNumber()  
{
    float r = (float)rand() / RAND_MAX;
    int lvl = 0;
    while (r < P && lvl < maxLevel)
    {
        lvl++;
        r = (float)rand() / RAND_MAX;
    }
    return lvl;
}

void skipList::insert(int value)
// Insert into base level
// Promote the inserted element depending on a probability
// Repeat until highest level or no promotion possible
try {
    //    Key of next node is less than key to be inserted then we keep on moving forward on the same level
    //    Key of next node is greater than the key to be inserted then we store the pointer to current node i at update[i] and move one level down and continue our search.
    Node* newNode = new Node(value, 0);
    Node** current = &head;

    for (int i = level; i >= 0; --i)
    {
        if (*current == nullptr) break;
        while ((*current)->value < value && *current != nullptr)
        {
            current = &(*current)->next[i]; // increment current, & returns address of pointer to next
        }
        if (*current != nullptr || (*current)->value > value) 
            // reached point of insertion or end of level
        {
            break;
        }
        else
        {
            newNode->addNext(*current, i);
            *current = newNode;
        }
    }

    int rlvl = randomNumber(); // generate random level for node
    // If level is increasing
    if (rlvl <= maxLevel && rlvl != level)
    {
        //Add new nodes at the top level
        for (int i = level; i < rlvl; ++i)
        {
            newNode->addNext(newNode, i); 
        }
        // Update the head pointer
        head = newNode;
        level = rlvl; 
    }
}
catch (std::exception& e)
{
    std::cerr << "Exception: " << e.what() << std::endl;
}
catch (...)
{
    std::cerr << "Unkown Exception!\n";
}

void skipList::display()
// Function to display the skipList
{
    std::cout << "\n\n\t---skipList---\n\n";
    for (int i = level; i >= 0; i--) // start at top level, go down
    {
        Node* temp = head;
        while (temp != nullptr)
        {
            std::cout << temp->value << " ";
            temp = temp->next[i];
        }
        std::cout << std::endl;
    }
}

int main()
{
    // seed randnum generator
    srand((unsigned)time(0));

    // insert() test
    Node node(1, 1);
    skipList SkipList(1, &node, 0.5);

    for (int i = 1; i <= 15; i++)
    {
        SkipList.insert(i); 
    }
    SkipList.display();   
}

After removing certain pieces of the code, it seems like the issue is me dereferencing a nullptr in the nested while loop and if statement in skipList::insert(): (*current)->value >/< value. When I get rid of this piece of code, it runs but outputs nothing. I have added a cout before this if statemment: if (*current == nullptr) break;, and it outputs a bunch of 0's, which I assume means its a nullptr. I've tried changing around my constructors but nothing I do seems to fix it. Any help is appreciated! Thanks in advance!

Upvotes: 0

Views: 52

Answers (0)

Related Questions