7 - Dynamická alokace a struktury

• pro vyučující

1. Dynamická alokace: malloc a realloc.
2. Dekompozice programu na funkce.
3. Implementace funkčního a správného programu s ošetřením možných chybových stavů.

• Dokončení příkladu z 6. cvičení - 6 - Dynamická alokace a textové soubory.
• Implementace funkce read_lines().
• Ve zbytku času nebo doma další úkoly na práci s malloc, free, realloc.

• Implementujte program, který načte vstupní textový soubor, který následně vypíše v opačném pořadí načtených řádků.
• Nejdříve implementujeme načtení řádků s dynamickou alokací. Předpokládáme, že vstup má řádky zakončeny znakem '\n'.
  • V případně chybějícího znaku \n načteme pouze jeden řádek, nebo reportujeme chybu vstupu.
• Program vhodně dekomponujeme a uvažujte tři chybové stavy.
  • 100 - Chyba načtení.
  • 101 - Chyba alokace dynamické paměti.
  • 102 - Chyba výstupu. Uvažujte, že tisk na standardní výstup může selhat.
• V lab06 jsme datovou strukturu uvažovali jako dynamicky alokované pole ukazatelů na textové řetězce reprezentující postupně načtené řádky.
• Program z předchozího cvičení rozšíříme o použítí složeného typu struct, kterým nahradíme více argumentů, jedním argumentem.
  • Budeme uvažovat možnou dynamickou alokaci proměnné složeného typu. Proto budeme předávat proměnnou typu ukazatel na naší datovou strukturu řádků.

Předpokládáme, že máme implementované funkce pro tisk a načtení jednoho řádku.

int print(char *str); //return error value
char* read(FILE *fd, int *error);

enum {
   ERROR_OK = EXIT_SUCCESS,
   ERROR_IN = 100,
   ERROR_MEM = 101,
   ERROR_OUT = 102,
};

Dále předpokládáme návrhy funkcí pro tisk a načtení řádků.

int print_lines(size_t n, char **str);
char** read_lines(FILE *fd, size_t *n, int *error);
void free_lines(size_t n, char ***str);

Příklad implementace free_lines()

void free_lines(size_t n, char ***str)
{
   if (str && *str) {
      for (int i = 0; i < n; ++i) {
         free((*str)[i]);
      }
      free(*str);
   }
   *str = NULL;
}

• Nejdříve si vyzkoušejte implementaci vytvoření permutace posloupnosti čísel 0 až n, viz man 3 rand.

1. Implementujte tři funkce init, print, permute, např.

void init(unsigned int n, unsigned int a[n]);
void print(unsigned int n, unsigned int a[n]);
void permute(unsigned int n, unsigned int a[n]);

1. Funkce použijte v např. v jednoúčelovém programu pro inicializaci pole celých čísel, jeho vytištění, permutování a znovu vytištění na stdout.

#include <stdio.h>
#include <stdlib.h>
 
#ifndef MAX_NUM
#define MAX_NUM 10
#endif
 
void init(unsigned int n, unsigned int a[n]);
void print(unsigned int n, unsigned int a[n]);
void permute(unsigned int n, unsigned int a[n]);
 
int main(void)
{
   int ret = EXIT_SUCCESS;
   const unsigned int n = MAX_NUM;
   unsigned int a[MAX_NUM];
 
   init(n, a);
   print(n, a);
   permute(n, a);
   printf("Randomized array\n");
   print(n, a);
   return 0;
}

S výstupem např.

clang -DMAX_NUM=5 perm.c -o perm && ./perm
0
1
2
3
4
Randomized array
3
0
4
2
1

• Dosud implementované funkce spojíme do výsledného programu
  1. Načte řádky.
  2. Vytvoří náhodnou permutaci Předpokládáme počet řádků je relativně malý a permutace čísel řádků se vejde na zásobník, proto použijeme VLA (pole variabilní délky).
  3. Vypíše řádky dle permutace.

int main(void)
{
   int ret = EXIT_SUCCESS;
   size_t n = 0;
   char **lines = read_lines(&n);
   unsigned int a[n]; // Počet řádku se musí vejít do paměti (zásobníku)
   init(n, a);
   permute(n, a);
   for (int i = 0; i < n; ++i) {
      print(lines[a[i]]);
   }
   free_lines(n, &lines);
   return ret; 
}

Naše výchozí implementace funkce main může vypadat například následovně.

int main(void)
{
   int ret = ERROR_OK;
   size_t n = 0;
   char **lines = read_lines(&n, &ret);
   unsigned int a[n];
   init(n, a);
   permute(n, a);
   for (int i = 0; i < n && ret == ERROR_OK; ++i) {
      ret = print(lines[a[i]]);
   }
   free_lines(n, &lines);
   return ret; 
}

Základní strategie návrhu funkce read_lines() vychází z funkce read, kde jsme postupně načítali znaky a v případě potřeby rozšiřovali paměť voláním realloc. Při načítání řádků postupujeme podobně, jen místo volání getchar() budeme volat funkci read(), která může skončit chybou, kdy vrací hodnotu NULL a indikaci chyby v proměnné error. Rámcově tak implementace funkce může vypadat následovně.

char** read_lines(size_t *n, int *error)
{
   sizet_t size = INIT_SIZE; //Počáteční velikost dynamicky alokovaného pole ukazatelů na jednotlivé řádky.
   char **lines = malloc(...);
   *n = 0;
   *error = ERROR_OK; //Předpokládáme, že vše proběhne v pořádku, případné chyby budeme indikovat přepsání hodnoty.
   if (lines) {
     char *str; // Ukazatel na načtený řádek
     while ((str = read(error))) {
        if (*n == size) {
           ... //Re-alokace paměti, nebo opuštění cyklu (případně uvolnění paměti a nastavení příznaku chyby
        }
        lines[*n] = str; //Řádek se provede pouze pokud je dostatečné místo v lines.
        *n = *n + 1;
     }
     ... /// Ukončení načítání a případně uvolnění paměti pokud nastala chyba načítání 
   } else {
     *error = ERROR_MEM; //První malloc se nezdařil. Proměnná lines je NULL.
    }
   return lines; 

V programu budeme dále uvažovat, že počet řádků může být výrazně vyšší než je velikost zásobníku pro uložení permutace celých čísel (např. v Linuxu je zásobník typicky 8 MB), proto výchozí implementaci s VLA nahradíme dynamickou alokací.

int main(void)
{
   int ret = ERROR_OK;
   size_t n = 0;
   char **lines = read_lines(&n, &ret);
   unsigned int *a = malloc(n * sizeof(unsigned int));
   if (a) {
      init(n, a);
      permute(n, a);
      for (int i = 0; i < n && ret == ERROR_OK; ++i) {
	 ret = print(lines[a[i]]);
      }
      free(a);
   } else {
      ret = ERROR_MEM;
   }
   free_lines(n, &lines);
   return ret; 
}

Program opět můžeme otestovat při definování omezené paměti.

clang -c rand.c -o rand.lnx
ulimit -v 5000
./rand.lnx <in-long.txt; echo $?
101

Při dynamické re-alokaci jsme využili relativně přímočarou strategii rozšiřování alokované paměti na dvojnásobek předchozí hodnoty. Určitě lze zvolit jinou strategii, případně nemusíme řešit, pokud jsou alokovaná pole (řádky) relativně malé. Přesto můžeme na závěr načtení řádku paměť redukovat, podobně jako pole ukazatelů na dynamicky alokované řetězce. Při návrhu funkce můžeme uvažovat, že takovou funkci použijeme jak pro řádky, tak pro pole ukazatelů. Pokusíme se proto funkci reduce() navrhnout obecně.

• Funkce bude volat funkci

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

která v případě, že požadavek na paměť size je menší než aktuálně alokovaná paměť na adrese ptr, paměť uvolní, tj. odřízne konec.

• Při volání naší funkce reduce předpokládáme, že size bude vždy menší než aktuální kapacita, což zajistíme tím, jak budeme funkci v programu používat.
• Zároveň budeme předpokládat, že takový realloc se vždy povede, pokud ne, tak je to chyba, na kterou nebudeme v programu reagovat a program ukončíme voláním exit(). Předtím však vypíšeme na stderr chybovou hlášku, aby případný uživatel věděl, co se stalo.
• Podobně budeme reagovat, pokud by chtěl uživatel redukovat velikost na nulu, což je vlastně volání free, neboť i to realloc umí, viz man realloc.
• Naše funkce, tak potřebuje jen adresu paměti a požadovanou velikost.
• Nicméně i při redukci může dojít ke změně bloku paměti, např. z důvodu efektivního využít velkých souvislých bloků paměti. Proto bude naše funkce vracet adresu na blok paměti jako hodnotu typu void*.
• V předchozím kódu jsme používali proměnnou capacity, kterou jsme však dále nepoužívali. Proto naše funkce nebude kapacitu měnit.
• Hlavička funkce tak může vypadat například následovně.

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

• V implementaci budeme testovat očekávaný vstup a případně vypíšeme chybu “ERROR: Calling reduce() failed!”.

void* reduce(size_t size, void *ptr)
{
   void *ret = NULL;
   if (size > 0 && ptr) { //
      ret = realloc(ptr, size);
   }
   if (!ret) {
      fprintf(stderr, "ERROR: Calling reduce() failed!\n");
      exit(ERROR_MEM);
   }
   return ret; // Because of if (!t), it always return non-NULL.
}

1. Určete výsledek a ověřte programem:

int *up, **uup, array[] = {5, -6, 0, 8, -9, 3, 1, -4};
 
up = array;
uup = &up;
 
printf("array[1] = %d \n", array[1]);
printf("array[1] + 4 = %d \n", array[1] + 4);
printf("(array + 1)[2] = %d \n", (array + 1)[2]);
 
printf("*up = %d \n", *up);
printf("*up + 4 = %d \n", *up + 4);
printf("*(up + 1) = %d \n", *(up + 1));
 
printf("**uup = %2d \n", **uup);
printf("*(*uup + 2) = %2d \n", *(*uup + 2));
printf("**uup + 4 = %2d \n", **uup + 4);

• 2D pole a příprava na násobení matic nebo ukazatelová (pointerová) aritmetika.

• Dynamická alokace paměti v C
• Smerodatna odchylka

1. Napište funkci, která formátovaně vypíše obecné pole reálných čísel.
2. Napište funkci, která vypočte směrodatnou odchylku z prvků zadaného pole.
3. Napište funkci, která zajistí načtení n prvků z klávesnice do pole a toto pole předá do volající funkce. Počet prvků bude zadán jako parametr funkce.
4. Společně s cvičícím si předveďte použití Valgrindu pro diagnostiku přístupů do paměti a správné alokace.
5. Aplikujte funkce pro výpis a výpočet směrodatné odchylky na pole získané načítací funkcí. Nezapomeňte na dealokaci pole při ukončení programu!
6. Upravte předchozí funkci tak, aby byla schopna načíst libovolnou posloupnost reálných čísel do pole ukončenou vhodnou zarážkou nebo lépe pomocí EOF, umí-li to vaše konzole.
7. Upravte předchozí kód tak, aby bylo možné načíst od uživatele více datových řad a pro každou zvlášť spočítat směrodatnou odchylku. Jednoduše to zařídíte tak, že vytvoříte dvourozměrné pole, které ale může mít různé délky řádků. Nezapomeňte zajistit i dealoakaci celého pole!
8. Vždy kontrolujte program na přístup do paměti a alokaci nástrojem valgrind.