Lab 07 - Dynamická alokace 2/2

• pro vyučující: 07

• Dokončení příkladu z 6. cvičení - 6 - Dynamická alokace 1/2.
• 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 náhodném pořadí řádků.
• Nejdříve si vyzkoušejte implementaci vytvoření permutace posloupnosti čísel 0 až n, viz man 3 rand.
• Následně implementujte načtení řádků s dynamickou alokací. Předpokládejte, že vstup má řádky zakončeny znakem '\n'.
• Program vhodně dekomponujte a uvažujte tři chybové stavy (jejich hlavní význam bude při následné úpravě programu pro přímou práci se soubory).
  • 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.
• Jako datovou strukturu uvažujte dynamicky alokované pole ukazatelů na textové řetězce reprezentující postupně načtené řádky. (Není nutné používat složený typ struct, byť to může být výhodné).
• Při implementaci můžete využít ladění programem valgrind.
• Před ukončením programu, uvolněte alokovanou paměť.

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

int print(char *str); //return error value
char* read(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(size_t *n, int *error);
void free_lines(size_t n, char ***str);

Implementace funkcí print_lines a free_lines je relativně přímočará.

int print_lines(size_t n, char **str)
{
   int ret = ERROR_OK;
   if (str) {
      for (size_t i = 0; i < n && ret == ERROR_OK; ++i) {
         ret = print(str[i]);
      }
   }
   return ret;
}

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;
}

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.
}

• 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.

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);