Jednostavni fajl sistem
Napisati program koji simulira jednostavan fajl sistem. Fajl sistem treba da podržava kreiranje, brisanje i prikazivanje fajlova i direktorijuma.
Hierarhija fajl sistema treba da bude predstavljena kao binarno stablo, gde svaki čvor može biti fajl ili direktorijum. Direktorijumi mogu sadržavati druge fajlove i direktorijume. Binarno stablo treba da bude implementirano pomoću LCRS (engl. Left-Child Right-Sibling) reprezentacije:
- Levo dete predstavlja prvo dete čvora (prvi fajl ili direktorijum unutar direktorijuma).
- Desno dete predstavlja sledećeg brata čvora (sledeći fajl ili direktorijum na istom nivou).
Na primer, sledeća struktura fajl sistema:
/
|-- home
| |-- user
| | |-- document.txt
| | `-- photo.jpg
| `-- guest
| `-- readme.md
`-- etc
`-- config.cfg
biće predstavljena kao binarno stablo sa LCRS reprezentacijom:
/
/
home
/ \
user etc
/ \ /
document.txt guest config.cfg
\ /
photo.jpg readme.md
Ulaz
Sa standardnog ulaza se učitavaju komande za upravljanje fajl sistemom. Svaka komanda je na posebnoj liniji i može biti jedna od sledećih:
mkdir <path>: Kreira novi direktorijum na zadatoj putanji.touch <path> <size>: Kreira novi fajl na zadatoj putanji sa zadatom veličinom u bajtovima.ls <path>: Prikazuje sadržaj direktorijuma na zadatoj putanji.size <path>: Prikazuje veličinu fajla ili direktorijuma na zadatoj putanji.count <path>: Prikazuje broj fajlova i direktorijuma unutar direktorijuma na zadatoj putanji.help: Prikazuje listu dostupnih komandi.exit: Završava rad programa.
Pretpostaviti da su sve putanje apsolutne i počinju sa /. Fajl sistem počinje sa samo jednim korenskim direktorijumom /. Pored toga predpostaviti da imena fajlova i direktorijuma neće biti duža od 255 karaktera, a da putanje neće biti duže od 1024 karaktera. Takođe, pretpostaviti da veličina fajla neće biti negativan broj.
Izlaz
Na standardni izlaz se ispisuju rezultati izvršavanja komandi:
ls <path>: Ispisuje imena svih fajlova i direktorijuma unutar zadatog direktorijuma, svaki na posebnoj liniji. Ako je direktorijum prazan, ne ispisuje ništa.size <path>: Ispisuje veličinu fajla ili ukupnu veličinu svih fajlova unutar direktorijuma.count <path>: Ispisuje broj fajlova i direktorijuma unutar zadatog direktorijuma.help: Ispisuje listu dostupnih komandi:Dostupne komande: mkdir <path> - Kreira novi direktorijum touch <path> <size> - Kreira novi fajl sa zadatom veličinom ls <path> - Prikazuje sadržaj direktorijuma size <path> - Prikazuje veličinu fajla ili direktorijuma count <path> - Prikazuje broj fajlova i direktorijuma unutar direktorijuma help - Prikazuje listu dostupnih komandi exit - Završava rad programa- Za ostale komande (
mkdir,touch), ne ispisuje ništa ako je komanda uspešno izvršena. U slučaju greške (npr. nepostojeća putanja, pokušaj kreiranja fajla u nepostojećem direktorijumu, itd.), ispisuje odgovarajuću poruku o grešci na standardni izlaz za greške.
Primer
stdin
mkdir /home
mkdir /home/wukong
touch /home/wukong/file1.txt 100
touch /home/wukong/file2.txt 200
mkdir /home/wukong/docs
touch /home/wukong/docs/doc1.pdf 300
ls /home/wukong
size /home/wukong
count /home/wukong/docs
exit
stdout
file1.txt
file2.txt
docs
600 bytes
1
Primer
stdin
mkdir /usr
touch /usr/bin.exe 500
touch /usr/lib.dll 300
mkdir /usr/local
ls /usr
size /usr
count /usr/local
mkdir /etc
touch /etc/config.cfg 150
mkdir /etc/logs
touch /etc/logs/log1.txt 50
ls /etc
size /etc
count /etc/logs
ls /
exit
stdout
bin.exe
lib.dll
local
800 bytes
0
config.cfg
logs
200 bytes
1
usr
etc
Rešenje
stablo_genericko.h
#ifndef __STABLO_GENERICKO_H__
#define __STABLO_GENERICKO_H__
#include <stdio.h>
#include <stdlib.h>
#include "stablo_podatak.h"
typedef enum
{
OK,
NEDOVOLJNO_MEMORIJE,
NEMA_ELEMENATA,
POSTOJI_ELEMENAT
} status;
typedef struct cvor_stabla
{
Data podatak;
struct cvor_stabla *levo;
struct cvor_stabla *desno;
} cvor_stabla;
typedef cvor_stabla *Stablo;
Stablo novi_cvor_stabla(const Data *podatak);
status inicijalizuj_stablo(Stablo *s);
status dodaj_u_stablo(Stablo *s, const Data *podatak,
int (*poredi)(const Data *, const Data *));
status pronadji(Stablo s, const Data *trazeno, Data **nadjeno,
int (*poredi)(const Data *, const Data *));
int broj_elemenata(Stablo s);
void ispisi_stablo(Stablo s);
void obrisi_stablo(Stablo *s);
#endifstablo_podatak.h
#ifndef __STABLO_PODATAK_H
#define __STABLO_PODATAK_H
#include <stdlib.h>
#define MAX_FILENAME_LENGTH 256
typedef enum {
FILE_NODE,
DIRECTORY_NODE
} DataType;
typedef struct {
char name[MAX_FILENAME_LENGTH];
size_t size; // valid only if type is FILE_NODE
} DataFileInfo;
typedef struct {
DataType type;
DataFileInfo info;
} Data;
Data napravi_fajl(const char* name, size_t size);
Data napravi_direktorijum(const char* name);
void dodeli(Data* dest, const Data* src);
void ispisi_podatak(const Data* data);
#endifmain.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stablo_podatak.h"
#include "stablo_genericko.h"
#define COMMAND_LENGTH 16
#define PATH_LENGTH (8 * MAX_FILENAME_LENGTH)
/* Ispisuje listu dostupnih komandi */
static void help()
{
printf("Dostupne komande:\n");
printf("mkdir <path> - Kreira novi direktorijum\n");
printf("touch <path> <size> - Kreira novi fajl sa zadatom velicinom\n");
printf("rm <path> - Brise fajl ili direktorijum\n");
printf("ls <path> - Prikazuje sadrzaj direktorijuma\n");
printf("size <path> - Prikazuje velicinu fajla ili direktorijuma\n");
printf("count <path> - Prikazuje broj elemenata u direktorijumu\n");
printf("help - Prikazuje listu dostupnih komandi\n");
printf("exit - Zavrsava rad programa\n");
}
/* Funkcija kreira root direktorijum fajl sistema, vraca status */
static status napravi_root(Stablo *fs)
{
Data root_podatak = napravi_direktorijum("/");
*fs = novi_cvor_stabla(&root_podatak);
if (*fs == NULL) {
return NEDOVOLJNO_MEMORIJE;
}
return OK;
}
/* Funkcija pronalazi dete sa zadatim imenom u roditeljskom cvoru,
* vraca pokazivac na dete ili NULL ako nije pronadjen
*/
static Stablo pronadji_dete(Stablo roditelj, const char* filename)
{
if (roditelj == NULL) {
return NULL;
}
// Krecemo se kroz listu dece
Stablo dete = roditelj->levo;
// Trazimo dete sa zadatim imenom
while (dete != NULL && strncmp(dete->podatak.info.name, filename, MAX_FILENAME_LENGTH) != 0) {
dete = dete->desno;
}
return dete;
}
/* Funkcija dodaje dete roditeljskom cvoru sa zadatim podatkom, vraca status */
static status dodaj_dete(Stablo roditelj, const Data *podatak, Stablo *dete)
{
if (*dete != NULL) {
return POSTOJI_ELEMENAT;
}
*dete = novi_cvor_stabla(podatak);
if (*dete == NULL) {
return NEDOVOLJNO_MEMORIJE;
}
if (roditelj->levo == NULL) { // roditelj nema decu
roditelj->levo = *dete; // prvo dete
} else { // roditelj ima decu
// Pronadji poslednje dete
Stablo poslednji = roditelj->levo;
while (poslednji->desno != NULL)
{
poslednji = poslednji->desno;
}
poslednji->desno = *dete; // dodaj dete na kraj liste
}
return OK;
}
/* Funkcija kreira novi direktorijum na zadatoj putanji, vraca status */
static status mkdir_komanda(Stablo *fs, const char* path)
{
if (path == NULL) {
return NEMA_ELEMENATA;
}
Stablo trenutni = *fs;
char* path_copy = strdup(path); // prave se kopija jer strtok menja string
char* token = strtok(path_copy, "/"); // razdvaja putanju na tokene po '/'
while (token != NULL) {
char* sledeci = strtok(NULL, "/"); // cuva sledeci token
Stablo dete = pronadji_dete(trenutni, token);
if (sledeci == NULL) { // poslednji token
// Kreiraj novi direktorijum
Data dir = napravi_direktorijum(token);
status s = dodaj_dete(trenutni, &dir, &dete);
if (s != OK) {
free(path_copy);
return s;
}
} else { // nije poslednji token
if (dete == NULL) { // dete nije pronadjeno
free(path_copy);
return NEMA_ELEMENATA;
}
if (dete->podatak.type != DIRECTORY_NODE) { // dete nije direktorijum
free(path_copy);
return NEMA_ELEMENATA;
}
}
// Nastavi pretragu
trenutni = dete;
token = sledeci;
}
free(path_copy);
return OK;
}
/* Funkcija prikazuje sadrzaj direktorijuma na zadatoj putanji, vraca status */
static status ls_komanda(Stablo *fs, const char* path)
{
if (path == NULL) {
return NEMA_ELEMENATA;
}
Stablo trenutni = *fs;
char* path_copy = strdup(path);
char* token = strtok(path_copy, "/");
while (token != NULL) {
Stablo dete = pronadji_dete(trenutni, token);
if (dete == NULL) { // dete nije pronadjeno
free(path_copy);
return NEMA_ELEMENATA;
}
if (dete->podatak.type != DIRECTORY_NODE) { // dete nije direktorijum
free(path_copy);
return NEMA_ELEMENATA;
}
trenutni = dete;
token = strtok(NULL, "/");
}
free(path_copy);
// Ispisi decu trenutnog direktorijuma
Stablo dete = trenutni->levo;
while(dete != NULL) {
ispisi_podatak(&dete->podatak);
dete = dete->desno;
}
return OK;
}
/* Funkcija kreira novi fajl na zadatoj putanji, vraca status */
static status touch_komanda(Stablo *fs, const char *path, const size_t size)
{
if (*fs == NULL) {
return NEMA_ELEMENATA;
}
Stablo trenitni = *fs;
char *path_copy = strdup(path);
char *token = strtok(path_copy, "/");
while (token != NULL) {
char *sledeci = strtok(NULL, "/");
Stablo dete = pronadji_dete(trenitni, token);
if (sledeci == NULL) { // token jeste poslednji
// Kreiraj novi fajl
Data file_podatak = napravi_fajl(token, size);
status s = dodaj_dete(trenitni, &file_podatak, &dete);
if (s != OK) {
free(path_copy);
return s;
}
} else { // token nije poslednji
if (dete == NULL) { // dete nije pronadjeno
free(path_copy);
return NEMA_ELEMENATA;
}
if (dete->podatak.type != DIRECTORY_NODE) { // dete nije direktorijum
free(path_copy);
return NEMA_ELEMENATA;
}
}
trenitni = dete;
token = sledeci;
}
free(path_copy);
return OK;
}
/* Rekurzivna funkcija koja racuna ukupnu velicinu fajla ili direktorijuma */
static size_t ukupna_velicina(cvor_stabla* cvor)
{
if (cvor == NULL) {
return 0;
}
// Ako je fajl, vrati njegovu velicinu
if (cvor->podatak.type == FILE_NODE) {
return cvor->podatak.info.size;
}
// Ako je direktorijum, rekurzivno saberi velicine dece
size_t total_size = 0;
cvor_stabla* dete = cvor->levo;
while (dete != NULL) {
total_size += ukupna_velicina(dete);
dete = dete->desno;
}
return total_size;
}
/* Funkcija prikazuje velicinu fajla ili direktorijuma na zadatoj putanji, vraca status */
static status size_komanda(Stablo* fs, const char* path)
{
if (path == NULL) {
return NEMA_ELEMENATA;
}
Stablo trenutni = *fs;
char* path_copy = strdup(path);
char* token = strtok(path_copy, "/");
while (token != NULL) {
Stablo dete = pronadji_dete(trenutni, token);
if (dete == NULL) { // dete nije pronadjeno
free(path_copy);
return NEMA_ELEMENATA;
}
trenutni = dete;
token = strtok(NULL, "/");
}
free(path_copy);
// Izracunaj ukupnu velicinu
size_t total_size = ukupna_velicina(trenutni);
printf("%zu bytes\n", total_size);
return OK;
}
static int count_komanda(Stablo* fs, const char* path)
{
if (path == NULL) {
return NEMA_ELEMENATA;
}
Stablo trenutni = *fs;
char* path_copy = strdup(path);
char* token = strtok(path_copy, "/");
while (token != NULL) {
Stablo dete = pronadji_dete(trenutni, token);
if (dete == NULL) { // dete nije pronadjeno
free(path_copy);
return NEMA_ELEMENATA;
}
if (dete->podatak.type != DIRECTORY_NODE) { // dete nije direktorijum
free(path_copy);
return NEMA_ELEMENATA;
}
trenutni = dete;
token = strtok(NULL, "/");
}
free(path_copy);
// Prebroj decu trenutnog direktorijuma
int count = 0;
Stablo dete = trenutni->levo;
while (dete != NULL) {
count++;
dete = dete->desno;
}
printf("%d\n", count);
return OK;
}
int main(void)
{
Stablo fajl_sistem;
status s = inicijalizuj_stablo(&fajl_sistem);
if (s != OK) {
exit(EXIT_FAILURE);
}
s = napravi_root(&fajl_sistem);
if (s != OK) {
obrisi_stablo(&fajl_sistem);
exit(EXIT_FAILURE);
}
char command[COMMAND_LENGTH];
char path[PATH_LENGTH];
int running = 1;
while (running) {
scanf("%s", command);
if (strcmp(command, "mkdir") == 0) {
scanf("%s", path);
s = mkdir_komanda(&fajl_sistem, path);
if (s != OK) {
fprintf(stderr, "Greska pri kreiranju direktorijuma na putanji: %s\n", path);
}
} else if (strcmp(command, "touch") == 0) {
size_t size;
scanf("%s %zu", path, &size);
s = touch_komanda(&fajl_sistem, path, size);
if (s != OK) {
fprintf(stderr, "Greska pri kreiranju fajla na putanji: %s\n", path);
}
} else if (strcmp(command, "ls") == 0) {
scanf("%s", path);
s = ls_komanda(&fajl_sistem, path);
if (s != OK) {
fprintf(stderr, "Greska pri ispisu sadrzaja direktorijuma na putanji: %s\n", path);
}
} else if (strcmp(command, "size") == 0) {
scanf("%s", path);
s = size_komanda(&fajl_sistem, path);
if (s != OK) {
fprintf(stderr, "Greska pri dobijanju velicine za putanju: %s\n", path);
}
} else if (strcmp(command, "count") == 0) {
scanf("%s", path);
s = count_komanda(&fajl_sistem, path);
if (s != OK) {
fprintf(stderr, "Greska pri brojjanju elemenata za putanju: %s\n", path);
}
} else if (strcmp(command, "help") == 0) {
help();
} else if (strcmp(command, "exit") == 0) {
running = 0;
} else {
fprintf(stderr, "Nepoznata komanda: %s\n", command);
}
}
obrisi_stablo(&fajl_sistem);
exit(EXIT_SUCCESS);
}stablo_genericko.c
#include "stablo_genericko.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
Stablo novi_cvor_stabla(const Data *podatak)
{
cvor_stabla *novi = malloc(sizeof(cvor_stabla));
if (novi == NULL)
return NULL;
dodeli(&(novi->podatak), podatak);
novi->levo = NULL;
novi->desno = NULL;
return novi;
}
status inicijalizuj_stablo(Stablo* s)
{
*s = NULL;
return OK;
}
status dodaj_u_stablo(Stablo* s, const Data* podatak,
int (*poredi)(const Data*, const Data*))
{
cvor_stabla* tmp;
cvor_stabla* novi = novi_cvor_stabla(podatak);
if (novi == NULL)
return NEDOVOLJNO_MEMORIJE;
novi->levo = NULL;
novi->desno = NULL;
if (*s == NULL) {
*s = novi;
return OK;
}
tmp = *s;
while (1) {
if (poredi(podatak, &(tmp->podatak)) <= 0) {
if (tmp->levo == NULL) {
tmp->levo = novi;
return OK;
}
else
tmp = tmp->levo;
}
else {
if (tmp->desno == NULL) {
tmp->desno = novi;
return OK;
}
else
tmp = tmp->desno;
}
}
return OK;
}
status pronadji(Stablo s, const Data* trazeno, Data** nadjeno,
int (*poredi)(const Data*, const Data*))
{
if (s == NULL)
return NEMA_ELEMENATA;
if (poredi(trazeno, &(s->podatak)) == 0) {
*nadjeno = &(s->podatak);
return OK;
}
if (poredi(trazeno, &(s->podatak)) < 0)
return pronadji(s->levo, trazeno, nadjeno, poredi);
return pronadji(s->desno, trazeno, nadjeno, poredi);
}
int broj_elemenata(Stablo s)
{
return s == NULL ?
0 :
broj_elemenata(s->levo)+1+broj_elemenata(s->desno);
}
void ispisi_stablo(Stablo s)
{
if (s != NULL) {
ispisi_stablo(s->levo);
ispisi_podatak(&(s->podatak));
ispisi_stablo(s->desno);
}
}
void obrisi_stablo(Stablo* s)
{
if (*s != NULL) {
obrisi_stablo(&((*s)->levo));
obrisi_stablo(&((*s)->desno));
free(*s);
*s = NULL;
}
}stablo_podatak.c
#include <stdio.h>
#include <string.h>
#include "stablo_podatak.h"
Data napravi_fajl(const char* name, size_t size)
{
Data data;
data.type = FILE_NODE;
strncpy(data.info.name, name, MAX_FILENAME_LENGTH);
data.info.size = size;
return data;
}
Data napravi_direktorijum(const char* name)
{
Data data;
data.type = DIRECTORY_NODE;
strncpy(data.info.name, name, MAX_FILENAME_LENGTH);
data.info.size = 0;
return data;
}
void dodeli(Data* dest, const Data* src)
{
dest->type = src->type;
strncpy(dest->info.name, src->info.name, MAX_FILENAME_LENGTH);
dest->info.size = src->info.size;
}
void ispisi_podatak(const Data* data)
{
printf("%s\n", data->info.name);
}