7.2 Többdimenziós tömbök, VLA és layout

Egy mérési táblázat vagy hálózati feldolgozó munkaterület esetén a „kétdimenziós adat” még nem határozza meg a tárolást. Lehet egyetlen folytonos tömbobjektum, de lehet különálló sorokra mutató pointerek táblája is. A két megoldáshoz eltérő pointertípus, indexelési szabály és élettartam-szerződés tartozik.

A Tömbobjektum, decay és függvényparaméter legfontosabb megállapítása itt is érvényes: a tömb nem pointer, bár számos kifejezésben az első elemére mutató pointerré konvertálódik. Többdimenziós tömbnél ez az első elem maga is tömb. A méretszámításokhoz pedig felidézzük a Promóciók, signedness és túlcsordulás szabályát: a size_t előjel nélküli aritmetikája körbefordulhat, ezért a szorzást megelőzően kell ellenőrizni a reprezentálhatóságot.

7.2.1 Tömbök tömbje és row-major elrendezés

ISO C17: az int a[2][3] deklaráció egy kételemű tömböt hoz létre, amelynek minden eleme háromelemű int tömb. A sorok és az egyes sorokon belüli elemek folytonosan helyezkednek el. Ez a sorfolytonos, angolul row-major elrendezés: a jobb szélső index változtatásával jutunk a következő skalár elemhez.

C17 deklarációrészlet:

int a[2][3] = {
    {10, 11, 12},
    {20, 21, 22}
};

Az a[r][c] jelentése:

*(*(a + r) + c)

Az első pointerlépés teljes sort, a második egyetlen int elemet lép át. Ha a soronkénti elemszám $N$, az elemtípus $T$, akkor a tömb kezdetéhez viszonyított eltolás:

$$\operatorname{offset}(r,c) = r\cdot\operatorname{sizeof}(T[N]) +c\cdot\operatorname{sizeof}(T) = (rN+c)\operatorname{sizeof}(T).$$

Az eltolás egysége C_byte, vagyis a sizeof egysége. Az indexelés előfeltétele $0\le r<R$ és $0\le c<N$, ahol $R$ a sorok száma.

Bizonyításvázlat. Egy sor pontosan $N$ darab $Ttípusú elemből áll, ezért mérete $N\operatorname{sizeof}(T)$. Az $r$ korábbi sor és a kiválasztott sor $c$ korábbi eleme adja a képletet. A tömb nem illeszt külön kitöltést az elemei közé; ha maga $T$ tartalmaz kitöltést, az már része asizeof(T)` értékének.

7.2.1.1 Fizikai sorhossz és logikai szélesség

A stride, azaz lépésköz azt mondja meg, milyen távol vannak egymástól az egymást követő sorok kezdetei. Mindig közölni kell az egységét. Ebben a fejezetben a stride elemszámot jelent.

Egy logikailag háromoszlopos mátrix fizikailag öt elemet is fenntarthat soronként. Ekkor:

$$\operatorname{offset}(r,c)=(rS+c)\operatorname{sizeof}(T),$$

ahol $S$ a fizikai sorhossz, $C$ a logikai oszlopszám, és $S\ge C$.

A következő számok Linux x86-64, System V ABI, LP64, C17 profilra vonatkoznak, ahol sizeof(int) == 4 és CHAR_BIT == 8. Ezek levezetett értékek, nem mérési eredmények.

A második esetben a sorok utolsó két eleme alkalmazásszinten kihagyott hely. Ez nem a fordító által beillesztett padding: ezek valódi, indexelhető int objektumok.

7.2.2 Sorra mutató pointer vagy pointerekre mutató pointer?

Az a tömb kifejezésbeli konverziójának eredménye int (*)[3]: pointer egy háromelemű int tömbre. Nem int **.

C17 deklarációrészlet, <stddef.h> mellett:

void clear_rows(size_t rows, int (*a)[3]);

/* Ugyanaz a függvényparaméter-típus: */
void clear_rows(size_t rows, int a[][3]);

A háromoszlopos sor típusa meghatározza az a + 1 lépésméretét. A sorok száma külön szerződés: a hívónak legalább rows darab élő, írható sort kell biztosítania.

Más reprezentációt ír le ez a C17-részlet:

int first[3] = {1, 2, 3};
int second[3] = {4, 5, 6};
int *rows[2] = {first, second};

Itt a rows konverziója valóban int **. A rows[r][c] először kiolvassa az r-edik pointerobjektumot, majd azon keresztül éri el az elemet.

A fenti lokális példában a befoglaló blokk kezeli mindhárom tömb élettartamát; a sorpointerek nem tulajdonolják a sorokat. A blokk elhagyása érvényteleníti a hozzájuk kötött kölcsönzött hozzáféréseket.

Külön dinamikusan allokált soroknál több allokáció, részleges sikertelenség és soronkénti felszabadítás kezelendő; ennek eszközeit a malloc, calloc, free és allokációs szerződés tárgyalja. A pointertábla ugyanakkor folytonos tároló soraira is mutathat: a T ** önmagában nem bizonyít szétszórt elhelyezést.

Mindkét reprezentáció indexelése állandó műveletszámú, de a pointertáblás változat egy további pointerérték betöltését igényli. A folytonos, soronként bejárt mátrix rendszerint kedvezőbb lokalitást ad; ez teljesítményre vonatkozó várakozás, nem nyelvi garancia.

Gyakori hiba: a mátrixot (int **)a kaszttal átadni. A kaszt nem hoz létre sorpointer-objektumokat. Az így végzett a[r][c] hozzáférésnek nincs érvényes tárolási szerződése, és UB-hez vezethet. A javítás a megfelelő signature, nem egy újabb kaszt.

7.2.3 VLA és variably modified típusok

A változó hosszúságú tömb (variable length array, VLA) tömbméretét nem egész konstanskifejezés határozza meg. Mérete például függvényparaméterből származhat.

C17 deklarációrészlet, VLA-támogatással és <stddef.h> mellett:

void fill(size_t rows, size_t cols, int (*a)[cols]);

Az a pointerváltozó, nem VLA-objektum, de a típusa VLA-tól függ. Az ilyen típus a változóan módosított típusok (variably modified types, VM) körébe tartozik. Az int a[rows][cols] paraméteralak itt szintén int (*a)[cols] alakra igazodik; nem foglal mátrixot és nem ellenőrzi automatikusan a sorok számát.

A C23 nyelvi módot és a konkrét képességet külön fordítási próbával kell ellenőrizni. A C17-es tiltó makróvizsgálatot ezért nem szabad változatlan jelentéssel C23-ra átvinni.

A kiértékelt VLA-méretnek pozitívnak kell lennie. Ez a függvénydefiníció paramétertípusában szereplő sorhosszra is lényeges: a nulla méretet a hívás előtt kell elutasítani, nem csak a függvénytörzs elején.

7.2.3.1 Miért veszélyes a bemenetről vett automatikus VLA?

Az int temporary[rows][cols]; deklaráció automatikus tárolási idejű objektumot hoz létre. Az ISO C nem ír elő hozzá vermet, de a szokásos Linux-fordítók jellemzően stackterületet használnak.

Egy reprezentálható méret még nem feltétlenül fér el a rendelkezésre álló stackben. A VLA-létrehozásnak nincs hordozható, NULL-lal jelzett sikertelen kimenete. Nem megbízható bemenet esetén ezért külön szükséges:

• a méretek pozitivitásának és reprezentálhatóságának ellenőrzése;
• alkalmazásszintű felső korlát;
• megfelelő tárolási stratégia.

A méretek ellenőrzése után képzett VLA-ra mutató pointer nem azonos egy nagy automatikus VLA létrehozásával.

7.2.4 Ellenőrzött méretszámítás és kidolgozott példa

Teljes fizikai sorokat fenntartó tárolónál legyen:

$$E=RS,\qquad B=E\operatorname{sizeof}(T).$$

Itt $E$ az elemszám, $B$ a C_byte-ban mért méret. Pozitív $R,S$ mellett a két biztonságos szorzás feltétele:

$$R\le\left\lfloor\frac{\mathrm{SIZE\_MAX}}{S}\right\rfloor, \qquad E\le\left\lfloor \frac{\mathrm{SIZE\_MAX}}{\operatorname{sizeof}(T)} \right\rfloor.$$

Az osztásos ellenőrzés azért előzi meg a szorzást, mert a már körbefordult eredményből az eredeti méret nem állítható helyre megbízhatóan.

Az alábbi teljes C17-program VLA/VM-támogatást igényel, de nem hoz létre futásidejű méretű automatikus tömböt. Választott laborprofil: Linux x86-64 System V, LP64, GCC 14.2.0 vagy Clang 18.1.8, glibc 2.39. A fordítási parancsok laborutasítások; a példához itt nem tartozik végrehajtott mérés.

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

#if defined(__STDC_NO_VLA__) && __STDC_NO_VLA__
#error "This C17 example requires VLA/VM support"
#endif

static int checked_bytes(size_t rows, size_t cols,
                         size_t stride, size_t *bytes)
{
    if (bytes == NULL || rows == 0 || cols == 0 || stride < cols)
        return 0;

    if (rows > SIZE_MAX / stride)
        return 0;

    size_t elements = rows * stride;

    if (elements > SIZE_MAX / sizeof(int))
        return 0;

    *bytes = elements * sizeof(int);
    return 1;
}

static void fill(size_t rows, size_t cols, size_t stride,
                 int (*a)[stride])
{
    for (size_t r = 0; r < rows; ++r)
        for (size_t c = 0; c < cols; ++c)
            a[r][c] = 7;
}

int main(void)
{
    int matrix[2][5] = {{0}};
    size_t bytes;

    if (!checked_bytes(2, 3, 5, &bytes))
        return 1;

    if (bytes != sizeof matrix)
        return 1;

    fill(2, 3, 5, matrix);

    if (printf("%zu %d %d\n",
               bytes, matrix[1][2], matrix[1][4]) < 0)
        return 1;

    return 0;
}

gcc -std=c17 -Wall -Wextra -Wpedantic -Wconversion -O2 matrix.c -o matrix-gcc
clang -std=c17 -Wall -Wextra -Wpedantic -Wconversion -O2 matrix.c -o matrix-clang

A választott ABI mellett, sikeres kimeneti művelet esetén a várt, nem mért kimenet 40 7 0. Csak a logikai oszlopok módosulnak.

A tulajdonos a main blokkja; a tároló a matrix, a kölcsönzött hozzáférés a fill paramétere. A tároló élettartama lefedi a teljes hívást, és a blokk elhagyása érvénytelenítené a megőrzött pointert. A fill sem pointert, sem tulajdonjogot nem őriz meg.

A checked_bytes hibára nullát ad, és nem írja a kimeneti objektumot. Nem null bytes esetén élő, írható size_t objektumra mutató pointer szükséges. A fill nem ellenőrző függvény: a hívó garantálja a pozitív méreteket, a helyes fizikai sortípust és a megfelelő írható tárolót. A méretellenőrzés önmagában nem bizonyítja, hogy egy tetszőleges pointer mögött valóban van ekkora objektum.

7.2.4.1 Lapos nézetnél a valódi objektumhatár számít

Valódi egydimenziós tömbben az index $rS+c$. Ha $r<R$, $c<C\le S$, akkor:

$$rS+c\le(R-1)S+(S-1)=RS-1.$$

Ez a határellenőrzés bizonyításvázlata; feltétele, hogy $RS$ reprezentálható, és a tároló legalább ennyi elemet tartalmaz.

Ne következtess ebből arra, hogy egy valódi int matrix[R][S] objektumot korlátlanul bejárhatsz a &matrix[0][0] pointerrel. Az így kapott int * az első sor elemeire mutat; az azon túli pointeraritmetikát nem teszi szabályossá a fizikailag szomszédos következő sor. Tömbök tömbjét sorpointerrel, lapos tárolót lapos pointerrel kezelj.

7.2.5 Feladatok

1. Levezetés. A megadott x86-64 laborprofilban int a[3][4] esetén mekkora a sorstride C_byte-ban, az a[2][1] eltolása és a teljes méret? Miért hibás hozzá az int ** paraméter?

2. Kódolás. A példa checked_bytes függvényére építve írj ellenőrzött set_cell függvényt valódi egydimenziós int tömb logikai mátrixnézetéhez! A kapacitás elemszám legyen. Hibánál ne változzon a tároló.

3. Diagnosztika. Egy függvény közvetlenül bemenetről veszi a rows és cols értékét, deklarál egy int a[rows][cols] tömböt, majd (int **)a értéket ad tovább. Nevezz meg legalább három egymástól független hibaforrást, és javasolj javítást!

7.2.6 Megoldások

7.2.6.1 Elrendezés és típus

A sorstride $4\cdot4=16$ C_byte. Az eltolás:

$$(2\cdot4+1)\cdot4=36\text{ C\_byte}.$$

A teljes méret $3\cdot4\cdot4=48$ C_byte. A megfelelő paraméter int (*a)[4]; az int ** pointerobjektumokat feltételezne a sorok helyén.

Ellenőrzési feltétel: sizeof a[0] == 16 és sizeof a == 48 a megjelölt profilon.

7.2.6.2 Ellenőrzött lapos hozzáférés

C17-részlet az előző program checked_bytes függvénye után:

static int set_cell(int *a, size_t capacity,
                    size_t rows, size_t cols, size_t stride,
                    size_t r, size_t c, int value)
{
    size_t bytes;

    if (a == NULL || r >= rows || c >= cols)
        return 0;

    if (!checked_bytes(rows, cols, stride, &bytes))
        return 0;

    if (bytes / sizeof(int) > capacity)
        return 0;

    a[r * stride + c] = value;
    return 1;
}

A hívó tulajdonolja a legalább capacity elemű egydimenziós tömböt; a függvény csak a hívás idejére kölcsönzi. A tulajdonos tárolójának megszűnése érvényteleníti a pointert. Sikerre egyet, ellenőrzött hibára nullát ad. Hamis kapacitásadat vagy dangling pointer ellen nem véd.

Ellenőrzési feltétel: int data[10] = {0}; mellett a $(R,C,S)=(2,3,5)$ nézet (1,2) cellája a 7-es indexet módosítja; a (1,3) kérés hibát ad, változtatás nélkül.

7.2.6.3 Bemeneti VLA diagnózisa

A nulla méret érvénytelen VLA-határ. A túl nagy méret túlterhelheti a tipikus stacktárolást akkor is, ha a méretszámítás reprezentálható. A size_t-szorzás külön ellenőrzés nélkül körbefordulhat. Végül az int ** kaszt hibás reprezentációt állít.

A javítás: ellenőrzött méretszámítás, alkalmazási méretkorlát, megfelelő tárolási stratégia és a tényleges reprezentációhoz illő signature.

Ellenőrzési feltétel: hibás méretnél se VLA-létrehozás, se memóriaművelet ne történjen; érvényes bemenetnél a paramétertípus egyezzen a tároló szerkezetével.

7.2.7 Rövid összefoglaló

A folytonos kétdimenziós C-tömb tömbök tömbje; természetes paramétertípusa sorra mutató pointer, nem T **. A helyes hozzáféréshez együtt szükséges a logikai méret, a fizikai stride, a reprezentálható méretszámítás és az élő tároló. A VLA támogatása szabványverzió-függő, használata pedig nem helyettesíti sem a kapacitásellenőrzést, sem az erőforráskorlátokat.