Bakhönnun gagnaskipana

Þegar verkefni verða stærri en einföld lykilorðsathugun fara forrit að geyma gögnin sín í gagnaskipanum (e. data structures): fylkjum, listum, trjám og töflum. Til að skilja hvað forritið gerir þurfum við að bera kennsl á þessar gagnaskipanir þegar þær birtast í bakþýðanda eða í minni.

Hver gagnaskipan skilur eftir sig einkennandi mynstur í kóðanum. Þegar við lærum að þekkja mynstrin getum við oft áttað okkur fljótt á því hvaða gagnaskipan er notuð.

Af hverju skipta gagnaskipanir máli?

Tökum dæmi: forrit sem geymir orðalista. Það gæti notað:

• fylki: einfalt en leit getur verið hæg
• tætitöflu: mjög hröð uppfletting
• tré: raðað og hægt að leita hratt

Sama verkefnið má útfæra á þrjá ólíka vegu og hver útfærsla lítur öðruvísi út í bakþýðandanum. Ef við þekkjum gagnaskipanina sjáum við hvernig gögnin tengjast og eigum auðveldara með að rekja okkur að fánanum.

Grunneiningin: grunngerð

Næstum allar flóknari gagnaskipanir eru byggðar úr grunngerðum (e. struct). Grunngerð hópar saman nokkrum sviðum (e. fields) í eina heild. Í minni er grunngerð einfaldlega nokkur gildi sem liggja hlið við hlið:

struct User {
    int   id;        // hliðrun 0  (4 bæti)
    int   age;       // hliðrun 4  (4 bæti)
    char  name[16];  // hliðrun 8  (16 bæti)
};                   // alls 24 bæti

Í minni:

block-beta
    columns 6
    BytesId["bæti 0–3"] BytesAge["bæti 4–7"] BytesName["bæti 8–23"]:4
    Id["id"] Age["age"] Name["name[16]"]:4

    style BytesId fill:transparent,stroke:transparent,color:#94a3b8
    style BytesAge fill:transparent,stroke:transparent,color:#94a3b8
    style BytesName fill:transparent,stroke:transparent,color:#94a3b8
    style Id fill:#1e3a8a,stroke:#60a5fa,color:#ffffff
    style Age fill:#1e3a8a,stroke:#60a5fa,color:#ffffff
    style Name fill:#1e3a8a,stroke:#60a5fa,color:#ffffff

Reitirnir eru í réttum hlutföllum: id og age taka hvort um sig 4 bæti en name tekur 16. Hliðrunin segir hversu mörg bæti eru frá upphafi grunngerðarinnar að byrjun sviðsins. Sviðið name hefst því 8 bætum frá byrjun User.

Hvernig grunngerð birtist í bakþýðanda

Bakþýðendur bera ekki alltaf kennsl á grunngerðir sjálfkrafa. Í staðinn sjáum við oft fastar hliðranir (e. offsets) út frá einum bendli:

// Það sem bakþýðandinn sýnir í fyrstu:
iVar1 = *(int *)(param_1 + 4);          // param_1->age
puts((char *)(param_1 + 8));            // param_1->name

Þegar sami bendillinn birtist með nokkrum föstum hliðrunum, til dæmis +0, +4 og +8, er það vísbending um grunngerð.

Fylki

Einfaldasta gagnaskipanin er röð gilda af sömu gerð sem liggja samfellt í minni. Við flettum gildunum upp með vísitölu.

int scores[5];
scores[2] = 99;

Hvernig á að þekkja fylki

Í smalamáli og bakþýðanda birtist aðgangur að fylki oft sem grunnvistfang að viðbættri vísitölu sem er margfölduð með stærð hvers staks:

// arr[i] þar sem arr er int (4 bæti):
iVar1 = *(int *)(arr + i * 4);

mov eax, dword ptr [rbx + rcx*4]   ; eax = arr[rcx]

Mynstrið grunnvistfang + vísitala * stærð er skýrasta merkið um fylki.

Keðjulisti

Keðjulisti er röð hnúta þar sem hver hnútur geymir gögn og bendil á næsta hnút.

struct Node {
    int data;
    struct Node *next;   // bendir á sömu gerð!
};

%%{init: {"themeVariables": {"fontSize": "18px"}}}%%
flowchart LR
    Head["head"] --> Node1

    subgraph Node1["Hnútur 1"]
        direction LR
        Data1["data: 12"] ~~~ Next1["next"]
    end

    subgraph Node2["Hnútur 2"]
        direction LR
        Data2["data: 7"] ~~~ Next2["next"]
    end

    Next1 --> Node2
    Next2 --> Null["NULL"]

    style Head fill:transparent,stroke:transparent,color:#94a3b8
    style Null fill:transparent,stroke:transparent,color:#94a3b8
    style Data1 fill:#1e3a8a,stroke:#60a5fa,color:#ffffff
    style Data2 fill:#1e3a8a,stroke:#60a5fa,color:#ffffff
    style Next1 fill:#4c1d95,stroke:#a78bfa,color:#ffffff
    style Next2 fill:#4c1d95,stroke:#a78bfa,color:#ffffff

Lykilmerkið

Grunngerð sem inniheldur bendil á aðra grunngerð sömu tegundar. Þegar við sjáum slíka sjálftilvísun er það vísbending um tengda gagnaskipan, til dæmis keðjulista eða tré.

Yfirferð keðjulista getur litið svona út í bakþýðanda:

// Að fara í gegnum allan listann:
for (node = head; node != NULL; node = *(void **)(node + 8)) {
    // node + 8 er 'next' bendillinn
    process(*(int *)(node + 0));   // node->data
}

Lykkja sem endar á node = node->next, það er les bendil úr hnútnum og notar hann sem nýja hnútinn, er einkenni keðjulista.

Tré og tvíundatré

Tré svipar til keðjulista en hver hnútur getur haft fleiri en einn bendil á börn. Algengt dæmi er tvíundatré þar sem hver hnútur hefur í mesta lagi tvö börn:

struct TreeNode {
    int value;
    struct TreeNode *left;    // vinstra barn
    struct TreeNode *right;   // hægra barn
};

flowchart TB
    Root["8"] --> Left["3"]
    Root --> Right["10"]

Endurkvæmni gefur tré upp

Endurkvæmni birtist oft þegar unnið er með tré, það er í föllum sem kalla á sjálf sig fyrir vinstra og hægra barn:

void walk(struct TreeNode *node) {
    if (node == NULL) return;
    walk(node->left);     // kallar á sjálft sig
    process(node->value);
    walk(node->right);    // kallar á sjálft sig aftur
}

Þegar fall kallar á sjálft sig tvisvar með tveimur ólíkum bendlum úr sömu grunngerð er það sterk vísbending um yfirferð tvíundatrés.

Tætitafla

Tætitafla geymir pör lykla og gilda og notar tætifall til að reikna í hvaða sæti hvert gildi fer. Þetta gefur mjög hraða uppflettingu.

Lykilmerkið

Fylki ásamt reikningi sem breytir lykli í vísitölu, oft með margföldun, XOR og afgangsdeilingu (%):

unsigned hash = 0;
for (int i = 0; key[i]; i++)
    hash = hash * 31 + key[i];     // dæmigert tætifall
index = hash % TABLE_SIZE;         // afgangsdeiling → sæti í fylkinu

Þegar við sjáum streng felldan saman í eina tölu með margföldun og % og töluna síðan notaða sem vísitölu í fylki er það vísbending um tætitöflu.

Net

Net (e. graph) er almenn tengd gagnaskipan: hnútar tengjast með brúnum án fastrar stigskiptingar eins og í tré. Net er oft geymt sem grannfylki, sem er tvívítt fylki, eða grannlistar, sem eru fylki af listum.

Net birtast í þrautum þar sem við þurfum að finna leið milli hnúta. Slík verkefni leysum við oft með leitarreikniritum eins og þverleit (e. breadth-first search, BFS) og lóðleit (e. depth-first search, DFS). Dýpri umfjöllun er í æfingaverkefninu Metro Map.

Yfirlit: hvernig á að þekkja skipanina

Að skoða gagnaskipanir á keyrslutíma í GDB

Stundum er auðveldast að rekja gagnaskipanina á meðan forritið er í keyrslu. Í GDB getum við elt bendla á milli hnúta:

# Skoða hnút (grunngerð með data við hliðrun 0 og next við hliðrun 8)
x/2gx 0x5555555592a0          # fyrsta gildið inniheldur data og uppfyllingu; annað er next

# Elta 'next' bendilinn í næsta hnút
x/2gx <gildið sem next benti á>

Ef við höfum skilgreint grunngerð í bakþýðandanum eða notum pwndbg getum við einnig prentað heilan hnút í einu. Þetta er sérstaklega gagnlegt þegar tréð eða listinn er byggður upp á keyrslutíma og er ekki til staðar í kyrrstæðu gögnunum.

Æfingar

Þessi verkefni æfa okkur í að bera kennsl á og rekja gagnaskipanir. Þau eru ívið erfiðari en fyrri verkefni og reyna á allt sem við höfum lært:

• spell-checker: Við skoðum hvernig forritið skipuleggur gögn á keyrslutíma og sækir upplýsingar úr þeim.
• Family Tree: Við rekjum tengsl milli hnúta og ákveðum í hvaða röð eigi að lesa gögn þeirra.
• Metro Map: Við skoðum tengingar milli staða á korti og finnum leið sem uppfyllir skilyrði verkefnisins.
• The Long Way Round: Við skoðum reiknirit sem tekur óraunhæfan tíma og leitum að skilvirkari nálgun.