Důležité!

Pozorně si přečtěte pokyny k výuce během rektorského volna!

HW05: Find

Odevzdávání úkolu je ukončeno.
Autor zadání Peter Stanko
Úprava Martin Piatka Martin Pulec
Odevzdávané soubory upřesněno na konci zadání
Začátek odevzdávání viz diskusní fórum
Bonus za brzké odevzdání 2020-05-24 01:00
Konec odevzdání 2020-05-26 24:00
K úkolu žádná kostra není

Doplnenie zadania:

2020-05-07 22:30

Upresnenie fungovania prepínačov -f a -t.

2020-05-21 14:20

Upresnenie typu súborov vo výpise.

2020-05-22 10:00

Upresnenie, že -s s radí podľa veľkosti súborov.

2020-05-23 22:30

Posun skorého deadline.

Predstavenie úlohy

V tejto úlohe si skúsite naprogramovať jednoduchú alternatívu k unixovému nástroju find(1). , ktorý slúži na rekurzívne prehľadávanie adresárov v systéme. Vyhľadávať môžete na základe mena súboru, dátumu vytvorenia, prípon alebo konkrétneho užívateľa, či skupiny, ktorá súbor vlastní. Viac o nástroji find sa môžete dočítať na Wiki,

Úloha je zameraná na prácu so súbormi a adresármi s využitím štandardu POSIX.

Vy sa však zameriate len na časť funkcionality nástroja find. Váš program bude schopný nájsť súbor na základe časti jeho mena alebo vlastníka. V prípade, že viacero súborov bude spĺňať podmienky vyhľadávania, cesty vypíšete utriedené. Cesty k súborom budú implicitne utriedené na základe mena, teda lexikograficky.

Zadanie

Úlohou je napísať program, ktorý pri spustení dostane argumenty na príkazovom riadku. Jedným z argumentov môže byť počiatočný adresár, od ktorého sa program postupne zanára a vyhľadáva súbory. Ďalšími argumentami budú prepínače a ich atribúty, ktoré budú podrobne opísané nižšie. Na ich spracovanie je vhodné použiť funkciu getopt(3) (ak sa rozhodnete funkciu použiť, je potreba použiť hlavičkový súbor getopt.h).V prípade, že nie sú zadané žiadne parametre, program začne vypisovať všetky súbory v podadresároch od aktuálneho adresára. Program implicitne ignoruje skryté súbory a adresáre. V Unix-like systémoch skryté súbory a adresáre začínajú bodkou.

V prípade viacerých podmienok pre vyhľadávanie musia byť splnené všetky, čo znamená, že medzi podmienky hľadania vložíme logický AND.

$ find5 -n obr -u root
./obraz.jpg
./obrazok.jpg

Program v ukážke hľadá súbory, ktoré obsahujú v názve obr a zároveň sú vlastnené užívateľom root.

Terminológia

Nech prehľadávanie adresára /home/xuser uvedeného ako argument programu narazí na súbor public/.file.jpg. V zadaní rozlišujeme tieto termíny:

meno (názov) súboru

posledná časť cesty bez adresárov, tzn. .file.jpg.

cesta k súboru

reťazec, ktorý vznikne spojením cesty k prehľadávanému adresáru a ceste k nájdenému súboru, tzn. /home/xuser/public/.file.jpg.

Ošetrenie chýb

  • Ak je zadaný chybný prepínač, prepínač vyžadujúci argument žiadny nedostane, alebo má argument chybný formát, program vypíše zmysluplnú chybovú hlášku a skončí s nenulovou návratovou hodnotou.

  • Ak počiatočná cesta neexistuje, neukazuje na adresár alebo nie je možné ju otvoriť a čítať, program vypíše chybovú hlášku a skončí s nenulovou návratovou hodnotou.

  • Ak nie je možné počas prehľadávania čítať niektorý adresár alebo zistiť vlastnosti objektu súborového systému, program vypíše chybovú hlášku a pokračuje ďalej v prehľadávaní.

Všetky chyby vypisujte na štandardný chybový výstup.

Chybová hláška pre nesprávny prepínač alebo parameter prepínača musí stručne popísať, o ktorý parameter ide. Môžete vypísať aj krátku nápovedu k používaniu programu.

Ostatné chybové hlášky, na ktoré program narazí pri prehľadávaní adresárovej štruktúry, musia byť vo výstupe každá na samostatnom riadku.

Limity (pre Aisu)

  • Meno súboru aj s príponou môže mať maximálne 255 znakov.

  • Cesta k súboru môže mať maximálne 4096 znakov.

Je vhodné, aby ste pre minimalizáciu spotreby pamäte nepoužívali vyššie spomenuté konštanty! Použite len toľko pamäte, koľko reálne potrebujete.

Požiadavky

  1. Jeden z argumentov bude cesta k počiatočnému adresáru. Môže byť relatívna alebo absolútna. Tento argument je voliteľný. Ak nie je zadaný, prehľadávať sa začína od aktuálneho adresára, v ktorom sa program sputil. Tento adresár sa označuje aj ako '.'. Cesta nesmie začínať znakom -, k takýmto argumentom sa program vždy správa ako k prepínačom. Na poradí argumentov programu nezáleží.

  2. Program bude akceptovať nasledujúce prepínače:

    -n ATTR

    Hľadanie na základe podreťazca v mene súboru, kde ATTR je hľadaný podreťazec. Meno súboru neobsahuje cestu (jednotlivé podadresáre). Reťazce sa porovnávajú case-sensitive, čiže záleží na veľkosti písmen.

    -s f | s

    Triedenie výpisu ciest k súborom na základe celej cesty (f) alebo veľkosti (s).

    -m MASK

    Hľadanie súboru na základe prístupových práv, kde MASK je vyjadrenie týchto práv v osmičkovej sústave. O tom ako fungujú sa dá dočítať tu, pomôže aj kalkulačka.

    -u USER

    Hľadanie súboru na základe mena používateľa, kde USER je používateľovo meno. Pre prácu s užívateľmi pod Linuxom (aisa) použite funkcie v hlavičkovom súbore pwd.h. Hľadanie na základe mena užívateľa je case-sensitive. Vo Windowse je možné používať tieto funkcie pomocou WSL (Doporučené) alebo cygwin-u.

    -f NUM

    Hľadanie súborov s minimálnym zanorením NUM adresárov. Upresnenie nižšie.

    -t NUM

    Hľadanie súborov s maximálnym zanorením NUM adresárov. Upresnenie nižšie.

    -a

    Hľadá aj v skryté súbory a podadresáre V Linuxe skryté súbory a adresáre začínajú bodkou.

    -0

    Pri výpise namiesto '\n' použije '\0'

    -h

    Zobrazí nápovedu na štandardný chybový výstup a skončí. Žiadne súbory sa nehľadajú.

    Upresnenie fungovania -f a -t: tieto prepínače ohraničujú minimálnu a maximálnu vzdialenosť uzlov od koreňa, ktoré program vypíše. Koreň je sám od seba vo vzdialenosti 0. Takže napríklad,

    • -t 1 vypíše súbory vo vzdialenosti 0 (implicitná hodnota pre -f) a 1 od koreňového adresára; vo vzdialenosti 0 je však len koreňový adresár, ten sa preto nevypíše,

    • -f 1 -t 1 vypíše súbory vo vzdialenosti 1 od koreňového adresára; výstup bude rovnaký ako pre -t 1,

    • -f 1 -t 2 vypíše súbory vo vzdialenosti 1 a 2 od koreňového adresára, teda potomkov a prapotomkov,

    • -f 2 vypíše súbory vo vzdialenosti aspoň 2, teda v potomkoch koreňového adresára, prapotomkoch, atď. (hodnota -t je implicitne ∞).

  3. (Preformulovaná poznámka na samostatný bod.) Program pracuje len s (regulárnymi) súbormi a adresármi, pričom vypisuje len súbory. Ostatné objekty súborového systému sa vypísať nesmú. Toto chovanie docielite použitím vhodnej funkcie z rodiny stat(3) (viď man 3 fstatat).

Testovacia súborová štruktúra priložená ku kostre obsahuje iba adresáre (môžu byť skryté) a obyčajné súbory (môžu byť skryté).

Špeciálne súbory si môžete vyrobiť napríklad príkazmi ln(1), mkfifo(1) alebo mknod(1).

Implicitné usporiadanie

Ak nie je zadaný žiadny prepínač, ktorý špecifikuje usporiadanie výstupu, program usporiada riadky výstup podľa mena súboru vzostupne. Usporiadanie je case-insensitive. V prípade rovnakého mena súboru sa použije lexikografické usporiadanie podľa celej cesty k súboru, avšak toto usporiadanie už je case-sensitive (na veľkosti písmen záleží).

$ ./find5 tree
tree/files/image.jpg
tree/files/image.png    # porovnanie na základe mena súboru (prípona)
tree/files/image1.jpg   # porovnanie na základe mena (image.jpg < image1.jpg)
tree/pics/image1.jpg    # porovnanie na základe celej cesty (files > pics)

Explicitné usporiadanie

Usporiadanie súborov na výstupe je možné upraviť prepínačom -s.

(Presnejšia formulácia a oprava.)

-s s

Cesty sa usporiadajú zostupne podľa veľkosti súborov (tj. od najväčšieho po najmenší). Súbory s rovnakou veľkosťou sa usporiadajú podľa implicitného radenia.

-s f

Cesty sa usporiadajú vzostupne lexikograficky s ohľadom na veľkosť písmen (case-sensitive) podľa celej cesty k súboru (čiže od a po z).

Iné hodnoty parametra pre prepínač -s nie sú povolené.

V prípade usporiadania podľa veľkosti sa môže stať, že porovnávané súbory budú mať rovnakú veľkosť. V takom prípade sa ďalej usporiadajú podľa implicitného pravidla na usporiadanie.

Príklady

$ find5 /home/xuzivatel/tmp/
/home/xuzivatel/tmp/a/123.jpg
/home/xuzivatel/tmp/b/236.txt
/home/xuzivatel/tmp/b/abc.xml
/home/xuzivatel/tmp/tmp_file.c
$ find5 ./prazdny_adresár      # hľadanie v prázdnom adresári, nič nevypisuje
$ find5 ./obrazky -u "root"    # ak žiaden súbor v podstrome nesplňuje podmienku, nič nevypisuje

Bonusové rozšírenie: dlhé prepínače (1 bod)

Jeden bonusový bod bude možné získať, ak bude program podporovať aj dlhé verzie prepínačov. Na ich implementáciu je vhodné použiť getopt_long(3)

Dlhý prepínač Ekvivalentný krátky prepínač

--name ATTR

-n ATTR

--sort HOW

-s HOW

--mask MASK

-m MASK

--user USER

-u USER

--mindepth N

-f N

--maxdepth N

-t N

--all

-a

--nullnewline

-0

--help

-h

Bonusové rozšírenie: sparse súbory (1 bod)

Druhý bonusový bod bude možné získať, ak bude program podporovať vyhľadávanie sparse súborov.

Sparse súbory (alebo aj riedke súbory) sú špeciálny typ súboru, ktorý umožňuje prázdnu časť súboru pri uložení na disk vynechať a tým ušetriť miesto. Typicky sa používajú pri ukladaní obrazu disku. Viac detailov vrátane návodu ako takýto súbor vytvoriť nájdete na Wikipédii.

Program bude po zadaní prepínača -S (prípadne --sparse) vyhľadávať len sparse súbory.

Na odhalenie sparse súboru si vystačíte s informáciami, ktoré vráti stat(2)

Poznámky

Odovzdávané súbory

V tejto úlohe si môžete úlohu rozdeliť na časti tak, ako uznáte za vhodné. Požiadavky sú:

  • Riešenie musí pozostávať len zo súborov s príponami .c alebo .h, iné súbory budú ignorované.

  • Súbory zanorené v adresároch alebo súbory s prefixom test budú ignorované.

Posledný bod má za cieľ umožniť vám napísať si k riešeniu vlastné testy, ktoré si môžete držať v repozitári spolu s riešením; buď vo vlastnom adresári, alebo ako súbory s prefixom test.

Hoci nie je zakázané všetko napísať len do main.c, výsledok bude takmer určite príliš dlhý a neprehľadný, čo vám opravujúci vráti na prepracovanie. Preto sa pokúste využiť túto voľnosť v zadaní na precvičenie dekompozície.
CMake
Ak používate na kompiláciu riešenia CMake, nezabudnite po každej zmene CMakeLists.txt znovu pustiť cmake.

Kompilácia

V tejto úlohe môžete používať funkcie zo štandardu POSIX.1-2008. Toto povolíte pri kompilácii programu pridaním prepínača pri kompilácii:

gcc -std=c99 -pedantic -D_POSIX_C_SOURCE=200809L ...

Pre vypracovanie bonusu s dlhými prepínačmi bude navyše povolené používať aj funkciu getopt_long(), ktorá je rozšírením GNU, a teda vyžaduje preklad s prepínačom -D_GNU_SOURCE.

Ak program kompilujete pomocou Makefile, tieto prepínače patria do premennej CPPFLAGS (prepínače pre preprocesor). V CMakeList.txt ich pridajte k cieľu pomocou target_compile_definitions().

Tieto makrá nesmiete definovať priamo v zdrojovom kóde!

Na čo si treba dať pozor

  • V OS Windows sú cesty case-insensitive, takže File.txt a file.txt v ňom predstavujú rovnaké názvy súborov. Tento fakt neplatí pre systémy založené na UNIXe (napr. Linux, ktorý beží na Aise).

  • Funkcia na čítanie adresára readdir(3) a funkcia zistenie mena vlastníka súboru getpwuid(3).

Vzorové riešenie

/home/kontr/pb071/hw05/find5

Na Aise tiež nájdete jednoduchú testovaciu adresárovú štruktúru:

/home/kontr/pb071/hw05/tree/

Túto štruktúru si môžete tiež stiahnuť a rozbaliť u seba:

wget https://www.fi.muni.cz/pb071/hw/homework-05/hw05-treestructure-2020.tar.gz
tar -zx -p -S -f hw05-treestructure-2020.tar.gz

Ak chcete súbory rozbaliť s originálnymi UID a GID, pustite vyššie uvedený príkaz s právami superpoužívateľa, napr. pomocou sudo.

Verzia pre ZIP dostupná nie je, pretože tento formát neumožňuje zachovať UNIXové oprávnenia súborov správne.

Vzorové riešenie má limit na maximum otvorených adresárov. Je to z dôvodu, ak by sa niekto pokusil spúšťať program nad zbytočne veľkou adresárovou štruktúrou. Maximum je 100 otvorených adresárov.