8.2 realloc és dinamikusan növekvő buffer

Egy beolvasópuffer végleges mérete gyakran csak feldolgozás közben derül ki. A dinamikus növelés azonban nem pusztán „több memória kérése”: megváltozhat a tároló helye és élettartama, érvénytelenné válhatnak a belső pointerek, az allokáció pedig meghiúsulhat. A helyes megoldás ezért állapotátmeneteket és tulajdonlási szerződést követ.

A malloc, calloc, free és allokációs szerződés alapján a sikeresen lefoglalt tároló felszabadításáért kijelölt tulajdonos felel. A Pointeraritmetika, objektumhatár és provenance szabályaiból pedig azt idézzük fel, hogy egy pointer érvényességéhez nem elegendő a látszólag megfelelő cím: élő tárolóhoz és megengedett tartományhoz kell kapcsolódnia.

8.2.1 A realloc két külön állapotátmenete

ISO C17. A <stdlib.h> által deklarált realloc(p, n) egy korábbi dinamikus allokációt cserél le n C bájt méretű allokációra. A következőkben feltesszük, hogy $n>0$, és p vagy null pointer, vagy egy még fel nem szabadított, megfelelő memóriafoglaló függvénytől származó allokáció kezdőpointere. Belső elemre mutató pointer, automatikus tömb címe vagy már felszabadított pointer nem megfelelő argumentum.

Ha p == NULL, a hívás a megadott méretű malloc hívásnak megfelelően működik. Nem null p esetén két lényegesen különböző kimenet van.

A biztonságos minta ideiglenes pointert használ. Az alábbi ISO C17 kódrészletben p az egyedüli tulajdonosi fogantyú, new_bytes > 0, a hibajelzés pedig a környező függvény feladata:

unsigned char *replacement = realloc(p, new_bytes);
if (replacement == NULL) {
    /* p és a korábbi tároló változatlanul használható. */
    return BUFFER_NOMEM;
}
p = replacement;

A közvetlen p = realloc(p, new_bytes) értékadás kudarc esetén felülírná a régi tároló elérhetőségét. Ha nincs más, felszabadításhoz használható kezdőpointer, memóriaszivárgás keletkezik.

8.2.1.1 Az azonos cím nem őrzi meg a régi pointer érvényességét

Siker után a korábbi allokációra mutató pointerek — köztük az elemekre mutató aliasok — nem használhatók tovább. Ez akkor is igaz, ha az implementáció ugyanazon a numerikus címen tudta megoldani az átméretezést. A régi pointerértéket még az újjal való összehasonlítás céljából sem szabad kiértékelni.

Ha egy pufferbeli pozíciót meg kell őrizni, indexet vagy eltolást tároljunk. Sikeres növelés után az új kezdőpointerből képezzük újra a hozzáférést. Ehhez az indexnek továbbra is a megfelelő tartományba kell esnie; elem olvasásakor az index kisebb legyen a logikai méretnél.

Az ideiglenes pointeres minta tehát két dolgot választ szét:

1. az új allokáció megszerzésének kísérletét;
2. a tulajdonosi állapot siker utáni véglegesítését.

Kudarc esetén a második lépés elmarad.

8.2.2 Megőrzött tartalom, inicializálás és nulla méret

ISO C17. Legyen a korábbi allokáció mérete $A$, az újé pedig $B$, C bájtban. Sikeres realloc esetén az első

$$\min(A,B)$$

C bájt tartalma megmarad. Növeléskor a hozzáadott rész nincs inicializálva; nem szabad például automatikusan nullterminátort vagy nulla számlálóértékeket feltételezni benne.

Ha egy puffer kapacitása 64, de csak 23 C bájt érvényes adatot tartalmaz, a 128-ra növelés nem hoz létre további 105 érvényes adatbájtot. A logikai méret továbbra is 23. A korábban nem inicializált terület megőrzése sem teszi annak tartalmát inicializálttá.

Szűkítéskor a levágott tartomány adatai elvesznek. Ha a logikai méret nagyobb lenne az új kapacitásnál, azt külön rendezni kellene; az alábbi megvalósítás ezért csak növel, kapacitást nem csökkent.

8.2.2.1 Miért kerüljük a realloc(p, 0) alakot?

ISO C17. A nulla méretű használat implementáció által meghatározott viselkedést érint, és elavuló használatnak számít. Meglévő allokációnál a NULL eredményből nem lehet hordozhatóan arra következtetni, hogy a korábbi tároló megmaradt.

C23-eltérés. Meglévő, nem null pointerrel végzett realloc(p, 0) esetén a viselkedés nem definiált.

A hordozható szerződés ezért egyszerű: felszabadításhoz free kell, nem nulla méretű realloc. Ezután a tulajdonosi állapotot külön nullázzuk. A bemutatott puffer egyetlen ágon sem hívja nulla mérettel a realloc függvényt.

8.2.3 Méret, kapacitás és ellenőrzött növekedés

A logikai méret (size) a már használható adatok mennyisége. A kapacitás (capacity) az allokációban rendelkezésre álló hely. Alapinvariánsunk:

$$0 \leq \text{size} \leq \text{capacity}.$$

A puffer három mezőjét itt egy struct fogja össze; a struktúrák részletes tárgyalása később következik.

További invariáns, hogy capacity == 0 pontosan akkor áll fenn, amikor data == NULL. A struktúra egyszerű másolása nem hoz létre új tulajdonost vagy külön allokációt; két másolat külön felszabadítása hibás lenne.

8.2.3.1 A méretszámítás levezetése

Ha $s$ meglévő elemhez $k$ újat adunk, az új méret $s+k$. size_t típusban az összeadás előtt kell ellenőrizni:

$$k \leq \mathrm{SIZE\_MAX}-s.$$

Egy $w=\texttt{sizeof(T)}$ C bájtos elemtípus $n$ eleméhez a szorzás feltétele:

$$n \leq \left\lfloor\frac{\mathrm{SIZE\_MAX}}{w}\right\rfloor.$$

Előbb ellenőrzünk, és csak utána számoljuk ki az n * sizeof(T) kifejezést. A szorzás utáni ellenőrzés már elveszett információból dolgozna.

Példánk unsigned char elemeket tárol, ezért egy elem mérete pontosan egy C bájt, CHAR_BIT értékétől függetlenül.

A kapacitást 16-ról indítjuk, majd megduplázzuk. A 2 * capacity művelethez:

$$\text{capacity}\leq \left\lfloor\frac{\mathrm{SIZE\_MAX}}{2}\right\rfloor$$

szükséges. Ha ez nem teljesül, a jelölhető maximumra telítünk. Ez csak az aritmetikai helyességet biztosítja: ekkora allokáció sikerére természetesen nincs garancia. Szolgáltatásban ennél jóval kisebb, alkalmazásszintű memórialimit is indokolt.

8.2.4 Teljes példa: hibánál változatlan puffer

Az alábbi buffer.c önálló ISO C17, hosted program, fordítóbővítések nélkül. A műveletek érvényes, inicializált puffert feltételeznek; ugyanazt a puffert nem módosítják párhuzamosan.

A buffer_reserve legalább a kért kapacitást biztosítja, de nem változtatja meg a logikai méretet. A buffer_push csak sikeres helybiztosítás után írja be az új elemet és növeli a méretet.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

struct byte_buffer {
    unsigned char *data;
    size_t size;
    size_t capacity;
};

enum buffer_result {
    BUFFER_OK,
    BUFFER_RANGE,
    BUFFER_NOMEM
};

static enum buffer_result
buffer_reserve(struct byte_buffer *b, size_t required)
{
    if (required <= b->capacity) {
        return BUFFER_OK;
    }

    size_t next = b->capacity == 0 ? 16 : b->capacity;

    while (next < required) {
        if (next > SIZE_MAX / 2) {
            next = SIZE_MAX;
            break;
        }
        next *= 2;
    }

    unsigned char *replacement = realloc(b->data, next);
    if (replacement == NULL) {
        return BUFFER_NOMEM;
    }

    b->data = replacement;
    b->capacity = next;
    return BUFFER_OK;
}

static enum buffer_result
buffer_push(struct byte_buffer *b, unsigned char value)
{
    if (b->size == SIZE_MAX) {
        return BUFFER_RANGE;
    }

    enum buffer_result result =
        buffer_reserve(b, b->size + 1);

    if (result != BUFFER_OK) {
        return result;
    }

    b->data[b->size] = value;
    ++b->size;
    return BUFFER_OK;
}

static void buffer_destroy(struct byte_buffer *b)
{
    free(b->data);
    *b = (struct byte_buffer){0};
}

int main(void)
{
    struct byte_buffer b = {0};

    for (size_t i = 0; i < 12; ++i) {
        if (buffer_push(&b, (unsigned char)i) != BUFFER_OK) {
            buffer_destroy(&b);
            return EXIT_FAILURE;
        }
    }

    const size_t saved_index = 7; /* Nem belső pointer. */

    for (size_t i = 12; i < 40; ++i) {
        if (buffer_push(&b, (unsigned char)i) != BUFFER_OK) {
            buffer_destroy(&b);
            return EXIT_FAILURE;
        }
    }

    assert(b.size == 40);
    assert(b.capacity == 64);
    assert(saved_index < b.size);

    {
        const unsigned char *view = b.data + saved_index;
        assert(*view == 7);
        /* A kölcsönzés alatt nincs átméretezés. */
    }

    buffer_destroy(&b);
    return EXIT_SUCCESS;
}

A main tulajdonosa b; a view csak kölcsönzött hozzáférés. Élettartamát szándékosan a felszabadítás előtti blokkra korlátoztuk. Allokációs hibánál a program felszabadítja a megmaradt tárolót, és hibás kilépési állapotot ad vissza.

Külön tanulói laborhoz kijelölt profil: Linux x86-64 System V, LP64, GCC 14.2.0 és Clang 19.1.7, glibc 2.40. A kód maga nem igényel 8 bites C bájtot vagy LP64 adatmodellt.

gcc -std=c17 -Wall -Wextra -Wpedantic -Wconversion \
    -O0 -g buffer.c -o buffer-gcc

clang -std=c17 -Wall -Wextra -Wpedantic -Wconversion \
    -O0 -g buffer.c -o buffer-clang

Ezek laborparancsok, nem dokumentált fordítási eredmények. Az ellenőrző állítások a sikeres út várt tulajdonságait írják le.

A függvények hibagaranciája erős: BUFFER_NOMEM vagy BUFFER_RANGE esetén a puffer mérete, kapacitása, tárolója és korábbi adatai változatlanok. A foglalást nem igénylő reserve a belső pointereket sem érvényteleníti.

8.2.5 Geometrikus növekedés és amortizált költség

Mi történne, ha minden új elemnél pontosan eggyel növelnénk a kapacitást? Ha az allocator minden alkalommal átmásolná a korábbi adatokat, $N$ beszúrás összes másolási munkája:

$$0+1+\dots+(N-1)=\frac{N(N-1)}{2},$$

tehát $O(N^2)$ lenne.

Bizonyításvázlat. Duplázásnál a növelésekhez tartozó korábbi kapacitások geometrikus sorozatot alkotnak:

$$16+32+\dots+2^k\cdot16 =16(2^{k+1}-1).$$

Üres pufferből induló, egyenkénti beszúrásoknál ez $2N$ alatt marad. Az $N$ új elem beírásával együtt az összes adatmozgatási munka $O(N)$, így egy beszúrás amortizált költsége $O(1)$.

Ez nem jelenti azt, hogy minden beszúrás konstans idejű. Egy növelést kiváltó művelet $O(N)$ adatmozgatást igényelhet. Az ISO C az allocator futási idejére nem ad ilyen komplexitási garanciát: a levezetés a mozgatott adatmennyiség költségmodellje. Az utolsó, SIZE_MAX-ra telítő növelés legfeljebb egyszer következhet be, és nem változtatja meg az összesített nagyságrendet.

Az alábbi adatok a növekedési szabályból következnek, nem mérési eredmények. A másolási oszlop azt feltételezi, hogy minden növelés a teljes régi allokáció másolásával jár.

A folytonos tároló kedvező térbeli lokalitást ad. Ennek ára a kihasználatlan kapacitás, az időnkénti nagyobb késleltetés és a növeléskori pointerérvénytelenítés. A puffer kapacitása nem azonos a folyamat RSS-ével vagy az allocator belső foglalási méretével.

8.2.6 Gyakori hibák és javításuk

A legsúlyosabb hiba a tulajdonosi pointer közvetlen felülírása. Javítása az ideiglenes pointer, majd a siker utáni véglegesítés.

Másik gyakori hiba a kapacitás idő előtti frissítése. Ha az allokáció később meghiúsul, a metaadat több helyet ígérne, mint amennyi ténylegesen rendelkezésre áll. A kapacitás csak siker után változhat.

A belső pointerek megtartását nem javítja az a megfigyelés, hogy „nálunk nem mozdult el a puffer”. Pozíciót indexként kell megőrizni.

Végül a reserve nem inicializálás: nagyobb kapacitás nem jelent több olvasható adatot. Az új logikai elemeket létrehozó műveletnek kell értéket írnia hozzájuk.

8.2.7 Feladatok

8.2.7.1 Állapotok megkülönböztetése

Egy puffer mérete 23, kapacitása 32. Legalább 50 C bájt kapacitást kérünk. Mi történik a megadott megvalósításban kudarc, illetve siker esetén? Hány C bájt tartalmának megőrzését garantálja a realloc, és hány C bájt marad logikailag érvényes adat?

8.2.7.2 Nullával feltöltő átméretezés

Írj buffer_resize_zero függvényt a példához. Növeléskor az új logikai elemeket töltse nullával; csökkentéskor csak a logikai méret változzon. Allokációs hibánál maradjon változatlan a puffer.

8.2.7.3 Belső pointer diagnosztikája

Az alábbi hibás ISO C17 kódrészlet előtt b.size == b.capacity == 16, és b érvényes tulajdonos:

const unsigned char *saved = b.data + 3;

if (buffer_reserve(&b, 32) == BUFFER_OK) {
    unsigned char value = *saved; /* Hibás. */
    (void)value;
}

Miért hibás akkor is, ha a tároló látszólag ugyanott marad? Javítsd ki.

8.2.8 Megoldások

8.2.8.1 Állapotok megkülönböztetése

Kudarc esetén size == 23, capacity == 32, és a régi tároló, valamint minden korábban érvényes belső pointer megmarad.

Siker esetén a duplázás miatt capacity == 64, de size == 23. A realloc az első 32 C bájt tartalmát őrzi meg; ettől még csak az első 23 C bájt logikailag érvényes adat. A korábbi allokációra mutató pointerek érvénytelenné válnak.

Ellenőrzési feltétel: mindkét kimeneten teljesüljön a méret–kapacitás invariáns, és az első 23 adatbájt maradjon változatlan.

8.2.8.2 Nullával feltöltő átméretezés

Az alábbi ISO C17 kiegészítő részlet a buffer.c fájlban, a buffer_reserve után helyezhető el; ugyanazok az include-ok és fordítási parancsok használhatók.

static enum buffer_result
buffer_resize_zero(struct byte_buffer *b, size_t new_size)
{
    enum buffer_result result = buffer_reserve(b, new_size);
    if (result != BUFFER_OK) {
        return result;
    }

    for (size_t i = b->size; i < new_size; ++i) {
        b->data[i] = 0;
    }

    b->size = new_size;
    return BUFFER_OK;
}

A tulajdonos továbbra is a hívó puffere. Kapacitásnövelés érvényteleníti a régi belső pointereket; puszta méretcsökkentés nem szünteti meg a tárolót, de a levágott indexek már kívül esnek a logikai adattartományon. Hibánál minden változatlan.

Ellenőrzési feltétel: növelés után az új tartomány minden eleme nulla; csökkentés után a kapacitás változatlan. Csökkentést követő újranöveléskor az ismét láthatóvá tett elemeket is nullázni kell.

8.2.8.3 Belső pointer diagnosztikája

Sikeres realloc után saved a megszűnt élettartamú korábbi allokációra hivatkozik. Dereferálása nem definiált viselkedés; nincs garantált eredménye.

A javítás indexet őriz meg, majd az aktuális kezdőpointert használja:

const size_t saved_index = 3;

if (buffer_reserve(&b, 32) == BUFFER_OK) {
    assert(saved_index < b.size);
    unsigned char value = b.data[saved_index];
    (void)value;
}

Ez szintén a meglévő programhoz tartozó C17-részlet. Ellenőrzési feltétele az index érvényessége és a harmadik indexű adat megőrzése, nem a régi és az új cím azonossága.

8.2.9 Összefoglaló

Pozitív méretű realloc kudarcakor a régi tároló megmarad; siker esetén kizárólag a visszaadott pointerből származtatott hozzáférések használhatók. A biztonságos puffer külön kezeli a méretet és a kapacitást, ellenőrzi az aritmetikát, és csak siker után módosítja tulajdonosi állapotát. A geometrikus növekedés amortizáltan olcsó beszúrást ad, de az egyedi növelések késleltetését és pointerérvénytelenítését nem szünteti meg.