Indeksowanie wskaźników

Obecnie czytam książkę zatytułowaną „Przepisy numeryczne w C”. W tej książce autor wyszczególnia, jak pewne algorytmy z natury działają lepiej, gdybyśmy mieli indeksy zaczynające się od 1 (nie do końca podążam za jego argumentem i nie o to chodzi w tym poście), ale C zawsze indeksuje swoje tablice zaczynające się od 0 Aby obejść ten problem, sugeruje po prostu zmniejszenie wskaźnika po alokacji, np .:

float *a = malloc(size);
a--;

To, jak mówi, da ci efektywnie wskaźnik, którego indeks zaczyna się od 1, a następnie zostanie zwolniony z:

free(a + 1);

O ile mi wiadomo, jest to niezdefiniowane zachowanie według standardu C. Jest to podobno bardzo renomowana książka w społeczności HPC, więc nie chcę po prostu lekceważyć tego, co mówi, ale po prostu zmniejszanie wskaźnika poza przydzielony zakres wydaje mi się bardzo szkicowe. Czy to „dozwolone” zachowanie w C? Przetestowałem to przy użyciu zarówno gcc, jak i icc, i oba te wyniki wydają się wskazywać, że nie martwię się niczym, ale chcę być absolutnie pozytywny.

Masz rację, że kod taki jak

float a = malloc(size);
a--;

daje niezdefiniowane zachowanie, zgodnie ze standardem ANSI C, sekcja 3.3.6:

O ile zarówno operand wskaźnika, jak i wynik wskazują na element członkowski tego samego obiektu tablicowego lub jeden za ostatnim elementem tego obiektu tablicowego, zachowanie jest niezdefiniowane

W przypadku takiego kodu jakość kodu C w książce (kiedy go używałem pod koniec lat 90.) nie była uważana za bardzo wysoką.

Problem z niezdefiniowanym zachowaniem polega na tym, że bez względu na wynik kompilatora, wynik ten jest z definicji poprawny (nawet jeśli jest wysoce destrukcyjny i nieprzewidywalny).
Na szczęście bardzo niewiele kompilatorów stara się spowodować nieoczekiwane zachowanie w takich przypadkach, a typowa mallocimplementacja na komputerach używanych do HPC ma pewne dane księgowe tuż przed zwróconym adresem, więc zmniejszenie zazwyczaj daje wskaźnik do tych danych księgowych. Pisanie tam nie jest dobrym pomysłem, ale samo tworzenie wskaźnika jest w tych systemach nieszkodliwe.

Należy pamiętać, że kod może ulec awarii, gdy środowisko wykonawcze zostanie zmienione lub gdy zostanie przeniesiony do innego środowiska.

Oficjalnie jego niezdefiniowanym zachowaniem jest umieszczenie wskaźnika poza tablicą (z wyjątkiem jednego za końcem), nawet jeśli nigdy nie jest dereferencyjny .

W praktyce, jeśli Twój procesor ma płaski model pamięci (w przeciwieństwie do dziwnych, takich jak x86-16 ), a jeśli kompilator nie wyświetli błędu w czasie wykonywania lub niepoprawnej optymalizacji, jeśli utworzysz nieprawidłowy wskaźnik, kod będzie działał w porządku.

Po pierwsze, jest to niezdefiniowane zachowanie. Niektóre kompilatory optymalizujące stają się obecnie bardzo agresywne wobec niezdefiniowanych zachowań. Na przykład, ponieważ - w tym przypadku zachowanie jest niezdefiniowane, kompilator może zdecydować o zapisaniu instrukcji i cyklu procesora, a nie zmniejszeniu a. Co jest oficjalnie prawidłowe i zgodne z prawem.

Ignorując to, możesz odjąć 1, 2 lub 1980. Na przykład, jeśli mam dane finansowe za lata 1980–2013, mogę odjąć 1980. Teraz, jeśli weźmiemy zmiennoprzecinkowe * a = malloc (rozmiar); jest na pewno jakiś duży stała k takie, że a - k jest wskaźnikiem NULL. W takim przypadku naprawdę spodziewamy się, że coś pójdzie nie tak.

Teraz weź dużą strukturę, powiedzmy megabajt. Przydziel wskaźnik p wskazujący na dwie struktury. p - 1 może być wskaźnikiem zerowym. p - 1 może się zawijać (jeśli struct jest megabajtem, a blok malloc ma 900 KB od początku przestrzeni adresowej). Więc może być bez komplikacji kompilatora, że ​​p - 1> p. Rzeczy mogą być interesujące.

... po prostu zmniejszanie wskaźnika poza przydzielony zakres wydaje mi się bardzo szkicowe. Czy to „dozwolone” zachowanie w C?

Dozwolony? Tak. Dobry pomysł? Zazwyczaj nie.

C jest skrótem od języka asemblera, aw języku asemblera nie ma wskaźników, tylko adresy pamięci. Wskaźniki C są adresami pamięci, które mają boczne działanie polegające na zwiększaniu lub zmniejszaniu o rozmiar tego, na co wskazują, gdy są poddawane arytmetyki. To sprawia, że ​​następujące elementy są w porządku z perspektywy składni:

double *p = (double *)0xdeadbeef;
--p;  // p == 0xdeadbee7, assuming sizeof(double) == 8.
double d = p[0];

Tablice nie są tak naprawdę w C; są tylko wskaźnikami do ciągłych zakresów pamięci, które zachowują się jak tablice. []Operator jest skrótem robi wskaźnik arytmetyczne i wyłuskania, tak a[x]naprawdę oznacza *(a + x).

Istnieją uzasadnione powody, aby zrobić powyższe, na przykład niektóre urządzenia I / O mające kilka doubles mapowanych na 0xdeadbee7i 0xdeadbeef. Bardzo niewiele programów musiałoby to zrobić.

Kiedy tworzysz adres czegoś, na przykład za pomocą &operatora lub połączenia malloc(), chcesz zachować oryginalny wskaźnik nietknięty, abyś wiedział, że to, co wskazuje, jest w rzeczywistości czymś ważnym. Zmniejszenie wskaźnika oznacza, że ​​trochę błędnego kodu może próbować go wyrejestrować, uzyskać błędne wyniki, zablokować coś lub, w zależności od środowiska, popełnić naruszenie segmentacji. Jest to szczególnie prawdziwe w przypadku malloc(), ponieważ obciążysz każdego, kto dzwoni, free()aby pamiętać o przekazaniu pierwotnej wartości, a nie jakiejkolwiek zmienionej wersji, która spowoduje, że wszyscy się uwolnią.

Jeśli potrzebujesz tablic opartych na 1 w C, możesz to zrobić bezpiecznie kosztem przydzielenia jednego dodatkowego elementu, który nigdy nie będzie używany:

double *array_create(size_t size) {
    // Wasting one element, so don't allow it to be full-sized
    assert(size < SIZE_MAX);
    return malloc((size+1) * sizeof(double));
}

inline double array_index(double *array, size_t index) {
    assert(array != NULL);
    assert(index >= 1);  // This is a 1-based array
    return array[index];
}

Zauważ, że nie ma to nic wspólnego z ochroną przed przekroczeniem górnej granicy, ale jest to dość łatwe w obsłudze.

Uzupełnienie:

Trochę rozdziału i wersetu z projektu C99 (przepraszam, to wszystko, co mogę link do):

§6.5.2.1.1 mówi, że drugie („inne”) wyrażenie używane z operatorem indeksu dolnego jest liczbą całkowitą. -1jest liczbą całkowitą, co czyni p[-1]poprawność, a zatem również poprawia wskaźnik &(p[-1]). Nie oznacza to, że dostęp do pamięci w tym miejscu spowodowałby określone zachowanie, ale wskaźnik jest nadal prawidłowym wskaźnikiem.

§6.5.2.2 mówi, że operator tablicy indeksów ocenia równoważność dodania numeru elementu do wskaźnika, a zatem p[-1]jest równoważny *(p + (-1)). Nadal obowiązuje, ale może nie powodować pożądanego zachowania.

W pkt 6.5.6.8 (podkreślenie moje):

Gdy wyrażenie, które ma typ liczb całkowitych, jest dodawane do wskaźnika lub odejmowane od niego, wynik ma typ argumentu wskaźnika.

... jeśli wyrażenie Pwskazuje na i-ty element obiektu tablicowego, wyrażenia (P)+N(równoważnie N+(P)) i (P)-N (gdzie Nma wartość n) wskazują odpowiednio na i+n-ty i i−n-ty element obiektu tablicowego, pod warunkiem że istnieją .

Oznacza to, że wyniki arytmetyki wskaźnika muszą wskazywać element w tablicy. Nie mówi, że arytmetykę należy wykonać od razu. W związku z tym:

double a[20];

// This points to element 9 of a; behavior is defined.
double d = a[-1 + 10];

double *p = a - 1;  // This is just a pointer.  No dereferencing.

double e = p[0];   // Does not point at any element of a; behavior is undefined.
double f = p[1];   // Points at element 0 of a; behavior is defined.

Czy polecam robić to w ten sposób? Nie wiem, a moja odpowiedź wyjaśnia, dlaczego.