13.1 Dinamikus tömb és string builder

A dinamikus tömb nem egyszerűen egy pointer és egy számláló: olyan tulajdonló objektum, amelynek minden művelet után igazolható állapotban kell maradnia. Ez különösen fontos hosszú életű szolgáltatásokban, ahol egy sikertelen allokáció nem teheti használhatatlanná a korábban összegyűjtött adatot.

A realloc és dinamikusan növekvő buffer szabályaira építve most vector-szerű C tárolót készítünk, majd erre string buildert építünk. A példában az elemek unsigned char értékek: nincs elemenként felszabadítandó erőforrás, így a tároló növelése nem igényel külön elemmásolási vagy destrukciós protokollt.

13.1.1 Reprezentáció és invariánsok

A reprezentációs invariáns olyan feltételrendszer, amely minden publikus művelet belépésekor és visszatérésekor teljesül. A bájtvektor három mezője:

• data: az allokált tároló kezdete;
• size: az inicializált, logikailag tárolt elemek száma;
• capacity: az allokált tárolóban elférő elemek száma.

A választott reprezentáció invariánsai:

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

továbbá capacity == 0 pontosan akkor igaz, ha data == NULL. Pozitív kapacitásnál data egy, a tároló által kizárólagosan birtokolt allokációra mutat. A [0,size) indextartomány olvasható elemeket tartalmaz; a [size,capacity) tartomány pusztán rendelkezésre álló tároló.

A kapacitás nem jogosít fel a logikai tartományon kívüli olvasásra. A végpozíció, data + size, nem egy tárolt elem címe. Üres, null pointeres reprezentációnál még ezt a pointerkifejezést sem képezzük.

Az allocator ownership itt egyszerű: a tároló realloc segítségével szerez memóriát, és free segítségével adja vissza. Nem fogad be idegen, például automatikus tárolási idejű tömböt.

A struktúrák értékmásolása miatt a leíró közönséges értékadása csak a pointert másolná, az allokációt nem. Két ilyen példány nem lehet egyszerre tulajdonos: az kettős felszabadításhoz vezethet. A példában ezért nincs implicit másolási szerződés.

13.1.2 Műveleti és hibaszerződés

A reserve(need) legalább need kapacitást biztosít, de nem változtatja meg a size értékét. A push(value) egy értéket, az append(src,n) pedig n elemet fűz a végére.

Az implementáció a következő változatlan állapotot garantáló hibaszerződést használja:

Túlcsordulás, hibás belső szelet vagy allokációs hiba esetén a korábbi tartalom, méret, kapacitás és tulajdonviszony változatlan.

Ez érvényes bemeneti leírókat feltételez. Érvénytelen pointert vagy nem olvasható forrástartományt a C függvény nem tud általánosan felismerni.

Az append külső forrása a hívás alatt érvényes és változatlan maradjon, és ne fedje át sem a leíró objektumot, sem annak allokált tárolóját. n == 0 esetén a forrás lehet null pointer. Saját tartalom hozzáfűzésére külön, indexalapú műveletet adunk.

Ez a szétválasztás nem fölösleges kényelmetlenség. Egy belső pointer már a másolás előtt dangling állapotba kerülhet, ha a kapacitás növelése sikeres realloc hívást végez. Ezen a memcpy lecserélése memmove-ra nem segít.

13.1.3 Biztonságos növekedés és amortizált költség

Legyen az elemméret $w>0$ C bájt. A legnagyobb reprezentálható elemszám:

$$M=\left\lfloor\frac{\text{SIZE\_MAX}}{w}\right\rfloor.$$

Előbb az elemszámot ellenőrizzük, és csak utána számítjuk ki a foglalási méretet:

$$c\leq M \quad\Longrightarrow\quad c\cdot w\leq\text{SIZE\_MAX}.$$

Hozzáfűzéskor az összeadás is ellenőrzendő. Ha $s$ a jelenlegi méret és $n$ a hozzáfűzendő elemszám, akkor:

$$n\leq\text{SIZE\_MAX}-s$$

szükséges ahhoz, hogy az s + n kifejezés ne forduljon körbe. A generikus esetben az így kapott elemszámot még $M$-hez is hasonlítani kell.

A kapacitást geometrikusan, itt kétszerezéssel növeljük. A határ közelében nem számítjuk ki vakon a 2 * capacity értéket: ha a duplázás már túl nagy lenne, $M$-re telítünk.

13.1.3.1 Bizonyításvázlat: amortizált elemmozgatás

Tegyük fel, hogy üres tárolóból indulunk, egyesével végzünk sikeres push műveleteket, nincs zsugorítás vagy külön felhasználói reserve, és az újraallokáláskor a régi elemek átmásolásával számolunk.

A geometrikus növekedésekhez tartozó másolási munka:

$$1+2+4+\dots+2^k=2^{k+1}-1.$$

Az utolsó ilyen növekedéshez már több mint $2^k$ elem beszúrása kellett. Ezért $N$ beszúrásra az összes korábbi elem mozgatása kevesebb mint $2N$. Az új elemek $N$ beírásával együtt a munka $O(N)$, tehát egy push amortizált költsége $O(1)$ elemmozgatás.

Ez ellenőrizhető költségmodell, nem mérési eredmény. Egyetlen növelő push legrosszabb esetben $O(N)$ elemet mozgathat; az allocator futásidejére ebből nem következik korlát. Az összefüggő tárolás kedvez a szekvenciális hozzáférés lokalitásának, és a geometrikus növekedés $O(\log N)$ allokációs hívással jár.

13.1.4 C17 megvalósítás

Az alábbi teljes fájl bájtvektort és arra épített string buildert tartalmaz. Minden méret C bájtban értendő; nincs szükség CHAR_BIT == 8 feltételezésre.

Nyelvi profil: ISO C17, hosted környezet, fordítóbővítések nélkül.
Kijelölt, itt nem validált laborprofil: Linux x86-64 System V ABI, LP64; GCC 14.2.0 vagy Clang 19.1.7; glibc 2.39. A kód nem használ platformfüggő API-t. Ellenőrzött külső forrásjegyzet és tényleges fordítási eredmény ehhez a példához nem áll rendelkezésre.

A builder belső vektorának size értéke tartalmazza a terminátort. Sikeres inicializálás után:

$$1\leq\text{size}\leq\text{capacity}, \qquad \text{data[size-1]}=0.$$

A logikai szöveghossz ezért size - 1.

/* buffer.c — ISO C17 */
#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

enum buf_status {
    BUF_OK,
    BUF_OVERFLOW,
    BUF_NOMEM,
    BUF_BOUNDS
};

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

struct strbuf {
    struct bytes bytes;
};

static enum buf_status
bytes_reserve(struct bytes *v, size_t need)
{
    const size_t max = SIZE_MAX / sizeof *v->data;

    if (need > max)
        return BUF_OVERFLOW;
    if (need <= v->capacity)
        return BUF_OK;

    size_t capacity = v->capacity ? v->capacity : 1;

    while (capacity < need) {
        capacity = capacity > max / 2 ? max : capacity * 2;
    }

    void *replacement =
        realloc(v->data, capacity * sizeof *v->data);

    if (replacement == NULL)
        return BUF_NOMEM;

    v->data = replacement;
    v->capacity = capacity;
    return BUF_OK;
}

/* src: külső, nem átfedő, a hívás alatt változatlan forrás. */
static enum buf_status
bytes_append(struct bytes *v, const void *src, size_t n)
{
    if (n == 0)
        return BUF_OK;
    if (n > SIZE_MAX - v->size)
        return BUF_OVERFLOW;

    size_t need = v->size + n;
    enum buf_status status = bytes_reserve(v, need);

    if (status != BUF_OK)
        return status;

    memcpy(v->data + v->size, src, n);
    v->size = need;
    return BUF_OK;
}

static enum buf_status
bytes_push(struct bytes *v, unsigned char value)
{
    return bytes_append(v, &value, 1);
}

/* Saját, már inicializált tartomány hozzáfűzése. */
static enum buf_status
bytes_append_slice(struct bytes *v, size_t offset, size_t n)
{
    if (offset > v->size || n > v->size - offset)
        return BUF_BOUNDS;
    if (n == 0)
        return BUF_OK;
    if (n > SIZE_MAX - v->size)
        return BUF_OVERFLOW;

    size_t old_size = v->size;
    enum buf_status status = bytes_reserve(v, old_size + n);

    if (status != BUF_OK)
        return status;

    memcpy(v->data + old_size, v->data + offset, n);
    v->size = old_size + n;
    return BUF_OK;
}

static void
bytes_destroy(struct bytes *v)
{
    free(v->data);
    *v = (struct bytes){0};
}

/* Csak új vagy már megsemmisített objektumra hívható. */
static enum buf_status
sb_init(struct strbuf *s)
{
    s->bytes = (struct bytes){0};
    return bytes_push(&s->bytes, 0);
}

/* Előfeltétel: sikeresen inicializált builder, külső forrás. */
static enum buf_status
sb_append(struct strbuf *s, const void *src, size_t n)
{
    struct bytes *v = &s->bytes;

    if (n == 0)
        return BUF_OK;
    if (n > SIZE_MAX - v->size)
        return BUF_OVERFLOW;

    size_t need = v->size + n;
    enum buf_status status = bytes_reserve(v, need);

    if (status != BUF_OK)
        return status;

    memcpy(v->data + v->size - 1, src, n);
    v->data[need - 1] = 0;
    v->size = need;
    return BUF_OK;
}

/* Kölcsönzött hozzáférés; nem ruház át tulajdonjogot. */
static const char *
sb_cstr(const struct strbuf *s)
{
    return (const char *)s->bytes.data;
}

static void
sb_destroy(struct strbuf *s)
{
    bytes_destroy(&s->bytes);
}

int main(void)
{
    struct bytes v = {0};
    struct strbuf s = {0};
    int result = EXIT_FAILURE;

    if (bytes_push(&v, (unsigned char)'A') != BUF_OK ||
        bytes_append(&v, "BC", 2) != BUF_OK ||
        bytes_append_slice(&v, 0, v.size) != BUF_OK ||
        sb_init(&s) != BUF_OK ||
        sb_append(&s, "node=", 5) != BUF_OK ||
        sb_append(&s, "ready", 5) != BUF_OK) {
        goto cleanup;
    }

    assert(v.size == 6);
    assert(memcmp(v.data, "ABCABC", 6) == 0);
    assert(s.bytes.size == 11);
    assert(strcmp(sb_cstr(&s), "node=ready") == 0);

    result = EXIT_SUCCESS;

cleanup:
    sb_destroy(&s);
    bytes_destroy(&v);
    return result;
}

A kijelölt kiadásoknak megfelelő fordítóparancsokkal:

gcc-14 -std=c17 -Wall -Wextra -Wpedantic -Wconversion -O2 \
    buffer.c -o buffer-gcc

clang-19 -std=c17 -Wall -Wextra -Wpedantic -Wconversion -O2 \
    buffer.c -o buffer-clang

A parancsnevek önmagukban nem garantálják a patchverziót; a tényleges kiadást a laborban rögzíteni kell. A program nem ír ki eredményt: sikeres műveletek esetén az állítások teljesülése és a sikeres kilépési állapot az elvárt ellenőrzés.

13.1.4.1 Miért helyes a hozzáfűzés?

A külső hozzáfűzés előbb ellenőrzi a méretet, majd biztosítja a tárolót, és csak ezután módosítja a tartalmat. Az allokációs hiba tehát megelőzi az első tartalmi változtatást.

A saját szeletnél a forrás címe csak a reserve után képződik újra az indexből. A forrás a régi [0,old_size) tartományban van, a cél pedig old_size-nál kezdődik, ezért a két másolt tartomány nem fed át: itt a memcpy megfelelő.

A builder a régi terminátor helyére másol, majd az új végére nullát ír. A terminátor helyigénye már benne volt a régi size értékében, ezért az új foglalási igény size + n, nem pedig ellenőrizetlenül size + n + 1.

13.1.5 Pointerstabilitás és gyakori hibák

ISO C17 szabály: sikeres, pozitív méretű realloc után a régi allokációra hivatkozó pointereket érvénytelennek kell tekinteni, akkor is, ha az új tároló numerikus címe azonosnak látszik.

A sb_cstr eredménye sem tulajdonló. Újraallokálás vagy megsemmisítés érvényteleníti; növelés nélküli hozzáfűzés pedig ugyanazon címen megváltoztatja a látható sztringet.

Gyakori hiba a data = realloc(data, ...) közvetlen értékadás: sikertelenségkor elveszhet a régi allokáció címe. A példában az ideiglenes replacement ezt akadályozza meg.

Másik hiba a terminátor és a logikai hossz összekeverése. A nullterminált sztringeknél tanultak szerint egy beágyazott nulla korábban lezárja a C-sztringet. Builderünk megőrzi a beágyazott nullákat, ezért strlen(sb_cstr(&s)) nem feltétlenül egyenlő s.bytes.size - 1 értékével. Kizárólag szöveget elfogadó API esetén a beágyazott nullákat külön kellene elutasítani.

13.1.6 Feladatok

1. Invariáns és költség. Üres vektorba kilenc elemet szúrunk. Mennyi a méret, a kapacitás és a modell szerinti összes másolás? Invalidál-e ezután egy reserve(7) hívás?

2. Kódolás. Készíts sb_append_slice függvényt, amely a builder saját szövegének egy indexelt részét fűzi hozzá. A forrásszelet nem tartalmazhatja a záró terminátort. Hiba esetén maradjon változatlan az állapot.

3. Diagnosztika. Az alábbi C17-részlet előtt v.size == v.capacity == 8. Mi a hiba, és miért nem megoldás a másolófüggvény lecserélése?

/* HIBÁS: sikeres növelés után érvénytelen pointert olvas. */
const unsigned char *saved = v.data;

if (bytes_push(&v, (unsigned char)'X') == BUF_OK) {
    unsigned char first = saved[0];
    (void)first;
}

13.1.7 Megoldások

13.1.7.1 Invariáns és költség

A méret 9, a kapacitás 16. A korábbi elemek másolásának modell szerinti összege:

$$1+2+4+8=15.$$

A reserve(7) nem csökkenti a kapacitást, nem allokál, és nem invalidál pointert. Ellenőrzési feltétel: a méret és a kapacitás is változatlan.

13.1.7.2 Saját szövegszelet hozzáfűzése

A következő részlet a teljes példába, a main elé illeszthető; ugyanaz a C17-profil és tulajdonlási szerződés érvényes rá.

static enum buf_status
sb_append_slice(struct strbuf *s, size_t offset, size_t n)
{
    struct bytes *v = &s->bytes;
    size_t length = v->size - 1; /* inicializált builder */

    if (offset > length || n > length - offset)
        return BUF_BOUNDS;
    if (n == 0)
        return BUF_OK;
    if (n > SIZE_MAX - v->size)
        return BUF_OVERFLOW;

    size_t need = v->size + n;
    enum buf_status status = bytes_reserve(v, need);

    if (status != BUF_OK)
        return status;

    memcpy(v->data + length, v->data + offset, n);
    v->data[need - 1] = 0;
    v->size = need;
    return BUF_OK;
}

Az indexek túlélik az újraallokálást; a pointereket utána képezzük. A forrás legfeljebb length-ig tart, a cél ott kezdődik, tehát nincs átfedés.

Ellenőrzési esetek: "abc" teljes önhozzáfűzése "abcabc"; üres szeletnél nincs változás; tartományhiba és injektált allokációs hiba esetén a teljes korábbi állapot megmarad. Sikeres növeléskor minden korábbi borrowed pointer érvénytelen.

13.1.7.3 Érvénytelen pointer újraképzése

A kilencedik elemhez újraallokálás kell. Siker esetén saved már nem használható: az olvasás nem definiált viselkedés, garantált kimenete nincs.

A helyes hozzáférés siker után v.data[0], vagyis az aktuális tárolóból újraképzett pointer. A memmove csak élő tartományok átfedő másolását kezeli, megszűnt tárolóhoz nem ad új élettartamot.

Allokációs hibánál a régi pointer továbbra is érvényes, de az elem nem került be. A két hibautat külön kell ellenőrizni.

13.1.8 Összefoglaló

A megbízható C tároló alapja az explicit invariáns, az egyértelmű tulajdonos és a változatlan állapotot megőrző hibakezelés. A geometrikus növekedés amortizált költséget javít, pointerstabilitást azonban nem biztosít. Saját tartalom másolásakor indexet őrizzünk, ne régi belső pointert. A string builder mindehhez hozzáadja a terminátor következetesen fenntartott invariánsát.