samedi 24 mars 2018

A very bizarre bug about run an uncalled statement in a function

Here I find a very strange bug about a little program in C++.

I wrote a doubly linked list, I thought this is rather simple, but it crashed every time and I don't know why.

After long time debugging, I find it always jumps to a statement within a function and then crash.

I marked that statement in the dllist.cpp.

It's so strange to me, how can you run a statement within a function without calling it? Or is there something else go wrong?

dllist.h:

class DLLElement{
public:
    DLLElement(void *itemPtr, int sortKey);
    DLLElement *next;
    DLLElement *prev;
    int key;
    void *item;
};

class DLList{
public:
    DLList();
    ~DLList();


    void *Remove(int *keyPtr);

    bool isEmpty();

    void SortedInsert(void *item, int sortKey);

private:
    DLLElement *first;
    DLLElement *last;
};


void genItems(DLList *dl, const int N);
void remove(DLList *dl, const int N);

dllist.cpp:

#include "dllist.h"

const int min = 0;
const int max = 1;

DLLElement::DLLElement(void *itemPtr, int sortKey){
    item = itemPtr;
    key = sortKey;
}

DLList::DLList() {
    first = nullptr;
    last = nullptr;
}

DLList::~DLList(){
    int *key;
    if(!isEmpty()){
        Remove(key);
    }
}

bool DLList::isEmpty() {
    if(first == nullptr && last == nullptr)
        return true;
    else
        return false;
}


void *DLList::Remove(int *keyPtr) {

    if(isEmpty())       // if list is empty, then there is no need to search
        return nullptr;

    auto fst = first;
    auto lst = last;

    if(fst == lst){
        first = nullptr;
        last = nullptr;
        *keyPtr = fst->key;

        void *item = fst->item;
        delete fst;
        return item;
    }
    else{
        first = first->next;
        first->prev = nullptr;

        ///////// crush statement ///////////
        *keyPtr = fst->key;
        /////////////////////////////////////

        void *item = fst->item;
        delete fst;
        return item;
    }
}

void DLList::SortedInsert(void *item, int sortKey) {

    DLLElement *newElm = new DLLElement(item, sortKey);

    if(isEmpty()){
        newElm->prev = nullptr;
        newElm->next = nullptr;
        first = newElm;
        last = newElm;
        return;
    }
    if(sortKey < (first->key)){     // if sortKey is even smaller than first key, then do preappend.
        newElm->prev = nullptr;
        newElm->next = first;
        first->prev = newElm;
        first = newElm;
        return;
    }
    if(sortKey >= (last->key)){   // if sortKey is even larger than last key, then do append
        newElm->next = nullptr;
        newElm->prev = last;
        last->next = newElm;
        last = newElm;
        return;
    }

    // else, assert newElm in the middle
    auto fst = first;
    auto lst = last;
    while(fst!=lst){
        fst = fst->next;
        if(sortKey <= (fst->key)){
            newElm->prev = fst->prev;
            newElm->next = fst;
            fst->prev->next = newElm;
            fst->prev = newElm;
            return;
        }
    }
}

In main function, just call it:

#include "dllist.h"

int main() {
    DLList dl;
    void* item = nullptr;
    dl.SortedInsert(item, 5);
    return 0;
}

Aucun commentaire:

Enregistrer un commentaire