Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Adresování I

Pointery

Text níže se týká uživatelských programů běžících na běžném OS.

Z pohledu programu se pamět jeví jako pole bajtů, kde indexu říkáme adresa. Je-li v paměti uložen nějaký objekt, jsou jeho jednotlivé bajty uloženy za sebou, přičemž první bajt je uložen na nejmenší adrese. Za adresu vícebajtového objektu považujeme právě adresu jeho prvního bajtu.

Díky mechanismu virtuální paměti má běžící program přístup k celému adresnímu rozsahu na dané platformě. Adresní rozsah je množina adres, se kterými jsme schopni pracovat, a je typicky dána velikostí adresy. Je-li například adresa 64bitová, jak tomu je na moderních počítačích, adresní rozsah je od 0 do 2^64 - 1.

V programu nemůžeme úplně libovolně určit, na jakých adresách jsou objekty uloženy. O tom rozhoduje operační systém. Pokus o zápis na nebo čtení z adresy, která nebyla programu operačním systémem zpřístupněna, vede k nedefinovanému chování.

Základní operací, které můžeme s pamětí dělat, je zjištění adresy na níž je uložen konkrétní objekt (např. proměnná). Děláme to pomocí unárního prefixového operátoru adresy: &.

int x = 10;
printf("%p\n", &x);  // vypiseme adresu, na ktere je promenna x

Pomocí %p vypisuje printf adresy, obvykle v hexadecimální soustavě.

Ke každému existujícímu typu z je v programu automaticky i typ adresa, na které je uložena hodnota typu z. Proměnným a často i hodnotám tohoto nového typu programátoři říkají pointer na z. Klíčovým slovem pro tento nový typ je pak z*. Adresu můžeme uložit do proměnné.

// typ 'pointer na int' zapisujeme int*
int x = 10;
int* ptr_x = &x;

Při definici pointeru se znak * ve skutečnosti váže ke jménu proměnné, to se ovšem projevuje pouze při definici více proměnných na jednom řádku. To ovšem v kurzu nepovažujeme za dobrý styl a nebudeme to dělat. Stejně tak mohou být před * bílé znaky.

Je nutné si uvědomit, že samotná proměnná ptr_x je v paměti a operátorem adresy lze zjistit na jaké adrese.

int x = 10;
int* ptr_x = &x; 
int** ptr_ptr_x = &ptr_x;

Druhou základní operací je přístup k hodnotě na dané adrese. To se dělá pomocí unárního prefixového operátoru dereference: *. Tímto způsobem můžeme hodnotu číst i na dané místo zapisovat.

int x = 10;
int* ptr_x = &x; 
printf("%i\n", *ptr_x); // vytiskne 10
*ptr_x = 20;            // zapise na adresu ptr_x hodnotu 20
printf("%i\n", x);      // vytiskne 20

Je nutné si uvědomit, že k přístupu k hodnotě na dané adrese je nutné znát typ této hodnoty. To je zajištěno typovým systémem, kdy je v typu pointeru zachycen typ hodnoty na dané adrese.

Dereferencování pointeru, které vede k přístupu na adresu paměti, která není programu přidělena, vede k nedefinovanému chování. O takovém pointeru řekneme, že je neplatný. Testovat, jestli je pointer neplatný, obecně nejde. Existuje ovšem jedna výjimka a tou je adresa 0 (jakéhokoliv typu). Ta je vždy neplatná a jako obecná pravdivostní hodnota odpovídá nepravdě. Je proto dobrým zvykem udržovat hodnoty neplatných pointerů rovny 0.

// pokud udrzujeme neplatne pointery rovny 0, nasledujici nevede k nedefinovanemu chovani
int* ptr_x = 0;

// nejaky kod, ktery mozna manipuluje s ptr_x

if (ptr_x) 
{ 
	printf("%i\n", *ptr_x);
}

Pole, pointery a pointerova aritmetika

Jméno pole je konstantní pointer s adresou prvního prvku pole.

int a[] = { 0,1,2,3,4,5 };
int* ptr_3 = a;
printf("a[0] = %i\n", *a);   // tiskne 0
*ptr_3 = 10;
printf("a[0] = %i\n", a[0]);  // tiskne 10

Pointer je konstatní, nelze tak měnit jeho hodnotu.

int b[] = { 10, 20 };
a = b;  // Chyba: a je konstantni pointer a nelze do nej priradit jinou hodnotu.

Při předání pole jako argumentu funkci toto pole degeneruje na pointer.

void fce(int array[]) 
{
	// array je typu int*
	// size je tedy sizeof(int*) / sizeof(int)
	int size = sizeof(array)/sizeof(array[0]); 
	printf("ve funkci: %i\n", size);
}

int main() 
{
	int a[] = { 0,1,2,3,4,5 };
	int size = sizeof(array) / sizeof(array[0]);
	printf("v mainu: %i\n", size);
	fce(a);
}

Kvůli degeneraci tak vlastně můžeme do funkce předat přímo pointer.

void fce(int* array)

K prvků pole přistupujeme pomocí pointerové aritmetiky. Protože pole je v paměti v souvislém bloku, lze adresu prvku na indexu i získat tak, že adresu začátku pole zvětšíme o i-krát velikost jednoho prvku pole. Tím se v paměti posuneme z prvního bajtu prvku na indexu 0 na první bajt prvku na indexu i. V programu počet bajtů, o které je nutno se posunout nemusíme počítat, aritmetické operace s pointery to udělají za nás. K pointeru lze totiž přičíst, nebo od něj odečíst, celé kladné číslo. Výsledkem přičtení čísla c k pointeru ptr je pointer, který získáme zvětšením ptr o c-krát velikost typu, na který ptr ukazuje, bajtů. Pokud by byl například ptr pointer na int, tak bychom jej zvětšili o c-krát sizeof(int). Odečítání celého čísla funguje analogicky.

int a[] = {0,1,2};
int* ptr = a;
printf("velikost int: %lu\n", sizeof(int));
for (int i = 0; i < 3; i += 1) 
{
	printf("index: %i, adresa: %p\n", i, a + i);
}

Pointerové aritmetiky v kombinaci s operátorem dereference můžeme využít pro přístup k prvkům pole. Použití [] je totiž jenom syntaktický cukr pro pointerovou aritmetiku a následnou dereferenci.

int array[] = { 1, 2, 3, 4 };
int* ptr = array + 1;    
printf("array[2] = %i\n", array[2]);      // vytiskne 3
printf("*(array+2) = %i\n", *(array+2));  // vytiskne 3
printf("ptr[1] = %i\n", ptr[1]);          // vytiskne 3

Operátor dereference má větší prioritu než sčítání, je proto nutné použít závorky. Protože je navíc operátor sčítání komutativní, je korektní i následující kuriózní přístup k prvku na indexu 2.

printf("array[2] = %i\n", 2[array]);        // vytiskne 3

Všimněme si také přístupu pomocí pointeru ptr. Ten ukazuje, že pole v C skutečně jsou adresou prvního prvku a současně každý pointer můžeme chápat jako adresu prvního prvku v poli (i když je toto pole vlastně jednoprvkové). Přístup k jednotlivým prvkům je potom realizován pomocí pointerové aritmetiky. V našem případě se můžeme na ptr dívat jako na pole, která začíná druhým prvkem array.

Pointery stejného typu můžeme od sebe odečíst, výsledkem je počet prvků daného typu, který se mezi obě adresy vejde. Je to tedy rozdíl adres (v bajtech) dělený velikostí typu (celočíselné dělení).

Pointery také můžeme mezi sebou porovnávat.

Pointery a struktury

Pointeru na strukturu lze použít k přístupu k položkám struktury s pomocí operátoru ->, alternativně lze použít dereference následované operátorem . (tečka).

typedef struct 
{
	int pol1;
	float pol2;
} My_Str;

My_Str str = {10, 13.1};
My_Str* ptr = &str;
// oba radky vytisknou totez
printf("polozka1: %i, polozka2: %f\n", ptr->pol1, ptr->pol2);
printf("polozka1: %i, polozka2: %f\n", (*ptr).pol1, (*ptr).pol2);

Operátory adresy a dereference mají menší prioritu než operátor tečky, proto jsme v příkladu museli použít závorky. V opačném případě bychom udělali dvě chyby: přistupovali bychom k položce struktury pomocí tečky a přitom ptr je pointer na strukturu; a dereferencovali bychom int a float. Naopak, při použití operátorů adresy a dereference na položky struktury závorky můžeme vynechat.

printf("adresa prvni polozky: %p\n", &str.pol1);

Struktura nemůže obsahovat položku stejného typu jako je sama. Může ovšem obsahovat položku, která je pointerem na typ, kterého je sama. Toho často využíváme při konstrukci datových struktur, například spojového seznamu.

typedef struct _node 
{
	int key;               // data v uzlu
	struct _node* next;    // pointer na další prvek v seznamu 
} Node;


Node storage[10];
for(int i = 0; i < 10; i += 1) 
{
	storage[i].key = i;
	if (i < 9) 
	{
		storage[i].next = &storage[i+1];
    }
    else 
	{
	
		// .next == 0 znamená, že uzel nemá souseda, tj. je to poslední uzel v seznamu
		// 
		storage[i].next = 0;
    }
}

//
//  teď je v seznamu 0, 1, 2, 3 ... 9 
//

//
// projdeme seznam a vytiskneme jej
//
Node *first = storage;
while(first) 
{
	printf("%i ", first->key);
	first = first->next;
}
printf("\n");

Parametry předané odkazem

Už víme, že pokud předáme funkci pole jako argument a funkce změní některé jeho prvky, zachovají se tyto změny i po skončení funkce na místě, ze kterého jsme ji volali. Děje se tak proto, že volané funkci nepředáváme jako argument pole, ale jeho adresu.

Tohoto mechanismu můžeme využít i pro jiné argumenty než pole, pokud chceme umožnit, aby funkce mohla změnit jejich hodnotu. Stačí předat adresu argumentu, místo jeho hodnoty. Toho se často používá, potřebujeme-li z funkce vrátit více než jednu hodnotu.

//
// funkce pro celočíselné dělení
// argument rem předáme odkazem; je to adresa, na kterou funkce zapíše zbytek po dělení
//
int division(int a, int b, int* rem) 
{
	*rem = a % b;
	return a / b;
}

int main() 
{
	int x = 0;
	int y = 0;
	x = division(10, 3, &y);
	printf("vysledek %i, zbytek %i\n", x, y); 
}

Úkoly

  1. Naprogramujte vlastní verze knihovních funkcí strlen a strcmp (string.h), které nepoužijí indexů, ale pouze pointerové aritmetiky a dereference.

  2. Vytvořte strukturu s několika položkami a aspoň jednu její proměnnou. Vypište informace o layoutu této proměnné: pro každou položku vypište její adresu a velikost. Vypište i adresu a velikost samotné proměnné.

  3. Naprogramujte funkci pro výpočet průměru a mediánu pole čísel (např. int). Jednu z hodnot vraťte pomocí argumentu předaného odkazem. (Funkce může změnit pořadí prvků v poli.)

  4. Napište funkci swap_int, která prohodí hodnoty dvou proměnných typu int.

  5. Napište funkci, která v poli řetězců najde znak, který se vyskytuje v nejvíce řetězcích v tomto poli.

Adresování II

Beztypový pointer, přetypování

V jazyce C existuje pointer bez informace o typu hodnoty, na kterou pointer ukazuje. To je užitečné například v situaci, kdy pracujeme čistě s pamětí (a nepotřebujeme znát typ hodnot tam uložených). Například při kopírování, porovnávání apod. Typ takového pointeru je void*, programátoři mu říkají void pointer.

Void pointer lze implicitně přetypovat na pointer jakéhokoliv typu, a pointer jakéhokoliv typu lze implicitně přetypovat na void pointer. Přetypování mezi ostatními typy pointerů je nutno provádět explicitně (jinak překladač vypíše warning nebo chybu).

Příkladem jednoduché funkce pracující s pamětí je tisk jejího obsahu na obrazovku. Jako argumenty funkce postačuje adresa začátku paměti a její velikost v bajtech.

void dump_mem(void *mem, size_t size);

Pamět budeme tisknout po bajtech do tabulky, která bude mít na každém řádku 8 bajtů. Jeden bajt vytiskneme jako dvouciferné hexadecimální číslo (zamyslete se proč je to vhodné). Ve funkci využijeme toho, že typ unsigned char má vždy velikost jeden bajt. Na začátku funkce (implicitně) přetypujeme pointer mem na pointer na unsigned char a můžeme se na pamět dívat jako na pole bajtů. Poté stačí toto pole projít a vytisknout.

void dump_mem(void *mem, int size) 
{
	unsigned char *bytes = mem; // tady pretypujeme
	for (size_t i = 0; i < size; i += 1) 
	{
		if (i && !(i % 8)) 
		{
			printf("\n"); 
		}
		printf("%.2X ", bytes[i]); 
  }
  printf("\n");
}

Chceme-li funkci použít, musíme získat její argumenty: získat adresu začátku paměti a její velikost.

int x = 300;
dump_mem(&x, sizeof(x));  // tady dochazi k implicitnimu pretypovani int* na void*

float f = 2.4;
dump_mem(&f, sizeof(f));

struct { char c; int a; } s = {'x', 55 };
dump_mem(&s, sizeof(s));

char a[] = "ahoj svete";
dump_mem(a, strlen(a) + 1);

double b[5] = { 1.1, 2.2, 3.3, 0, 4.4 }
dump_mem(b, sizeof(b));

Přetypování z void* na unsigned char* je vždy bezpečné. Jinde může dojít k nedefinovanému chování. Prvním důvodem jsou tzv. trap reprezentace. Mohou existovat typy, kde ne každý obsah paměti odpovídá platné hodnotě daného typu. Takový obsah paměti, který neodpovídá platné hodnotě je past: pokus o dereferenci vede k nedefinovanénu chování. Podle standardu je jediný typ, který zaručeně nemá trap reprezentaci, právě unsigned char. Ostatní typy trap reprezentaci mít mohou, ale nemusí. Dalším problémem může být tzv. zarovnání (anglicky alignment): na některých architekturách je vyžadováno, aby vícebajtové objekty začínaly na adrese s určitou vlastností, například na adrese dělitelné velikostí objektu. Dereference nezarovnané adresy vede k nedefinovanému chování.

Pro explicitní konverze mezi pointery jiných typů existují ve standardu pravidla (strict aliasing rules), která svým rozsahem do kurzu nepatří. Doporučuji se prozatím takovým konverzím vyhýbat.

Některé funkce ze standardní knihovny

Pro manipulaci s pamětí lze využít některé funkce ze string.h. Jsou to zejména:

  • void* memcpy(void* dest, void* src, size_t count)

    Zkopíruje count bajtů z adresy src na adresu dest. Oblasti paměti odkud a kam se kopíruje se nesmí překrývat.

  • void* memmove(void* dest, void* src, size_t count)

    Zkopíruje count bajtů z adresy src na adresu dest. Oblasti paměti odkud a kam se kopíruje se mohou překrývat.

  • void* memset(void* dest, int ch, size_t count)

    Zkopíruje hodnotu (unsigned char)ch do count bajtů paměti začínajících adresou dest.

  • int memcmp(void* lhs, void* rhs, size_t count)

    Lexikograficky porovná prvních count bajtů paměti na adresách lhs a rhs. Vrací znaménko rozdílu mezi hodnotami prvních dvou bajtů na kterých se lhs a rhs liší. Pokud takové bajty neexistují, vrací 0.

Další podrobnosti o zmíněných funkcích si čtenář nastuduje z referenční příručky. Důležité je podívat zejména okrajové chování (např. když je některý argument 0).

Úkoly

  1. Upravte funkci dump_mem tak, aby na začátku každého řádku vypsala adresu prvního bajtu na tomto řádku. Přidejte možnost vypisovat bajty jako posloupnost 8 bitů (je nutné využít bitových operátorů).

  2. Naprogramujte vlastní verze funkcí memcpy, memcmp, memset. Funkce mohou být implementovány naivně.

  3. Najděte způsob, jak bez použití sizeof programově zjistit velikost nějakého typu, například float.

  4. Napište funkci pro detekci endianity a pro převod mezi big endian a small endian (například pro typ unsigned int, nebo obecnou funkci). Wiki o endianitě.

První bonusový úkol

Odevzdání

Úkol odevzdejte mailem (adresu najdete na webu katedry), s předmětem ZP2 - Bonusový úkol 1, jako přílohu soubor se zdrojovým kódem (a nic dalšího). Odevzdávejte nejpozději 2. 3. ve 23:59.

Body

Za úkol lze získat 4 body.

Zadání

Uvažujme následující strukturu pro řetězec. Položka data není zakončená 0, místo toho si pamatuje svoji délku v položce len.

typedef struct 
{
	char*  data;
	size_t len;
} String;

Prázdný řetězec má obě položky nastaveny na 0.

Řětězce budeme vytvářet pomocí funkce (není nutno se zabývat jejím tělem, funkci stačí skopírovat do zdrojáku).

String clone_from_cstring(char *cstring) 
{
	String ret = {0};
	ret.len  = strlen(cstring);
	if (ret.len == 0) 
	{
		ret.data = 0;
	}
	else 
	{
		ret.data = malloc(ret.len);
		assert(ret.data);
		memcpy(ret.data, cstring, ret.len);
	}
	return ret;
}

Naprogramujte následující funkce

void print_string(String str);

Funkce vytiskne řetězec str.

String get_prefix(String str, char delimiter, String* remainder);

Funkce vrátí prefix řetězce str až do prvního výskytu znaku delimiter. Ten ovšem do výsledku nepatří. Do argumentu remainder zapíše zbytek řetězce, s tím že delimiter na začátku vynechá.

//
// Příklad použítí funkce get_prefix
//
String a = clone_from_cstring("xx-yy");
String b = clone_from_cstring("xx--zz");
String c = clone_from_cstring("-xxxx");
String d = clone_from_cstring("xxx");
String e = clone_from_cstring("");

String rem;
String res;

//
// následující vytiskne "xx" a "yy" 
//
res = get_prefix(a, '-', &rem);
print_string(res);
print_string(rem);

//
// následující vytiskne "xx" a "-zz" 
//
res = get_prefix(b, '-', &rem);
print_string(res);
print_string(rem);

//
// následující vytiskne "" a "xxxx" 
//
res = get_prefix(c, '-', &rem);
print_string(res);
print_string(rem);

//
// následující vytiskne "xxx" a "" 
//
res = get_prefix(d, '-', &rem);
print_string(res);
print_string(rem);

//
// následující vytiskne "" a "" 
//
res = get_prefix(e, '-', &rem);
print_string(res);
print_string(rem);

int string_to_long(String s, long* result);

Funkce převede číslo zapsané jako řetězec na long. Číslo může být záporné. Pokud je s prázdný, je výsledkem převodu 0. Výsledné číslo je zapsáno do argumentu result. Funkce vrací 1, pokud se povedlo číslo z řetězce převést, jinak vrací 0.

int compute_the_thing(String s, long* result);

s je text, který obsahuje na každém řádku mezerami oddělená celá čísla. Funkce vrací číslo, které dostane následovně: čísla v každém řádku sečte; výsledek dostane tak, že sečte součty sudých řádků a od toho odečte součty lichých řádků. Výsledek zapíše do result. Pokud se část řetězce nepovede převést na číslo, vrátí funkce 0, jinak vrací 1. Například, pokud je s

2 2
2 2 2
-2 3

jsou součty řádků postupně 4, 6, 1 a výsledek je -4 + 6 -1 = 1 a funkce vrátí 1.

int res = 0;
int ok  = 0;

//
//  Následující vytiskne 1, 1
//
String s = clone_from_cstring("2 2\n2 2 2\n-2 3");
ok = compute_the_thing(s, &res);
printf("%i %i\n", res, ok);


//
// Následující vytiskne -3, 0
//
res = -3;
String t = clone_from_cstring("2 2\nx y\n");
ok = compute_the_thing(t, &res);
printf("%i %i\n", res, ok);

Omezení

Je zakázáno používat funkce pro manipulaci s řetězci, které jsou ve standardní knihovně. Tj. úkol nelze řešit způsobem: nejdříve převedu String na řetězec v C, potom zavolám knihovní funkci, a nakonec výsledek převedu zpátky na String.

Životnost objektů

Pro nás význam: kdy je objekt v paměti během běhu programu? (anglicky storage duration). Když je pamět objektu přidělena, říkáme, že je pro něj alokována. Uvolnění paměti objektu někdy říkáme dealokace.

Existují tři typy životnosti, statická, automatická a manuální.

Pro objekty se statickou životností je paměť alokována při startu programu, uvolněna na konci běhu programu. O její alokaci je rozhodnuto při překladu programu. Statickou zprávu paměti mají zejména

  • objekty definované na úrovni souboru, například globální proměnné, složené literály.
  • lokální proměnné definované se storage class static,
  • řetězcové literály (globální i uvnitř funkcí).

Objekty lze inicializovat na hodnotu známou v době překladu. Bez explicitní inicializace v kódu jsou automaticky inicializovány na 0.

Storage class static se u proměnné specifikuje při definici, píše se na první místo. Proměnná si uchovává hodnotu mezi jednotlivými zavoláními funkce.

int fce() {
	static int count;  // inicializace na 0 pri startu programu
	count += 1;
	return count;      // vraci kolikrat byla zavolana
}

Řetězcové literály jsou pouze ke čtení, pokus o jejich změnu vede k nedefinovanému chování. Mohou být uloženy tak, že se překrývají a sdílejí svůj konec.

char *r = "retezcovy literal";
r[0] = 'x';  // nedefinovane chovani

Složené literály lze měnit.

typedef struct {
	float x;
	float y;
} vec2f;

// globalni promena
vec2f *ptr = &(vec2f){.x=3.2f, .y=2.1f};

// nekde uvnitr funkce
prt->x = 2.4;   // OK

Alokace a dealokace objektů s automatickou životností se děje automaticky za běhu programu. Mezi objekty s automatickou životností patří

  • lokální proměnné, které nemají storage class static,
  • lokální složené literály,
  • dočasné objekty vytvořené jako návratové hodnoty funkcí (navíc jsou pouze ke čtení)

Objekty typicky vznikají v momentě vstupu do bloku, ve kterém jsou definovány a zanikají při výstupu z tohoto bloku. Lokální proměnné nejsou automaticky inicializovány, je nutné je inicializovat explicitně. Je chyba vracet z funkce adresu objektu s automatickou životností, objekt je totiž po skončení funkce dealokován. Dereference adresy pak vede k nedefinovanému chování.

int* fce() {
  int array[] = {1,2,3};
  return array;            // chyba !!!!!
}

// nekde v kodu
int *a = fce();
a[0] = 5;    // nedefinovane chovani

K manuální správě paměti aplikační programátor většinou využije nejakou knihovnu, kde je implementován alokátor paměti (ten se stará o přidělování paměti, který ji sám získává od operačního systému, případně spravuje paměť se statickou životností). Rozhraní alokátoru ze standardní knihovny je dáno funkcemi z hlavičkového souboru stdlib.h.

  • alokační funkce malloc, calloc,
  • dealokační funkce free,
  • realokační funkce realloc.

Princip použití alokačních funkcí je následující: funkci předáme počet bajtů, které chceme alokovat. Funkce vrátí adresu prvního bajtu souvislého kusu paměti požadované velikosti. V případě, že se alokace nepovede, vrací funkce 0.

Funkci free předáme jako argument adresu, kterou někdy předtím vrátila některá alokační nebo realokační funkce, a která ukazuje na doposud neuvolněnou paměť.free tuto paměť uvolní. Pokud jí předáme 0, nedělá free nic. Pokud jí ovšem předáme jakoukoliv jinou adresu, vede to nedefinovanému chování.

Funkce realloc umožňuje změnit velikost již alokované paměti.

Podrobnosti k jednotlivým funkcím si čtenář najde v referenční příručce, řekneme si pouze příklady typického použití a častých chyb.

int m = 20;
int* array = malloc(m * sizeof(int)); // alokace pro pole int velikosti m
assert(array);  // pro ucely kurzu staci tato kontrola, 
                // obecne muze byt potreba komplikovanejsi test uspechu alokace

// pracuj s polem array

free(array);   // uvolnime pamet
array = 0;     // nastavime pointer na neplatny

Funkce realloc muze při změně velikosti alokovane paměti přesunout její obsah na jinou adresu a původní paměť uvolnit.

int realloc_size[] = {10, 12, 512, 32768, 65536, 32768};
int m = sizeof(realloc_size)/sizeof(realloc_size[0]);
int *next = 0;

for (int i = 0; i < m; i += 1) {
	int *ret = realloc(next, sizeof(int) * realloc_size[i]);
    assert(ret);
    printf("%p -> %p\n", next, ret);   // pokud dojde k presunu, vypisi se ruzne adresy
    next = ret;
}
free(next);

Mezi hlavní chyby při manuální správě paměti patří tzv. memory leak a double free. První chyba nastane tak, že v programu zapomeneme adresu alokované paměti bez toho, abychom ji uvolnili. Tím pádem už ji nikdy uvolnit nemůžeme. Program má pak tuto paměť alokovánu zbytečně. Ke druhé chybě dojde tak, že se alokovanou paměť pokusíme uvolnit dvakrát (nebo vícekrát), mimo první pokus to vede k nedefinovanému chování.

Na závěr dodejme, že po skončení programu všechnu jeho paměť uvolní operační systém.

Existují také jiné přístupy ke správě paměti, které nahrazují nebo vylepšují manuální správu, například tzv. počítání referencí nebo garbage kolektory. Ty jsou v určité formě pro jazyk C přístupné jako knihovny (např.Boehm garbage collector).

Úkoly

  1. Implementujte funkci, která vrátí nově alokovaný řetězec, jehož obsah vznikne spojením dvou řetězců předaných funkci jako argumenty.

  2. Implementuje zásobník pomocí dynamického pole.

    typedef struct 
{
	int *data;    // pole pro vlozena data
	int top;      // pocet vlozenych prvku
	int cap;	  // velikost pole data
} Stack;
  
Stack create_stack() 
{
     return (Stack){0};
}

    Doprogramujte operaci push tak, aby v momentě, kdy je zásobník zaplněn, tato operace realokovala položku data na dvojnásobnou velikost.

    Doprogramujte operaci ‘pop’ tak, aby v momentě, kdy je zásobník zaplněn z jedné čtvrtiny, zmenšila položku data na polovinu.

    První nenulovou velikost zásobníku vyberte jako malou mocninu 2, např. 16.

  3. Vytvořte strukturu struct matrix pro matici desetinných čísel (double), s položkami pro rozměry matice (počet řádků a sloupců) a data (obsah matice). O vnitřním uložení a adresování jednotlivých prvků matice rozhodněte sami.

    Naprogramujte funkce:

    // 
// Funkce nastaví v `m` položky pro rozměry matice a alokuje pamět pro  data.
//
void allocate_matrix(struct matrix *m, int rows, int cols);

//
// Funkce inicializuje obsah podle pole `array` v row-major pořadí:
// řádky matice jsou naskládány za sebe.  Můžete
// předpokládat, že `array` je dostatečně velké.
//
void initialize_matrix_from_array(struct matrix *m, double *array)

//
// Funkce dealokuje paměť a nastaví odpovídající pointery na 0.
//
void destroy_matrix(struct matrix *m);

//
// Funkce vynásobí matice (předpokládejme, že vynásobit jdou). Pro data
// výsledné matice alokuje novou paměť.
//
struct matrix multiply_matrix(struct matrix a, struct matrix b);

//
// Funkce vytiskne matici jako tabulku.
//
void print_matrix(struct matrix a);

Druhý bonusový úkol

Variadické funkce

Variadické funkce

Variadické funkce jsou funkce s proměnným počtem parametrů. Variadické funkce mají povinné argumenty, těch je v každém zavolání stejný počet, a volitelné argumenty, jejichž počet se může mezi voláními může lišit. Každá variadická funkce musí mít alespoň jeden povinný argument.

Zjištění počtu a typu volitelných argumentů uvnitř funkce se neděje automaticky, řeší se konvencí. Existují v zásadě tři přístupy.

  • Předpokládáme pevný typ volitelných argumentů, v povinném argumentu předáváme jejich počet.

    //hlavicka
double sum_of_doubles(int count, ...);  // hlavicka

// volani
sum_of_doubles(3, 1.2, 2.2, 3.3);  // vysledek je 6.6 
sum_of_doubles(2, 2.1, 3.3);       // vysledek je 5.4

  • Předpokládáme pevný typ argumentů, ale poslední nepovinný argument má speciální hodnotu, například 0.

    //hlavicka
int sum_of_ints(int first, ...);  // hlavicka

// volani
sum_of_ints(1, 2, 3, 0);  // vysledek je 6
sum_of_ints(2, 2, 0);     // vysledek je 4

  • Informaci o typech i počtu volitelných argumentů předáme pomocí povinných argumentů. Tento přístup používá například funkce printf.

K nepovinným argumentům přistupujeme pomocí maker z stdarg.h.

  • typ va_list pro udržování nezpracovaných argumentů,
  • va_start nastaví va_list na všechny volitelné argumenty,
  • va_arg vrátí hodnotu prvního argumentu ve va_list, potřebuje znát typ, první argument odstraní z va_list.
  • va_end ukončí práci s nepovinnými argumenty.

Podrobnosti v následujících příkladech.

double sum_of_doubles(int n, ...) 
{
	va_list args;
	double ret = 0;
	va_start(args, n); // tady se musi predat va_list a posledni povinny argument 
	
	for (int i = 0; i < n; i += 1) 
	{
		ret += va_arg(args, double); // tady se musi predat va_list a typ argumentu
	}
	
	va_end(args);  // ukonceni prace s argumenty
	return ret;
}

//
// nutno volat aspon dvema argumenty !!!
// jinak UB
//
int sum_of_ints(int first, ...) 
{
	va_list args;
	int ret = first;
	va_start(args, first);

	while (1) 
	{
		int val = va_arg(args, int);
		if (!val) break;
		ret += val;
	}
	
	va_end(args);
	return ret;
}

void almost_printf(char *format, ...) 
{
	va_list args;
	int index = 0;
	va_start(args, format);
	
	while(format[index]) 
	{
		switch(format[index]) 
		{
			case 'i':
				printf("%i ", va_arg(args,int));
				break;
			case 'd':
				printf("%f ", va_arg(args,double));
				break;
		}
		index += 1;
	}

	va_end(args);
}

Při předávání variadických argumentů dochází ke automatické konverzi typů: float je konvertován na double, char a short jsou konvertovány na int, jejich bezznaménkové varianty na unsigned int.

Úkoly

  1. Navhněte strukturu pro komplexní číslo a naprogramujte variadickou funkci pro výpočet sumy komplexních čísel využívají prvního přístupu k určení počtu volitelných argumentů.

  2. Napište funkci long double prumer(char* format, ...), která výpočítá aritmetický průměr ze zadaných hodnot různých datových typů. Typy předávaných hodnot jsou určeny pomocí parametru format, který může tvořit libovolná posloupnost znaků odpovídající typům následujících parametrů - i pro typ int, d pro typ double a l pro long double.

  3. Naprogramujte vlastní verzi funkce printf, která s podporou tiskových direktiv %i, %f a %z, kde poslední direktiva vede k tisku zlomku. Při řešení lze využít funkci printf.

Pointery na funkce

Pointery na funkce

S pomocí pointerů na funkce lze v omezené míře pracovat s funkcemi vyššího řádu. Pointer na funkci sebou nese i typové informace: typ návratové hodnoty a počet a typy argumentů. Zápis tohoto typu podobný jako zápis hlavičky funkce bez jmen argumentů, pouze jméno funkce nahradíme (*).

int (*)(int*, int)   // typ pointer na fci, ktera vraci int, 
	                 // jeji argumenty jsou typu int* a int.

Při definici proměnné se identifikátor píše dovnitř závorky za *.

int (*fce_ptr)(int*, int);   // definice pointeru

Předchozí syntax je trochu nešikovná, proto se často používá typedef.

typedef int (*p_fun)(int* , int); // typ se jmenuje p_fun
p_fun ptr;   // definice promenne

S pointery na funkce nelze provádět aritmetiku, ani aplikovat operátory adresy a dereference (resp, tyto operátory nedělají nic). Můžeme ovšem funkci volat, syntax volání je přitom stejná jako u běžného volání funkce.

Podobně jako u polí, jméno funkce degeneruje na pointer na funkci.

typedef int (*p_fun)(int* , int);

int array_sum(int *array, int n) {
	int r = 0;
	for (int i = 0; i < n; i += 1) {
		ret += i;
	}
	return ret;
}

int array_product(int *array, int n) {
	int ret = 1;
	for (int i = 0; i < n; i += 1) {
		ret += i;
	}
	return ret;	
}

int main() {
	int a[] = { 1, 2, 3, 4, 5 };
	int n = sizeof(a)/sizeof(*a);
	
	p_fun reduce = array_sum;      // reduce ukazuje na funkci array_sum
	printf("%i\n", reduce(a, m));   // vytiskne 15, vola array_sum
	reduce = array_product;
	printf("%i\n", reduce(a, m));   // vytiskne 120, vola array_product
	return 0;
}

S pointery na funkce lze pracovat jako s jinými typy v C. Lze tvořit jejich pole, předávat je do funkcí jako argumenty, mohou být návratovými hodnotami funkcí atd.

Pointer na funkci může být neplatný, v tom případě vede pokus o volání k nedefinovanému chování. Pointeru na funkci je možné přiřadit 0 a pointery na funkce lze porovnávat.

Jedno z využití pointerů na funkce je tvorba analogie generických funkcí známých z jiných jazyků. Ideou je, že funkci naprogramujeme jednou a ona poté pracuje pro více typů. Ukážeme si to na příkladu binárního vyhledávání.

typedef int (*compare_fn)(void *, void *);  // argumenty jsou void*, aby byla funkce obecna

int compare_int(void *a, void *b) 
{ 
    int *aa = a; // tuto funkci budeme volat pouze s int*,
    int *bb = b; // muzeme bezpecne pretypovat

    if (*aa < *bb) return -1;
    if (*bb < *aa) return 1;

    return 0;
}

int compare_long(void *a, void *b) 
{
    long* aa = a;
    long* bb = b;

    if (*aa < *bb) return -1;
    if (*bb < *aa) return 1;

    return 0;
}

//
//  genericka funkce pro binarni vyhledavani
//

int binary_search(void *array,              // pole, ve kterem vyhledavame
                  void *key,                // ukazatel na hodnotu klice
                  size_t n,                 // pocet prvku pole
                  size_t element_size,      // velikost jednoho prvku v bajtech
                  compare_fn cmp)          // funkce pro porovnani dvou prvku
{
	unsigned char* bytes = array;

	int l = 0;
	int p = n-1;

	while (l <= p) {
		int s = (l + p) / 2;

	    unsigned char* s_ptr = bytes + s * element_size;  // tady adresu  prvku na indexu s
		int cmp_result = cmp(key, s_ptr);                 // zjistime vysledek porovnani

	    if (!cmp_result) {
			return s;
		}
		else if (cmp_result > 0) { // klic je vetsi
			l = s + 1;
		}
		else {
			p = s - 1;
		}
	}

	return -1;
}

//
//  pro jednotlive typy vytvorem funkce tvorici rozhrani
//
int binary_search_int(int* array, int key, size_t n) 
{
	return binary_search(array, &key, n, sizeof(int), compare_int);
}

int binary_search_long(long* array, long key, size_t n) 
{
	return binary_search(array, &key, n, sizeof(long), compare_long);
}

int main() 
{
	int array_int[20];
	long array_long[20];

	for(int i = 0; i < 20; i += 1) 
	{
		array_int[i] = i;
		array_long[i] = i;
	}

	int key_int_ok = 10;
	int key_int_fail = 30;

	long key_long_ok = 5;
	long key_long_fail = -3;

	printf("index of %i in array_int is %i\n",
		    key_int_ok,
		    binary_search_int(array_int, key_int_ok, 20));

	printf("index of %i in array_int is %i\n",
		   key_int_fail,
           binary_search_int(array_int, key_int_fail, 20));

	printf("index of %li in array_long is %i\n",
           key_long_ok,
           binary_search_long(array_long, key_long_ok, 20));

	printf("index of %li in array_long is %i\n",
           key_long_fail,
           binary_search_long(array_long, key_long_fail, 20));
		 
	return 0;
}

Úkoly

  1. Napište funkci double* map(double (*fce)(double), double* input, int len), která na hodnoty pole input aplikuje funkci fce a vrátí pole výsledných hodnot. Velikost pole input parametrem len.

  2. Napište funkci double akumulator(double (*fce)(double, double), double numbers[], int len), která zpracuje pomocí předané funkce fce hodnoty z pole numbers, jehož velikost je dána parametrem len. Můžete předpokládat, že len je vždy alespoň 2.

  3. Vytvořte funkci pro binární vyhledávání zlomků (s použitím příkladu z poznámek).

Třetí bonusový úkol

Vstup a výstup I

Proud je prostředek, kterým lze s pomocí standardní knihovny pracovat se soubory a dalšími vstupně-výstupními zařízeními (např. klávesnice, terminál). Existují i další prostředky, například systémová volání nebo jiné knihovny. Těm se ovšem věnovat nebudeme.

Funkce, o kterých budeme mluvit, mohou skončit chybou. Uvedeme si jenom, jakým způsobem poznáme, že k chybě došlo a proč k ní mohlo dojít. Zpracování chyby a to, jak se má program chovat, pokud k chybě dojde, je mimo rozsah tohoto kurzu. V příkladech budeme možnost, že k chybě dojde buď ignorovat, nebo použijeme assert.

Proudy ze standardní knihovny

Proud je objekt, do kterého lze zapisovat nebo z něj číst. Otevřením souboru jej na proud napojíme a poté zapisování do či čtení z proudu odpovídá zapisování do souboru či čtení ze souboru. Jsou definovány i další, tzv. standardní proudy. Pomocí nich můžeme zapisovat na standardní výstup (tam zapisuje např.printf), na standardní chybový výstup a číst ze standardního vstupu.

Proud je reprezentován strukturou FILE, v programu pracujeme s ukazateli na tuto strukturu. Získáme jej pomocí funkce fopen.

FILE* fopen(char* path, char* mode);

První argument je cesta k otevíranému souboru (ta je buď absolutní, nebo relativní vzhledem k umístění binárky spoušteného programu). Textový řetězec mode určuje způsob otevření souboru. Jeden ze znaků mode obvykle udává režim otevření: ten je buď textový nebo binární. Další znak pak to, co se souborem můžeme dělat: číst jej, zapisovat do něj, připojit něco na jeho konec, vytvořit jej, pokud neexistuje, nebo nějaká kombinace předchozího. Nejpoužívanější možnosti ukážeme níže.

/*
POPIS ZNAKU
'r' otevreno pro cteni
'w' otevreno pro zapis, existujici soubor je prepsan
'a' otevreno pro zapis, pokud soubor existuje, zapisujeme na jeho konec
't' otevreno v textovem rezimu 'b' otevreno v binarnim rezimu

PRIKLADY KOMBINACI
"rt" cteni v textovem rezimu
"wt" zapis v textovem rezimu 
"rb" cteni v binarnim rezimu 
"wb" zapis v binarnim rezimu
*/

Pokud se v řetězci nenachází ani jeden ze znaků tb, otevře se proud v textovém režimu.

Pokud otevření souboru selže, vrátí fopen 0. Tuto situaci je potřeba ošetřit, pro účely kurzu se spokojíme s assercí. (Pro zjištění důvodu lze někdy použít kombinaci errno a strerror.)

FILE *st = fopen("path/to/file", "t");
assert(st);

Nepoužívaný proud se zavírá funkcí fclose.

V textovém režimu čteme a zapisujeme znaky, v binárním režimu bajty. Ačkoliv se zdá, že je to totéž, rozdíl je například u konce řádku ve Windows, který končí dvojící bajtů '\r' '\n'.

Ze streamu se čte a zapisuje se do něj pomocí funkcí z stdio.h. Stream si udržuje místo, ze kterého se bude číst při příštím zavolání funkce pro čtení. Po přečtení nějakého úseku (např. znaku, řádku apod.) posune toto místo na první bajt nepřečteného obsahu.

Pokud se knihovní funkci pro čtení ze streamu čtení nepovede, programátor to pozná z návratové hodnoty, případně může zkontrolovat příznaky streamu pro konec souboru a pro chybu. To se dělá funkcemi

int feof(FILE* stream); // vraci true, pokud jsme na konci souboru
int ferror(FILE* stream); // vraci true, pokud došlo k chybě

Analogické úvahy platí i pro zápis.

Textový režim

Základní funkce pro čtení je

int getc(FILE *stream);

Přečte ze streamu jeden znak, který získáme přetypováním návratové hodnoty na char. Při neúspěšném čtení vrací konstantu EOF.

Větší část textu lze načíst pomocí funkce fgets (tu si čtenář dostuduje z referenční příručky).

Základními funkcemi pro zápis jsou

int fputc(int ch, FILE* stream);
int fputs(char *s, FILE* stream);
int fprintf(FILE* stream, char* format, ...),

Funkce fputc zapíše do streamu znak, který dostane přetypováním ch na unsigned int. Funkce fputs zapíše do streamu řetězec. V případě neúspěchu obě funkce vracejí EOF a nastaví streamu flag ferror.

Funkce fprintf funguje jako printf pouze tiskne do streamu. Při chybě vrací zápornou hodnotu, jinak počet vytistěných znaků.

Zápis do streamu je bufferovaný, zapsané změny se v napojeném souboru (či zařízení) mohou projevit později. Chceme-li si jejich okamžité projevení, můžeme k tomu použít funkci

int fflush(FILE* stream);

V případě neúspěchu vrací EOF. Tato funkce je volána (či je prováděn kód jí velmi podobný) i při zavření streamu, proto fclose také může neuspět a vrátit EOF.

Existují tři standardní proudy, přistupné jsou pomocí proměnných stdin, stdout, stderr.

Jako příklad si uvedeme funkci, která načte obsah souboru na disku a vytiskne jej na standardní výstup.

void print_file(char *filename) 
{
	FILE *in = fopen(filename, "rt");
	assert(in);

	int z = 0;
	while (1) 
	{
		z = getc(in);

	    if (z == EOF)    // konec souboru nebo chyba cteni
		{ 
			if (ferror(in)) 
			{ 
				fprintf(stderr, "chyba cteni\n");
				assert(0);
			}
			break;
		}
		fputc(z, stdout);
	}
	fclose(in);
}

Úkoly

  1. Napište program, který spočítá počet znaků, řádků a slov v textovém souboru. (Analogie textové utility wc).

  2. Napište funkci, která z proudu načte jeden řádek, když předem neznáme délky řádků. Zajistěte, aby šla funkce používat opakovaně. (Musíte vymyslet vhodné argumenty, jejich předání a vypořádat se s alokacemi).

  3. Nastudujte v referenční příručce a vyzkoušejte funkci fgets.

  4. Napište program, který načte textový soubor a do jiného souboru uloží kopii jeho obsahu tak, že jeden řádek bude mít maximálně 80 znaků. Přitom nerozdělí žádná slova kratší než 80 znaků a minimalizuje počet řádků.

Vstup a výstup II

Binární režim

Čteme a zapisujeme bajty, které při čtení nejsou nijak interpretovány.

Funkce pro čtení

size_t fread(void *dest, size_t element_size, size_t count, FILE *in)

Čteme count prvků, každý o velikost element_size bajtů, ze streamu in, ukládáme je do pole na adrese dest. Vrací počet přečtených prvků, pokud bylo čtení bez chyby, pak se count a návratová hodnota rovnají. Je nutné myslet na to, že na adrese dest musí být naalokováno dostatek paměti, jinak dojde k nedefinovanému chování.

Funkce pro zápis

size_t fwrite(void *src, size_t element_size, size_t count, FILE *out)

do streamu out zapise count položek, každy o velikosti element_size uložených za sebou na adrese src. Funkce vrací počet zapsaných položek.

Můžeme také pracovat s akturální pozicí, ze které v souboru čteme. Pozice je hodnota typu long a je to index bajtu od začátku. Aktuální pozici můžeme získat pomocí funkce

long ftell(FILE* stream)

Aktuální pozici také můžeme nastavit pomocí funkce

int fseek(FILE *stream, long offset, int start)

kde offset je počet bajtů, o které se chceme posunout a start určuje místo, ze kterého se chceme posunout. Pro tento účel jsou definovány konstanty

SEEK_SET zacatek souboru
SEEK_CUR aktualni pozice
SEEK_END konec souboru

V následujícím příkladu zapíšeme obsah pole do souboru a zase je načteme.

char *filename = "tmp.xx";

// zapis do souboru

float out_array[4] = { 1.0f, 2.0f, 3.0f, 4.0f };
	
FILE *out = fopen(filename, "wb");
assert(out);

size_t written = fwrite(out_array, sizeof(float), 4, out);
assert(written == 4);

fclose(out);
	
// cteni ze souboru, od druheho prvku
FILE *in = fopen(filename, "rb");
// posuneme se o jeden float dopredu
int fail = fseek(in, sizeof(float), SEEK_SET);
assert(!fail);

float in_array[3]= { 0.0f, 0.0f, 0.0f };
size_t read = fread(in_array, sizeof(float), 3, in);
assert(read == 3);
fclose(in);	
	
for(int i = 0; i < 3; i += 1) {
	printf("%f ", in_array[i]);
}
printf("\n");

Práce s binárními soubory a čtení binárních formátů má svá specifika, musíme si dávat pozor na velikosti typů, endianitu apod.

Úkoly

  1. Uvažme ukládání řetězců do souboru v binárním formátu.

    Naprogramujte funkci void append(char* string, char* filename), která na konec souboru přidá nový řetězec.

    Naprogramujte funkci long search(char* string, char* filename), která prohledá soubor a pokud obsahuje záznam o daném řetězci, vrátí jeho offset od začátku souboru. Jinak vrátí -1.

    V souboru odpovídá řetězci jeden záznam, záznamy jsou v souboru za sebou. Jeden záznam vypadá následovně.

    offset  velikost   vyznam
--------------------------------------------------------------------------
     0       2          velikost retezce v bajtech

     2       ?          ulozeny retezec, chapan jako posloupnost unsigned 
                        char bez 0 na konci
--------------------------------------------------------------------------

Čtvrtý bonusový úkol