HW05: Find
Autor zadání Peter Stanko
Úprava Martin Pulec Martin Piatka Miroslav Jaroš Jakub Plhal
Odevzdávané soubory *.c *.h
Začátek odevzdávání viz diskusní fórum
Další odevzdání navíc do 2024-05-08 24:00
Konec odevzdání 2024-05-15 24:00
Vzorová implementace /home/kontr/pb071/hw05/find5
Opravy v zadání 2024-05-01 11:59 2
Kostra úkolu

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 používateľa, či skupiny, ktorá súbor vlastní. Viac o nástroji find(1) sa môžete dočítať na Wikipédii,

Ú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é použí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)

  • Môžete sa spoľahnúť, že dĺžky mien súborov a ciest neprekročia limity stanovené systémom.

Je vhodné, aby ste pre minimalizáciu spotreby pamäte nepoužívali konštanty! Použite len toľko pamäte, koľko reálne potrebujete.
Môže sa vám hodiť súbor limits.h.

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 spustil. 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 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 správanie docielite použitím vhodnej funkcie z rodiny stat(3) (viď man 3 fstatat).

  3. 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). Upresnenie nižšie.

    -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 používateľmi pod Linuxom (Aisa) použite funkcie v hlavičkovom súbore pwd.h. Hľadanie na základe mena používateľa je case-sensitive. Vo Windowse je možné používať tieto funkcie v prostredí WSL (Doporučené)

    -f NUM

    Hľadanie súborov s minimálnou vzdialenosťou NUM od koreňového adresára. Implicitná hodnota je 0. Upresnenie nižšie.

    -t NUM

    Hľadanie súborov s maximálnou vzdialenosťou NUM od koreňového adresára. Implicitná hodnota je ∞. Upresnenie nižšie.

    -a

    Do prehľadávania zahŕňa aj skryté súbory. V Linuxe skryté súbory 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:

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

  • -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ď.

Š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 (na veľkosti písmen nezáleží). 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 súboru (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.

-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

Predpokladajme existenciu testovacej štruktúry

/home/xuser/
│
├── folder_empty
├── folder_a
│   ├── image.jpg [owner: user1, size: 1.2MB]
│   └── folder_b
│       ├── notes.txt [owner: user1, size: 300KB]
│       ├── draft.docx [owner: user2, size: 800KB]
│       └── lnk -> /home/xuser/folder_a/image.jpg
│
│
├── folder_c
│   ├── text.txt [owner: user2, size: 500KB]
│   └── projects_folder
│       └── code.c [owner: user2, size: 600KB]
│
└── tmp_file.c [owner: user1, size: 2MB]

potom nasledujúce príkazy vrátia nasledujúce výstupy:

# implicitné zoradenie podľa mena súboru, maximálna vzdialenosť 2
$ find5 /home/xuser/ -t 2
/home/xuser/folder_a/image.jpg
/home/xuser/folder_c/text.txt
/home/xuser/tmp_file.c
# explicitné zostupné zoradenie podľa veľkosti súboru, maximálna vzdialenosť 2
$ find5 /home/xuser/ -s s -t 2
/home/xuser/tmp_file.c
/home/xuser/folder_a/image.jpg
/home/xuser/folder_c/text.txt
# hľadanie súborov s minimálnou vzdialenosťou 3, implicitné zoradenie podľa mena súboru
$ find5 /home/xuser/ -f 3
/home/xuser/folder_c/projects_folder/code.c
/home/xuser/folder_a/folder_b/draft.docx
/home/xuser/folder_a/folder_b/notes.txt
$ find5 /home/xuser/folder_empty      # hľadanie v prázdnom adresári, nič nevypisuje
$ find5 /home/xuser/ -u "root"    # ak žiaden súbor v podstrome nesplňuje podmienku, nič nevypisuje

Bonusové rozšírenie

Dlhé prepínače (5 bodov)

Päť bonusových bodov je 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

Sparse súbory (5 bodov)

Dalších päť bonusových bodov je možné získať, ak bude program podporovať vyhľadávanie sparse súborov.

Sparse súbor (alebo aj riedky súbor) je š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
Pri testovaní na Aise využívajte adresár /data/$(whoami) namiesto /home/$(whoami).

Táto úloha sa zaoberá prácou na súborovom systéme a teda pravdepodobne budete potrebovať vytvárať súbory rôznych veľkostí a vlastností, proti ktorým budete spúšťať ako svoju implementáciu, tak aj tú referenčnú. Majte ale na mysli, že /home/ je zdieľaný súborový systém vo vzdialenom úložisku, ktorý je používaný všetkými používateľmi siete FI MU. CVT tento disk pravidelne zálohuje a jeho výpadok by mohol ohroziť napríklad funkčnosť klientskych počítačov v sieti. Teda /home/ nie je pre takéto testovanie vhodný. Naproti tomu, máte prístupný aj súborový systém v /data/, ktorý nie je zálohovaný a je na ňom výrazne vyššia kvóta.

Viac informácií o kvótach a úložisku sieti FI si môžete prečítať v technickej dokumentácii FI.

Opravy v zadání

Fix example outputs
2024-05-01 11:59 Jakub Plhal
Clarify arguments to -t and -f options
2024-05-01 11:59 Jakub Plhal

Fix example outputs

3596682 2024-05-01 11:59 Jakub Plhal 
 -244,4 +244,4  potom nasledujúce príkazy vrátia nasledujúce výstupy:
 ----
-# implicitné zoradenie podľa mena súboru, maximálne zanorenie 1
-$ find5 /home/xuser/ -t 1
+# implicitné zoradenie podľa mena súboru, maximálna vzdialenosť 2
+$ find5 /home/xuser/ -t 2
 /home/xuser/folder_a/image.jpg
 -252,4 +252,4  $ find5 /home/xuser/ -t 1
 ----
-# explicitné zostupné zoradenie podľa veľkosti súboru, maximálne zanorenie 1
-$ find5 /home/xuser/ -s s -t 1
+# explicitné zostupné zoradenie podľa veľkosti súboru, maximálna vzdialenosť 2
+$ find5 /home/xuser/ -s s -t 2
 /home/xuser/tmp_file.c
 -260,4 +260,4  $ find5 /home/xuser/ -s s -t 1
 ----
-# hľadanie súborov s minimálnym zanorením 2, implicitné zoradenie podľa mena súboru
-$ find5 /home/xuser/ -f 2
+# hľadanie súborov s minimálnou vzdialenosťou 3, implicitné zoradenie podľa mena súboru
+$ find5 /home/xuser/ -f 3
 /home/xuser/folder_c/projects_folder/code.c

Clarify arguments to -t and -f options

318936a 2024-05-01 11:59 Jakub Plhal 
 -144,6 +144,6  link:https://docs.microsoft.com/en-us/windows/wsl/about[WSL] (Doporučené)
 `-f NUM`::
-Hľadanie súborov s minimálnym zanorením `NUM` adresárov. Implicitná hodnota je 0. <>
+Hľadanie súborov s minimálnou vzdialenosťou NUM od koreňového adresára. Implicitná hodnota je 0. <>
 
 `-t NUM`::
-Hľadanie súborov s maximálnym zanorením `NUM` adresárov. Implicitná hodnota je ∞. <>
+Hľadanie súborov s maximálnou vzdialenosťou NUM od koreňového adresára. Implicitná hodnota je ∞. <>