"substi" - Náhrada symbolů v textu Programová vrstva SUBSTI (jejíž úmyslně pitvorné jméno je zkratkou z anglického "substitute") je jediným programovým modulem v jazyku "C" substi.c s příslušným hlavičkovým souborem (tedy headerem) substi.h, definujícím rozhraní pro použití funkcí tohoto programového bloku. Pomineme-li tři z celkových čtyř funkcí rozhraní (inicializace, ukončení, ladění), zbude jedna jediná - hlavní, provozní. Má jen jeden funkční argument typu (char const *) a návratovou hodnotu téhož typu. Této funkci jsou zmíněným argumentem předávány řádky textu (jsou to samozřejmě znakové řetězce ukončené znakem '\0'; většinou se však jedná o jednotlivé řádky nějakého textového souboru, ponechme proto termín "řádky textu" v tomto kontextu platným). Řádky jsou zpracovávány dvojím způsobem: (1) Buď je na řádku obsažena definice zástupného symbolu (tedy dvojice řetězců symbol+hodnota ve smyslu identifikátor + skutečný text, který je identifikátorem zastoupen), (2) nebo se na řádku textu nacházejí aplikace (tedy symboly, které popisovaná funkce nahradí - chcete-li substituuje - přiřazenými hodnotami). Je to vlastně z textových editorů notoricky známé "SEARCH & REPLACE". Rozdíl je jen v tom, že předpis určující co čím nahradit je obsažen v textu. Zde je v podobě několika řádků fiktivního textového souboru ilustrace obou možných případů:
V některých speciálních případech jsou hodnoty pro význam výsledného textu obsahově nezajímavé. Postačí, když se od sebe navzájem liší. Typickým, případem může být číslování. Obvykle nezáleží na tom, zda položka nějakého seznamu má pořadové číslo 17. Důležité je pouze to, aby byla jednoznačně odlišena (měla jiné číslo) od položky číslo 26. Na to je zde pamatováno formou automatického generování symbolů, u nichž se smíříme s tím, že jejich hodnotami budou řetězce reprezentující dekadická čísla zvyšující se s krokem 1. Zde je vysvětlující příklad:
Řádek textu
$$BASE. 11
vytvoří bázový symbol (vždy končící znakem '.') s přiřazenou hodnotou 11 (je to číslo, ne textový řetězec). Při následném automatickém generování symbolů je z čísla 11 vytvořen textový řetězec "11" a hodnota bázového symbolu je inkrementována.
Další výskyt bázového symbolu doplněný příslušným "suffixem" automaticky generuje nový symbol (POZOR! Bez definice s úvodní dvojicí "$$"). Proto v následujícím řádku
Výsledné pořadí: $BASE.ALFA, $BASE.BETA, $BASE.GAMA, $BASE.DELTA, $BASE.BETA, $BASE.EPSILON.
jsou provedeny substituce s výsledkem
Výsledné pořadí: 11, 12, 13, 14, 12, 15.
Tato programátorská hříčka však nevznikla proto, aby demonstrovala techniku náhrady textových řetězců. Vyhledat v paměti skupinu znaků a při pozitivním nálezu text přemístit do jiné paměťové oblasti se současnou náhradou některých částí textu, na tom opravdu není nic zajímavého. Jestli zde něco stojí za pozornost, je to správa paměti potřebné pro takové manipulace.
Má-li programová vrstva SUBSTI pracovat podle předpokladů deklarovaných předchozími odstavci, musí mít k dispozici dostatečné množství paměťového prostoru. V něm si uchovává průběžně vytvářený a aktualizovaný seznam dvojic symbol+hodnota a zároveň musí mít dostatečné místo pro sestavení nové podoby zpracovávaného textu (vstupní text není činností tohoto programového bloku nijak modifikován).
Na obrázku vlevo je typické rozmístění paměti. Ke snazšímu pochopení je vhodné nahlédnout do zdrojového textu substi.c. Symboly končící písmenem 's' (tedy substis, mempools a sympairs) jsou jména struktur, které se v modulu vyskytují. Symboly začínající tečkou (znakem '.') jsou vybrané členy těchto struktur, důležité z hlediska vazeb mezi paměťovými oblastmi. Místa s popisem "free space" jsou samozřejmě volná místa v paměti pro následné použití.
Struktura substis sdružuje základní proměnné nutné k fungování vrstvy SUBSTI. Pointer na tuto strukturu je handle, který spolu s funkcemi této vrstvy tvoří spojení (interface) s programovými bloky používajícími tuto vrstvu. Pro téma této kapitoly je tato struktura vcelku nezajímavá, neboť z pohledu na vazby mezi paměťovými oblastmi obsahuje pouze pointery na začátky dvou zřetězených seznamů .poolp a .pairp a ty už za zmínku rozhodně stojí.
Pozn.: Zajímavostí je umístění této struktury v paměti. Netvoří úplný začátek, jak by se podle zvyklostí očekávalo, ale je pouhým článkem řetězu paměťových oblastí, které má na starost podřízená programová vrstva vlastnící strukturu mempools.
Se strukturou mempools je spojena podřízená programová vrstva, která s popisovanou problematikou (náhrada symbolů v textu) nemá nic společného. Jejím posláním je pouze v případě potřeby "někde sehnat" požadované množství paměti. V inicializační funkci hlavní vrstvy SUBSTI je tato struktura (jako paměťové místo) vytvořena/inicializována jako první. Prvním "klientem" této podvrstvy je hlavní vrstva SUBSTI s požadavkem na přidělení paměti pro strukturu substis (viz poznámka na konci předchozího odstavce). Struktura mempools je hlavičkou jednoho článku řetězu paměťových oblastí, které jsou postupně podle potřeby k sobě navzájem napojovány. Základní vlastností při přidělování nové paměti je stanovená velikost pro každý jednotlivý článek řetězu: požadavek je vždy zaokrouhlen na nejbliží vyšší násobek 8KB. Bylo by mimořádně nešikovné každých 37 bytů alokovat z "heapu". Krok 8KB je hodnota vhodná jak z hlediska zpracování textu, tak s ohledem na správu systémových prostředků. Ze struktury jsou zobrazeny dva významné pointery: .linkp je vazbou na další článek řetězu a .memp je ukazatel na první byte paměti, kterou lze přidělit. U druhého článku je čára naznačující vazbu zakončena čtverečkem místo šipky. Je to značka konce řetězu, příslušný pointer má hodnotu NULL.
Pozn.: Při malých nárocích na paměť (zpracovávaný textový soubor zabírá jen několik KB a obsahuje krátké řádky) je typické, že celý zřetězený seznam paměťových bloků má pouze jediný (na obrázku nahoře umístěný) článek.
Z prostorů "free space" držených vrstvou pro postupné přidělování paměti (mempools, viz minulý odstavec) jsou "ukrajovány" menší kousky tvořící seznam dvojic zástupných symbolů a odpovídající hodnot reprezentovaných strukturou sympairs. Seznam je opět zřetězením struktur a má se strukturou a funkcemi obsluhujícími postupné přidělování paměti společnou ještě jednu důležitou vlastnost: nemá žádný vztah k ostatním programovým vrstvám obsaženým v modulu substi.c. S nadsázkou se dá říci, že umí bezvadně hromadit a následně podle různých kritérií vyhledávat dvojice symbol+hodnota, neví ale proč to dělá!
Jak stojí výše, dvě programové podvrstvy reprezentované strukturami mempools resp. sympairs o sobě navzájem ani o jíném programovém bloku "nic nevědí". Jejich vzájemnou interakci zařídí až hlavní vrstva (se strukturou substis). Ta ví přesně, co celý modul dělá, nezabývá se však "drobnostmi" typu kde vzít příslušně velký kus paměti nebo jak se "přehrabovat" v řetězech různých paměťových oblastí. Na to jí slouží zmíněné dvě podvrstvy.
Z hlediska čistě objektového pojetí (to nemá nic společného s C++ :-) by bylo "košer" celý modul substi.c rozdělit přinejmenším na tři samostatné moduly (asi by se jmenovaly substimain.c, substimempool.c a substisympair.c). Byla by tím jasně prokázána nezávislost podvrstev manipulujících s paměťovými oblastmi. To by s sebou přineslo potřebu zavést příslušné headery (pokračujme ve vymýšlení jmen: substimempool.h a substisympair.h), které by definovaly rozhraní pro hlavní vrstvu (soubor substimain.c). Pokud by se mělo jít ještě dál ve stopách metodiky OOP (zapouzdření, polymorfismus, abstrakce, znáte ty pojmy, že?) a hlavní vrstva by neznala skladbu struktur mempools resp. sympairs, musely by vziknout patrně další funkce, které by celé řešení těmto metodikám přizpůsobily. Cílem vytvoření této legrácky není ukázka zpracování textu (jak bylo výše řečeno), ani po formální stránce stylově čisté objektové řešení. Má-li tento programový blok být něčím zajímavý, je to především úporná snaha o jednoduchost vytvořeného kódu a šetrné zacházení s pamětí. A za to technologický ústupek v podobě umístění do jediného souboru .c rozhodně stojí. Je třeba si uvědomit, že z pohledu generovaného strojového kódu je vcelku lhostejné, jestli se nějaká vazba neuskuteční protože to nejde (z důvodu nějaké syntaktické zábrany à la C++, absence příslušných programových prostředků, ...), nebo se taková konstrukce do programu nenapíše. Výsledný kód bude v obou případech stejný. Pokud tedy přineseme nepatrný kousek formální čistoty na oltář technologii, budeme odměněni efektivnější optimalizací strojového kódu generovaného překladačem (jednoduché funkce třídy uložení static se často vkládají i tehdy, nejsou-li opatřeny deklarátorem inline) i výrazně menším počtem nevyřízených externálů pro linker (opět se to týká funkcí static, pro něž se externály negenerují).
Drobnou zajímavostí této kapitoly je, že skutečné přidělení a uvolnění paměti prováděné touto vrstvou vůbec není v rámci jejích funkcí řešeno. Očekávané funkce malloc() a free() nejsou volány přímo, ale prostřednictvím indirekce (viz macro substi_initial() v headeru substi.h). Jakým způsobem bude správa paměti pro účely SUBSTI implementována je zcela na uživateli.
Pojďme se na závěr podívat, co konkrétně obsahuje header substi.h jako rozhraní pro použití programové vrstvy SUBSTI. Není toho mnoho a to je dobře. Jsou zde především prototypy tří provozních funkcí (provozních proto, že jejich použití pro správnou činnost SUBSTI nezbytné)...
extern substihndp_t substi_initial0(substiallocfncp_t,
substifreefncp_t,
int __symbolc,
int __commentc);
extern char const *substi_operate(substihndp_t,
char const *__linep);
extern void substi_leave(substihndp_t);
...a jedné funkce spíš ladicí, bez které by se celá paráda asi obešla. Použití by našla snad jedině v případě potřeby "pohrabování se" v seznamu dvojic symbol+hodnota nezávisle na vnitřních funkcích vrstvy SUBSTI.
extern int substi_list(substihndp_t,
substilistfncp_t,
void *__userdata);
Dále definice nějakých typů a konstant, ale to nemá smysl zde komentovat, vše je jasné při pohledu do headeru. Výčtem prototypů funkcí je zde pouze ilustrováno obvyklé použití:
Součástí "balení" je také jednoduchý zkušební program obsažený v modulu test.c, který ilustruje použití popisovaného výtvoru lépe, než další zbytečná slova. Co je pro to potřeba? Předně sestavit testovací program. Na to bohatě postačí prostý příkaz na "command-line":
# cc -O3 -fomit-frame-pointer -Wall -Wno-parentheses -o substi substi.c test.c
Pro ty, kteří mají ambice "prokrokovat to debuggrem", je doporučen ještě jednodušší:
# cc -g -Wall -Wno-parentheses -o substi substi.c test.c
Dalším krokem by měla být tvorba nějakého souboru s testovacím obsahem. I na to je pamatováno. Pro začátek postačí ten přiložený, test.txt. Můžeme tedy rovnou přikročit k vlastnímu použití testovacího programu. K dispozici jsou tři různé varianty:
# ./substi <test.txt
# ./substi d <test.txt
# ./substi l <test.txt
Pokud se ze začátku posledních pěti řádků souboru test.txt odstraní znaky komentáře '#', je předvedeno i rušení (ve smyslu vypuštění ze seznamu) již vložených dvojic symbol+hodnota.
Pokud náhodou některý z čtenářů vytrval až k této větě, lze ho úspěšně podezírat z potřeby položit otázku: "Ale teď vážně, je ta bejkárna k něčemu?". Odpověď na takovou otázku není zrovna snadná, ale za pokus to stojí...
Pro ukázku "skutečného použití" je tu ještě jeden soubor s obsahem pro testování. Je to bitnum-rpn.txt. Má co do činění s interpreterem RPN instrukcí RPN32 (nebo starší RPNPROC). Aby byl obsah souboru bitnum-rpn.txt pro funkce některého z interpreterů "stravitelným", je nejprve třeba "propasírovat" zkrz SUBSTI. Vrstva SUBSTI mění řádky čtené ze souboru bitnum-rpn.txt tak, že některé části textu nahradí jinými (symboly zastupující čísla návěští a paměťových registrů a přímé číselné konstanty), jiné bez náhrady vypustí (to se týká komentářů). Výstupem je "čistý" RPN kód, se kterým si RPN32 nebo RPNPROC hravě poradí.
Zde je návod, jak to vyzkoušet. Autor těchto řádků však naléhavě prosí případné čtenáře (a "vyzkušitele" v jedné osobě) o bezbřehou dávku shovívavosti. RPN kód obsažený v souboru bitnum-rpn.txt totiž počítá procentuální vyjádření počtu bitů zadané vstupní hodnoty vzhledem k (rovněž zadané) šířce slova, ve kterém se hodnota nachází. Pokud si někdo myslí, že větší hloupost se nedala vymyslet, není pravdě daleko. Kromě nedostatečné míry tvůrčí invence autorovy je zde ještě jedna omluva (ne-li hned polehčující okolnost): jde přeci o to, aby bylo vidět automatické generování dvou posloupností čísel použitých pro rozlišení dvou entit - návěští a paměťových registrů.
Nejprve původní obsah:
# more bitnum-rpn.txt
Potom zpracovaný text:
# ./substi <bitnum-rpn.txt
Výpis seznamu dvojic symbol+hodnota:
# ./substi l <bitnum-rpn.txt
Už se to dá předhodit interpreteru a zkontrolovat výpis:
# ./substi <bitnum-rpn.txt | rpn32 -L | more
# ./substi <bitnum-rpn.txt | rpnproc -ll - | more
A nakonec spustit výpočet kolik procent zabere hodnota 0x7E ve 24-bitovém slově:
# ./substi <bitnum-rpn.txt | rpn32 - 24 0x7e
# ./substi <bitnum-rpn.txt | rpn32 -mxia -r - 24 0x7e
# ./substi <bitnum-rpn.txt | rpnproc 24 0x7e -
Je to 25%. Uf, to byla šichta!!!
Následující tabulka nabízí ke stažení všechny soubory, na které se předchozí text odkazuje.
| Soubor | Komentář |
|---|---|
| substi.h | Header s rozhraním pro použití programové vrstvy SUBSTI |
| substi.c | Programový modul s výkonnými funkcemi |
| test.c | Modul pro vytvoření testovacího programu |
| test.txt | Soubory s testovacím obsahem |
| bitnum-rpn.txt | |
| RPN32 | Sekce "Download" některého z interpreterů RPN instrukcí |
| RPNPROC |