read_lines()
.
malloc
, free
, realloc
.
man 3 rand
.
'\n
'.
struct
, byť to může být výhodné).
valgrind
.
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);S řešením chybové návratové hodnoty
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; }
free_lines
chceme nastavovat hodnotu ukazatele alokované paměti na prokazatelně neplatnou adresu NULL
, proto předáváme ukazatel na datový typ proměnné, který je v našem případě ukazatel na ukazatel na char, proto tři hvězdičky.
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í.
unsigned int
.
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ě.
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.
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.
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.
free
, neboť i to realloc
umí, viz man realloc
.
void*
.
capacity
, kterou jsme však dále nepoužívali. Proto naše funkce nebude kapacitu měnit.
void* reduce(size_t size, void *ptr);
“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. }
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);