Základy

Tato kapitola obsahuje základní informace o programování v jazyce C. Předpokládáme, že čtenář má již nějaké zkušenosti s programováním v procedurálním jazyce. Čtenář musí zkousnout situaci, kdy narazíme na programovací konstrukt, který je vysvětlen až později.

První program

/*
	Toto je víceřádkový komentář.
	Nelze je vnořovat.	
*/

// Toto je jednořádkový komentář, platí do konce řádku 

//
// je potřeba kvůli funkci printf, přesný mechanismus je vysvětlen později
//
#include <stdio.h>

//
// definice funkce main, provedení programu odpovídá provedení funkce main
//
int main()
{
	//
	// volání funkce printf
	// argument "Ahoj svete" je řetězcový literál.
	//
	printf("Ahoj svete!!\n");
	return 0;
}

Proměnné, funkce, pole

Proměnné

Proměnnou definujeme následovně.

typ identifier;            // bez inicializace
typ identifier = init;     // s inicializací

Při definici je nutné specifikovat typ proměnné pomocí klíčového slova. Inicializace je nepovinná. Při inicializaci platí pravidla jako při provádění operátoru přiřazení. Přístup k neinicializované proměnné vede k nedefinovanému chování. Neinicializovaná proměnná totiž nějakou hodnotu má, jenom není dopředu na úrovni popisu jazyka definováno jakou.

int x;
int y = 10;

printf("%i\n", y);     // toto volání printf vypíše hodnotu proměnné y
printf("%i\n", x);     // nedefinované chování, přístup k neinicializované proměnné

Blok je část kódu uzavřená mezi { }, které si odpovídají: Bloky lze vytvářet jenom tak, aby se zanořovali, otevírací i uzavírací závorka bloku musí být uvnitř nadřazeného bloku. Takto bloky přirozeně vytváří stromovou hierarchii, jejím kořenen je úroveň samotného souboru, tj. obsah souboru mimo všechny bloky.

C je jazyk s lexikálním rozsahem platnosti proměnných. Proměnná existuje od místa své definice do konce bloku, ve kterém je definována. Pokud je v nějakém bloku použita proměnná (např. součást výrazu atd.), je hledána v aktuálním bloku a poté v blocích nadřazených. Hledání končí na úrovni souboru, pokud tam není proměnná nalezena, vyhlásí překladač chybu. Proměnné, které jsou definovány na úrovni souboru označujeme jako globální. Ve stejném bloku, mimo podbloky, nemohou být definovány dvě proměnné stejného jména.

Důsledkem mechanismu vyhledávání proměnných je jejich shadowing.

int x = 10;
{
	int x = 100;
	printf("%i\n", x);      // vytiskne 100
}
printf("%i\n", x);          // vytiskne 10

Funkce

Funkci definujeme následujícím způsobem.

type identifier (parameter_list)
{
	// body
}

První řádek je tzv. hlavička funkce, kde je postupně typ návratové hodnoty funkce, jméno funkce a v závorkách seznam argumentů funkce: čárkami oddělená posloupnost dvojic typ id, specifikujíc typ argumentů a jejich jména. Příkaz return val; ukončí vykonávání funkce a jako návratovou hodnotu vrátí hodnotu výrazu val. Pokud chceme funkci bez návratové hodnoty, napíšeme na místo typu návratové hodnoty klíčové slovo void a používáme return bez val, nebo jej nepoužijeme vůbec a funkce končí, když kód doběhne na konec těla funkce.

int sum(int a, int b)
{
	return a + b;
}

void print_numbers(int a, int b, int c)
{
	printf("%i %i %i\n", a, b, c);
}

Funkci voláme následovně.

identifier(list_of_values)

Tady je identifier jméno funkce a list_of_values je čárkami oddělený seznam výrazů. Ty se vyhodnotí a výsledky těchto vyhodnocení se přířadí argumentům funkce (hodnoty se kopírují, argumenty se předávají hodnotou). Pokud má funkce návratovou hodnotu, je výsledkem vyhodnocení volání funkce hodnota, kterou funkce vrátí.

int z = sum(1 + 4, 7);
printf("%i\n", z);        // vytiskne 12

print_numbers(z, z, 3);    // vytiskne 12 12 3

Pole

Pole je indexovaná kolekce hodnot stejného typu. Indexujeme pomocí čísel 0, 1, 2 …

Pole lze definovat následujícími způsoby.

type a[no_els]; 
type b[no_els] = init; 
type c[] = init;

Výraz type je typ prvků, a, b, c jsou jména polí, no_els je počet prvků pole: toto musí být hodnota známá v době překladu, například literál. Výraz init je inicializační výraz pro pole.

{ val_0, val_1, ..., val_n }

Výrazy val_ se vyhodnotí a výsledky vyhodnocení se po řadě přiřadí na indexy 0, 1, …. Pokud je počet výrazů menší než velikost pole, jsou zbylé hodnoty vynulovány. Další možností je

{ [0] = val_0, [3] = val_3, [5] = val_5 }

Výrazy v hranatých závorkách jsou indexy, na které se při inicializaci zapíše hodnota na pravé straně =. Prvky na indexech, které v inicializačním výrazu nejsou, jsou vynulovány.

Pokud v definici pole není uveden počet prvků, je převzat z inicializačního výrazu.

K jednotlivým prvků pole přistupujeme pomocí indexu zapsaného do hranatých závorek za jméno pole.

Pole si nenese informaci o své velikosti a jazyk nekontroluje, zda při přístupu k poli používáme korektní index. Přístup k poli pomocí neplatného indexu vede k nedefinovanému chování.

Pole lze předat jako argument funkci, obvykle je s ním nutné předat i jeho velikost.

/* n je velikost pole a */
int find_max(int a[], int n)
{
	int max = a[0];
	for (int i = 1; i < n; i += 1)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	return max;
}

Tisk

K tisku budeme používat funkci printf ze standardní knihovny. Její hlavička je

int printf(format_string, values)

Argument format_string je řetězec, který může obsahovat speciální instrukce pro tisk. Tyto instrukce jsou ve tvaru %instr, kde instr je vlastní instrukce. Každé instrukci ve format_string odpovídá ve values, seznami výrazů oddělených čárkami, jedna hodnota, která se pomocí dané instrukce vytiskne (bráno zleva doprava). Instrukce se většinou týkají toho, jaký typ hodnoty se tiskne, podrobnosti lze nalézt v manuálu ke standardní knihovně. Základní instrukce jsou v příkladu níže.

printf("hello");     // žádné speciální instrukce, vytiskne se hello
printf("%i", -2);    // instrukce %i -- tisk celého znaménkového čísla
printf("%u", 15);    // instrukce %u -- tisk celého bezznaménkového čísla

instrukce     popis
-------------------
%c            znak
%s            řetězec
%f            číslo s desetinnou čárkou

Typový systém

Jazyk C je staticky typovaný (typy se kontrolují při překladu) a slabě typovaný (děje se mnoho implicitních typových konverzí).

Skalární typy

Pro celá čísla máme char, short, int, long, long long. Tyto typy mají ještě bezznaménkovou variantu uvozenou klíčovým slovem unsigned. Pro čísla s desetinnou čárkou máme typy float, double, long double.

Standard jazyku zaručuje minimální velikosti a rozsahy hodnot jednotlivých typů. (Velikost typu lze zjistit pomocí sizeof(typ).) Dále je zaručeno

sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long)

sizeof(float) <= sizeof(double) <= sizeof(long double)

Skutečné velikosti se liší podle překladače a platformy. Například na 64 bitovém unixovém OS s překladačem gcc je

typ          sizeof(typ)
------------------------
char             1
short            2
int              4
long             8
long long        8
float            4
double           8
long double     16
------------------------

přičemž celá čísla jsou typicky uložena ve dvojkové (doplňkové) soustavě a čísla s desetinnou čárkou podle IEEE 754 standardu.

Jazyk C nemá typ pro pravdivostní hodnotu. Celočíselná hodnota 0 je nepravda, ostatní hodnoty jsou pravda.

Znaky a řetězce

Typ char je používán uložení znaků podle ASCII tabulky (která znaky kóduje pomocí čísel). Znakové literály jsou mezi apostrofy. Některé speciální znaky je nutné v literálech zapisovat pomocí backquotování, například znak nového řádku je \n.

/*
	x a y níže se rovnají
*/
char x = 'A';      // znakový literál
char y = 65;       // numerický literál

Řetězec v C je uložen v poli typu char. Přitom znaky čteme od začátku pole až po hodnotu 0. Poslední znak řetězce je tak znak na indexu o jedna menším, než na kterém je hodnota 0. Pole, ve kterém je řetězec uložen, tak musí být alespoň o jedna větší, než samotný řetězec (potřebujeme jedno místo pro hodnotu 0), může být ovšem větší. Řetězcové literály píšeme do uvozovek.

char string[] = "hellope";
/*
pole je velikosti 8
a[0] je znak 'h'
a[1] je znak 'e
...
a[6] je znak 'e'
a[7] je znak '\0' (hodnota 0)
*/

Alias typu

Alias vytvoříme typu následujím způsobem.

typedef def_expr;

Výraz def_expr je ve tvaru definice proměnné, k typu v něm vytvoříme alias tvořený identifikátorem proměnné v něm. V následujícím příkladu vytvoříme k typu int alias number.

typedef int number;

Strukturovaný datový typ

Položky různých typů lze spojit do strukturovaného typu, který vytvoříme

struct type_id 
{
	item_1;
	item_2;
	...
	item_n;
};

kde jednotlivé položky item_1 až item_n jsou zápisy ve formě type item_id, type je tu typ položky a item_id je jméno položky. Nově vytvořený typ je struct type_id. Ke kratšímu pojmenování lze použít alias, je možný i následující zápis.

struct type_id
{
	item_1;
	item_2;
	...
	item_n;
} type_id;

Tímto vytvoříme typ pojmenovaný jenom type_id. (Pokud ponecháme první výskyt type_id, vytvoříme typy struct type_id a type_id současně; první výskyt type_id jde vynechat, potom vytvoříme pouze type_id.)

Předchozí funguje protože

struct type_id 
{
	item_1;
	item_2;
	...
	item_n;
};

s případným vynecháním type_id je platným zápisem typu. Ten lze používat na místech, kde se obvykle píše jméno typu. Můžeme například vytvořit proměnné typu, který nemá jméno.

struct 
{
	item_1;
	item_2;
	...
	item_n;
} var1, var2.;

Inicializační výraz strukturovaného typu vytvoříme následovně.

{ init_1, init_2, ..., init_n }

Výrazy init_1 až init_n jsou inicializační výrazy jednotlivých položek. Pokud některé položky vynecháme, jsou vynulovány. Alternativně lze použít zápis

{ 
	.item_id_1 = init_1,
	.item_id_2 = init_2,
	...
	.item_id_n = init_n,
}

přičemž lze opět vynechat některé položky. Chceme-li vynulovat všechny položky, lze použít následující výraz.

{ 0 }

Pro přístup k jednotlivým položkám použijeme operátoru . (tečka).

var.item_id

Příklad

/*
	Příklad ukazuje použití struktury pro reprezentaci
	vektoru ve dvourozměrném euklidovkém prostoru.
	Funkce počítají skalární součin a násobení skalárem.
*/
typedef struct 
{
	float x;
	float y;
} vec2f;

float dot_product(vec2f a, vec2f b)
{
	return a.x * b.x + a.y * b.y;
}

vec2f product(vec2f a, float b)
{
	return (vec2f){b * a.x, b * a.y};	
}

int main()
{
	/* inicializace */
	vec2f u = { .x = 0.3, .y = 0.5 };
	vec2f v = { .x = 1.2, .y = 10.5 };
	
	/* zápis do položek */
	u.x += 10;
	v.y = 6;

	/* volání funkcí */
	float dp = dot_product(u, v);
	vec2f p  = product(v, 4.1);
	
	return 0;
}

Výčtový typ

Hodnotami výčtového typu je množina pojmenovaných celočíselných konstant. Typ spolu s konstantami vytvoříme následovně

enum type_id
{
	id_1,
	id_2,
	id_3,
	...
	id_n
};

Vytvoříme typ enum type_id (pro kratšího aliasu lze jako u strukturovaného typu použít typedef). Jména jednotlivých konstant jsou id_1, id_2, ..., jejich hodnoty jsou po řadě 0,1,2 .... Konstantám lze v definici typu přiřadit explicitní hodnoty.

enum type_id
{
	id_1 = value_1,
	id_2,
	id_3 = value_3,
	...
	id_n
};

Přiřazení hodnot není povinné. Pokud nemá konstanta v definici přiřazenu hodnotu, je její hodnota o jedna větší, než hodnota předchozí konstanty. Pokud nemá hodnotu přiřazenu první konstanta, je její hodnota 0.

Typické využití je pro určování druhů entit (například chyb, tokenů apod).

/*
	Následující enum lze použit pro určení typu chyby,
	která se může stát při zpracování souboru. 
*/

typedef enum
{
	FE_NONE,
	FE_NOT_FOUND,
	FE_PERMISSION_DENIED,
	FE_BAD_FORMAT,
} file_error;

/*
	První konstantou je FE_NONE pro žádnou chybu, toto je výhodný
	trik, protože FE_NONE má hodnotu 0, která je jediná nepravda,
	ostatní položky mají hodnotu indikující pravdu.
*/	

file_error err = process_file(filename);
if (err) 
{
	// tady ošetříme chybu
}

/*
	V následujícím výčtovém typu má poslední konstanta
	hodnotu, která se rovná počtu konstant. Toho lze 
	použít pro vytvoření pole, kde jednotlivá políčka
	indexujeme pomocí konstant.
*/

typedef enum
{
	TT_OPERATOR,
	TT_IDENTIFICATOR,
	TT_BRACE,
	TT_TOKEN_TYPE_COUNT,
} token_type;
	
int last_token_offsets[TT_TOKEN_TYPE_COUNT];
last_token_offsets[TT_BRACE] = 10;

Jména konstant jsou globální (pro soubor, ve kterém jsou definována), na začátek těchto jmen většinou dáváme zkratku jména typu, abychom zmenšili pravděpodobnost konfliktu jména konstanty se jménem nečeho jiného. Jména konstant jsou často kapitálkami.

Union

Definice unionu je podobná definici strukturovaného typu

union type_id
{
	item_1,
	item_2,
	...
};

Všechny položky (hodnoty) unionu jsou ovšem v paměti začínají na jednom místě a překrývají se tak (velikost unionu je pak velikostí jeho největší položky, je to úspora místa). Za platnou tak můžeme považovat pouze hodnotu jedné položky. Lze využít při potřebě šetřit pamět, spolu s výčtovým typem lze vytvořit obdobu tzv. tagged unionu.

typedef enum 
{
	RT_INT,
	RT_STRING,
	RT_FLOAT,
	
} result_type;


typedef struct
{
	result_type type;
	union 
	{
		int int_value;
		char *string;
		float float_value;
		
	} value;
} tagged;

/*
	při zpracování hodnoty typu tagged potom nejdříve zkontrolujeme
	položky type a podle ní víme, kterou položku z unionu value máme
	zpracovat.
*/

tagged x = function_that_returns_tagged();
if (x.type == RT_INT)
{
	// zpracujeme int
	process_int(x.value.int_value);
}
else if (x.type == RT_STRING)
{
	// zpracujeme string
	process_string(x.value.string);
}
else 
{
	// zpracujeme float
	process_float(x.value.float_value);
}

Operátory

Operátory (= akce, výpočet) aplikujeme na operandy (= data), a získáme tím nějaký výsledek (= data). Ve složitějších výrazech se operátory vyhodnocují v pořadí podle priority, toto pořadí lze změnit uzávorkováním. Operátory se stejnou prioritou jsou vyhodnocování podle associativity (zleva či zprava), opět to jde změnit pomocí uzávorkování.

Aritmetické operátory

Operátor je počítán z hodnot stejného typu a téhož typu je i výsledek. Pokud je v kódu operátor aplikován na hodnoty různých typů, dojde k implicitním typovým konverzím (tj. změnám typů) operandů směrem k většímu typu (anglicky jde o type promotions).

Toto se řídí následujícími pravidly (aplikovanými seshora dolů):

Je-li jeden operand neceločíselného typu.

Je-li jeden operand long double, je druhý konvertován na long double.
Je-li jeden operand double, je druhý konvertován na double.
Je-li jeden operand float, je druhý konvertován na float

Jsou-li oba operandy celočíselné.

Typy menší než int (znaménkové a bezeznaménkové verze char a short) jsou přetypovány na int, pokud int dokáže reprezentovat všechny hodnoty původního typu. Jinak jsou přetypovány na unsigned int.
Operand menšího typu je převeden na větší typ, který je schopen reprezentovat jeho hodnoty. Typy jsou uspořádány do následujícího pořadí.
```
unsigned long long > long long > unsigned long > long > unsigned int > int
```

Níže je tabulka aritmetických operátorů.

Operátor    Arita     Popis
-----------------------------------------------------------------------
 -            1       Prefixový unární operátor, mění znaménko
+,-,*,/       2       Binární operátory, klasické aritmetické operace
%             2       Binární operátor,  zbytek po celočíselném dělení

Priorita a associativita se řídí stejnými pravidly jako v matematice.

Operátor přiřazení

Slouží k přiřazení hodnoty na nějaké zapisovatelné místo. Syntax je následující.

lvalue = rvalue

Výraz lvalue musí označovat místo, kam se dá zapisovat (například proměnnou, položku struktury, prvek v poli), rvalue je výraz, který se vyhodnotí, a výsledek je zapsán do lvalue. Dochází k implicitní konverzi typu rvalue na typ lvalue. Tato konverze může být ztrátová: například dojde k zaokrouhlování, ztrátě desetinné části čísla, zachování pouze spodních bajtů celého čísla. (Některé konverze typů jsou zakázány, operátor provádí pouze konverze mezi kompatibilními typy, detaily lze nalézt ve standardu.) Výsledkem je hodnota rvalue po přiřazení.

Operátor přiřazení lze kombinovat s binárními operátory, analogicky následujícímu příkladu, kde jej kombinujeme s operátorem +.

int x = 10;
/* místo  */
x =  x + 3;
/* můžeme psát */
x += 3;

Operátory porovnání

Následující operátory porovnávají číselné typy. Výsledek je 1 pokud je porovnání pravdivé, nebo 0 jinak. Operátory jsou následující.

<, >, <=, >=, ==

Test rovnosti je tvořen dvěma rovnítky, nikoliv jedním. Jedno rovnítko je operátor přiřazení.

Logické operátory

Operátory pro konjunkci (logická spojka a), disjunkci (logická spojka nebo) a negaci.

Operátor    Popis
--------------------------------------
&&          konjunkce
||          disjunkce
!           negace, unární, prefixový
--------------------------------------

Operátory konjunkce a disjunkce jsou asociativní zleva a vyhodnocují se líně. Uveďme si to na příkladu konjunkce.

/* 
	Uvažme následující konjunkci 
*/
x && y && z && w

/* 
	Díky asociativitě zleva je to vlastně
*/
((x && y) && z) && w

/*
   Pokud je x == 1, y == 1, z == 0, w == 1, probíhá výpočet následovně:

	1. x && y  dá  výsledek 1
	2. 1 && z  dá  výsledek 0, výpočet hodnoty výrazu končí s výsledkem 0
   
    V tomto vyhodnocení líné, 0 && w už se nepočítá.	
	
	Líného vyhodnocení lze s výhodou využít, pokud je ve výrazu 

	(pred && op)
	
	výraz pred kontrolou toho, jestli můžeme výraz op bezpečně vyhodnotit.
	Pokud se totiž pred vyhodnotí na 0, výraz op už se nevyhodnocuje.
*/

Bitové operátory

Bitové operátory aplikujeme na celočíselné operandy. Umožnují pracovat s jednotlivými bity těchto operandů. Jedná se logické operátory aplikované po bitech, nebo bitové posuvy. Operátory si vysvětlíme na následujících příkladech.

Předpokládejme, že x == 100 a y == 50 jsou jednobajtová čísla (typu unsigned char). Ve dvojkové soustavě máme

x ==  0 1 1 0 0 1 0 0
y ==  0 0 1 1 0 0 1 0

Potom máme

konjunkce po bitech
x       0 1 1 0 0 1 0 0
y       0 0 1 1 0 0 1 0
-----------------------
x & y   0 0 1 0 0 0 0 0


disjunkce po bitech 
x       0 1 1 0 0 1 0 0
y       0 0 1 1 0 0 1 0
-----------------------
x | y   0 1 1 1 0 1 1 0

nonekvivalence po bitech
x       0 1 1 0 0 1 0 0
y       0 0 1 1 0 0 1 0
-----------------------
x ^ y   0 1 0 1 0 1 1 0

negace po bitech
x       0 1 1 0 0 1 0 0
-----------------------
~x      1 0 0 1 1 0 1 1

bitový posuv doleva, tady o 2 bity, lze o obecný počet bitů
(zprava nahrazujem prázná místa 0)
x       0 1 1 0 0 1 0 0
-----------------------
x << 2  1 0 0 1 0 0 0 0

bitový posuv doprava o 2 bity, lze o obecný počet bitů 
(zleva nahrazujeme prázdná místa 0 pro unsigned a 1 pro signed typy)
x       0 1 1 0 0 1 0 0
-----------------------
x >> 2  0 0 0 1 1 0 0 1

Na bitové operátory se aplikují typové konverze jak u aritmetických operátorů. U operátorů posuvu musí být druhý operand nezáporný.

Kontrola běhu programu

Větvení

if (tval)
{
	// blok při nenulovém tval
}
else 
{
	// blok při nulovém tval
}

Větev else je nepovinná. Pokud blok obsahuje pouze jeden příkaz, lze závorky vynechat. Při vynechávání závorek bloků, nemusí být na první pohled patrné, ke kterému if patří dané else: toto je dáno pravidlem, že patří k nejbližššímu if, které připadá v úvahu (tj. není obsazeno jiným else podle struktury bloků). Toto pravidlo se zhusta používá v konstrukci známé jako žebřík.

if (tval_1)
{
	// tval_1 je pravda (tj. není 0)
}
else if (tval_2)
{
	// tval_1 je nepravda (tj. je 0)
	// tval_2 je pravda
}
else if (tval_3)
{
	// tval_1 a tval_2 jsou nepravda
	// tval_3 je pravda
}
else 
{
	// tval_1, tval_2, tval_3 jsou nepravda
}

Není špatným zvykem psát závorky pro bloky skoro vždy (mimo speciálních idiomů, například žebříku).

Dalším příkazem pro větvení je switch. Tuto konstrukci si nastudujte z literatury jako cvičení.

Cykly

Základní cyklus.

while (tval)
{
	// tělo
}

Běh je následující

Vyhodnotíme tval, pokud není pravdivý, cyklus končí
Provedeme tělo cyklu a přejdeme k bodu 1.

Krokovací cyklus.

for (iter; tval; incr)
{
	// tělo
}

Běh je následující

Když cyklus začíná, provede se část iter. Ta může obsahovat i definici proměnné, tato proměnná je potom platná jenom v cyklu, uchovává si ale hodnotu mezi jednotlivými iteracemi.
Potom se vyhodnotí tval. Pokud je pravdivá, provede se tělo cyklu, jinak cyklus skončí.
Provede se výraz incr a přechází se k bodu 2.

Části iter, tval i incr lze vynechat (středníky musí zůstat), pokuch chybí tval je brán jako pravdivý.

Cyklus s alespoň jednou iterací.

do 
{
	// tělo
} while (tval);

Podobné cyklu while, pouze vyhodnocujeme tval na konci těla cyklu, nikoliv na začátku. V důsledku toho tělo cyklu provede vždy aspoň jednou.

/*
	Příklad: výpis čísel od 0 do n (n už se netiskne)
*/
int n = 10;

{ 
	// pomocí while
	int i = 0;
	while(i < n)
	{
		printf("%i\n", i);
		i += 1;
	}
}

{
	// pomocí for
	for(int i = 0; i < n; i += 1)
	{
		printf("%i\n", i);
	}	
}

{ 
	// pomocí do while
	// nefunguje pro n == 0 
	int i = 0;
	do
	{
		printf("%i\n", i);
		i += 1;
	} while(i < n);
}

Vykonávání libovolného cyklu lze přerušit provedením příkazu break. Ukončit provádění aktuální iterace cyklu a skočit dopředu na konec těla cyklu lze příkazem continue.

Poznámka k úkolům

Pokud se v úkolech vyskytují čísla, vhodně zvolte typ. Většinou stačí int, případně float. Můžete předpokládat, že funkce dostanou správné argumenty: pokud je například v úkolu napsáno, že argumentem funkce má být přirozené číslo, můžete pro ně zvolit typ int a přitom ve funkci nekontrolovat, že argument je nezáporný. Nemusíte volit unsigned int.

/* funkce zjišťující, jestli je n prvočíslo */
int is_prime(int n)
{
	/* následující test není potřeba */
	if (n <= 0) 
	{
		// a very bad error !!!!
	}
}

Úkoly

Ve vybraném vývojovém prostředí vytvořte program, který vytiskne větu: Ahoj světe. Program zkompilujte a spusťte.
Napište funkce pro výpočet obsahu obdélníka a kruhu.
Napište funkci pro převod malého písmena na velké.
Napište program, který vypíše velikosti všech skalárních typů.
Napište program, který vytiskne první a poslední číslici tříciferného čísla.
Napište funkci, která zvlášť vytiskne celou a desetinnou část desetinného čísla.
Napište funkci, která vrátí i-tý bit čísla (bezznaménkového typu).
Napište funkci, která vypíše hodnoty všech bitů čísla typu unsigned char. (Nevadí, že nepoužijete cyklus, ten bude až příště).
Pomocí unsigned char lze reprezentovat podmnožinu množiny {0,..,7} následovně: bit na indexu i je roven 1, pokud i patří do podmnožiny, jinak je roven 0. Naprogramujte funkce pro test podmnožinovosti a výpočet rozdílu.
Napište funkci, která spočítá minimum tří čísel.
Napište funkci, která rozhodne, zda je daný rok přestupný.
Napište funkci, která vypočítá a-té Fibonacciho číslo.
Napište funkci, která vytiskne všechna čtyřciferná čísla, jejichž součet číslic je dělitelný 7.
Napište funkci, který pro přirozená čísla x, y vypíše všechna čísla větší než x a menší než y taková, že se čtou stejně zepředu jako zezadu (např. 12321, 1001).
Napište funkci, která pro přirozené číslo vytiskne jeho rozklad na prvočísla.
Napište funkci, která rozhodne, zda jsou dvě pole stejná, když * pole jsou stejná, pokud na všech indexech mají stejné hodnoty. * pole jsou stejná, pokud můžeme proházet prvky v prvním poli tak, aby bylo stejné jako druhé pole podle definice z předchozího bodu.
Napište funkci, která ověří, zda-li jsou prvky v poli uspořádány vzestupně.
Napište funkci, který určí maximální počet znaků, na kterých konec řetězce r1 stejný jako začátek řetězce r2.
```
Například pro "ahoj" a "hojnost" jsou to tři znaky, odpovídající řetězci "hoj".
a h o j
h o j n o s t
```
Napište funkci, která pro řetězce x, y spočítá, kolikrát se x vyskytuje jako podřetězec y. Jednotlivé výskyty se mohou překrývat.

Paměť

Pointery

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.

Program běžící na běžném OS má díky virtuální paměti 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 64-bitová, jak tomu je na moderních počítačích, adresní rozsah je od 0 do $2^64$.

Při psaní programu se o to, na jakých konkrétních adresách jsou objekty uloženy, nestaráme. 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í operace, které můžeme s pamětí dělat, je zjištění adresy na níž je konkrétní objekt (např. proměnná). To se provádí pomocího 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ě.

Adresu můžeme uložit i do proměnné, k tomu ale potřebujeme znát její typ. 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*.

// 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ý. Obecně nelze testovat, jesli je pointer neplatný. 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 funkce 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)

Jak je to s přístupem k prvkům pole? To řeší pointerová aritmetika. Protože pole je v paměti v souvislém bloku, lze adresu prvku na indexu i získat tak, že adresu začátku pole zvětšíme o i-krát velikost jednoho prvku pole. Tím se v paměti posuneme z prvního bajtu prvku na indexu 0 na první bajt prvku na indexu i. V programu počet bajtů, o které je nutno se posunout nemusíme počítat, aritmetické operace s pointery to udělají za nás. K pointeru lze totiž přičíst, nebo od něj odečíst, celé kladné číslo. Výsledkem přičtení čísla c k pointeru ptr je pointer, který získáme zvětšením ptr o c-krát velikost typu, na který ptr ukazuje. Pokud by byl například ptr pointer na int, tak bychom je zvětšili o c-krát sizeof(int). Odečítání celého čí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 (můžeme je psát kvůli čitelnosti, nebo “pro jistotu”).

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é je sama. Toho často využíváme při kostrukci datových struktur, například spojového seznamu.

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


Node storage[10];
for(int i = 0; i < 10; i += 1) 
{
	// naplnime seznam
	storage[i].key = i;
	if (i < 9) 
	{
		storage[i].next = &storage[i+1];
    }
    else 
	{
		storage[i].next = 0;       // posledni prvek nema souseda
    }
}

// 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 celociselne deleni
// argument rem je predan odkazem, je to adresa, na kterou funkce zapisuje

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);  // tady predame adresu promenne y
	printf("vysledek %i, zbytek %i\n", x, y); // vypise: vysledek 3, zbytek 1
}

void 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, size_t size) {
	unsigned char *bytes = mem; // tady pretypujeme
	for (size_t i = 0; i < size; i += 1, bytes += 1) {
		if (i && !(i % 8)) {
			printf("\n"); 
		}
		printf("%.2X ", *bytes); 
  }
  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).

Životnost objektů za běhu programu

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

Naprogramujte funkci Token parse(char string[]), určenou k převodu prvního slova řetězce string na hodnotu. (První slovo je do bílého znaku nebo do konce řetězce). Typ Token (který také definujte) přitom musí být technikou tagged unionu schopen reprezentovat následující případy
- je-li první slovo desetinným číslem, pak je hodnota typu double
- je-li první slovo celý číslem, pak je hodnota typu int
- prvním slovem je jedno z klíčových slov if for while
- string je prázdný
- nastala chyba (situace nepokryté předchozími body)
Naprogramujte vlastní verze knihovních funkcí strlen a strcmp (string.h), které nepoužijí indexů, ale pouze pointerové aritmetiky a dereference.
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é.
Naprogramujte funkci pro výpočet průměru a mediánu pole čísel (např. float). Jednu z hodnot vraťte pomocí argumentu předaného odkazem. (Funkce může změnit pořadí prvků v poli.)
Napište funkci swap_int, která prohodí hodnoty dvou proměnných typu int.
Napište funkci, která v poli řetězců najde znak, který se vyskytuje v nejvíce řetězcích v tomto poli.
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;
```
Řětězce budeme vytvářet pomocí funkce (není nutno se zabývat jejím tělem, zejména ne funkcí malloc).
```
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
```
String get_prefix(String str, char delimiter, String* remainder);
```
Funkce vrátí prefix řetězce str až do znaku delimiter, který ovšem do výsledku nepatří. Do argumentu remainder zapíše zbytek řetězce bez delimiteru. Tedy pokud spojíme návratovou hodnotu, delimiter a remainder dostaneme str (vše chápáno jako řetězce). Pokud je první symbols str roven delimiter, vrací funkce prázdný řetězec. Pokud str delimiter neobsahuje, je výsledkem celý řetězec. Funkce v tomto případě musí nastavit remainder na prázdný řetězec. Funkce vytváří novou strukturu string, ovšem nealokuje novou pamět pro pole typu char, položka data je ukazatelem do pole, na které ukazuje položka str.data. Stejně tak pro remainder.
```
int string_to_long(String s, long* result);
```
Funkce převede číslo zapsané jako řetězec na long. Předpokládáme kódování v desítkové soustavě. Čí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čet součtů 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ů 4, 6, 1 a výsledek je -4 + 6 -1 = 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ů).
Naprogramujte vlastní verze funkcí memcpy, memmove, memcmp, memset. Funkce mohou být implementovány naivně.
Najděte způsob, jak bez použití sizeof programově zjistit velikost nějakého typu, například float.
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ě.
Implementujte funkci, která vrátí nově alokovaný řetězec, jehož obsah vznikne spojením dvou řetězců předaných funkci jako argumenty.
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.

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

Naprogramujte následující funkci.
```
char** split_string(char *str, char delimiter, int *n);
```
Funkce rozdělí řetězec str na části oddělené znakem delimiter, ten přitom do žádné části nepatří. Funkce vrátí takto vzniklé řetězce v nově alokovaném poli, každý z jeho prvků je klonem části původního řetězce, tj. jeho paměť je
nově alokována. Počet vzniklých řetězců zapíše na adresu n.

Příklady rozdělení řetězce (delimiter je '-')
```
"ahoj-svete"       -> { "ahoj", "svete" }
"ahoj--svete"      -> { "ahoj", "", "svete" }
"-ahoj-svete"      -> { "", "ahoj", "svete" }
"ahoj-svete-"      -> { "ahoj", "svete", "" }
"ahoj"             -> { "ahoj" }
```

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.

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

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ů.
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.
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.
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.
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.
S použitím příkladu z kapitoly vytvořte funkci pro binární vyhledávání zlomků.

Do následujícího kódu doprogramujte generickou funkci pro třídění a s její pomocí funkce pro třídění zlomků a short int. (Můžete si doprogramovat libovolné pomocné funkce.) Je zakázáno použít třídicí funkci ze standardní knihovny.

typedef struct
{
    int numerator;
    int denominator;
} Fraction;

typedef int compare_fn(void*, void*);

int compare_fraction(void *a, void *b)
{
    // TODO
}

int compare_unsigned(void *a, void *b)
{
    // TODO
}

void generic_sort(void *array, size_t n, size_t element_size, compare_fn* cmp)
{
    // TODO
}

void fraction_sort(Fraction *array, int n)
{
    // TODO
}

void unsigned_sort(unsigned int* array, int n)
{
    // TODO
}

Vstup a výstup pomocí proudů

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é, nestandardní, 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 kterého lze zapisovat nebo z něj číst. Otevřením souboru jej na proud napojíme a poté zapisování do či čtení z proudu odpovídá zapisování do souboru či čtení ze souboru. Jsou definovány i další, tzv. standardní proudy. Pomocí nich můžeme zapisovat na standardní výstup (tam zapisuje např.printf), na standardní chybový výstup a číst ze standardního vstupu.

Proud je reprezentován strukturou FILE, v programu pracujeme s ukazateli na tuto strukturu. Získáme jej pomocí funkce fopen.

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

První argument je cesta k otevíranému souboru (ta je buď absolutní, nebo relativní vzhledem k umístění binárky spoušteného programu). Textový řetězec mode určuje způsob otevření souboru. Jeden ze znaků mode obvykle udává režim otevření: ten je buď textový nebo binární. Další znak pak to, co se souborem můžeme dělat: číst jej, zapisovat do něj, připojit něco na jeho konec, vytvořit jej, pokud neexistuje, nebo nějaká kombinace předchozího. Nejpoužívanější možnosti ukážeme níž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 otevření souboru selže, vrátí 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);
}

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

Napište program, který spočítá počet znaků, řádků a slov v textovém souboru. (Analogie textové utility wc).
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).
Nastudujte v referenční příručce a vyzkoušejte funkci fgets.
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ů.

PBM je textový formát pro uložený černobílého obrázku (každý pixel je buď černý nebo bílý).

Řádky začínající znakem # jsou komentáře
První řádek obsahuje řetězec "P1".
Druhý řádek obsahuje dvě čísla v desítkové soustavě oddělená mezerou, tato čísla udávají šiřku a výšku obrázku (v pixelech).
Počínaje třetím řádkem obsahuje soubor pixelová data. Jeden pixel je buď 0 nebo 1. Pixely jsou zapsány za sebou po řádcích odshora obrázku, jeden řádek obrázky na jeden řádek souboru. Mezi pixely na jednom řádku je mezera.

Doplňte chybějící kód v následujícím. (Můžete si dopsat pomocné funkce atd.)

//
//  Pro jednoduchost případné chyby (nelze otevřít soubor atd.)
//  řešte pouze ukončením programu pomocí assert
//
//  Volitelně lze dopsat funkci pro dealokaci vnitřních dat
//  struktury Picture (ale není to nutné, jde o procvičení práce
//  se streamy).
//

//
// Struktura pro černobílý obrázek
//
typedef struct 
{
	// TODO
} Picture;

//
// nahraje ze souboru obrázek ve formátu pbm
// 
Picture load_from_pbm(char* filename)
{
	// TODO 
}

//
// zrcadlově obrátí obrázek podle svislé osy
//
void mirror_picture(Picture* p)
{
	// TODO
}

//
// uloží obrázek v pbm formátu
//
void save_to_pbm(char* filename, Picture src)
{
	// TODO
}

//
// příklad použití
//
int main()
{
	Picture picture = load_from_pbm("test.pbm");
	mirror_picture(&picture);
	save_to_pbm("foo.pbm", picture);
}

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
--------------------------------------------------------------------------
```
Run Length Encoding (RLE) je velmi jednoduchý bezeztrátový kompresní princip. Vysvětlíme jej na posloupnostech symbolů a později si řekneme, jak jej uplatníme v jednoduchém kompresním programu.

Vstupem RLE je posloupnost symbolů (symbol je zde abstraktní pojem, který nijak nevztahujeme k jazyku C, znakům v textu atd.). Tu převedeme do komprimované podoby s pomocí následujícího principu:
- Pokud se v posloupnosti za sebou nachází n-krát symbol x, převedeme ji na dvojici (x, n).
- Předchozí bod aplikujeme na maximálně dlouhé (= nejdou prodloužit) podposloupnosti vstupní posloupnosti v pořadí, ve kterém se ve vstupní posloupnosti vyskytují.
Například posloupnost aaabaabcccccbccccd zakódujeme na
```
(a,3)(b,1)(a,2)(b,1)(c,5)(b,1)(c,3)(d,1)
```
Naprogramujte základ jednoduchého kompresního programu.

Soubor pro kompresi budeme otevírat v binárním módu. Pro RLE budeme za jeden symbol považovat jeden bajt souboru. Dvojici (x, n), kde x je symbol a n je počet jeho výskytů budeme do výsledného souboru ukládat pomocí dvou bajtů: do prvního uložíme x, do druhého uložíme n-1. Takto jsme schopni uložit pouze dvojice, kde je n <= 256. Dvojice, kde je n>256, si představíme jako posloupnost n/256 dvojic (x, 256) následovanou dvojicí (x, r), kde r = n % 256. Tyto dvojice poté uložíme stejným způsobem, jako dvojice s n<=256.

Kompresní program implementujte jako funkce
```
void RLE_encode(char* in_path, char *out_path);
void RLE_decode(char* in_path, char *out_path);
```

Preprocesor

Preprocesor je součást překladače, která zpracovává zdrojový kód před tím, než je dále zpracován. Na zdrojovém kódu provádí textové operace (mazání, vkládání a nahrazování textu). Tyto operace jsou prováděny s následujícími cíly

smazání komentářů,
expanze maker,
podmíněný překlad (podmíněné vynechání/vložení části kódu),
vložení obsahu jiných souborů.

Překladače umožňují prohlédnout si kód poté, co je zpracován preprocesorem. Pro překladač gcc toho lze dosáhnout pomocí

gcc -E -P source.c

Je důležité si uvědomit, že preprocesor je součástí překladu. Nemůže proto například znát hodnoty proměnných, ty jsou známy až za běhu překladu. Provádí jenom textové substice.

Části kódu určené pro preprocesor, jsou uvozené znakem #. Ty, kterým preprocesor rozumí říkáme direktivy preprocesoru.

Makra

Makra definujeme pomocí #define. Lze také oddefinovat pomocí #undef macro_name.

Makra bez argumentů — definice symbolů

Makro definujeme následovně

#define name replacement

Preprocesor v kódu nahradí text name textem replacement. Nenahrazuje výskyty name, které jsou součástí identifikátorů, klíčových slov nebo se vyskytují v řetězcových literálech.

Například kód

#define PI 3.14
#define ERROR  printf("Chyba") 

double circle_area(double r)
{
	if (r > 0) { return 2 * PI * r; }	
	ERROR;
	return -1;
}

předělá preprocesor na následující.

double circle_area(double r)
{
	if (r > 0) { return 2 * 3.14 * r; }
	printf("Chyba");
	return -1;
}

Symbol lze definovat i bez replacement části. Říkáme tím pouze, že symbol je definován (o použití více později).

V případě, že replacement chceme napsat na více řádků, lze řádek zlomit pomocí znaku \ (zpětné lomítko), přitom je to bráno jako jeden řádek.

#define HELLO printf("%s %s", \
                     "hello", \
					 "world")

Podle standardu existují některá předdefinovaná makra, například

__LINE__, expanduje na číslo řádku, na kterém se makro nachází (celočíselný literál)
__FILE__, expanduje na jméno souboru (řetězcový literál)
__DATE__, expanduje na aktuální datum (řetězcový literál)
__TIME__, expanduje na aktuální čas (řetězcový literál)

Další makra může definovat konkrétní překladač. Například seznam maker definovaných překladačem gcc lze vytisknout pomocí následujího řádku pro shell.

echo "" | gcc -dM -E -

Makra s argumenty

#define name(parameter-list) replacement

parameter-list je čárkami oddělený seznam jmen parametrů. Při expanzi jsou jména parametrů vyskytující se v replacement (s jednou výjimkou) nahrazena argumenty makra.

// makro pro druhou mocninu
#define square(x)  x*x

// "volani" makra
square(value) 
// vede k expanzi na
value*value

Při psaní maker je nutno dávat si pozor na mnohá nebezpečí, například následující použití makra square vede k nečekanému výsledku.

square(x+1)
// expanduje na 
x+1*x+1
// a to je něco jiného, než očekáváme: hodnota výrazu je 2x + 1, nikoliv (x+1)*(x+1)

Při psaní maker je tak výhodné využívat uzávorkování v maximální míře: závorky okolo jmen argumentů a závorky okolo celého výrazu.

#define square(x) ((x)*(x))

Problémem může být také situace, kdy je parametr makra použit v jeho těle vícekrát, a příslušný argument je výraz s vedlejším efektem.

#define square(x) ((x)*(x))

int foo(int x)
{
	printf("launching %i misiles\n", x);
	return x;
}

// výraz
int y = square(foo(3));
// expanduje na 
int y = ((foo(3))*(foo(3)));
// a vedlejší efekt tak nastane dvakrát

Řešením je psát makra tak, aby se v jejich těle parametry neopakovaly, nebo jim nepředávat jako argumenty výrazy s vedlejším efektem.

int z = foo(3); // vedlejší efekt nastane pouze jednou
int y = square(z);

Výraz #par v těle makra, kde par je jméno parametru, expanduje na řetězcový literál, jehož obsahem je příslušný argument.

#define print_value(val) printf("value of " #val " is %f", val)

int main()
{
	double x = 3;
	double y = 4;
	print_value(x + y);
	return 0;
}

// expanduje na 
int main()
{
	double x = 3;
	double y = 4;
	printf("value of x + y is %f", x + y);
	return 0;
}

Výraz a ## b expanduje na ab. Toto lze využít k vytváření nových identifikátorů spojováním slov.

#define VAR(x) variable_ ## x

VAR(10)   // expanduje na variable_10
VAR(f)   // expanduje na variable_f

S výhodou to lze použít pro automatické vytváření specializovaných verzí generických funkcí (viz kapitola 3)

// funkce prohodí n bajtů na adresách a,b
void mem_swap(void *a, void *b, size_t n);

//specializacni makro
#define define_swap(type) void swap_ ## type (type *a, type *b) {\
	                        mem_swap(a, b, sizeof(type));            \
						  }
define_swap(double)
// expanduje na
void swap_double(double *a, double *b) {
	mem_swap(a, b, sizeof(double));
}

Krátké shrnutí procesu expanze maker

Pokud se jedná o makro s argumenty, nejdříve prozkoumáme jestli předané argumenty obsahují makra. Pokud ano, jsou expandována.
Do textu je vložena textová náhrada makra z jeho definice. U makra s argumenty jsou jména parametrů nahrazena expanzemi argumentů, a jsou provedeny převody na řetězcové literály a spojení pomocí ##.
Pokud se ve výsledném textu nachází nějaká makra, jsou expandována.

Variadická makra

Makra s proměnným počtem argumentů. Například

#define pprint(fmt, ...) printf("[pretty] " fmt, __VA_ARGS__)

Nepovinné argumenty v těle nahrazují __VA_ARGS. Například

pprint("%i %i", i, j);

expanduje na

printf("[pretty] " "%i %i", i, j);

Podmíněný překlad

#if constant_expression
   // code
#endif

constant_expression je výraz obsahující literály, logické operátory a operátory porovnání, operátor defined a případně již definovaná makra, která se na ně expandují. Pokud je hodnota constant_expression nenulová, je část mezi #if a #endif v kódu ponechána, jinak je vypuštěna. Výraz lze doplnit o #else a #elif s obvyklým významem.

Lze použít se speciálním výrazem defined(symbol), který je nenulový, pokud je symbol již definované makro. Toto lze využít k zařazení či vynechání kódu určeného pro specifické situace (debug/release build atd.) nebo platformy. Definovat jednoduchá makra lze totiž i přímo pomocí přepínačů překladače, například pro gcc

// definuje makro Symbol
gcc -dSymbol

// definuje makro Symbol na literál 10
gcc -DSymbol=10

Příklad použití

#if defined(WIN)
	// kód specifický pro windows
#elif defined(UNIX)
	// kód specifický pro unix
#else
	// kód pro ostatní platformy, případně vyvolání chyby
	// viz níže
#endif

Výše používáme operátor defined, který je pravdivý, pokud je jeho argument již definované makro.

// #if defined(SYMB)  lze nahradit #ifdef SYMB
// #if !defined(SYMB) lze nahradit #ifndef SYMB

S podmíněným překladem můžeme výhodně použít dalších direktiv preprocesoru

#error message při překladu se vytiskne message a je vyvolána chyba překladu
#warning message při překladu je vypsáno message jako warning

Například v části #else předchozího příkladu bychom mohli dát

#error Won't compile on unsupported platforms. We support only windows and unix.

Vložení obsahu jiných souborů

Direktiva #include slouží k vložení obsahu jiného souboru do zdrojového kódu. Soubor, který se má vložit, lze specifikovat dvojím způsobem

#include <path-to-file>
#include "path-to-file"

V prvním případě je soubor hledán v předdefinovaných adresářích (ty jsou dány nastavením systému, případně je lze předat jako argumenty překladači) a path-to-file je brána jako relativní cesta z nějakého takového adresáře. Druhém případě se nejdříve prohledává adresář, ve kterém je uložen aktuální soubor (obsahující #include). (Někdy se poté vyhledávají předdefinované adresáře.

Obvykle je nutno zabránit tomu, aby byl obsah nějakého souboru vložen vícekrát. (To hrozí například pokud vkládáme dva různé soubory, které samy obsahují directivu #include, která vkládá stejný soubor.) K tomu lze výhodně využít podmíněného překladu (předpokládejme například, že jde o soubor stdio.h)

#if !defined(__STDIO_H__)
#define __STDIO_H__

// kód

#endif

U většiny překladačů také funguje vložení následující direktivy.

#pragma once

Pragma

Mimo výše zmiňované direktivy existují i další. Například direktiva #pragma, jejíž syntax i sémantika je závislá na konkrétním překladači.

Úkoly

Napište makro

is_digit(base, character)

pro testování, zda je znak určený výrazem character číslicí soustavy se základem daným base. Makro musí korektně fungovat pro základy soustav od 2 do 36 a libovolné znaky. Pro číslice s hodnotou vyšší než 9 používejte pro jednoduchost pouze velká písmena anglické abecedy.

Příklady použití

if (is_digit(8,'8') != 0 { printf("Ano\n"); } 
else                     { printf("Ne\n");  }

if (is_digit(10+6, '0'+4) != 0) { printf("Ano\n"); } 
else                            { printf("Ne\n");  }

if (is_digit(30, '@') != 0) { printf("Ano\n"); } 
else                        { printf("Ne\n");  }

//
//  vede k výpisu následujícího
//
Ne
Ano
Ne

Upravte makro
```
#define LOG(fmt, ...) printf("[LOG] " fmt "\n", __VA_ARGS__)
```
tak, aby tisklo i soubor a řádek, na kterém je použito.
K úkolu 7 z kapitoly Funkce doprogramujte makro EMIT_SORT(type), které expanduje na definici třídící funkce pro type. Přitom předpokládejte, že porovnáváci funkce pro type se jmenuje compare_type (např. pro double je to compare_double)

Další

Projekty s více soubory

Zdrojový kód lze rozdělit do více souborů. Jeden soubor (.c) lze chápat jako samostatný modul, který může ostatním modulům poskytovat některé své funkce a globální proměnné, a ostatní si přitom ponechat soukromé.

Chceme-li, aby byla funkce nebo proměnná platná pouze v souboru, ve kterém jsou definovány, použijeme k tomu static. Toto klíčové slovo se píše před definici. Pokud se v jiném souboru nachází definice proměnné nebo funkce se stejným jménem, jedná se o jinou proměnnou (nebo funkci).

//
// proměnná private_variable a funkce private_function jsou viditelné
// pouze v souboru, kde se nachází následující definice
// 

static int private_variable;

static int private_function(int a, int b)
{
	return a + b;
}

Předtím než použíjeme globální proměnnou nebo funkci z jiného souboru, musíme je deklarovat s klíčovým slovem extern. U proměnných je povinné, u funkcí je nepovinné, ale je dobré jej tam psát.

//
// následující musí být před použitím dané proměnné nebo funkce
//

extern int variable_in_different_file;
extern int function_in_different_file(int, int);

Linkage

Každý identifikátor (jméno proměnné) má v souboru, kde je definován atribut linkage, který může nabývat tří hodnot.

no linkage. Tento atribut mají lokální proměnné.
external linkage. Identifikátor je viditelný pro kód vně modulu, ve kterém je definován. Identifikátor může být s external linkage definován nejvýše jednou v celém programu. Jinde musí být definován s internal linkage nebo bez linkage.
internal linkage. Identifikátor je viditelný pouze uvnitř .c souboru, kde je definován.

Vidíme tak, že obyčejné funkce a globální proměnné mají external linkage, funkce a proměnné definované s klíčovým slovem static mají internal linkage.

Je důležité si uvědomit, že external linkage není identifikátoru přidělen použitím slova extern.

// file1.c

int x;                             // external 
static int y;                      // internal 

static int sum(int a, int b)       // internal
{
	int s = a + b;                 // no linkage
	return s;
}

int product(int a, int b)          // external
{
	int p = a + b;                 // no linkage
	return p;
}

// file2.c

extern int x;                 // je to proměnná x z file1.c
extern int product(int,int);  // funkce product z file1.c

// file3.c

static int x;                 // toto je OK, má internal linkage
static int product(int, int)  // toto je OK, má internal linkage
{ 
	// code
}

// V souboru uz nesmime deklarovat sum nebo product s extern!!!

Klasické dělení na soubory

Definice proměnných a funkcí je v .c souborech (např. code.c). Funkce a proměnné, které nemají být viditelné vně souboru, ve kterém jsou definovány, definujeme se static. Funkční prototypy a proměnné, které mají být viditelné, deklarujeme v souboru .h (např. code.h) s extern. Soubory, které tyto funkce a proměnné chtějí používat, potom tento soubor vloží pomocí #include.

Hlavičkový soubor navíc obsahuje i definice typů a maker, které jsou pro daný .c soubor veřejné nebo potřebné, např. typy, které se vyskytují ve funkcích a proměnných v daném .h souboru.

Proces překladu

Pro každý .c soubor se provede následující.

Spustí se preprocessor.

# pouze preprocesor
gcc -E code.c      # tiskne na stdout

Překladač přeloží kód do jazyka symbolických adres.

# preprocesor + preklad do symbolickych adres
gcc -S code.c  # vytvoří soubor code.s

Assembler poté kód přeloží do objektového souboru (strojový kód a další informace, např. poskytovaná jména funkcí a proměnných.)
```
# vytvori objektovy soubour code.o
gcc -c code.c
```
Linker sloučí vytvořené objektové soubory, spojí je s knihovnami (např. standardní knihovnou) a vytvoří cílený binární soubor (spustitelný soubor, knihovnu).
```
# code1.o, code2.o jsou objektové soubory
gcc code1.o code2.o   # volá linker, např. ld
```

Argumenty funkce main

Funkce main může mít žádný nebo paramatery, její hlavička je potom

int main(int argc, char *arg[]);

Hodnoty parametrů je možné funkci předat při spuštění programu z příkazové řádky (terminálu, skriptu apod.). Do parametru argc se uloží jejich počet zvětšený o jedna, jejich hodnoty (jako řetězce) jsou v poli argv počínaje indexem 1; argv[0] je totiž řetězec odpovídající spuštěnému programu. (argc je tak velikost pole argv.)

Úkoly

Napište program pro výpočet objemu a povrchu válce, pravidelného trojbokého, čtyřbokého a šestibokého hranolu. Parametry výpočtu by mělo být možné předávat programu při spuštění z příkazové řádky. Zdrojový kód programu by měl být rozdělen do 2 modulů. Modul hlavní funkce (soubor main.c) bude zajišťovat zpracování a případně načtení chybějící parametrů výpočtu, budou z něj volány funkce zajišťující vlastní výpočet a vypisovány vypočítané hodnoty na obrazovku. Druhý modul (soubory vypocet.h a vypocet.c) pak bude zajišťovat veškeré požadované výpočty. Při řešení úlohy dbejte všech zásad zmíněných na přednášce. zdroj
Napište v jazyku C jednoduchou knihovnu funkcí pro vykreslování obrázků pomocí znaků (tzv. ASCII art). Knihovna by měla mít tyto vlastnosti:
- Obrázky se budou vykreslovat pomocí plátna - dvojrozměrné matice, která bude obsahovat jednotlivé znaky.
- Vykreslování se tedy neprovádí přímo na výstupu, ale pouze dochází ke změně daného plátna (struktura Canvas).
- Je možné pracovat současně s několika plátny.
- Je možné “vykreslovat” i za hranicí kreslící plochy, tyto body se ale nebudou při zobrazení plátna vykreslovat. Jinými slovy, při pokusu o kreslení mimo plátno nedojde k vyjímce při běhu programu.
Knihovna by měla být samostatným modulem, bude tedy tvořena jedním zdrojovým a jedním hlavičkovým souborem. V knihovně vytvořte strukturovaný datový typ Canvas a dále definujte tyto funkce:
```
//
// Inicializuje plátno na prazdné plátno široké width a vysoké height znaků
//
void canvas_init(Canvas *c, int width, int height);

//
// Vrátí znak nacházející na řádku x ve sloupci y
//
int canvas_get_point(Canvas c, int x, int y);

//
// Nakreslí obdélník, jehož stěna je tvořena znakem ch
//
void canvas_draw_rect(Canvas *c, int x, int y, int width, int height, char ch);

//
//  Vyprázdní plátno
//
void canvas_clear(Canvas *c);

//
//  Vykreslí obsah plátna na standardní výstup/do souboru
//
void canvas_print(Canvas *c);
void canvas_output(Canvas *c, FILE *f);

//
//  Uvolní vnitřní pamět plátna
//
void canvas_destroy(Canvas *c);
```

Keyboard shortcuts

Poznámky ke kurzům KMI/JC a KMI/XJC, ZS 2025