Každý z vás už by mal poznať funkcie
void *malloc(size_t size);
void free(void *ptr);

a aj to, na čo slúžia. Tieto sú k dispozícii v štandardnej knižnici jazyka C. Ak potrebujeme pracovať s dynamickými dátovými štruktúrami, tak takéto funkcie potrebujeme. Ak nechceme (alebo nemôžeme) obmedziť maximálnu veľkosť (zoznamu, frontu, grafu ap.) staticky, tieto funkcie nám umožňujú vytvoriť program tak, aby príslušné štruktúry rástli podľa aktuálnej potreby počas behu programu. V rámci prvého zadania sa máte možnosť zoznámiť s tým, ako sa takýto malloc a free implementuje. Je to tradičná predohra ku ostatným zadaniam na tomto predmete. Slúži na nácvik a zlepšovanie remeselných zručností.

Vašou úlohou je implementovať funkcie:
void *dsa_alloc(unsigned size);
void dsa_free(void *ptr);
void dsa_init(void *ptr, unsigned size);

Môžete (ale nemusíte) definovať aj iné pomocné funkcie okrem hore uvedených troch. Funkcia dsa_alloc má poskytovať podobné služby ako štandardný malloc. T.j. programátor zadá veľkosť úseku pamäte (v bajtoch), ktorý chce alokovať a táto funkcia mu vráti buď ukazovateľ na začiatok kúsku voľnej pamäte, ktorý sa podarilo alokovať, alebo NULL keď nie je možné alokovať kus pamäte uvedenej veľkosti. Funkcia dsa_free má mať podobný efekt ako free funkcia z štandardnej knižnice. Ak pred prvým volaním funkcie dsa_alloc je potrebné spravovaný región pamäte nejako inicializovať, túto inicializáciu sústreďte do funkcie dsa_init.

Pre realizáciu zadania som využil statické pole typu int, ktoré slúži ako klasická pamäť (ďalej len pamäť). Pamäť je postupným alokovaním a uvoľňovaním rozdelená do segmentov. Pre prácu s pamäťou, respektíve s jednotlivými segmentmi je vyčlenená réžia, čiže akési metadata, ktoré sú uložené v hlavičke segmentu. Pamäť obsahuje aj jeden segment bez hlavičky, a to konkrétne prvé štyri bajty pamäte, ktoré obsahujú informáciu o veľkosti pamäte. Táto informácia sa inicializuje vo funkcii dsa_init. V hlavičkách si uchovávam informácie o jednotlivých segmentoch. Jej veľkosť je 8 bajtov, t.j. dve čísla typu integer. Je rozdelená na dve časti. Prvú časť tvorí jedno číslo, ktoré obsahuje informáciu o naplnenosti, čiže indikuje či sa pole alokovalo, ale nie, respektíve bolo uvoľnené. V mojom prípade 0 indikuje prázdny segment a 1 naplnený. Druhá časť je tvorená opäť jedným číslom, v ktorom je uložená informácia o veľkosti segmentu.

Funkcia dsa_init okrem spomínaného uloženia veľkosti pamäti vytvorí jeden základný segment, ktorému uloží informáciu o veľkosti voľných dát a obsadenosť pamäti nastaví na voľnú. Funkcia sa vykoná ihneď, čiže časová zložitosť je minimálna O(1).

Obrázok 1 Pamäť po vykonaní funkcie dsa_init

Funkcia *dsa_alloc prechádza pamäťou a hľadá voľný segment s želanou veľkosťou (v najhoršom prípade O(n) časová zložitosť). Ak nájde vyhovujúci segment, zapíše do hlavičky informáciu o veľkosti a zmení indikátor naplnenosti na stav naplnený. Ak je veľkosť želaného segmentu menšia ako veľkosť prázdneho segmentu, do ktoré sa ide zapísať, funkcia rozdelí pôvodný segment na dva, kde do prvého dá želané dáta a ďalej vytvorí nový segment o veľkosti pôvodného segmentu mínus veľkosť želaného a veľkosti hlavičky pre nový segment. V prípade, že zadáme veľkosť väčšiu ako je veľkosť samotnej pamäte, funkcia ihneď vráti smerník na NULL. Tak isto ak sa v pamäti nenachádza žiadny segment s dostatočným voľným priestorom, funkcia vracia opäť NULL. Zaujímavosťou je aj prípad, ak zadaná veľkosť nie je väčšia ako voľný segment, no napriek tomu je dostatočne veľká a bráni vytvoreniu ďalšieho segmentu (fragmentácia), aj vtedy sa tento segment preskočí a hľadá ďalší, ktorý vyhovuje.

Obrázok 2 Jednoduchá rotácia (jedným smerom)

Funkcia dsa_free slúži na uvoľňovanie segmentov pamäti. Triviálnosť riešenia spočíva v tom, že funkcia modifikuje danému segmentu, ktorý chceme uvoľniť, informáciu o naplnenosti t.j. zmení ho hodnotu naplnenosti z 1 na 0. Zároveň sa pozrie na nasledujúci segment, či je prázdny. V prípade, že je voľný, zlúči tieto dva segmenty. Zároveň prehľadá pamäť a nájde predchádzajúci segment a v prípade, že je prázdny, tak ho zlúči s uvoľňovaným segmentom, čím sa rapídne zvýši časová náročnosť funkcie (v najhoršom prípade O(n) časová zložitosť). Táto operácia by sa dala obísť, ak by sme do hlavičiek segmentov ukladali aj informáciu o umiestnení predchádzajúceho segmentu. To by nám však zvýšilo nároky na pamäť a operácie s hlavičkami.

Obrázok 3 Dvojitá rotácia (jedným smerom)

Program je implementovaný v jazyku C.

Testovanie bolo vykonávané po krokoch, to znamená, že po pridaní každej novej funkcie, alebo časti funkcie, som túto funkciu otestoval, či pracuje správne a zároveň som otestoval, či nenarušila chod programu – regresívne testovanie. Ak nastal nejaký problém, program som opravil a opätovne testoval. Nakoniec som program otestoval zverejnenými testovacími kódmi, tzv. stress-testami. Program prešiel všetkými testami bez spadnutia, aj pod OS Windows, gcc aj Linuxom.