Dynamická alokace paměti

V této kapitole se již nebudete učit nové konstrukce jazyka C, ale ukáži vám některé funkce ze standardní knihovny. Konkrétně funkce pro získávání dynamické paměti.

Každý program lze v zásadě rozdělit na dvě části. Na část datovou, kde jsou uloženy data, se kterými program pracuje (tj. proměnné, textové literály, konstanty) a na část programovou, která obsahuje instrukce programu.
Ihned po spuštění programu jsou data která ukládáte do proměnných uložena v paměti počítače. Z této paměti lze data číst a lze do ní i zapisovat.

Takto získaná paměť má své pro i proti. Výhodou je v zásadě rychlost a zaručená dostupnost paměti. Ovšem jsou situace, kdy dopředu nemůžete vědět, kolik budete paměti potřebovat. Například budete chtít program, který načte od uživatele několik čísel a pak je setřídí od nejmenšího do největšího. Jelikož dopředu nevíte, kolik čísel bude uživatel chtít setřídit, můžete to jenom odhadnout a vytvořit si pro tyto čísla pole dlouhé např. 1000 položek typu float. To už je velké pole, které zvětší velikost programu a zpomalí jeho chod, přičemž se může stát, že uživatel bude využívat v průměru třeba jen 10 položek. Na druhou stranu se také může stát, že bude potřebovat 1001 položek.

Naštěstí nejste odkázáni jen na paměť představovanou proměnnými, které definujete ve zdrojovém kódu (taková místa v paměti se nazývají statická). Můžete žádat o paměť pro proměnnou (nebo celá pole proměnných) za chodu programu. A tomu se říká „dynamická alokace paměti“.

I dynamická alokace paměti má své výhody a nevýhody. Výhodou je, že program využívá právě tolik paměti, kolik potřebuje. Navíc získanou paměť můžete (měli byste) během programu uvolnit. Takže když například jednou potřebujete 10 MiB dat a podruhé 15 MiB dat, nejdříve požádáte o 10 MiB, využijete je, potom uvolníte, pak požádáte o těch potřebných 15 MiB dat … Takže i když jste potřebovali celkem 25 MiB dat, v jeden okamžik jste jich potřebovali maximálně 15.

Jistou nevýhodou je zvýšená pracnost s dynamickými strukturami (a časová režie při získávání a uvolňování paměti). Proto vždy rozvažte, zda se vyplatí (například pro ukládání řetězce čteného od uživatele) vytvářet dynamické data, nebo využít statických polí.

Získání a uvolnění paměti pomocí malloc() a free()

Nejdříve se podívejte na deklarace funkcí malloc() a free() a pak popíši jejich funkce. Obě funkce najdete v hlavičkovém souboru <stdlib.h>. Datový typ size_t, který se používá k určování velikosti získávané paměti, je definován též v <stddef.h>. Je to datový typ definovaný pomocí typedef. Je to celočíselný typ, něco jako unsigned int. Máte zaručeno, že size_t je dostatečně velký na to, aby se v něm mohla uložit velikost paměti (přesněji řečeno velikost datového typu). Proto používejte size_t a ne unsigned int, který nemusí být na všech platformách dostatečně velký.

void *malloc(size_t size);
void free(void *ptr);

Funkce malloc() má jako jediný argument počet bajtů paměti, které chcete od operačního systému získat (alokovat). Zajímavá je návratová hodnota, která je deklarována jako ukazatel void *. Asi vás už napadlo, že s dynamicky alokovanou pamětí se bude pracovat pomocí ukazatelů. Novou paměť vám totiž přidělí operační systém a funkce malloc() vrátí ukazatel na začátek paměti, která byla programu operačním systémem přidělena. Samo sebou se může stát, že již není dostatek volné paměti. V takovém případě funkce malloc() vrací hodnotu NULL.

Vrácený ukazatel je třeba přetypovat na správný datový typ, který budete chtít v alokovaném datovém poli (nebo jedné proměnné) používat.

Paměť, kterou takto získáte, je souvislá oblast dlouhá size_t bajtů s nedefinovaným obsahem. Jsou v ní tedy náhodné hodnoty bajtů. Pokud použijete funkci malloc() vícekrát, získáte několik souvislých oblastí, ale vzájemně již souvislé být nemusí a také většinou nejsou. Maximální velikost dynamicky alokované paměti je dána jednak fyzickými možnostmi vašeho počítače a také velikostí adresování paměti. U 32 bitových programů je možné adresovat až 4GB, u 16 bitových je to samozřejmě méně a u 64 bitových více.

Jak jsem již v začátku kapitoly předeslal, dynamicky alokovanou (získanou) paměť je možné operačnímu systému vrátit a tím snižovat nároky programu na paměť. To se provádí funkcí free(). Tato funkce má jako argument ukazatel na začátek alokované paměti (tedy hodnotu, kterou vrací funkce malloc(), nebo calloc(), nebo realloc(), viz níže). Pokud funkci free() v programu nepoužijete, je alokovaná paměť vrácena operačnímu systému až po skončení programu. Přesto byste měli funkci free() v programu vždy volat, a to co nejdříve to jde.

Pokud program neuvolňuje nepotřebnou paměť, dochází k takzvanému „úniku paměti“ (memory leaks). Déle běžící aplikace si tak říká o stále více a více paměti, až nakonec spotřebuje všechnu, která je dostupná. Takovými problémy často trpěla například Mozilla Firefox (ale i mnoho jiných profesionálních aplikací).

Po volání funkce free() již paměť není přidělena programu a pokus o zápis do této paměti (nebo čtení z ní) by byl po zásluze potrestán sejmutím programu nebo dokonce operačního systému (pokud je tak hloupý a nechá si to líbit).

Následující zdrojový kód ukazuje použití funkcí malloc() a free(). Jde o program, který načte od uživatele číslo určující počet následně zadaných čísel, které se poté setřídí. Všimněte si, jak je v programu pomocí NULL kontrolováno, zda byla dynamická paměť skutečně alokována, jak je přetypována návratová hodnota a jak se určuje velikost získávaného datového pole.

  1. *------------------------------------------------*/
  2. /* c18/dynamic1.c                                 */
  3. #define _CRT_SECURE_NO_WARNINGS
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <stddef.h>
  7.  
  8. #ifdef _MSC_VER
  9.        #define ZU  "Iu"
  10.        #define SZU "lu"
  11. #else
  12.        #define ZU  "zu"
  13.        #define SZU "zu"
  14. #endif
  15.  
  16. /**
  17. * funkce pro setrideni pole od nejmensiho do nejvetsiho
  18. */
  19. void setrid(size_t delka, float pole[])
  20. {
  21.     size_t i, j;
  22.     float pom;
  23.     if (delka <= 1)
  24.         return;
  25.  
  26.     for (j = 0; j < delka - 1; j++) {
  27.         i = 0;
  28.         do {
  29.             if (pole[i] > pole[i + 1]) {
  30.                 pom = pole[i];
  31.                 pole[i] = pole[i + 1];
  32.                 pole[i + 1] = pom;
  33.             }
  34.             i++;
  35.         } while (i < delka - 1);
  36.     }
  37. }
  38.  
  39. int main(void)
  40. {
  41.     unsigned int i;
  42.    /*
  43.    ukazatel na dynamicky alokovane cislo, ktere bude urcovat
  44.    delku pole pro tridene cisla. V tomto pripade by bylo
  45.    lepsi pouzit statickou promennou (size_t i);
  46.    je to tu tak udelano jen pro nazorny priklad */
  47.     size_t *ui;
  48.    /* ukazatel na dynamicky alokovane pole, do ktereho budou
  49.       ulozeny tridene cisla */
  50.     float *uf;
  51.  
  52.  
  53.     ui = (size_t *) malloc(sizeof(size_t));
  54.     if (ui == NULL) { /* jeden mozny zpusob kontroly */
  55.         printf("Nedostatek pameti!\n");
  56.         return 0;
  57.     }
  58.  
  59.     printf("Zadejte pocet cisel: ");
  60.     /* u funkce scanf by se melo kontrolovat, zda skutecne
  61.        nacetla to, co mela. Pro strucnost prikladu to nedelam */
  62.     scanf("%" SZU, ui);
  63.  
  64.     /* pozadam o tolik bytu, kolik ma
  65.        typ float krat pocet prvku pole */
  66.     if ((uf = (float *) malloc(sizeof(float) * (*ui))) == NULL)
  67.         /* taky zpusob kontroly :-) */
  68.     {
  69.         printf("Nedostatek pameti!\n");
  70.         return 0;
  71.     }
  72.  
  73.     for (i = 0; i < *ui; i++) {
  74.         printf("Zadejte cislo [%2" ZU "]: ", i + 1);
  75.         scanf("%f", uf + i); /* nebo uf[i] */
  76.     }
  77.  
  78.     setrid(*ui, uf);
  79.  
  80.     for (i = 0; i < *ui; i++) {
  81.         printf("%5.2f ", uf[i]); /* nebo uf + i */
  82.     }
  83.     printf("\n");
  84.     free(ui);
  85.     free(uf);
  86.     return 0;
  87. }
  88.  
  89. /*------------------------------------------------*/
Visual Studio

Makro _CRT_SECURE_NO_WARNINGS je tu kvůli funkci scanf(), viz scanf().

Popis definic ZU a SZU viz datový typ pro ukazatel.

Výstup z programu:

Zadejte pocet cisel: 5
Zadejte cislo [ 1]: 4
Zadejte cislo [ 2]: -3.5
Zadejte cislo [ 3]: 3.8
Zadejte cislo [ 4]: 2
Zadejte cislo [ 5]: 0.5
-3.50  0.50  2.00  3.80  4.00

V druhém příkladě uvidíte, jak lze dynamicky vytvořit dvourozměrné pole. Jeho velikost bude 100*200*sizeof(int) bajtů. Především si všimněte, jak je paměť uvolňována.

  1. /*------------------------------------------------*/
  2. /* c18/dynamic2.c                                 */
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <stddef.h>
  7.  
  8. #ifdef _MSC_VER
  9.        #define ZU  "Iu"
  10. #else
  11.        #define ZU  "zu"
  12. #endif
  13.  
  14. #define X  100                  /* pocet radku */
  15. #define Xv1 10                  /* vypis radek Xv1 az Xv2 */
  16. #define Xv2 20
  17.  
  18. #define Y  200                  /* sloupce */
  19. #define Yv1 50                  /* vypis sloupcu Yv1 az Yv2 */
  20. #define Yv2 60
  21.  
  22. int main(void)
  23. {
  24.     unsigned int **ui;
  25.     size_t a, b;
  26.  
  27.     ui = (unsigned int **) malloc(X * (sizeof(unsigned int *)));
  28.     if (ui == NULL)
  29.         return 1;
  30.  
  31.     for (a = 0; a < X; a++) {
  32.         ui[a] = (unsigned int *) malloc(Y * (sizeof(unsigned int)));
  33.         if (ui[a] == NULL)
  34.             return 1;
  35.     }
  36.  
  37.     for (a = 0; a < X; a++)
  38.         for (b = 0; b < Y; b++)
  39.             ui[a][b] = (unsigned int) a * b;
  40.  
  41.     printf("     ");
  42.     for (b = Yv1; b <= Yv2; b++)
  43.         printf("%5" ZU " ", b);
  44.  
  45.     printf("\n");
  46.     for (a = Xv1; a <= Xv2; a++) {
  47.         printf("%3" ZU ": ", a);
  48.         for (b = Yv1; b <= Yv2; b++)
  49.             printf("%5i ", ui[a][b]);
  50.         printf("\n");
  51.     }
  52.  
  53.     /* jak byla pamet alokovana, tak musi byt dealokovana.
  54.      * Jednoduseji to opravdu nejde. */
  55.     for (a = 0; a < X; a++) {
  56.         free(ui[a]);
  57.     }
  58.     free(ui);
  59.  
  60.     return 0;
  61. }
  62.  
  63. /*------------------------------------------------*/

Pokud bych zavolal jen free(ui);, uvolnila by se jen paměť alokovaná prvním zavoláním funkce malloc(). Navíc by se tak ztratili všechny ukazatele na paměť získávanou v cyklu na řádku 32. To by byla krásná ukázka úniku paměti.

Získání paměti pro struktury pomocí calloc()

Funkce calloc() je deklarována následovně:

void *calloc(size_t nmemb, size_t size);

Funkce calloc() alokuje paměť pro nmemb položek velikosti size. Velikost položky může být například sizeof(int). Ovšem častěji se využívá pro vytvoření dynamického pole struktur.

Tato funkce, na rozdíl od funkce malloc(), vyplní alokovanou paměť nulami. Všechno ostatní je stejné jako u funkce malloc() (návratová hodnota, uvolňování pomocí free() atd.). Musíte samozřejmě počítat s nějakou časovou režijí, kterou zabere nulování paměti.

Na příkladu ukáži, jak lze vytvářet seznam. Seznam obsahuje datové objekty (struktury), které jsou mezi sebou provázány ukazateli. První prvek seznamu ukazuje na druhý, druhý na třetí atd. V příkladě bude prvek obsahovat (kromě ukazatele na další prvek v seznamu) pole typu char, do kterého bude ukládat slova načtené od uživatele. Po skončení načítání se slova lexikograficky seřadí. Struktura bude také obsahovat číslo určující kolikáté bylo slovo načteno.

K setřídění použiji funkci strcmp(), kterou popíši v kapitole věnované standardnímu souboru <string.h>. Tato funkce porovnává lexikograficky dva řetězce a vrací nulu, pokud jsou si rovny.

  1. /*------------------------------------------------*/
  2. /* c18/dynamic3.c                                 */
  3. #define _CRT_SECURE_NO_WARNINGS
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <stddef.h>
  7. #include <string.h>
  8. #include <stdbool.h>
  9.  
  10. #define MAXSLOVO 20
  11. #define NACTISLOVO "%20s"
  12.  
  13. struct veta {
  14.     unsigned int poradi;
  15.     char slovo[MAXSLOVO + 1];
  16.     struct veta *dalsi;         /* ukazatel na dalsi strukturu */
  17. };
  18.  
  19.  
  20. /**
  21. * pomocna funkce na kopirovani retezce
  22. */
  23. void strcopyruj(char *cil, const char *zdroj)
  24. {
  25.     size_t i = 0;
  26.     do {
  27.         cil[i] = zdroj[i];
  28.     } while (zdroj[i++]);
  29. }
  30.  
  31.  
  32. /**
  33. * funkce vypisujici seznam
  34. */
  35. void vypis_veta(struct veta *zacatek)
  36. {
  37.     struct veta *dalsi;
  38.  
  39.     dalsi = zacatek;
  40.     printf("\n");
  41.     do {
  42.         if (strcmp(dalsi->slovo, "")) { /* prazdne slova ignoruj */
  43.             printf("%3i: %s\n", dalsi->poradi, dalsi->slovo);
  44.         }
  45.         dalsi = dalsi->dalsi;   /* prejdi na dalsi slovo */
  46.     }
  47.     while (dalsi != NULL);
  48. }
  49.  
  50. void setrid_seznam(struct veta *zacatek)
  51. {
  52.     bool zmena = false;
  53.     struct veta *dalsi, pom;
  54.  
  55.     dalsi = zacatek;
  56.     if (dalsi == NULL)
  57.         return;
  58.  
  59.     do {
  60.         /* dosli jsme na konec a nic se nezmenilo?
  61.            pak mame setrideno */
  62.         if ((dalsi->dalsi == NULL) && (!zmena))
  63.             break;
  64.         else if (dalsi->dalsi == NULL) {
  65.             dalsi = zacatek;
  66.             zmena = false;
  67.         }
  68.         if (strcmp(dalsi->slovo, dalsi->dalsi->slovo) > 0) {
  69.             pom = *dalsi;
  70.             strcopyruj(dalsi->slovo, dalsi->dalsi->slovo);
  71.             dalsi->poradi = dalsi->dalsi->poradi;
  72.             strcopyruj(dalsi->dalsi->slovo, pom.slovo);
  73.             dalsi->dalsi->poradi = pom.poradi;
  74.             zmena = true;
  75.         }
  76.         dalsi = dalsi->dalsi;
  77.     } while (1);
  78. }
  79.  
  80.  
  81. /**
  82.  * Funkce pro uvolneni pameti. Prvni polozka je staticka, proto se
  83.  * pomoci free() neuvolnuje a take se musi jeji atribut "dalsi"
  84.  * nastavit na NULL */
  85. void zabij(struct veta *zacatek)
  86. {
  87.     struct veta *v, *pom;
  88.  
  89.     v = zacatek->dalsi;
  90.     while (v != NULL) {
  91.         pom = v->dalsi;
  92.         free(v);
  93.         v = pom;
  94.     }
  95.     zacatek->dalsi = NULL;
  96. }
  97.  
  98. int main(void)
  99. {
  100.     unsigned int poradi;
  101.     int navrat;
  102.     struct veta prvni, *posledni;
  103.  
  104.     printf("Zadavejte slova ne delsi nez %i znaku.\n"
  105.            "Zadavani vet ukoncete pomoci znaku konec souboru.\n"
  106.            "(tj. CTRL+D v unixech nebo CTRL+Z + Enter v DOSu a Windows)\n\n",
  107.            MAXSLOVO);
  108.  
  109.     poradi = 0;
  110.     /* Struktura "prvni" je prvni prvek ze seznamu. Ukazatel
  111.        "posledni" ukazuje na posledni prvek v seznamu. */
  112.     posledni = &prvni;
  113.     do {
  114.         poradi++;
  115.         navrat = scanf(NACTISLOVO, posledni->slovo);
  116.         posledni->poradi = poradi;
  117.         if ((navrat == EOF) || (navrat != 1)) {
  118.             /* EOF * -> konec vstupu,
  119.              * navrat  !=1 -> nebyl nacten spravne retezec */
  120.             /* dalsi prvek v seznamu jiz nebude. seznam ukoncime
  121.                zarazkou NULL */
  122.             posledni->dalsi = NULL;
  123.             break;
  124.         }
  125.         posledni->dalsi = (struct veta *) calloc(1, sizeof(struct veta));
  126.         if(posledni->dalsi == NULL) {
  127.             printf("Nedostatek pameti!\n");
  128.             exit(1);
  129.         }
  130.         posledni = posledni->dalsi;
  131.     } while (1);
  132.  
  133.     setrid_seznam(&prvni);
  134.     vypis_veta(&prvni);
  135.     zabij(&prvni);
  136.  
  137.     return 0;
  138. }
  139.  
  140. /*------------------------------------------------*/

Možný výstup z programu:

Zadavejte slova ne delsi nez 20 znaku.
Zadavani vet ukoncete pomoci znaku konec souboru.
(tj. CTRL+D v unixech nebo CTRL+Z + Enter v DOSu a Windows)

Kdyz nejde hora k Moha-Medovi, musi Moha-Med k hore.

  1: Kdyz
  7: Moha-Med
  5: Moha-Medovi,
  3: hora
  9: hore.
  4: k
  8: k
  6: musi
  2: nejde

Lepším příkladem na použití calloc() by byl asi příklad s řídkou maticí (tj matice, která obsahuje spoustu nul). Tam by se ukázala výhoda inicializace paměti nulami funkcí calloc(), oproti neinicalizované paměti vrácené funkcímalloc() (paměť alokované funkcí malloc() může obsahovat všelijaké „smetí“).

Změna velikosti získané paměti pomocí realloc()

Funkce realloc() umožňuje změnit velikost dříve alokované paměti s tím, že data v již alokované paměti zůstanou nezměněna. Deklarace funkce je následující:

void *realloc(void *ptr, size_t size);

První argument funkce, ptr je adresa paměti (anglicky pointer), která byla alokována pomocí funkcí malloc(), calloc() nebo realloc(). Velikost tohoto paměťového bloku se zvětší (či zmenší) na size bajtů.

Návratovou hodnotou je ukazatel na „přealokovanou“ paměť. To ovšem nemusí být stejné místo v paměti jako původní paměť (na kterou ukazoval argument ptr)! Proto po volání funkce realloc() se již nepokoušejte přistupovat do paměti pomocí hodnoty v ukazateli ptr, ani ji uvolňovat, ale používejte jen paměť na kterou ukazuje hodnota vrácená funkcí realloc().

Pokud by byl argument ptr NULL, pak by bylo volání realloc() obdobné jako malloc(). Pokud byste velikost pole size nastavili na nulu, bylo by to stejné, jako byste volali pro ptr funkci free().

Nově alokovaná paměť má nedefinované hodnoty (není vynulována jako u calloc()). Původní části paměti, kterou jste přealokovali, bude obsahovat stejná data, jako před alokací. (Jen mohou být na jiném místě v paměti, takže pozor na používání odkazů inicializovaných před realokací).

Pokud se funkci realloc() nepodaří získat dostatek nové paměti, vrátí ukazatel NULL. Proto byste neměli v programu používat následující konstrukci:

ukazatel = realloc(ukazatel, SIZE);

Takto by se totiž do ukazatele uložila hodnota NULL a vy byste přišli o ukazatel na původní alokovanou paměť, která by zůstala alokovaná, ale už by jste se k ní neměli jak dostat.

V příkladu bude uživatel zadávat programu požadovanou velkost v MiB alokované paměti a program jí bude alokovat.

/*------------------------------------------------*/
/* c18/dynamic4.c                                */
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

#define MIB 1024*1024

int main(void)
{
    unsigned long x; size_t a;
    char *pom, *v = NULL;

    do {
        printf("Zadejte pocet megabajtu, 0 pro konec: ");
        scanf("%lu", &x);
        pom = (char *) realloc((void *) v, x * MIB);
        if ((pom == NULL) && (x))
            printf("Nedostatek pameti!!\n");
        else {
            v = pom;
            /* vyplneni pameti jednickami.
             * To pocitac trosilinku zamestna :-) */

            for (a = 0; a < x * MIB; a++) {
                v[a] = '1';
            }
        }
    } while (x);

    return 0;
}

/*------------------------------------------------*/

Pokud spustíte program v Linuxu, můžete na konzoli pomocí příkazu free sledovat, jak vám roste a klesá velikost využité paměti počítače podle toho, kolik si jí zrovna žádáte.
V DOSu a Windows 3.11 bude 1 MiB souvislé paměti příliš velký požadavek1). Pokud překládáte program tam, žádejte o paměť raději po kibibytech :-).


1) LOL, to už je ale starej tutoriál :D. Ale pořád aktuální ;-).

Komentář Hlášení chyby
Created: 29.8.2003
Last updated: 21.6.2014
Tato stánka používá ke svému běhu cookies, díky kterým je možné monitorovat, co tu provádíte (ne že bych to bez cookies nezvládl). Také vás tu bude špehovat google analytics. Jestli si myslíte, že je to problém, vypněte si cookies ve vašem prohlížeči, nebo odejděte a už se nevracejte :-). Prohlížením tohoto webu souhlasíte s používáním cookies. Dozvědět se více..