Alokace paměti

Než si ukážeme jak alokovat paměť v jazyku C, tak si popíšeme jaké druhy paměti můžeme využít pro uložení hodnot proměnných.

Zásobník

Na zásobníku jsou uloženy všechny lokální a globální proměnné. Dále jsou zde uloženy informace o volaných funkcích. Podrobnější informace se dozvíte v předmětu Operační Systémy 1. Zásobník (angl. stack) je část paměti přiřazená OS spuštěnému programu a v průběhu se jeho velikost nemění. Uvažujme program níže, kde máme definovanou funkci multiply a funkci main , kde jsou definované 3 lokální proměnné x, y a z.

    int multiply(int left, int right) {
        return left * right;
    }
    
    int main() {
        int x = 10;
        int y = 20;
        int z = multiply(x, y);
        
        printf("%i\n", z);
        return 0;
    }

Na obrázku níže je ukázáno, jak se mění obsah zásobníku v průběhu vykonávání programu. Po spuštění programu se vytvoří místo na zásobníku pro globální proměnné a pro funkci main (tzv. stack frame). Funkce main obsahuje volání funkce multiply. To způsobí, že je nutné na zásobníku vytvořit stack frame pro funkci multiply. Zde jsou uloženy lokální proměnné funkce a argumenty. Naše funkce nemá žádné lokální proměnné a tak se na zásobník jen uloží hodnoty argumentů left a right a pak se provedou instrukce obsažené v těle funkce. Jakmile je dokončen výpočet a navrácena hodnota (pokud má), tak je stack frame vymazán. To je důvod proč nesmíme vracet ukazatel na lokální proměnnou funkce.

Halda

Pokud chceme v těle funkce vytvořit hodnotu (například pole), tak kvůli výše uvedenému důvodu to nemůžeme provést následovně.

    int* create_array() {
        int array[200];
        return array; 
    }

Jakmile vrátíme hodnotu, tak dojde k vymazání stack frame funkce create_array a vrácený ukazatel bude ukazovat na místo v paměti o které nevíme co obsahuje. Dalším problémem je, že nemůžeme předat velikost pole jako argument protože pole můžeme definovat pouze pomocí číslených kostant a nebo konstant definovaných pomocí #define. Abychom mohli tento problém vyřešit musíme mít možnost uložit hodnoty proměnných jinam než na zásobník. Kromě zásobníku máme možnost uložit hodnoty na tzv. haldu (angl. heap). Prozatím předpokládejme, že máme funkci alloc. Funkce alokuje množství paměti potřebné pro uložení hodnoty typu int a jako výsledek vráci ukazatel na na toto místo v paměti.

    int* alloc_value(int number) {
        int *value = alloc();
        *value = number;
        return value; 
    }
    
    int main() {
        int a = 10;
        int *p = alloc_value(33);
        
        return 0;
    } 

Takto alokovaná není smazána jakmile skončí vykonávání funkce, protože halda a zásobník jsou na sobě nezavíslé. Na obrazku jsou znázorněny stavy zásobníku a haldy v průběhu vykonávání programu.

Po vykonání funkce alloc ve funkci alloc_value je alokována buňka na adrese 79 a následně je do buňky na této adrese vložena hodnota 33. Funkce alloc_value vrátí hodnotu 79, což je adresa alokované paměti a tato hodnota je přiřazena do proměnné p ve funkci main.

Funkce pro alokaci paměti

Všechny funkce pro práci s pamětí jsou obsaženy v knihovně <stdlib.h>. Pokud chceme alokovat paměť, tak stačí zavolat funkci malloc. Funkce má jediný argument a to hodnotu typu unsigned int, která udává počet bajtů které chceme alokovat. Funkce vrací ukazatel na void.

Deklarace

    void* malloc(size_t size);
            

Příklad

    // Alokujeme paměť pro uložení 10 hodnot typu int.
    int *array = (int*) malloc(10 * sizeof(int));
    
    // Alokace může skončit chybou (např. nedostatek paměti).
    // Funkce malloc vrací NULL v případě, že se alokace nezdařila.
    
    if (array) {
        // Muzeme pracovat s alokovanou pameti
    } else {
        printf("Při alokaci nastala chyba");
        return 1;
    }
    
    // Druhý způsob alokace + test
    int *array;
    
    if ((array = (int*) malloc(10 * sizeof(int)))) {
         // Muzeme pracovat s alokovanou pameti
    } else {
        printf("Při alokaci nastala chyba");
        return 1;
    }
            

V jazyce C máme dále funkci calloc, která slouží k alokaci n prvků, kde každý prvek má szejnou velikost. Dále je pak alokovaná paměť vynulována.

Deklarace

    void* calloc(size_t num, size_t size);
            

Příklad

    int *array;
    
    if ((array = (int*) calloc(10, sizeof(int)))) {
        // Muzeme pracovat s alokovanou pameti
    } else {
        printf("Při alokaci nastala chyba");
        return 1;
    }
    
    // Výše uvedený kód je ekvivaletní s následujícím
    
    int *array;
    
    if ((array = (int*) malloc(10 * sizeof(int)))) {
        for (int i = 0; i < 10; i += 1) {
            array[i] = 0;
        } 
      
        // Muzeme pracovat s alokovanou pameti  
    } else {
        printf("Při alokaci nastala chyba");
        return 1;
    }
            

Uvolnění paměti

Uvolnění paměti je opačný proces než alokace. Obecně platí, že pokud již paměť nepotřebujeme , tak ji musíme vrátit k dalšímu použítí. K uvolnění paměti slouží funkce free.

Deklarace

    void free(void *ptr)
            

Příklad

    int *array;
    
    if ((array = (int*) calloc(10, sizeof(int)))) {
        // Muzeme pracovat s alokovanou pameti
        
        // Zde již paměť nepotřebujeme a tak ji uvolníme.
        free(array);
    
        // Funkce free uvolní paměť, ale nezmění hodnotu ukazatele a
        // proto je dobré vymazat adresu která je v něm uložená
        array = NULL;
    } else {
        printf("Při alokaci nastala chyba");
        return 1;
    }
            

Pokud bychom používali ukazatel array po zavolání funkce free , tak by došlo k práci z pamětí která už nám nepatří a vedlo by to k neočekávanému chování.

Realokace paměti

Pokud potřebujeme v průběhu programu zvětšit/zmenšit již alokovanou paměť, tak k tomu můžeme použít funkci realloc. Tato funkce uvolní již alokovanou paměť a vrací ukazatel na nově alokovanou paměť požadované velikosti. Maximální obsah původní paměti je zachován a pokud je nová velikost větší, tak paměť mimo původní může obsahovat jakékoliv hodnoty. Pokud je velikost nové paměti menší než původní, tak docházi ke ztrátě hodnot.

Deklarace

    void* realloc(void *ptr, size_t size)
            

Příklad

    int *array = malloc(10 * sizeof(int));
    
    if (!array) {
        printf("Při alokaci nastala chyba");
        return 1;
    }
    array[0] = 42;
    array[9] = 15;

    int *temporary = realloc(p, 1000000 * sizeof(int));
    
    if (temporary) {
        // Realokace se povedla
        
        array = temporary;
        printf("%d %d\n", array[0], array[9]); 
        free(array);
    } else {
        printf("Realokace pameti selhala."); 
        free(array);
        return 1;
    }
            

Další funkce pro práci s pamětí

V knihovně string.h máme k dispozici další fuknce pro práci z pamětí.

memcpy

    void* memcpy (void *destination, const void *source, size_t num);

Funkce zkopíruje obsah pamětí na kterou ukazuje ukazatel source do pamětí na kterou ukazuje ukazatel destination. V paměti source musí být dostatečné množství bytů (alespoň n) pro čtení a v destination musí být dostatečný počet bytů pro zápis. Pokud se paměti překrývají, tak chování tétu funkce není definováno. Modifikátor const u argumentu source označí tento argument jako poute pro čtení a nelze tedy měnit hodnoty paměti uložené v source. Funkci můžeme použít například pro kopírování polí.

    #define SIZE 9

    int source[] = {1,2,3,4,5,6,7,8,9};
    int destination[SIZE];
    
    memcpy(destination, source, sizeof(int) * SIZE);

memmove

    void* memmove (void *destination, const void *source, size_t num);

Funkce funguje obdobně jako memcpy, s tím rozdílem, že funkce se chová korektně i v případě, že se zdrojová i cáílová paměť překrývají. Příkladem může být posunout prvky pole o jeden index dopředu.

    #define SIZE 9

    int source[] = {1,2,3,4,5,6,7,8,9};   
     
    memmove(source ,source + 1,sizeof(int) * SIZE - 1);

memset

    void* memset (void *ptr, int value, size_t num);

Funkce slouží k nastavení všech bytů v paměti předané ukazatelem ptr na hodnotu value. Parametr num udává počet bytů které má funkce nastavit.

    #define SIZE 9

    int source[] = {1,2,3,4,5,6,7,8,9};   
    memset(source, 0, sizeof(int) * SIZE);     

Otázka k zamyšlení: Je možné položky pole typu int nastavit na hodnotu 1 pomocí funkce memset?

Struktura odkazující na jinou strukturu

Struktura může obsahovat i ukazatel na jinou strukturu. Jako příklad si ukážeme implementaci lineárního seznamu, kde prvek seznamu je reprezetován strukturou Node. Hodnota data obsahuje číselnou hodnotu typu int uloženou v daném uzlu a nex odkazuje na další prvek seznamu. Pokud se jedná o polední prvek, tak položka next obsahuje hodnotu NULL.

    typedef struct node {
        int value;
        struct node *next ; 
    } Node;

Strukturu Node NEMŮŽEME definovat následovně:

    typedef struct {
        int value;
        Node *next ; 
    } Node;

Protože ve chvíli, kdy definujeme položku next, tak nemáme ještě definovaný typ Node pomocí typedef.

Funkce pro přidání prvku do seznamu

    #include <stdio.h>
    #include <stdlib.h>

    typedef struct node {
        int value;
        struct node *next ;
    } Node;
    
    // Funkce vloží prvek na začátek seznamu
    void push(Node **list, int value) {
        Node *new_node;
        new_node = (Node*) malloc(sizeof(Node));
        new_node->value = value;
        new_node->next = *list;
        *list = new_node;
    }
    
    int main() {
        Node* list = (Node*) malloc(sizeof(Node));
        list->value = 1;
        list->next = NULL;
        
        // Funkci add předáváme ukazatel na ukazatel na list.
        push(&list, 2);
        push(&list, 3);
        
        return 0;
    }

Úkoly