Seminář 4

Životnost objektů za běhu programu

Pro nás význam: kdy je objekt v paměti během běhu programu? (anglicky storage duration). Když je pamět objektu přidělena, říkáme, že je pro něj alokována. Uvolnění paměti objektu někdy říkáme dealokace.

Existují tři typy životnosti, statická, automatická a manuální.

Pro objekty se statickou životností je paměť alokována při startu programu, uvolněna na konci běhu programu. O její alokaci je rozhodnuto při překladu programu. Statickou zprávu paměti mají zejména

objekty definované na úrovni souboru, například globální proměnné, složené literály.
lokální proměnné definované se storage class static,
řetězcové literály (globální i uvnitř funkcí).

Objekty lze inicializovat na hodnotu známou v době překladu. Jinak jsou automaticky inicializovány na 0.

Storage class se u proměnné specifikuje při definici, píše se na první místo. Proměnná si uchovává hodnotu mezi jednotlivými zavoláními funkce.

int fce() {
    static int count;  // inicializace na 0 pri startu programu
    count += 1;
    return count;      // vraci kolikrat byla zavolana
}

Řetězcové literály jsou pouze ke čtení, pokus o jejich změnu vede k nedefinovanému chování. Mohou být uložen tak, že se překrývají, například sdílejí svůj konec.

char *r = "retezcovy literal";
r[0] = 'x';  // nedefinovane chovani

Složené literály lze měnit.

typedef struct {
    float x;
    float y;
} vec2f;

// globalni promena
vec2f *ptr = &(vec2f){.x=3.2f, .y=2.1f};

// nekde uvnitr funkce
prt->x = 2.4;   // OK

Alokace a dealokace objektů s automatickou životností se děje automaticky za běhu programu. Mezi objekty s automatickou životností patří

lokální proměnné, které nemají storage class static,
lokální složené literály,
dočasné objekty vytvořené jako návratové hodnoty funkcí (navíc jsou pouze ke čtení)

Objekty typicky vznikají v momentě vstupu do bloku, ve kterém jsou definovány a zanikají při výstupu z tohoto bloku. Nejsou automaticky inicializovány je nutné je inicializovat explicitně. Je chyba vracet z funkce adresu objektu s automatickou životností, objekt je totiž po skončení funkce dealokován. Dereference adresy pak vede k nedefinovanému chování.

int* fce() {
  int array[] = {1,2,3};
  return array;            // chyba !!!!!
}

// nekde v kodu
int *a = fce();
a[0] = 5;    // nedefinovane chovani

K manuální správě paměti aplikační programátor většinou využije nejakou knihovnu, kde je implementován alokátor paměti (ten se stará o přidělování paměti, sám ji získává od operačního systému). Rozhraní alokátoru ze standardní knihovny je dáno funkcemi z hlavičkového souboru stdlib.h.

alokační funkce malloc, calloc,
dealokační funkce free,
realokační funkce realloc.

Princip použití alokačních funkcí je následující: funkci nějakým způsobem předáme počet bajtů, které chceme alokovat. Funkce vrátí adresu prvního bajtu souvislého kusu paměti požadované velikosti. V případě, že se alokace nepovede, vrací funkce 0.

Funkci free předáme jako argument adresu, kterou někdy předtím vrátila některá alokační nebo realokační funkce, a která ukazuje na doposud neuvolněnou paměť.free tuto paměť uvolní. Pokud jí předáme 0, nedělá free nic. Pokud jí ovšem předáme jakoukoliv jinou adresu, vede to nedefinovanému chování.

Funkce realloc umožňuje změnit velikost již alokované paměti.

Podrobnosti k jednotlivým funkcím si čtenář najde v referenční příručce, řekneme si pouze příklady typického použití a častých chyb.

int m = 20;
int* array = malloc(m * sizeof(int)); // alokace pro pole int velikosti m
assert(array);  // pro ucely kurzu staci tato kontrola, 
                // obecne muze byt potreba komplikovanejsi test uspechu alokace

// pracuj s polem array

free(array);   // uvolnime pamet
array = 0;     // nastavime pointer na neplatny

Funkce realloc muze při změně velikosti alokovane paměti přesunout její obsah na jinou adresu a původní paměť uvolnit.

int realloc_size[] = {10, 12, 512, 32768, 65536, 32768};
int m = sizeof(realloc_size)/sizeof(realloc_size[0]);
int *next = 0;

for (int i = 0; i < m; i += 1) {
    int *ret = realloc(next, sizeof(int) * realloc_size[i]);
    assert(ret);
    printf("%p -> %p\n", next, ret);   // pokud dojde k presunu, vypisi se ruzne adresy
    next = ret;
}
free(next);

Mezi hlavní chyby při manuální správě paměti patří tzv. memory leak a double free. První chyba nastane tak, že v programu zapomeneme adresu alokované paměti bez toho, abychom ji uvolnili. Tím pádem už ji nikdy uvolnit nemůžeme. Program má pak tuto paměť alokovánu zbytečně. Ke druhé chybě dojde tak, že se alokovanou paměť pokusíme uvolnit dvakrát (nebo vícekrát), mimo první pokus to vede k nedefinovanému chování.

Na závěr dodejme, že po skončení programu všechnu jeho paměť uvolní operační systém.

Existují také jiné přístupy ke správě paměti, které nahrazují nebo vylepšují manuální správu, například tzv. počítání referencí nebo garbage kolektory. Ty jsou v určité formě pro jazyk C přístupné jako knihovny (např.Boehm garbage collector).

Úkoly

Implementujte funkci, která vrátí nově alokovaný řetězec, jehož obsah vznikne spojením dvou řetězců předaných funkci jako argumenty.
Implementuje zásobník pomocí dynamického pole.
```
typedef struct {
    int *data;    // pole pro vlozena data
    int top;      // pocet vlozenych prvku
    int cap;    // velikost pole data
} Stack;

Stack create_stack() {
    return (Stack){0};
}
```
Doprogramujte operaci push tak, aby v momentě, kdy je zásobník zaplněn, tato operace realokovala položku data na dvojnásobnou velikost.

Doprogramujte operaci ‘pop’ tak, aby v momentě, kdy je zásobník zaplněn z jedné čtvrtiny, zmenšila položku data na polovinu.

První nenulovou velikost zásobníku vyberte jako malou mocninu 2, např. 16.