Wskaźniki w c, dziwny błąd

Question

Próbuję rozwiązać zadanie z uczelni po wysłaniu kodu sprawdzarka sprawdza kolejne testy chyba że się na którymś wywali. Metodą komentowania i wysyłania doszedłem do momentu, że wiem jaka dokładnie linijka wywala mi program, jednak wydaje mi się ona w porządku. Tu kod:

typedef struct node Node;
struct node{
    Node *g[3];
    long val;
    int vis;
};

Node *create(long val){
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    for(int i = 0; i<3; i++)
        newNode->g[i] = NULL;
    newNode->vis = 0;

    return newNode;
}

#define N 100000
Node * poziom[N]; /// globalna tablica 


----------- w jakiejs funkcji:

poziom[i] = create(10); /// cos tego typu mam w pewnej funkcji, do poziom odwoluje sie tylko w tym jednym miejscu nigdzie indziej (bo wszystko wykomentowalem)

i okazuje się że jak zakomentuję poziom[i] = create(10); to program się nie wywala (oczywiście daje złą odpowiedź ale przechodzi przez wszystkie testy). Sprawdziłem też że malloc zawszy przydziela pamięć (nigdy nie zwraca NULLa, bo gdyby zwrócił to kończyłby się program i błędu by nie było). Nie wychodzi tez poza tablicę poziom, ale też się nie zapętla. Powód musi być jakiś inny. Jakieś pomysły?

 

Edit:

Jeszcze lepiej, zobaczcie na to: (niesamowite jest co tu się dzieje)

typedef struct node Node;
struct node{
    Node *g[3];
    long val;
    int vis;
};

Node *create(long val){
  return NULL;
}

#define N 100000
Node * poziom[N]; /// globalna tablica 


----------- w jakiejs funkcji:

poziom[i] = create(10); /// to wywala blad
jak zamienie na to to nie ma bledu:
create(10); 

I jeszcze raz powtórzę, że mam pewność że nie wychodzi za tablicę

Answer 1

Skompiluj program z włączonym sanitizerem pod Linuksem i wtedy potestuj.
https://en.wikipedia.org/wiki/AddressSanitizer

Comments

Właśnie odkryłem coś dla mnie niepojętego:

typedef struct node Node;
struct node{
    Node *g[3];
    long val;
    int vis;
};
 
Node *create(long val){
  return NULL;
}
 
#define N 100000
Node * poziom[N]; /// globalna tablica 
 
 
----------- w jakiejs funkcji:
 
poziom[i] = create(10); /// to wywala blad

natomiast jak zamienie na to, to NIE WYWALA BLEDU:
poziom[i] = NULL:

W moim rozumieniu create(10) i NULL to jest dokładnie to samo, bo create(10) zwraca NULLa, a okazuje się że jedno wywala błąd a drugie nie

---

Teraz mamy pewność, że gdzieś wyjechałeś poza zakres danych. Nadpisałeś fragment stosu i dlatego nie udało się wykonać skoku do funkcji.

Jeżeli zbudujesz program z obsługą sanitizera od razu ci pokaże w której linijce kodu nastąpił problem.

---

Kompiluję w ten sposób:

gcc main.c -o main -fsanitize=address -static-libasan -g

i odpalam ./main wrzucam dane, program daje poprawną odpowiedź, sanitizer nie krzyczy, a jak wrzucam na sprawdzarkę to jest błąd, widocznie moje testy jakoś go omijają.

A może coś się psuć jak się zaalokuje za dużo pamięci? Choć w sumie raczej to nie to, bo malloc na sprawdzarce nie wywaliło NULLa. Ehh c to tragedia.

---

Niewykluczone, że jest ustawiony limit pamięci na testowane programy.

Pewny jesteś, że konieczna jest ta 100k-elementowa tablica?

---

W sensie sprawdziłem, że poza tę tablicę nie wychodzi, bo gdyby wyszło to by się program zakończył bezbłędnie ze złym wynikiem i poszedłby do kolejnego testu. Wina tej tablicy to raczej nie jest (choć w przypadku c niczego nie wykluczam), bo by się w poprzednich testach wywaliło, a pierwsze pięć testów przechodzi, gdzie ta tablica o tym samym rozmiarze także jest deklarowana.

---

@j23, Btw. nawet dla pięciu milionów elementów w tej tablicy wywala się dalej na tym samym teście. Więc to raczej nie wina zbyt małej ilości pamięci

---

Daj cały kod. Może ktoś zauważy w czym jest problem.

---

bo by się w poprzednich testach wywaliło

Inne testy mogą mieć inne limity pamięci.

nawet dla pięciu milionów elementów w tej tablicy wywala się dalej na tym samym teście.

5M to więcej niż 100k, a jeśli założyć, że sprawdzarka ma ustawiony jakiś tam limit, to oczywistym jest, że tym bardziej będzie błąd.

---

https://onlinegdb.com/Hyg5-NNiw

treść jest dosyć długa więc nie wiem czy jest sens żebym ją przytaczał, w każdym razie dostaje się drzewo binarne i następnie pary indeksów i trzeba znaleźć dla każdej pary liczbę krawędzi pomiędzy nimi.

---

@j23, Znaczy, może złego argumentu użyłem. Gdy zamieniam ten kod co napisałem to wtedy na tamtym teście się nie wywala, a daje po prostu złą odpowiedź nawet przy 5mln elementów.

---

Masz jakieś dane testowe?
Najlepiej takie, dla których się wywala?
j23 może mieć rację. Kolejne wykonania testu mogą mieć ustawione inne rozmiary stosu. Bezpieczniej by było umieścić te duże tablice na stercie.

---

No właśnie problem w tym że sam nie mogę znaleźć testu dla którego się wywala. Nie wiem też czy mogę tak upubliczniać teść zadania które jest na uczelni, na priv wyślę

---

Nie podoba mi się konstrukcja

while( isSeparator(c = getchar()) ) 
    c = getchar();

W warunku pętli wczytujesz znak i go sprawdzasz, potem wczytujesz kolejny znak i go ignorujesz a potem zaczynasz od nowa.
Zamień to na

do {
    c = getchar();
} while ( isSeparator(c) );

 

---

o Jezu, rzeczywiście

---

ale jednak nie miał to wpływu, bo separator był zawsze jeden, dalej na tym samym teście wywrotka :/

---

Czy w tych testach otrzymujesz wyjście z programu (stdout/stderr) lub wynik wykonania programu?

---

Niestety nic. Gdyby się coś dało ujrzeć to bym ten przykład wejściowy dał na wyjście :)

---

@tangarr,

do {
    c = getchar();
} while ( isSeparator(c) );

Tak bezpieczniej:

while ((c = getchar()) != EOF && isSeparator(c)) {}

 

---

while ( isSeparator(c=getchar()) ){}

Tak też jest dobrze.

Wszystkie te 3 wersje działają tak samo

---

Ostatecznie metodą prób i błędów znalazłem zakres ilości elementów jakie miał na wejściu ten test i go wyifowałem, żeby program zakończył się bez błędu. W efekcie wszystkie 10 testów przeszło oprócz tego jednego i jest 14/15 pkt. Czemu się to wywaliło nie wiem, ale mam teorię, że to wina zbyt dużej liczby wywołań rekurencji, bo jak zmieniłem build z rekurencji na iterację to przestał się tam wywalać i zaczął w rekurencji w dfs'ie. Mógłbym bawić się w pisanie stosu i zamianę tego na iterację 14/15 mi wystarcza.