13.2 Láncolt és intrusive listák

Egy láncolt listában a pointerek helyes átállítása csak a feladat egyik fele. A másik: ki tartja életben a csomópontot, ki szabadíthatja fel, és mit jelent egy korábban eltett bejárópozíció a lista módosítása után? Egy feladatütemezőben például ugyanaz a munkaobjektum átkerülhet a várakozó listából a futó listába anélkül, hogy maga az objektum elköltözne.

A fejezet a struktúrák értékmásolására, az explicit tulajdonlási szerződésre és a pointeraritmetika objektumhatáraira épít. A példák ISO C17-et használnak; a listákhoz egy időben egy végrehajtási szál fér hozzá.

13.2.1 A kapcsolatok és a tulajdonlás külön szerződés

Az egyszeresen láncolt lista (singly linked list) csomópontja a következő csomópontra mutat. A kétszeresen láncolt lista (doubly linked list) az előzőre is tárol hivatkozást. Ezek a kapcsolatok önmagukban semmit sem mondanak a tulajdonlásról.

A tulajdonló lista (owning list) felel a csomópontjai felszabadításáért. Gyakori megvalósításában minden beszúrás külön csomópontot allokál. A csomópontban tárolt payload tulajdonlása ettől még külön döntés: egy benne tárolt pointer lehet kölcsönzött is.

Az intrusive lista kapcsolómezői magába a nyilvántartott objektumba vannak beágyazva. Emiatt nincs szükség külön listacsomópont-allokációra. Az intrusive jelleg azonban nem tulajdonlási szabály: itt kifejezetten nem tulajdonló intrusive listát tervezünk.

Ugyanaz az objektum több intrusive listában is szerepelhet, de minden egyidejű tagsághoz külön kapcsolópár szükséges. Ugyanazt a next/prev párt két lista nem használhatja.

13.2.2 Sentinel és reprezentációs invariáns

A sentinel, vagy őrszemcsomópont, szerkezeti elem, nem felhasználói adat. Körkörös, kétszeresen láncolt listánál az őrszem next mezője az első, prev mezője az utolsó elemre mutat. Üres listában mindkettő önmagára mutat.

Minden bekapcsolt csomópontra, az őrszemet is beleértve, megköveteljük:

$$n\mathbin{\to}\mathrm{next}\mathbin{\to}\mathrm{prev}=n, \qquad n\mathbin{\to}\mathrm{prev}\mathbin{\to}\mathrm{next}=n.$$

További invariáns, hogy a next kapcsolatokat követve minden adatelem pontosan egyszer érinthető az őrszemhez való visszatérés előtt. A lokális egyenletek önmagukban ezt nem bizonyítják: egy különálló kör is teljesítheti őket.

Egyszeresen láncolt listában egy ismert előd után beszúrni vagy törölni konstans számú kapcsolatmódosítás. Pusztán a törlendő csomópont ismerete általában nem elég: az előd megkeresése lineáris lehet. Kétszeresen láncolt listánál az előd közvetlenül rendelkezésre áll.

Az őrszemet tartalmazó listaobjektumnak stabil címen kell maradnia. A struct értékmásolása nem készít új, önálló listát: az átmásolt pointerek továbbra is az eredeti objektumokra mutatnak.

13.2.3 Kidolgozott példa: munkák áthelyezése

A következő teljes programban a main a job objektumok tulajdonosa. A listák csak kölcsönzik őket. A member_of mező nyilvántartja a tagságot, így felismerhető a kétszeres beszúrás és a rossz listából történő eltávolítás.

Előfeltételek: minden átadott pointer élő, megfelelően inicializált objektumra mutat; a listák invariánsai teljesülnek; a bekapcsolt objektumokat és listaobjektumokat nem másolják vagy költöztetik. A false visszatérés felismert szerződéssértést jelent, változatlan állapottal. Érvénytelen pointert ezek az ellenőrzések nem tesznek biztonságossá.

A list.c tartalma:

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>

struct list;

struct job {
    struct job *prev;
    struct job *next;
    struct list *member_of;
    unsigned id;
};

struct list {
    struct job root;
};

static void list_init(struct list *l)
{
    l->root = (struct job){
        .prev = &l->root,
        .next = &l->root,
        .member_of = l
    };
}

static bool list_push_back(struct list *l, struct job *n)
{
    if (n->member_of != NULL ||
        n->next != NULL || n->prev != NULL)
        return false;

    struct job *tail = l->root.prev;
    n->prev = tail;
    n->next = &l->root;
    tail->next = n;
    l->root.prev = n;
    n->member_of = l;
    return true;
}

static bool list_unlink(struct list *l, struct job *n)
{
    if (n == &l->root || n->member_of != l)
        return false;

    n->prev->next = n->next;
    n->next->prev = n->prev;
    n->prev = NULL;
    n->next = NULL;
    n->member_of = NULL;
    return true;
}

static bool list_move_back(struct list *dst,
                           struct list *src,
                           struct job *n)
{
    if (dst == src || n == &src->root ||
        n->member_of != src)
        return false;

    if (!list_unlink(src, n))
        return false;

    /* Az invariáns szerint n most leválasztott. */
    return list_push_back(dst, n);
}

int main(void)
{
    struct list pending;
    struct list running;
    struct job a = {.id = 7};
    struct job b = {.id = 8};

    list_init(&pending);
    list_init(&running);

    if (!list_push_back(&pending, &a) ||
        !list_push_back(&pending, &b))
        return EXIT_FAILURE;

    struct job *cursor = &a;

    if (!list_move_back(&running, &pending, &a))
        return EXIT_FAILURE;

    if (cursor->member_of != &running)
        return EXIT_FAILURE;

    if (!list_unlink(&pending, &b) ||
        !list_unlink(&running, cursor))
        return EXIT_FAILURE;

    return EXIT_SUCCESS;
}

Fordítási profil: ISO C17, hosted környezet; javasolt laborprofil Linux x86-64, System V ABI, LP64, GCC 14.2.0 vagy Clang 19.1.0, glibc 2.39. A kód nem használ ABI-függő layoutot vagy fordítóbővítést. Az alábbi parancsokhoz nem tartozik itt igazolt fordítási vagy futási eredmény.

gcc -std=c17 -Wall -Wextra -Wpedantic -Wconversion -O1 -g list.c -o list-gcc
clang -std=c17 -Wall -Wextra -Wpedantic -Wconversion -O1 -g list.c -o list-clang

Beszúráskor először az új csomópont két kapcsolatát állítjuk be, majd a két szomszédot kapcsoljuk hozzá. A művelet közben átmenetileg nem teljesül minden invariáns; ezért ez nem konkurens hozzáférésre alkalmas algoritmus.

Bizonyításvázlat: az üres lista teljesíti az invariánst. Beszúrás csak a régi utolsó elem és az őrszem közötti kapcsolatot bontja ketté. Leválasztás az eltávolított elem két szomszédját közvetlenül összeköti. Minden más kapcsolat változatlan, ezért a teljes lista invariánsa megmarad. A list_move_back ellenőrzései után a leválasztás sikeres, majd a beszúrás feltételei szükségképpen teljesülnek: nincs allokációs vagy más várható közbülső hibakimenet.

13.2.4 Cursorérvényesség és splice

A cursor itt eltett csomópont-pointer és az ahhoz társított bejárási szerződés. Külön kell választani az objektum létezését és a listabeli pozíció érvényességét.

A példában cursor az áthelyezés után továbbra is a-ra mutat, de már nem használható a pending lista bejárójaként.

A splice meglévő csomópontok átkapcsolása másik listapozícióra, másolás és új csomópont-allokáció nélkül. A példában egyetlen elemet mozgatunk eltérő listák között. Tulajdonló listánál ehhez a felszabadítási szabályok kompatibilitása és a tulajdonjog átadása is szükséges.

Általános, $[first,last)$ tartományt mozgató splice esetén rögzíteni kell, hogy a tartomány összefüggő, a forráshoz tartozik, és a célpozíció nem esik a mozgatott tartomány belsejébe. Az üres tartományt és a saját listán belüli áthelyezést külön kell specifikálni.

Fontos költségkülönbség: a határkapcsolatok átállítása lehet $O(1)$, de a példabeli member_of mező frissítése $k$ mozgatott elemnél $O(k)$. A diagnosztikai metaadat is része a költségmodellnek.

13.2.5 Locality és a konstans idejű művelet korlátai

Az $O(1)$ beszúrás feltétele, hogy a pozíció már ismert. Ha előbb azonosító alapján keresünk, a teljes művelet $O(n)$ lehet. Tulajdonló listánál az allokáció költsége sem következik a kapcsolatmódosítás konstans műveletszámából.

Bejáráskor a következő cím az aktuális csomópontból olvasható ki. Ez a pointer chasing adatfüggő hozzáférési lánc: a következő olvasás gyakran csak az előző eredménye után indítható. Szétszórt csomópontoknál gyenge lehet a cache-locality, és több lapot kell érinteni.

A folytonos tömb szintén $O(n)$ időben járható be, mégis kedvezőbb lehet az előbetöltés és a cache-kihasználás. Az intrusive lista elhagyja a külön csomópont-allokációt, de nem garantál jó localityt: azt az objektumok tényleges elhelyezése határozza meg. Itt nem mért gyorsulásról, hanem eltérő költségtényezőkről beszélünk.

13.2.6 A container_of hordozhatósági határa

Generikus intrusive megoldások gyakran külön kapcsolóstruktúrát ágyaznak a payloadba. A container_of jellegű művelet a kapcsolómező pointeréből próbálja visszakapni a befoglaló objektum pointerét.

A gyakori recept a mező címéből kivonja az offsetof(T, member) értéket. Az offsetof ISO C17-es eszköz, de a numerikusan helyes offset önmagában nem igazolja a teljes visszaalakítás hordozhatóságát. A karakterpointeres aritmetika objektumhatárait és a kapott pointer jogosultságát is vizsgálni kell.

Egyes makrók GNU typeof vagy statement expression bővítést használnak; ezek nem ISO C17-szolgáltatások. Más változat szintaktikailag szabványosnak látszhat, miközben továbbra is implementációs feltételezésekre épít.

További előfeltétel a tényleges befoglaló típus, a megfelelő tag, valamint az élő befoglaló objektum. Önálló sentinel-hookra alkalmazva a makró nem varázsol mögé payloadot.

ISO C17: a struktúra és első, nem bitmező tagja közötti megfelelő pointerkonverzió külön nyelvi garanciát kap; ez nem általános felhatalmazás tetszőleges belső tagból történő visszalépésre. A példánk teljes, típusos job őrszemet használ, ezért nincs szüksége container_of műveletre.

13.2.7 Gyakori hibák

A kétszeres beszúrás felülírhatja a már használt kapcsolatokat, elveszett elemeket vagy hibás ciklust létrehozva. A tagságjelző ezt a szabályos API-használat keretein belül felismeri.

A körkörösség önmagában nem hiba: a sentinel-lista szándékosan körkörös. Az a hiba, ha a bejárás az őrszem elérése nélkül ismétel csomópontot.

A felszabadítás előtti leválasztás elmulasztása dangling next/prev kapcsolatot hagy a listában. A törlési ciklus másik gyakori hibája, hogy a következő pointert csak a leválasztás vagy felszabadítás után olvassa ki. A következő pozíciót előre kell elmenteni, és annak élettartamát is garantálni kell.

13.2.8 Feladatok

1. Magyarázat: egy egyszeresen láncolt listában csak a törlendő csomópont pointerét ismered. Miért nem ígérhetsz általánosan $O(1)$ törlést? Mi változik kétszeresen láncolt listánál?

2. Kódolás: írj függvényt, amely a példabeli listából leválasztja a páros id értékű munkákat. Az objektumokat nem szabad felszabadítani.

3. Diagnosztika: mi romlik el, ha egy bekapcsolt munkát újra beszúrnak, egy nem üres listát érték szerint lemásolnak, vagy egy heapen tárolt munkát leválasztás nélkül felszabadítanak? Adj ellenőrzési feltételt mindháromhoz.

13.2.9 Megoldások

13.2.9.1 A törlés előfeltétele

Egyszeresen láncolt listánál az előd next mezőjét kell módosítani, ezért az előd megkeresése $O(n)$ lehet. Kétszeresen láncolt listánál az ismert, érvényes csomópont prev mezője biztosítja ezt az információt. Az ellenőrzési feltétel: a törölt csomópont kihagyásával minden megmaradó elem elérhető, eredeti sorrendben.

13.2.9.2 Biztonságos leválasztó bejárás

Az alábbi C17-részlet a list.c függvényeire épül. A tulajdonos továbbra is a hívó; minden csomópont él a teljes bejárás alatt. A leválasztás csak az aktuális listapozíciót érvényteleníti.

static bool unlink_even(struct list *l)
{
    struct job *p = l->root.next;

    while (p != &l->root) {
        struct job *next = p->next;

        if (p->id % 2u == 0u && !list_unlink(l, p))
            return false;

        p = next;
    }
    return true;
}

Ellenőrzésként próbálj üres, csak páros, csak páratlan és váltakozó listát. A megmaradó elemek sorrendje változatlan; minden leválasztott elem három kapcsolati mezője nullpointer. A false belső szerződéssértést jelez, nem tranzakciós visszagörgetést.

13.2.9.3 Három eltérő sérülés

A kétszeres beszúrást a member_of != NULL feltétel utasítja el; ellenőrizni kell, hogy a lista változatlan maradt.

Az értékmásolat kapcsolatai az eredeti őrszemre és csomópontokra mutatnak. Javítása nem pointerfoltozás: új listát kell inicializálni, majd meghatározott másolási vagy áthelyezési szerződést alkalmazni.

Leválasztás nélküli felszabadítás után a szomszédok érvénytelen élettartamra hivatkoznak. A tulajdonosnak előbb sikeresen le kell választania az elemet, majd felszabadítania; utána egyetlen listakapcsolat és használható cursor sem hivatkozhat rá.

13.2.10 Összefoglaló

A lista kapcsolati topológiája, tulajdonlása és cursorérvényessége három külön szerződés. Az intrusive tárolás stabil című objektumokat és explicit tagságkezelést igényel. A splice megőrizheti a csomópont címét, miközben megváltoztatja a tagságát vagy tulajdonosát. A konstans számú pointermódosítás pedig nem jelent automatikusan olcsó keresést, allokációt vagy cache-barát bejárást.