Paměť - Poznámky ke kurzům KMI/JC a KMI/XJC, ZS 2025

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.

Adresní prostor je množina adres a je typicky dána velikostí adresy. Je-li například adresa 64-bitová, jak tomu je na moderních počítačích, obsahuje adresní prostor adresy od 0 do 2^64 - 1. Díky virtuální paměti pracuje každý proces s vlastním adresním prostorem: tatáž adresa znamená v různých procesech různé místo ve fyzické paměti a jeden proces se k paměti druhého nedostane. Naprostá většina adres z tohoto prostoru ovšem platná není. Operační systém procesu zpřístupní jen ty oblasti, o které si řekne. Přístup na kteroukoliv jinou adresu program ukončí (např. chybou segmentation fault).

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", (void*)&x);  // vypiseme adresu, na ktere je promenna x, 
                            // %p vyzaduje typ void* o tom pozdeji

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. V cizím kódu se místo 0 často píše makro NULL z stddef.h. Znamená to totéž a lze je pro účely testování platnosti pointeru zaměňovat. (Nemusí ovšem být totožné, NULL nemusí mít všechny bity 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 se ve výrazech konvertuje na pointer na jeho první prvek (tzv. degenerace). Výjimkou je sizeof a operátor &.

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 neni lvalue

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(a) / sizeof(a[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́ 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};
printf("velikost int: %zu\n", sizeof(int));
for (int i = 0; i < 3; i += 1) 
{
	printf("index: %i, adresa: %p\n", i, (void*)(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 čísle, jehož absolutní hodnota je rovna počtu prvků daného typu, který se mezi obě adresy vejde. Je to tedy rozdíl adres (v bajtech) dělený velikostí typu (je použito celočíselné dělení). Výsledek je typu ptrdiff_t: je to znaménkový celočíselný typ, jehož šířka závisí na implementaci (může to bý například long). Operace je definována pouze pro adresy ukazující do stejného pole, jinak výsledek není definován.

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", (void*)&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). Skutečné hlavičky obsahují ještě klíčové slovo const, ke kterému se vrátíme v kapitole Další.

Ž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í. (Manuální životnosti se někdy také říká alokovaná, od C11 přibyla životnost pro vlákna, ale tou se zabývat nebudeme.)

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 životnost 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
ptr->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.

Alokace paměti je první operace, se kterou jsme se setkali a která může za běhu selhat, aniž by na tom bylo cokoliv nelegálního. Její návratovou hodnotu je proto potřeba kontrolovat. Nejjednodušší způsob, jak to udělat, je makro assert z hlavičkového souboru assert.h.

#include <assert.h>
#include <stdlib.h>
 
int *array = malloc(sizeof(int) * 10);
 
//
// pokud je array nulovy pointer, program se ukonci
// a vypise, ve kterem souboru a na kterem radku k tomu doslo
//
assert(array);

Makro dostane jeden výraz. Je-li výraz pravdivý, neudělá assert nic a program pokračuje. Je-li nepravdivý, vypíše se na chybový výstup zpráva s názvem souboru, číslem řádku a zněním výrazu a program se okamžitě ukončí.

Je-li při překladu definováno makro NDEBUG, všechna volání assert z programu zmizí. Toho se využívá pro finální, odladěnou verzi programu, u které už kontroly nechceme platit. Jak přesně to udělat je v kapitole Preprocesor. Z toho plyne pravidlo, které je nutné dodržet bez výjimky: do assert nikdy nedávejte výraz s vedlejším účinkem. Zmizí-li totiž assert, zmizí i ten vedlejší účinek.

Primárně slouží assert pro odhalování chyb programátora, tedy situací, o kterých tvrdíme, že nastat nemohou. Například ověření předpokladů na začátku funkce nebo o kontrolu, že jsme někde nespočítali nesmysl.

void set_element(int *array, int n, int index, int value)
{
	//
	// tvrdime, ze funkce nikdy nebude volana se spatnym indexem
	// pokud bude, chceme se to dozvedet hned
	//
	assert(index >= 0 && index < n);
 
	array[index] = value;
}

Naopak se assert nehodí na situace, které za běhu legitimně nastat mohou: neexistující soubor, neplatný vstup od uživatele, nedostatek paměti. Ty je potřeba ošetřit a nějak na ně zareagovat, ne program ukončit. (Během vývoje můžeme dát assert i na místa, kam ošetření chyb doplníme později.)

V tomto textu assert používáme i nesprávně v situacích, na které se nehodí. Je to proto, aby příklady kódu zůstaly krátké. Makro lze ze stejného důvodu používat i při řešení úkolů.

Chyby při práci s pamětí — zápis za konec pole, použití uvolněné paměti, dvojí free — překladač neohlásí. Odhalí je ale AddressSanitizer, který stačí zapnout při překladu:

gcc -std=c17 -Wall -Wextra -g -fsanitize=address program.c -o program

Program pak při chybě vypíše, o jakou chybu šlo a na kterém řádku k ní došlo. Podrobněji v kapitole Další.

Nyní následují příklady použití typického použití alokačních funkcí 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

Napište funkci swap_int, která prohodí hodnoty dvou proměnných typu int.
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, 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, pokud jej str obsahuje, a remainder dostaneme str (vše chápáno jako řetězce). Pokud je první symbol 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 spočítá čí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ů. Toto číslo 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.
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)
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.

Doprogramujte funkci destroy_stack, pro uvolnění alokované paměti zásobníku.

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. Nejjednodušší je uložit data do jednorozměrného pole a index počítat jako radek * cols + sloupec.

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" }
```

Naprogramujte spojový seznam celých čísel, jehož uzly jsou alokovány pomocí malloc.

typedef struct _node
{
	int key;
	struct _node *next;
} Node;

Node *list_push_front(Node *head, int key);  // vraci novou hlavu
Node *list_find(Node *head, int key);        // vraci uzel s klicem, jinak 0
Node *list_remove(Node *head, int key);      // odstrani prvni uzel s klicem
void  list_print(Node *head);
void  list_destroy(Node *head);              // uvolni vsechny uzly

Program přeložte se sanitizerem (-fsanitize=address) a ověřte, že po zavolání list_destroy nehlásí žádnou neuvolněnou paměť.

Naprogramujte strukturu, která si udržuje pole řetězců a umí ho zvětšovat.

typedef struct
{
	char **items;
	int    count;
	int    cap;
} String_List;

void list_add(String_List *l, char *s);   // prida KLON retezce s
void list_destroy(String_List *l);        // uvolni vse

Zamyslete se nad tím, kolik volání free musí list_destroy udělat.

Řešení úkolů

Úkol 1

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

void swap_int(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

// volani
int x = 1, y = 2;
swap_int(&x, &y);      // x je 2, y je 1

Funkce dostane adresy obou proměnných a zapisuje přes dereferenci. Kdyby brala int a, int b, prohodila by jenom své lokální kopie a volající by nic nepoznal.

Úkol 2

Naprogramujte vlastní strlen a strcmp pouze pomocí pointerové aritmetiky a dereference, bez indexů.

size_t my_strlen(char *s)
{
	char *p = s;
	while (*p) { p += 1; }
	return (size_t)(p - s);    // rozdil pointeru, typ ptrdiff_t
}

int my_strcmp(char *a, char *b)
{
	while (*a && *a == *b) { a += 1; b += 1; }
	return (int)(unsigned char)*a - (int)(unsigned char)*b;
}

U my_strlen je pěkně vidět, k čemu je odčítání pointerů: rozdíl adres vydělený velikostí typu dá přímo počet prvků.

U my_strcmp je podstatné přetypování na unsigned char. Norma říká, že se znaky porovnávají jako unsigned char, a na platformě se znaménkovým char by bez něj vyšlo pro bajty nad 127 porovnání opačně.

Cyklus končí, jakmile narazíme na rozdíl nebo na konec a. Jsou-li řetězce stejné, *a i *b jsou 0 a výsledek je 0.

Úkol 3

Vypište layout struktury: pro každou položku její adresu a velikost, a totéž pro celou proměnnou.

struct layout { char c; int a; double d; };

int main()
{
	struct layout L;

	printf("cela struktura: velikost %zu, adresa %p\n", sizeof(L), (void*)&L);
	printf("  c: velikost %zu, adresa %p\n", sizeof(L.c), (void*)&L.c);
	printf("  a: velikost %zu, adresa %p\n", sizeof(L.a), (void*)&L.a);
	printf("  d: velikost %zu, adresa %p\n", sizeof(L.d), (void*)&L.d);
	return 0;
}

Typický výstup na 64-bitovém unixu:

cela struktura: velikost 16, adresa 0x7ffd...130
  c: velikost 1, adresa 0x7ffd...130
  a: velikost 4, adresa 0x7ffd...134
  d: velikost 8, adresa 0x7ffd...138

Součet velikostí položek je 1 + 4 + 8 = 13, struktura má ale 16 bajtů. Mezi c a a jsou tři nevyužité bajty, protože int musí začínat na adrese dělitelné čtyřmi — to je zarovnání, o kterém mluví podsekce o void*.

Zkuste si pořadí položek změnit na char c; double d; int a; a podívat se, jak se velikost změní. Vycpávky bývá nejméně, seřadíme-li položky od největší po nejmenší.

Pozor na %p — vyžaduje void*, přetypování je proto nutné.

Úkol 4

Funkce pro výpočet průměru a mediánu pole; jednu hodnotu vraťte argumentem předaným odkazem.

double mean_and_median(double *a, int n, double *median)
{
	double sum = 0;
	for (int i = 0; i < n; i += 1) { sum += a[i]; }

	//
	// medianem je prostredni prvek setrideneho pole,
	// zadani dovoluje pole prehazet
	//
	sort_doubles(a, n);

	*median = (n % 2) ? a[n/2] : (a[n/2 - 1] + a[n/2]) / 2.0;
	return sum / n;
}

Pro pole {5,1,4,2,3} vyjde průměr 3 a medián 3.

Třídicí funkci si napište sami: stačí naivní bubble sort. ( Lze použít i qsort ze stdlib.h — ta ovšem potřebuje pointer na porovnávací funkci, což je látka z pozdější kapitoly Funkce. )

Pozor na past při testování. Následující zápis je nedefinované chování:

printf("%f %f\n", mean_and_median(arr, 5, &med), med);   // SPATNE

Norma neurčuje pořadí vyhodnocení argumentů, takže med se může přečíst dřív, než do něj funkce zapíše. Správně:

double m = mean_and_median(arr, 5, &med);
printf("%f %f\n", m, med);

Úkol 5

V poli řetězců najděte znak, který se vyskytuje v nejvíce řetězcích.

int most_common_char(char **strings, int n)
{
	int counts[256] = { 0 };

	for (int i = 0; i < n; i += 1)
	{
		//
		// v kazdem retezci zapocitame kazdy znak nejvyse jednou,
		// zajima nas v kolika RETEZCICH se vyskytuje
		//
		int seen[256] = { 0 };

		for (char *p = strings[i]; *p; p += 1)
		{
			unsigned char c = (unsigned char)*p;
			if (!seen[c]) { seen[c] = 1; counts[c] += 1; }
		}
	}

	int best = -1, bestcount = 0;
	for (int c = 0; c < 256; c += 1)
	{
		if (counts[c] > bestcount) { bestcount = counts[c]; best = c; }
	}
	return best;
}

Pomocné pole seen je tu klíčové. Bez něj bychom počítali celkový počet výskytů, nikoliv počet řetězců — a "aaa" by přebilo tři různé řetězce.

Index do pole musí být unsigned char, jinak by na platformě se znaménkovým char byl pro bajty nad 127 záporný a četli bychom mimo pole.

Úkol 6

Funkce get_prefix, string_to_long a compute_the_thing nad typem String.

String get_prefix(String str, char delimiter, String *remainder)
{
	size_t i = 0;
	while (i < str.len && str.data[i] != delimiter) { i += 1; }

	String prefix = { str.data, i };

	if (i == str.len)
	{
		//
		// delimiter se nenasel, zbytek je prazdny retezec
		//
		remainder->data = 0;
		remainder->len  = 0;
	}
	else
	{
		remainder->data = str.data + i + 1;    // preskocime delimiter
		remainder->len  = str.len - i - 1;
	}
	return prefix;
}

Žádná paměť se nealokuje — obě vrácené struktury ukazují dovnitř původního pole. To je celý smysl typu String: podřetězec je jenom dvojice (adresa, délka).

int string_to_long(String s, long *result)
{
	size_t i = 0;
	int    neg = 0;
	long   value = 0;

	if (s.len == 0) { *result = 0; return 1; }

	if (s.data[0] == '-' || s.data[0] == '+')
	{
		neg = (s.data[0] == '-');
		i = 1;
		if (s.len == 1) { return 0; }     // samotne znamenko
	}

	for (; i < s.len; i += 1)
	{
		char c = s.data[i];
		if (c < '0' || c > '9') { return 0; }
		value = value * 10 + (c - '0');
	}

	*result = neg ? -value : value;
	return 1;
}

Funkce vrací 1 při úspěchu a 0 při chybě, výsledek zapisuje odkazem. Jde o typický způsob, jak z funkce vrátit hodnotu i informaci o úspěchu.

Na přetečení value se tu nekontroluje; v ostrém kódu by bylo potřeba před každým vynásobením deseti ověřit, že se výsledek do long vejde (viz podsekci Přetečení a podtečení).

int compute_the_thing(String s, long *result)
{
	long total = 0;
	int  row   = 1;
	String rest = s;

	while (rest.len > 0 || rest.data != 0)
	{
		String line = get_prefix(rest, '\n', &rest);

		long rowsum = 0;
		String word_rest = line;
		while (word_rest.len > 0)
		{
			String w = get_prefix(word_rest, ' ', &word_rest);
			if (w.len > 0)
			{
				long v;
				if (!string_to_long(w, &v)) { return 0; }
				rowsum += v;
			}
		}

		//
		// sude radky pricitame, liche odecitame
		// prvni radek je lichy
		//
		total += (row % 2 == 0) ? rowsum : -rowsum;
		row += 1;

		if (rest.data == 0) { break; }
	}

	*result = total;
	return 1;
}

Všimněte si, jak se get_prefix používá dvakrát ve dvou úrovních: jednou na rozdělení textu na řádky, podruhé na rozdělení řádku na slova. Podmínka w.len > 0 ošetří dvě mezery za sebou.

Úkol 7

Naprogramujte funkci Token parse(char string[]) pro převod prvního slova řetězce na hodnotu; typ Token má být tagged union.

typedef enum { TT_INT, TT_DOUBLE, TT_KEYWORD, TT_EMPTY, TT_ERROR } TokenType;
typedef enum { KW_IF, KW_FOR, KW_WHILE } Keyword;

typedef struct
{
	TokenType type;
	union
	{
		int     i;
		double  d;
		Keyword kw;
	} value;
} Token;

Pro případy TT_EMPTY a TT_ERROR se žádná položka unionu nepoužívá; to nevadí, tagged union to dovoluje.

static int is_space(char c) { return c==' ' || c=='\t' || c=='\n' || c=='\r'; }

Token parse(char string[])
{
	Token t = { TT_ERROR, {0} };

	//
	// najdeme prvni slovo
	//
	size_t start = 0;
	while (string[start] && is_space(string[start])) { start += 1; }
	if (!string[start]) { t.type = TT_EMPTY; return t; }

	size_t end = start;
	while (string[end] && !is_space(string[end])) { end += 1; }

	size_t len = end - start;
	char  *w   = string + start;

	//
	// klicova slova
	//
	if (len == 2 && !memcmp(w, "if", 2))    { t.type=TT_KEYWORD; t.value.kw=KW_IF;    return t; }
	if (len == 3 && !memcmp(w, "for", 3))   { t.type=TT_KEYWORD; t.value.kw=KW_FOR;   return t; }
	if (len == 5 && !memcmp(w, "while", 5)) { t.type=TT_KEYWORD; t.value.kw=KW_WHILE; return t; }

	//
	// znamenko a celociselna cast
	//
	size_t i = 0;
	int    neg = 0;
	if (w[0]=='-' || w[0]=='+') { neg = (w[0]=='-'); i = 1; }
	if (i == len) { return t; }              // samotne znamenko je chyba

	long   ip = 0;
	size_t digits = 0;
	while (i < len && w[i] >= '0' && w[i] <= '9') { ip = ip*10 + (w[i]-'0'); i += 1; digits += 1; }
	if (digits == 0) { return t; }

	if (i == len) { t.type = TT_INT; t.value.i = (int)(neg ? -ip : ip); return t; }

	//
	// desetinna cast
	//
	if (w[i] != '.') { return t; }
	i += 1;

	double frac = 0, scale = 1;
	size_t fdigits = 0;
	while (i < len && w[i] >= '0' && w[i] <= '9') { frac = frac*10 + (w[i]-'0'); scale *= 10; i += 1; fdigits += 1; }

	//
	// musime dojit az na konec slova a za teckou musi neco byt
	//
	if (i != len || fdigits == 0) { return t; }

	double v = (double)ip + frac/scale;
	t.type = TT_DOUBLE;
	t.value.d = neg ? -v : v;
	return t;
}

Podstatná je poslední kontrola i != len. Bez ní by "1.2.3" prošlo jako 1.2, protože bychom se po zpracování desetinné části nepodívali, zda ve slově ještě něco nezbylo.

Zpracování hodnoty vždy začíná kontrolou type:

Token t = parse(text);
switch (t.type)
{
	case TT_INT:     printf("%i\n", t.value.i); break;
	case TT_DOUBLE:  printf("%f\n", t.value.d); break;
	case TT_KEYWORD: /* ... */ break;
	case TT_EMPTY:   /* ... */ break;
	case TT_ERROR:   /* ... */ break;
}

Úkol 8

Upravte dump_mem tak, aby vypisovala adresu prvního bajtu na řádku, a přidejte možnost vypisovat bajty jako posloupnost bitů.

void dump_mem(void *mem, size_t size, int as_bits)
{
	unsigned char *bytes = mem;

	for (size_t i = 0; i < size; i += 1)
	{
		if (i % 8 == 0) { printf("%p  ", (void*)(bytes + i)); }

		if (as_bits)
		{
			for (int b = 7; b >= 0; b -= 1) { printf("%i", (bytes[i] >> b) & 1); }
			printf(" ");
		}
		else
		{
			printf("%.2X ", bytes[i]);
		}

		if (i % 8 == 7) { printf("\n"); }
	}
	if (size % 8) { printf("\n"); }    // dokoncime neuplny radek
}

Adresu tiskneme na začátku každého osmého bajtu. Poslední if dopíše konec řádku, pokud velikost není násobkem osmi — jinak by výpis neskončil novým řádkem.

Bitový výpis je stejný jako v úkolu 8 z kapitoly Základy: jdeme od nejvyššího bitu k nejnižšímu.

Úkol 9

Naprogramujte vlastní memcpy, memmove, memcmp a memset.

void *my_memcpy(void *dest, const void *src, size_t n)
{
	unsigned char       *d = dest;
	const unsigned char *s = src;
	for (size_t i = 0; i < n; i += 1) { d[i] = s[i]; }
	return dest;
}

void *my_memset(void *dest, int ch, size_t n)
{
	unsigned char *d = dest;
	for (size_t i = 0; i < n; i += 1) { d[i] = (unsigned char)ch; }
	return dest;
}

int my_memcmp(const void *lhs, const void *rhs, size_t n)
{
	const unsigned char *a = lhs, *b = rhs;
	for (size_t i = 0; i < n; i += 1)
	{
		if (a[i] != b[i]) { return a[i] - b[i]; }
	}
	return 0;
}

Zajímavá je jedině memmove, která musí fungovat i pro překrývající se oblasti. Kopíruje-li se doprava (dest > src), přepsali bychom při kopírování zepředu zdrojová data dřív, než je přečteme. Řešení je kopírovat v takovém případě odzadu:

void *my_memmove(void *dest, const void *src, size_t n)
{
	unsigned char       *d = dest;
	const unsigned char *s = src;

	if (d < s)
	{
		for (size_t i = 0; i < n; i += 1) { d[i] = s[i]; }
	}
	else
	{
		//
		// odzadu; idiom i-- > 0 funguje i pro bezznamenkovy typ
		//
		for (size_t i = n; i-- > 0; ) { d[i] = s[i]; }
	}
	return dest;
}

Všechny čtyři funkce převádějí void* na unsigned char*. To je jediné přetypování, které je podle normy vždy bezpečné.

Úkol 10

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

size_t size_of_float(void)
{
	float a[2];
	return (size_t)((unsigned char*)&a[1] - (unsigned char*)&a[0]);
}

Prvky pole leží v paměti hned za sebou, takže vzdálenost mezi adresami dvou sousedních prvků je velikost typu. Přetypováním na unsigned char* docílíme toho, že se rozdíl počítá v bajtech — bez něj by odčítání float* dalo 1, protože pointerová aritmetika už dělí velikostí typu.

Totéž s pointerovou aritmetikou bez pole:

size_t size_of_float2(void)
{
	float *p = 0;
	return (size_t)((unsigned char*)(p + 1) - (unsigned char*)p);
}

Tato varianta je ovšem formálně nedefinované chování — aritmetika s nulovým pointerem není povolena, i když v praxi funguje. Právě proto sizeof existuje.

Úkol 11

Napište funkci pro detekci endianity a pro převod mezi big endian a little endian.

int is_little_endian(void)
{
	unsigned int   x = 1;
	unsigned char *b = (unsigned char*)&x;

	//
	// je-li nejmene vyznamny bajt na nejnizsi adrese, jde o little endian
	//
	return b[0] == 1;
}

//
// pro 32-bitovy typ
//
unsigned int byte_swap(unsigned int x)
{
	return ((x & 0x000000FFu) << 24)
	     | ((x & 0x0000FF00u) <<  8)
	     | ((x & 0x00FF0000u) >>  8)
	     | ((x & 0xFF000000u) >> 24);
}

Pro 0x12345678 vrátí byte_swap hodnotu 0x78563412.

Detekce funguje proto, že se na paměť díváme jako na pole bajtů — což smíme jen přes unsigned char*. Maska a posuv v byte_swap přesouvají jednotlivé bajty; všechny literály jsou bezznaménkové (u), aby se nikde nemíchaly znaménkovosti.

Obecná varianta pro libovolný typ prohodí bajty na místě:

void reverse_bytes(void *p, size_t size)
{
	unsigned char *b = p;
	for (size_t i = 0; i < size / 2; i += 1)
	{
		unsigned char t = b[i];
		b[i] = b[size - 1 - i];
		b[size - 1 - i] = t;
	}
}

Úkol 12

Implementujte funkci, která vrátí nově alokovaný řetězec vzniklý spojením dvou řetězců.

char *concat(char *a, char *b)
{
	size_t la = strlen(a);
	size_t lb = strlen(b);

	char *ret = malloc(la + lb + 1);    // +1 pro ukoncovaci 0
	assert(ret);

	memcpy(ret, a, la);
	memcpy(ret + la, b, lb);
	ret[la + lb] = 0;

	return ret;
}

Nejčastější chybou je zapomenout + 1 na ukončovací nulu. Volající funkce musí zajistit uvolnění paměti. (Toto je u funkcí potřeba dokumentovat.)

char *s = concat("ahoj ", "svete");
printf("%s\n", s);
free(s);

Úkol 13

Implementujte zásobník pomocí dynamického pole.

void push(Stack *s, int v)
{
	if (s->top == s->cap)
	{
		int newcap = (s->cap == 0) ? 16 : s->cap * 2;
		int *p = realloc(s->data, (size_t)newcap * sizeof(int));
		assert(p);                  // pri neuspechu zustava s->data platne
		s->data = p;
		s->cap  = newcap;
	}
	s->data[s->top] = v;
	s->top += 1;
}

int pop(Stack *s)
{
	assert(s->top > 0);
	s->top -= 1;
	int v = s->data[s->top];

	//
	// zmensujeme az pri ctvrtinovem zaplneni, ne pri polovicnim:
	// jinak by stridave push a pop porad realokovaly
	//
	if (s->cap > 16 && s->top * 4 <= s->cap)
	{
		int newcap = s->cap / 2;
		int *p = realloc(s->data, (size_t)newcap * sizeof(int));
		assert(p);
		s->data = p;
		s->cap  = newcap;
	}
	return v;
}

void destroy_stack(Stack *s)
{
	free(s->data);
	s->data = 0;
	s->top  = 0;
	s->cap  = 0;
}

Návratovou hodnotu realloc vždy ukládáme do pomocné proměnné. Zápis s->data = realloc(s->data, ...) by při neúspěchu přepsal původní adresu nulou a paměť by se stala nedosažitelnou.

Podmínka s->cap > 16 zabrání tomu, abychom klesli pod počáteční velikost. Zmenšování až na čtvrtině je záměr: kdybychom zmenšovali na polovině, střídavé push/pop na hranici by realokovalo při každém volání.

Po destroy_stack nastavujeme data na 0, aby se struktura dala bezpečně použít znovu a aby případné druhé volání free nic neudělalo.

Úkol 14

Struktura struct matrix a funkce pro alokaci, inicializaci, násobení, tisk a dealokaci.

struct matrix
{
	int     rows;
	int     cols;
	double *data;    // row-major: prvek (i,j) je data[i*cols + j]
};

void allocate_matrix(struct matrix *m, int rows, int cols)
{
	m->rows = rows;
	m->cols = cols;
	m->data = malloc((size_t)rows * (size_t)cols * sizeof(double));
	assert(m->data);
}

void initialize_matrix_from_array(struct matrix *m, double *array)
{
	for (int i = 0; i < m->rows * m->cols; i += 1) { m->data[i] = array[i]; }
}

void destroy_matrix(struct matrix *m)
{
	free(m->data);
	m->data = 0;
	m->rows = 0;
	m->cols = 0;
}

struct matrix multiply_matrix(struct matrix a, struct matrix b)
{
	struct matrix c;
	allocate_matrix(&c, a.rows, b.cols);

	for (int i = 0; i < a.rows; i += 1)
	{
		for (int j = 0; j < b.cols; j += 1)
		{
			double s = 0;
			for (int k = 0; k < a.cols; k += 1)
			{
				s += a.data[i*a.cols + k] * b.data[k*b.cols + j];
			}
			c.data[i*c.cols + j] = s;
		}
	}
	return c;
}

void print_matrix(struct matrix a)
{
	for (int i = 0; i < a.rows; i += 1)
	{
		for (int j = 0; j < a.cols; j += 1) { printf("%8.2f", a.data[i*a.cols + j]); }
		printf("\n");
	}
}

Data ukládáme do jednorozměrného pole a index počítáme ručně jako radek * cols + sloupec (row-major, tedy řádky za sebou). Je to jednodušší i rychlejší než pole pointerů na řádky: celá matice je v jednom souvislém bloku, takže stačí jedno malloc a jedno free.

multiply_matrix vrací strukturu hodnotou. Kopíruje se přitom jenom trojice (rows, cols, data) — data samotná zůstávají tam, kde jsou. Volající musí výsledek uvolnit destroy_matrix.

Úkol 15

Naprogramujte char **split_string(char *str, char delimiter, int *n).

static char *clone_n(char *src, size_t n)
{
	char *r = malloc(n + 1);
	assert(r);
	memcpy(r, src, n);
	r[n] = 0;
	return r;
}

char **split_string(char *str, char delimiter, int *n)
{
	//
	// pocet casti je o jedna vetsi nez pocet oddelovacu
	//
	int parts = 1;
	for (char *p = str; *p; p += 1) { if (*p == delimiter) { parts += 1; } }

	char **ret = malloc((size_t)parts * sizeof(char*));
	assert(ret);

	int   idx   = 0;
	char *start = str;
	for (char *p = str; ; p += 1)
	{
		if (*p == delimiter || *p == 0)
		{
			ret[idx] = clone_n(start, (size_t)(p - start));
			idx += 1;
			start = p + 1;
			if (*p == 0) { break; }
		}
	}

	*n = parts;
	return ret;
}

Klíčem je, že počet částí spočítáme jedním průchodem, takže pole pointerů alokujeme jednou a nemusíme ho zvětšovat. Prázdné části vznikají přirozeně: p - start je pro dva oddělovače za sebou nula.

Uvolnění je dvoustupňové a je snadné na něj zapomenout:

void free_split(char **a, int n)
{
	for (int i = 0; i < n; i += 1) { free(a[i]); }   // jednotlive retezce
	free(a);                                        // pole pointeru
}

Přeložte si řešení s -fsanitize=address a ověřte, že po free_split nehlásí žádnou neuvolněnou paměť.

Úkol 16

Naprogramujte spojový seznam celých čísel, jehož uzly jsou alokovány pomocí malloc.

Node *list_push_front(Node *head, int key)
{
	Node *n = malloc(sizeof(Node));
	assert(n);

	n->key  = key;
	n->next = head;
	return n;        // novy uzel je novou hlavou
}

Node *list_find(Node *head, int key)
{
	for (Node *p = head; p; p = p->next)
	{
		if (p->key == key) { return p; }
	}
	return 0;
}

void list_print(Node *head)
{
	for (Node *p = head; p; p = p->next) { printf("%i ", p->key); }
	printf("\n");
}

void list_destroy(Node *head)
{
	while (head)
	{
		Node *next = head->next;    // adresu si musime ulozit PRED uvolnenim
		free(head);
		head = next;
	}
}

Podmínka p v cyklu využívá toho, že nulový pointer odpovídá nepravdě, takže konec seznamu poznáme bez explicitního porovnání.

V list_destroy je klíčové pořadí. Zápis free(head); head = head->next; by četl z už uvolněné paměti — tedy nedefinované chování, které AddressSanitizer hlásí jako use-after-free.

Nejzajímavější je odstranění uzlu, protože se liší podle toho, zda mažeme hlavu, nebo prvek uvnitř. Oběma případům se lze vyhnout pointerem na pointer:

Node *list_remove(Node *head, int key)
{
	//
	// link ukazuje na misto, kam je zapsana adresa aktualniho uzlu
	// na zacatku je to promenna head, pozdeji polozka next predchudce
	//
	Node **link = &head;

	while (*link)
	{
		if ((*link)->key == key)
		{
			Node *dead = *link;
			*link = dead->next;     // prepojime, at uz je to hlava nebo ne
			free(dead);
			break;
		}
		link = &(*link)->next;
	}
	return head;
}

Kdo si na Node ** netroufá, může napsat i přímočařejší variantu se zvláštní větví pro hlavu — je delší, ale funguje stejně.

Úkol 17

Naprogramujte strukturu, která si udržuje pole řetězců a umí ho zvětšovat.

void list_add(String_List *l, char *s)
{
	//
	// nejdriv misto na dalsi pointer
	//
	if (l->count == l->cap)
	{
		int newcap = (l->cap == 0) ? 4 : l->cap * 2;
		char **p = realloc(l->items, (size_t)newcap * sizeof(char*));
		assert(p);
		l->items = p;
		l->cap   = newcap;
	}

	//
	// potom klon samotneho retezce, vcetne ukoncovaci nuly
	//
	size_t len   = strlen(s);
	char  *clone = malloc(len + 1);
	assert(clone);
	memcpy(clone, s, len + 1);

	l->items[l->count] = clone;
	l->count += 1;
}

void list_destroy(String_List *l)
{
	for (int i = 0; i < l->count; i += 1) { free(l->items[i]); }   // kazdy retezec
	free(l->items);                                               // a pole pointeru
	l->items = 0;
	l->count = 0;
	l->cap   = 0;
}

Volání free je count + 1. Alokací je totiž také count + 1: jedna na pole pointerů a jedna na každý klonovaný řetězec. To je stejná dvoustupňová struktura jako u split_string z úkolu 15 a je to nejčastější místo, kde v této kapitole vzniká únik paměti.

Zdvojnásobování kapacity znamená, že je počet realokací logaritmický v počtu prvků. Např. po pěti voláních list_add je count roven 5 a cap roven 8 (kapacita rostla 0 → 4 → 8).

Klonujeme len + 1 bajtů, abychom vzali i ukončovací nulu. Právě tím se tato struktura liší od typu String z úkolu 6, který si délku pamatuje a nulu nepotřebuje.

Klonování je podstatné: kdybychom uložili rovnou předaný pointer, záviselo by to na tom, jak dlouho původní řetězec žije. Pro řetězcový literál by to prošlo, pro lokální pole nikoliv.

Keyboard shortcuts

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