6 - Dynamická alokace a textové soubory

• pro vyučující

1. Dynamická alokace: malloc a realloc.
2. Načítání vstupu ze souboru.
3. Zpracování argumentů programu.
4. Implementace funkčního a správného programu s ošetřením možných chybových stavů.

• Dynamická alokace paměti v C

• Implementujte program, který načte vstupní textový soubor, který následně vypíše v opačném pořadí řádků (varianta příkazu tac).
• 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.
  • 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é a ukážeme si v lab07.).
• Při implementaci můžete využít ladění programem valgrind.
• Před ukončením programu uvolněte alokovanou paměť.

Program dekomponujeme na následující funkce.

• Načtení řádku, např.

  char* read(FILE *fd);

  .
• Načtení řádků, např.

  char** read_lines(FILE *fd, size_t *n);

  .
• Tisk řádku a řádků, pokud nechceme například použít printf(“%s”), např.

  int print_lines(size_t n, char **lines); 

  nebo jen

  int print_lines(char **lines);

  pokud použijeme NULL-terminated pole řetězců.
• Uvolnění paměti např.

  free_lines(char ***lines);

  .

Implementační postup můžeme zvolit například následující.

1. Implementace načtení řádku znak-po-znaku s dynamickou alokací, pro zjednodušení budeme uvažovat FILE *fd = stdin;.
2. Implementace načtení řádků.
3. Vytištění výstupu.
4. Přidání zpracování argumentu programu se jménem vstupního souboru.
5. Rozlišení chyby vstupu a chyby alokace.

• Vytvoříme si funkce pro načtení textové řetězce ze souboru typu FILE* a jeho vytištění na stdout, funkce print.
• Pro začátek použijme vstupní stdin, např. jako FILE *fd = stdin;.
• Výpis řádku předpokládá, že na vstupu načteme konec řádku '\n', který je součástí textového řetězce.
• Výpis je tisk jednotlivých znaků dokud nenarazíme na znak konce řetězce '\0'.
• Naše funkce print předpokládá, že arugment je platný ukazatel na paměť zakončenou znakem '\0'. To musíme zajistit programově, korektní incializací, načtením vstupu a předáváním proměnných.

Příklad funkce print()

int print(char *line)
{
   int r = 0;
   while (line && *line != '\0' && (r = putchar(*line++)) != EOF);
   return r == EOF ? ERROR_OUT : ERROR_OK;
}

• Pro zjednodušení zatím neuvažujeme rozlišení chyby vstupu a chyby alokace paměti.
• Nicméně program ve funkci read korektně ošetřuje možné chybové stavy načtení a alokace paměti.
• V případě chyby vrací funkce read hodnotu neplatného ukazatele NULL.

Příklad volání načtení vstupu a tisk

#include <stdlib.h>
#include <stdio.h>
 
void print(char *str);
char* read(FILE *fd);
 
int main(void)
{
   int ret = EXIT_SUCCESS;
   FILE *fd = stdin;
   char *str = NULL;
   unsigned int count = 1;
   while ((str = read(fd))) {
      printf("%3d ", count++);
      print(str);
      free(str);
   }
   return ret; 
}

• Ve funkci read() použijeme dynamickou alokaci (volání malloc) a realokaci (volání realloc) s kontrolou úspěšného přidělení paměti.
• Můžeme použít různé strategie postupného zvětšování, přesto je postačující zvěšovat počáteční velikost dvakrát.
• Možná úspora je po načtení řádku realokovat paměť řetězce na velikost (+1 pro '\0') voláním realloc.

• Program zobecníme pro postupné načítání všech řádků s využitím implementované funkce read.
• Využijeme k tomu funkce read_lines a print_lines.
• Můžeme explicitně uvažovat počet načtených řádků, nebo využijeme podobného mechanismu jako null terminating string.

Příklad volání read_lines(), print_lines() a free_lines()

int print_lines(size_t n, char **str);
char** read_lines(FILE *fd, size_t *n);
void free_lines(size_t n, char ***str);
 
int main(void)
{
   int ret = EXIT_SUCCESS;
   FILE *fd = stdin;
   size_t n = 0;
   char **lines = read_lines(fd, &n);
   print_lines(n, lines);
   free_lines(n, &lines);
   return ret; 
}
 
 
void print_lines(size_t n, char **str)
{
   if (str) {
      for (size_t i = 0; i < n; ++i) {
	 print(str[i]);
      }
   }
}
 
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;
}

• Program zobecníme pro načítání vstupu ze souboru, jehož jméno je prvním argumentem programu. Pokud není argument zadán, budeme uvažovat stdin nebo ohlásíme chybu.
• Použijeme funkci fclose() pro explicitní uzavření souboru, jakmile načteme řádky ze souboru. Podobně jako volání free() v krátkých programech, učíme se programovat správně, přestože v malém, jednorázovém programu to nemusí být pragmaticky nutné, neboť soubory jsou uzavřeny po skončení programu.

Příklad zpracování argumentu programu

int main(int argc, char const *argv[]
{
   FILE *fd = stdin;
 
   if (argc > 1) {
      fd = fopen(argv[1], "r");
   }
   if (!fd) {
      fprintf(stderr, "ERROR: Cannot open input file\n");
      fprintf(stderr, "Usage is %s [filename]\n", argv[0]);
      fprintf(stderr, "If filename is not given, stdin is used\n");
      return ERROR_IN;
   }
 
   size_t m = 0;
   char **lines = read_lines(fd, &m);
 
   ...
 
   if (argc > 1) {
      fclose(fd); //close input if it is not the stdin
   }
   ...

• Upravíme program pro ošetření chybových stavů. (Řešení je několik, můžete realizovat různě.)
• Jednou z možností je přidat do funkcí načítání a výpisu ukazatel na proměnnou error. (podobně funguje errno ve std. knihovně C).
• Přidáme výčtový typ, kde zavedeme též vlastní ERROR_OK jako EXIT_SUCCESS, abychom unifikovali identifikátory.

Příklad chybových kódu programu

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

• Hlavičky funkcí načítání upravíme přidáním ukazatele na error. Při chybě vrací NULL, kterým nerozlišíme důvod chyby.

Defince prototypů funkcí

char* read(FILE *fd, int *error);
char** read_lines(FILE *fd, size_t *n, int *error);

• Výstup realizujeme vlastní funkcí print() a přidáme návratovou hodnotu.

Příklad hlavičky funkcí print a read

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

• Opakování cyklu výpisu řádku podmíníme úspěšným výpisem, např.

Příklad funkce print_lines

int print(char *line)
{
   int r = 0;
   while (line && *line != '\0' && (r = putchar(*line++)) != EOF);
   return r == EOF ? ERROR_OUT : ERROR_OK;
}
 
int print_lines(size_t n, char **lines)
{
   int ret = ERROR_OK;
   // Since i is of the size_t type, we might have to avoid "underflow" to negative values. Note that over/underflow of unsigned integers is defined in C/C++; however, for educative purposes, think about it! 
   for (size_t i = n; ret == ERROR_OK && lines && i > 0; --i) { 
      ret = print(lines[i-1]);
   }
   return ret;
}

• Podobně výpis jednoho řádku

Jiný příklad tisku jednoho řádku

int print(char *str)
{
   int ret = ERROR_OK;
   size_t i = 0;
   while (str && str[i] != '\0') {
      if (putchar(str[i++]) == EOF) {
         ret = ERROR_OUT;
         break;
      }
   }
   return ret;
}

• Nebo kratší verzí bez break s využitím ternárního operátor.

Kratší verze ternárním operátorem ? :

int print(char *str)
{
   int ret = ERROR_OK;
   size_t i = 0;
   while (str && ret == ERROR_OK && str[i] != '\0') {
      ret = putchar(str[i++]) == EOF) ? ERROR_OUT : ret;
   }
   return ret;
}

• Podobně upravíme funkce načítání řádku read a read_lines.

• Otestování chyby dynamické alokace z důvodu nedostatečné paměti můžeme realizovat nastavením limitu process, např. limit, ulimit nebo limits, dle OS a použitého interpretu příkazů.
• Lze omezit heap paměť, ale také přímo velikost virtuální paměti přidělené processu.
• Pro otestování budeme potřebovat nějaký rozumě veliký vstupný soubor (příklad vygenerování 20MB souboru

   $ tr -dc A-Za-z'\n' < /dev/urandom | head -c 20000000 > in-long.txt 

  ). Nicméně i tak je heap paměť využívána standardní knihovnou a i 2MB mohou být málo pro incializaci knihovny libc.

limits  -v 2621440 ./main <in-long.txt; echo $?
ld-elf.so.1: /lib/libc.so.7: mmap of entire address space failed: Cannot allocate memory
1

• V případě nastavení 5 MB již program pro vstup řádově desítky MB selže a korektně vrátí návratovou hodnotu 101.

limits -v 5242880 ./main <in-long.txt; echo $?
101

• Program dále můžeme rozšířit o vypsání chybové hlášky na stderr.

int main(int argc, char const *argv[])
{
  ...
  print_error(ret);
  return ret;
}

Například

void print_error(int error)
{
   switch(error) {
      case ERROR_READ:
         fprintf(stderr, "ERROR: Reading input file\n");
         break;
      case ERROR_MEM:
         fprintf(stderr, "ERROR: Memory allocation\n");
         break;
      case ERROR_OUT:
         fprintf(stderr, "ERROR: Print the read input\n");
         break;
      case ERROR_OK:
      default:
         //nothing to do
         break;
   }
}

• V programu můžeme vypsat ladící informaci o počtu načtených řádků, např. ve funkci read_lines

  fprintf(stderr, "DEBUG: n: %lu size: %lu\n", *n, size);

• Při spuštění však zjistíme, že ani 5 MB není dost.

limits -v 5242880 ./main <in-long.txt; echo $?
101

• Proto nastavíme více, např. 12 MB.

limits -v 12582912 ./main <in-long.txt; echo $?
...
DEBUG: n: 5921 size: 8192
DEBUG: n: 5922 size: 8192
101

• Z čehož vidíme, že se nám podařilo načíst pouze 5922 řádků, což v našem případě odpovídá 742533 bytům, např. si necháme vypsat pouze prvních 5922 řádků programem head a spočítáme řádky, slova a znaky programem wc.

head -n 5922 in-long.txt |wc
  5922   95927  742533

• Alternativou, tak může být přidat do funkce read_lines ladící výpis o pokusu rozšíření paměti, např. následovně.

  char** read_lines(size_t *n, int *error)
  {
     size_t size = INIT_SIZE;
     char **lines = malloc(size * sizeof(char*)); //Assume INIT_SIZE would always be > 0
     *n = 0;
     *error = ERROR_OK; //assume everything would be fine
     if (lines) {
        char *str;
        while ((str = read(error))) { //read would return NULL and set the error
           if (*n == size) {
  	    fprintf(stderr, "DEBUG: realloc from %lu -> %lu\n", size, size * 2);
  	    char **t = realloc(lines, sizeof(char*) * size * 2);
  ...

• Následně program spustíme s 26 MB

   ulimit -v 26624 
   ./main < in-long.txt
  DEBUG: realloc from 128 -> 256
  DEBUG: realloc from 256 -> 512
  DEBUG: realloc from 512 -> 1024
  DEBUG: realloc from 1024 -> 2048
  DEBUG: realloc from 2048 -> 4096
  DEBUG: realloc from 4096 -> 8192
  DEBUG: realloc from 8192 -> 16384
  DEBUG: realloc from 16384 -> 32768
  DEBUG: realloc from 32768 -> 65536
  DEBUG: realloc from 65536 -> 131072
  zsh: segmentation fault (core dumped)  ./main < in-long.txt

• kdy se nám podaří načíst 65536 řádků, následně malloc (nebo realloc) selže ve funkci read(), podařilo se nám tak načíst pouze část vstupu.
• Program tak havaruje z důvodu alokace unsigned int a[n]; a omezené velikosti zásobníku.
• Pokud paměť zvětšíme na 32 MB, program havaruje později, např.

   ulimit -v 32768     
   ./main < in-long.txt
  DEBUG: realloc from 128 -> 256
  DEBUG: realloc from 256 -> 512
  DEBUG: realloc from 512 -> 1024
  DEBUG: realloc from 1024 -> 2048
  DEBUG: realloc from 2048 -> 4096
  DEBUG: realloc from 4096 -> 8192
  DEBUG: realloc from 8192 -> 16384
  DEBUG: realloc from 16384 -> 32768
  DEBUG: realloc from 32768 -> 65536
  DEBUG: realloc from 65536 -> 131072
  DEBUG: realloc from 131072 -> 262144
  zsh: segmentation fault (core dumped)  ./main < in-long.txt

• Ověření správného chování při chybě vstupu nebo výstupu je náročnější, o to více, že používáme stdin a stdout společně s dostatečnými zdroji. Spíše můžeme realizovat např. omezený diskový prostor při ukládání na disk nebo vzdálené síťové uložiště, což vyžaduje hlubší znalost používání OS.
• V našem případě se tak prozatím spokojíme s inspekcí kódu.

• Program rozšiřte o zpracování dvou argumentů program indikující vstupní a výstupní soubor.
• Práci se soubory můžete realizovat funkcemi fopen, fclose a náhradou getchar a putchar funkcemi pro práci s proudem getc a putc.
• Místo explicitního udržování početu řádků můžeme použít dynamicky alokované pole se “zarážkou” reprezentovanou položkou s hodnotou NULL, podobně jako je u textového řetězce null character, viz https://en.wikipedia.org/wiki/Null-terminated_string.