[c++] segfault w algorytmie Insa (szeregowanie zadan)

Witam,
piszę algorytm Insa dla problemu szeregowania zadań w job shop'ie dla przykładów Tailarda. Zasadniczo napisałem cały kod, kompiluje się, jednak przy debuggowaniu gdb wyrzuca mi Segmentation Fault dla linii typu:

if(0 == this->FirstOnMachines[this->PSorted[i]->iMachineNum])

(Jeśli zamiast 0 stosuje NULL'a jest to samo).

http://wyslijto.pl/plik/eef8cjbcti <<-- tutaj kompletny kod programu wraz z jednym przykładem Tailarda.

Sprawdzałem działanie poszczególnych metod i błąd tyczy się tej części kodu:

int CInsa::CheckPosition(){
    int iTemp = 0;
    if(0 == this->pTemp->pk){
        if(0 == this->pObjectToAdd->nt) iTemp = this->pTemp->Operation.q;
        else iTemp =  max(this->pObjectToAdd->Operation.q,this->pTemp->Operation.q);
        if(0 != this->pObjectToAdd->pt) iTemp += this->pObjectToAdd->pt->Operation.r;
        iTemp += this->pObjectToAdd->Operation.p;
    }else{
        if(0 == this->pObjectToAdd->nt) iTemp = this->pTemp->Operation.q;
        else iTemp =  max(this->pObjectToAdd->Operation.q,this->pTemp->Operation.q);
        if(0 == this->pObjectToAdd->pt) iTemp += this->pTemp->pk->Operation.r;
        else iTemp += max(this->pObjectToAdd->Operation.r,this->pTemp->pk->Operation.r);
        iTemp += this->pObjectToAdd->Operation.p;
    }
    return iTemp;
}

void CInsa::AddOperation(){
    if(0 == this->pPosition->pk){
        this->pObjectToAdd->nk = pPosition;
        this->pPosition->pk = pObjectToAdd;
    }else{
        if(0 == this->pPosition->nk){
            this->pObjectToAdd->pk = this->pPosition;
            this->pPosition->nk = this->pObjectToAdd;
        }else{
            this->pPosition->pk->nk = this->pObjectToAdd;
            this->pObjectToAdd->pk = this->pPosition->pk;
            this->pObjectToAdd->nk = this->pPosition;
            this->pPosition->pk = this->pObjectToAdd;
        }
    }
}

void CInsa::InsaAlg(){
    this->SortP();
    int iTemp,iCmaxTmp;
    STaskData* pLast;

    for(int i=1;i<this->iSize;i++){
        this->SetTopologicalQueue();
        this->CalcR();
        this->CalcQ();
        iCmaxTmp = -1;
        iTemp = 0;
        this->pPosition = 0;
        this->pObjectToAdd = 0;
        this->pTemp = 0;
        pLast = 0;
        if(0 == this->FirstOnMachines[this->PSorted[i]->iMachineNum]){
            this->FirstOnMachines[this->PSorted[i]->iMachineNum] = this->PSorted[i];
            this->PSorted[i]->pk = 0;
            this->PSorted[i]->nk = 0;
        }else{
            this->pTemp = this->FirstOnMachines[this->PSorted[i]->iMachineNum];
            while(this->pTemp != 0){
                iTemp = this->CheckPosition();
                if((-1 == iCmaxTmp)||(iTemp < iCmaxTmp)){
                    iCmaxTmp = iTemp;
                    this->pPosition = this->pTemp;
                }
                if(0 == this->pTemp->nk) pLast = this->pTemp;
                this->pTemp = this->pTemp->nk;
            }
            if(0 == this->PSorted[i]->pt) iTemp = pLast->Operation.r;
            else iTemp = max(this->PSorted[i]->pt->Operation.r,pLast->Operation.r);
            if(0 != this->PSorted[i]->nt) iTemp += this->PSorted[i]->nt->Operation.q;
            iTemp += this->PSorted[i]->Operation.p;
            if(iTemp < iCmaxTmp){
                iCmaxTmp = iTemp;
                this->pPosition = pLast;
            }
            this->AddOperation();
            if(this->pPosition == FirstOnMachines[this->PSorted[i]->iMachineNum])
                FirstOnMachines[this->PSorted[i]->iMachineNum] = this->PSorted[i];
        }
    }

    this->CalcR();
    this->iCmax = this->Data[1].Operation.r;
    for(int i=2;i<this->iSize;i++) if(this->Data[i].Operation.r > this->iCmax) this->iCmax = this->Data[i].Operation.r;
    pLast = 0;
}

Wdzięczny bym był za pomoc, najlepiej szybką bo do poniedziałku powinienem to oddać, a ja już 3 dzień siedzę kombinuję i nic:/

Pzdr.,
Kamil
</cpp></url>

Nikt się nie zabierze za anlizę kodu bez zadnego komentarza.
A jeśli rzuca ci segfaulta w tej linii to najpewniej któryś z tych wskaźników jest po prostu nullem a ty próbujesz go dereferować.
Wypisz sobie owe wskaźniki przed wywołaniej tej instrukcji i popatrz jak wyglądają.

http://wyslijto.pl/plik/2kupj0mdol <<-- kompletny okomentowany kod.

No właśnie w niektórych iteracjach ten wskaźnik ma wskazywać na adres nullowy i wykonywać tą część kodu znajdującą się po if'ie

A poniżej okomentowany kod, którego dotyczy błąd.

//Metoda zwracajaca wartosc funkcji kryterialnej dla zadania
//this->ObjectToAdd wstawionego przed zadaniem wskazywanym przez
//this->pTemp
int CInsa::CheckPosition(){
    int iTemp = 0;
    //Sprawdzamy czy zadanie jest w stawiane na poczatek kolejki zadan znajdjacych sie
    //na maszynie, jesli tak liczymy wartosc funkcji kryterialnej, jesli nie tez liczymy
    //ale uwzgledniamy czas r z poprzednika kolejnosciowego (zadania za ktre wstawiamy)
    if(0 == this->pTemp->pk){
        if(0 == this->pObjectToAdd->nt) iTemp = this->pTemp->Operation.q;
        else iTemp =  max(this->pObjectToAdd->Operation.q,this->pTemp->Operation.q);
        if(0 != this->pObjectToAdd->pt) iTemp += this->pObjectToAdd->pt->Operation.r;
        iTemp += this->pObjectToAdd->Operation.p;
    }else{
        if(0 == this->pObjectToAdd->nt) iTemp = this->pTemp->Operation.q;
        else iTemp =  max(this->pObjectToAdd->Operation.q,this->pTemp->Operation.q);
        if(0 == this->pObjectToAdd->pt) iTemp += this->pTemp->pk->Operation.r;
        else iTemp += max(this->pObjectToAdd->Operation.r,this->pTemp->pk->Operation.r);
        iTemp += this->pObjectToAdd->Operation.p;
    }
    return iTemp;
}

//Metoda dodajaca zadanie wskazywane przez this->pObjectToAdd na pozycje o wskazywanej przez
// this->pPosition
void CInsa::AddOperation(){
    //Sprawdzamy czy zadanie ma zostac dodane na poczatku kolejki danej maszyny
    if(0 == this->pPosition->pk){
        this->pObjectToAdd->nk = pPosition;
        this->pPosition->pk = pObjectToAdd;
    //jesli nie wstawiamy zadanie przed zadanie wskazywane przez pPosition
    //i zapewniamy wlasciwe wskazniki poprzendikow i nastepnikow kolejnows
    }else{
        this->pPosition->pk->nk = this->pObjectToAdd;
        this->pObjectToAdd->pk = this->pPosition->pk;
        this->pObjectToAdd->nk = this->pPosition;
        this->pPosition->pk = this->pObjectToAdd;
    }
}


//Mtdoa spinajaca wszystko w jedna calosc
void CInsa::InsaAlg(){
    //sortujemy zadania po czasie P
    this->SortP();
    //iTemp - wartosc kryterium dla obecnego ustawienia
    //iCmaxTmp - najlepsza dotychczas znaleziona wartosc kryterium
    int iTemp,iCmaxTmp;
    STaskData* pLast; //wskaznik na ostatnie zadanie w kolejce danej maszyny

    //petla wykonuje sie tyle razy ile zadan jest do dodania
    for(int i=1;i<this->iSize;i++){
        this->SetTopologicalQueue(); // ustalamy kolejnosc topologiczna dla obecnego uszeregowania
        this->CalcR(); // liczymy czasy r i q: akceleracja liczenia funkcji kryterialnej
        this->CalcQ();
        //zerujemy wartosci i wskazniki
        iCmaxTmp = -1;
        iTemp = 0;
        this->pPosition = 0;
        this->pObjectToAdd = 0;
        this->pTemp = 0;
        pLast = 0;
        //sprawdzamy czy na maszynie przypisanej do i-tego zadania znajduja sie jakeis zadania
        // jesli nie to wstawiamy nasze zadanie
        if(0 == this->FirstOnMachines[this->PSorted[i]->iMachineNum]){
            this->FirstOnMachines[this->PSorted[i]->iMachineNum] = this->PSorted[i];
            this->PSorted[i]->pk = 0;
            this->PSorted[i]->nk = 0;
        //w przeciwnym wypadku wykonujemy kolejne kroki algorytmu
        }else{
            //zaczynamy od wstawienia zadania na sam poczatek
            this->pTemp = this->FirstOnMachines[this->PSorted[i]->iMachineNum];
            //dopoki nie sprawdziwy calej kolejki znajdujacej sie na danej maszynie
            //liczymy wartosc funkcji kryterialnej i zapamietujemy najlepsza pozycje
            while(this->pTemp != 0){
                iTemp = this->CheckPosition();
                if((-1 == iCmaxTmp)||(iTemp < iCmaxTmp)){
                    iCmaxTmp = iTemp;
                    this->pPosition = this->pTemp;
                }
                if(0 == this->pTemp->nk) pLast = this->pTemp; //zapamietujemy wskaznik na ostatnie zadanie na maszynie
                this->pTemp = this->pTemp->nk;
            }
            //SPrawdzamy wartosc kryterium po wstawieniu zadania na koniec, jesli jest mniejsze od
            // obecnej wartosci to wstawiamy na koniec
            if(0 == this->PSorted[i]->pt) iTemp = pLast->Operation.r;
            else iTemp = max(this->PSorted[i]->pt->Operation.r,pLast->Operation.r);
            if(0 != this->PSorted[i]->nt) iTemp += this->PSorted[i]->nt->Operation.q;
            iTemp += this->PSorted[i]->Operation.p;
            if(iTemp < iCmaxTmp){
                iCmaxTmp = iTemp;
                pLast->nk = this->PSorted[i];
                this->PSorted[i]->pk = pLast
            }
            //Jesli najlepsza pozycja jest inna niz koniec kolejki dla danej maszyny
            //to dodajem yzadanie metdoa this->AddOperation;
            if(this->pPosition != pLast) this->AddOperation();
            //Jesli najlepsza pozycja to na poczatku kolejki dla danej maszyny
            //to zmieniamy wskaznik na pierwsze zadanie na maszynie
            if(this->pPosition == FirstOnMachines[this->PSorted[i]->iMachineNum])
                FirstOnMachines[this->PSorted[i]->iMachineNum] = this->PSorted[i];
        }
    }

    //Raz jeszcze liczymy czasy R danego uszeregowania, bo wartosc Cmax
    //bedzie najwiekszym sposrod nich;
    this->CalcR();
    this->iCmax = this->Data[1].Operation.r;
    for(int i=2;i<this->iSize;i++) if(this->Data[i].Operation.r > this->iCmax) this->iCmax = this->Data[i].Operation.r;
    pLast = 0; // zeruje wskaznik
}

no tak, ale jeżeli masz linijkę: this->FirstOnMachines[this->PSorted[i]->iMachineNum]
to może się zdarzyć np., że:
Psorted[i] jest za zakresem,
this->PSorted[i]->iMachineNum jest za duży

Karolaq napisał(a)

no tak, ale jeżeli masz linijkę: this->FirstOnMachines[this->PSorted[i]->iMachineNum]
to może się zdarzyć np., że:
Psorted[i] jest za zakresem,
this->PSorted[i]->iMachineNum jest za duży

Hmm, masz rację, tylko że mój program ma działać dla przykładów Tailarda, więc przyjmuję na wiarę, że dane wejściowe są poprawne. W takim przypadku this->PSorted[i] nie wykracza poza zakres (sprawdzałem wyniki działania metody), tak samo this->PSorted->iMachineNum nie moze być za duży bo to pochodzi danych wejściowych (któe z założenia mają być poprawne).

Pzdr.,
Kamil

Juz Ci odpowiedzialem na innym forum. Wystarczy spojrzec na te jakze inteligentna linijke ;p
for (int i=0;i<(m+1);i++) this->FirstOnMachines = 0; I pozniejsze proby czytania z przesunietego o 2 wskaznika.

Thx:) Ale program dlaej sie wywala tym razem dla
int CInsa::CheckPosition(){
dla linii
if(0 == this->pObjectToAdd->nt) iTemp = this->pTemp->Operation.q;

A wskazniki na nastepniki i poprzedniki kolejnosciowe wykonuje petla w main() wczytująca dane:

    int n = 0;
    for(int i=1; i<(iTemp*iTemp2+1); i++){
        InFile >> Problem->Data[i].iMachineNum;
        InFile >> Problem->Data[i].Operation.p;
        Problem->Data[i].nk = 0;
        Problem->Data[i].pk = 0;
        if(i == (n*iTemp2 + 1)){      // jesli i (nr operecji) jest wielokrotnoscia liczb maszyn(iTemp2) + 1
            Problem->Data[i].pt = 0;  // tzn jest czas z pierwszej kolumny z danego zadania to nie ma pt
            n++;
        }else Problem->Data[i].pt = &(Problem->Data[i-1]); // w przeciwnym razie pt to poprzednia operacja
        if(0 == (i % iTemp2)) Problem->Data[i].nt = 0; // jesli nr operacji dzieli sie bez reszty to nt = 0
                                                                             //tzn. ze jest to czas z ostatniej kolumny danego zadania
    }
    for(int i=1; i<(iSize+1); i++)
        // jesli nr operacji dzieli sie zreszta, to nastepnikiem technologicznym jest nastepna operacja
        if(0 != (i % iTemp2)) Problem->Data[i].nt = &(Problem->Data[i+1]); 

http://wyslijto.pl/plik/c7cfw1dnm1 <<-- Poprawiony kod, bo jeszcze pare innych rzeczy wyłapałem.

To już chyba wiem co jest źle. Funkcja SetTopologicalQueue buduje niepełną kolejność topologiczną, przez co nie są policzone wszystkie czasy r i q, a w związku z tym funkcja CheckPosition() odwołuje się do pól, któe nie mają przypisanej żadnej wartości...

Jeśli dodam jedną pętlę while to powinno być dobrze.

Ale to jutro sprawdzę, temat chwilowo zawieszony:P

http://www.sendspace.com/file/58f5qe <<-- Poprawny, działający program.

Błąd polegał na złym zrozumieniu ustalania kolejności topologicznej, co skutkowało tym, że odwoływałem się do wartości, które nie zostały ustawione. Poza tym dopisałem destruktory.

Pzdr.,
i dzięki za pomoc

możesz zrobić reupload'a z poprawioną częścią kodu