Filesystem in memoria

di il
11 risposte

Filesystem in memoria

Salve, sono nuovo del forum e vi ringrazio in anticipo per l'aiuto.
Volevo un vostro parere sull'implementazione di una specie di filesystem che risiede in memoria e ha delle funzioni che devono avere una determinata complessità. È un progetto universitario che porto avanti da fine agosto ma ancora oggi a poche settimane dalla pubblicazione non sono riuscito a giungere ad una conclusione corretta. Vi allego delle immagini che descrivono il progetto perché è abbastanza specifico. Qui viene spiegato





Ora, io ne ho provate di tutti i colori.
Inizialmente ho implementato un albero (come nel disegno, non binario) che è costituito da nodi di questo tipo
struct node {
node* padre;
node* figlio;
node* destro;
node* sinistro;
}
Ogni volta che si crea un figlio lo si fa puntare da child, i figli seguenti dello stesso padre sono identificati dal puntatore destro o sinistro del figlio e dal figlio stesso che quando verrà creato avrà come padre il nodo che effettivamente l'ha creato.

Chiaramente solo l'albero non avrebbe la complessità richiesta dato che dovrei scorrere ogni volta un bel po' di nodi per trovare il giusto posizionamento di quello nuovo, quindi creo una hashmap che mappa stringhe, cercando in internet trovo che la funzione hash djb2
unsigned long
    hash(unsigned char *str)
    {
        unsigned long hash = 5381;
        int c;

        while (c = *str++)
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

        return hash;
    }
funziona piuttosto bene e decido di usarla, il problema è che restituisce valori troppo elevati come index dell'array e dovrei creare una hashmap troppo grande che mi creerebbe problemi per eccesso di memoria. Decido quindi che l'albero così non funziona per l'impossibilità di avere le complessità spaziali palesemente eccessive.

Provo a controllare se un albero binario potrebbe funzionare in questo caso, ragionando però mi viene da pensare che quest ultimo aggiunge in basso i nuovi nodi, qualora dovessi creare tantissimi nodi l'albero sarebbe molto profondo, e se a quel punto dovessi creare una cartella con lunghezza di percorso pari a 1, la funzione create() e find() e tutte le altre non sarebbero della complessità richiesta.

A questo punto mi rimane poco da fare, mi viene in mente un'ultima struttura di cui già dubitavo, si tratta di un nodo con già 1024 puntatori a figli salvati in un array della struttura del nodo. Il problema è, anche qui, che nel momento in cui io debba accedere a una specifica cartella nella complessità specificata dovrei passarmi tutti gli array dei padri e anche dei figli che portano a quella directory. Sorge quindi ancora il bisogno di una funzione hash che mi restituisca in qualche nano secondo l'index dell'array a cui devo accedere in sequenza per raggiungere la path. In questo caso però dovrei avere una funzione hash che lavora su 1024 caselle dell'array, e ogni figlio ha sempre la stessa funzione che calcola l'index per il suo array di figli. La mia paura è che il programma ecceda ancora nell'utilizzo della memoria. Dopo queste ipotesi fallimentari ammetto di trovarmi in difficoltà e non essendomi mai successo inizio ad essere abbastanza demoralizzato.

Posso avere un vostro parere sul giusto metodo di implementazione e di algoritmi che mi permetterebbe di avere delle complessità del genere?
Non riesco proprio a farmi venire in mente altre strutture dati efficienti che possano funzionare.

11 Risposte

  • Re: Filesystem in memoria

    ...
  • Re: Filesystem in memoria

    Sono al corrente che non esistono solo alberi binari, principalmente il primo esempio che ho scritto serviva a creare qualcosa di simile ad un albero con N rami, poi ho provato con i Btree (ma usarli con le stringhe è piuttosto complicato per me) e anche i Trie ma non hanno la complessità richiesta.
    Per quanto riguarda la creazione della funzione della mappa ti do ragione ed ho parecchi problemi, purtroppo il nostro programma universitario ci ha solo spiegato cosa sono le mappe e a cosa servono ma non ci hanno mai fatto masticare del codice per avere degli esempi.

    La creazione dell'albero di per se non è un problema, anzi, ne ho provati di tutti i tipi. Il problema che mi trovo davanti è la funzione della hashmap, perché evidentemente la funzione hash che ho utilizzato è sconveniente in questo caso perché torna valori int (che sarebbero gli index a cui accedere della hashmap) troppo alti, sopra al 1000000000 per intenderci, e una hashmap così grande sarebbe inutile dato che circa l'80% di essa rimarrebbe vuota. La creazione di linked list per le collisioni era implicita perché ormai possiamo darla per scontata questa implementazione necessaria.

    Non riesco a capire bene cosa mi suggerisci di fare, quello che ho capito dal tuo suggerimento è che devo lasciare perdere l'albero (?) e usare una mappa formata da nomi e flag che identificano se si tratta di file o directory. Principalmente era la prima idea che ho avuto del progetto, come ho scritto sopra, solo che la mappa conteneva il puntatore al nodo dell'albero invece che contenere il nodo stesso.
    Però a questo punto dovrei comunque allocare uno spazio bello grande per l'immagazzinamento di tutte queste caselle, e una gestione dinamica del problema la vedo troppo complessa per un problema del genere, specialmente perché non ci è mai stato detto che ce ne sarebbe stato il bisogno. L'ultimo problema inoltre rimane la funzione hash della mappa, forse è il mio più grande problema. Il mio libro è vuoto, senza codice e in internet trovo delle funzioni hash di cui non capisco l'implementazione (Come il CRC32) specialmente per le stringhe che sarebbero in questo caso la 'key' della hashmap.

    Puoi stare tranquillo, lo svolgerò da solo farmelo fare da qualcun altro sarebbe una sconfitta peggiore

    Per ora ho scritto per bene la manipolazione dell'input in modo che riesca a leggere sequenzialmente il comando, la path completa tipo /dir/dir2/file, la path superiore che in questo caso sarebbe /dir/dir2 e ogni singolo nome nella path, quindi un array multidimensionale di stringhe che in questo caso restituisca dir dir2 e file.
  • Re: Filesystem in memoria

    ...
  • Re: Filesystem in memoria

    Ciao migliorabile, anche io avrei lo stesso problema. Potrei contattarti in privato per farti vedere il mio codice e chiederti una delucidazione? grazie in anticipo.
  • Re: Filesystem in memoria

    L'array multidimensionale sarebbe l'array che logicamente costituisce la mappa. Basta pensare una mappa come tante caselle che contengono <nome, tipo> come dicevi all'inizio.
    Inoltre penso tu non abbia letto per nulla la dimensione massima dell'albero e la complessità delle funzioni richiesta. Già con la root potrei avere 1024 cartelle, ora ogni singola cartella di queste può averne altre 1024 e la profondità può essere al massimo 255! Non devo gestirne milioni, hai ragione, devo gestirne decine di miliardi nella peggiore ipotesi. Ora la mappa è un array o un array bidimensionale immagino, e allocarla dinamicamente non è richiesto quindi evidentemente un motivo ci sarà e sinceramente penso ci sia un metodo più efficace per un progetto simile.
    La mappa potrei benissimo utilizzarla come dici ma non sarei in grado di allocare lo spazio per ogni singolo elemento, probabilmente allora dovrei almeno dimezzare la grandezza, il che significa raddoppiare le collisioni, il che porta ad avere delle liste molto lunghe che aumentano poi la complessità di tutte le funzioni richieste.
    La lista come ben sai non è utilizzabile dato che la complessità per scorrerla tutta sarebbe ridicolmente lunga mentre io devo avere qualcosa di estremamente veloce. Anche con sole tre sottocartelle della root la complessità richiesta non verrebbe soddisfatta dato che per accederci dovrei impiegare O(1) e la lista invece nel caso peggiore ci impiega 0(#N cartelle create).
    2) una qualunque funzione hash va bene: il problema e' la gestione delle collisioni. Banale funzione hash: converti i primi 8 caratteri/byte, in un long. Ma ti basterebbero anche solo i primi 4, o anche 1!
    Quindi a tuo parere quella sarebbe una buona funzione di hashing in questo caso, praticamente se dovessi creare 250 sotto cartelle della cartella /dir1/dir2/dir3 avrebbero tutte la stessa funzione hash, avrei quindi 250 collisioni, non credo possa essere una funzione adeguata.
    non ho capito che te ne fai di un array MULTIDIMENSIONALE, visto che per smontare il path nelle sue componenti ti basta un vettore di stringhe di al massimo 10 elementi!
    Questo array di 10 elementi non ho proprio capito a cosa serva sinceramente. Trovo molti pressapochismi nelle tue risposte, forse è perché vuoi essere apposta un po' vago per non farmi tutto il lavoro, ma un conto è essere vaghi e dire cose sensate, altro è proporre strutture dati estremamente banali e sicuramente inadatte a un problema del genere.
    NON PUOI dire che non hai idea di come convertire un numero nel range [0,100000000000000000] in un numero nel range [0,26]! E' robbbbba da scuole elementari! Vebbe' medie!
    Certo che lo so, basta un semplice modulo, peccato che la funzione hash funziona bene così se è stata creata così no? Se modificassi l'output della funzione probabilmente romperei l'efficacia della funzione stessa.

    Se ti può aiutare a chiarire la grandezza di alcune ramificazioni, questo è una possibile sequenza di input del programma ed è inserita solo in parte perché il resto non me lo faceva mettere:
    create_dir /dir0rid
    create_dir /dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    create_dir /dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid/dir0rid
    
  • Re: Filesystem in memoria

    ...
  • Re: Filesystem in memoria

    Quello che sottovaluta la persona che ha di fronte in questo caso sei tu. Si potesse fare questa cosa con una ridicola liked list pensi non mi sarebbe venuto in mente?
    Ad ogni modo, ribadisco, la mappa prima deve essere allocata e deve avere una grandezza che gli permetta di avere poche collisioni in modo da arrivare quasi sempre con complessità O(1) alla path. Questo ovviamente non è possibile, allocare subito lo spazio per tutti i possibili file o meno è comunque di per sé uno spreco abnorme di memoria, non capisco come tu faccia a creare la mappa e nemmeno la sua struttura, se un array oppure un array multidimensionale o chissà cosa(?), in poche parole dalla tua spiegazione ho colto praticamente nulla. Sarò ignorante io probabilmente...

    Praticamente la tua dritta è stata un riassunto del progetto, fortunatamente so leggere e scrivere quindi diciamo che non è niente di nuovo quello che hai risposto, senza offesa eh.
    Ti do SOLO una dritta:
    1) hai DUE dipi di oggetti:
    --- directory, descritta da una mappa <nome,oggetto>
    --- file, descritto da un byte array e dalla sua lunghezza
    2) ti serve l'equivalente della directory ROOT.

    3) nella mappa, gli 'oggetti' possono essere directory o file

    4) la navigazione la devi fare usando delle stringhe formattate tipo 'filesystem' con path assoluto:

    /topolinia/investigazioni/topolino

    a) parti dalla ROOT
    b) scegli l'oggetto con chiave 'topolinia'
    c) b) DEVE essere una directory (altrimenti ERRORE), scegli l'oggetto con nome 'investigazioni
    d) c) DEVE essere una directory, scegli l'oggetto con nome 'topolino'
    e) d) PUO' essere una directory OPPURE un file
  • Re: Filesystem in memoria

    ...
  • Re: Filesystem in memoria

    Sono un pochino confuso, forse perchè non sono Einstein, forse perchè non mi intendo particolarmente di file system.
    ma qual'è il tuo dramma esistenziale? perchè ti vuoi "amminchiare" con gli hash, che tipicamente sono l'ultima delle strutture dati usate per un file system?

    inizia a ragionare sul semplice, cioè un vettore o array che dir si voglia. fai attenzione, infatti, che un filesystem di questo tipo (in memoria) in realtà non ha nulla a che vedere con un filesystem "vero".

    Il vero "dramma" è il create file col no in caso di creazione.
    Comunque calma e gesso, suggerisco di partire dall'inizio e vedere poi se e cosa aggiustare.
  • Re: Filesystem in memoria

    Sono riuscito nella gran parte dell'impresa per il momento, mi mancano solamente le funzioni
    delete_r
    e
    find
    a cui sto pensando al momento. La delete_r dovrebbe cancellare la cartella indicata e tutti i suoi discendenti. Vorrei fare un lavoro pulito e quindi liberare la memoria da ogni singolo nodo che sta sotto alla directory da cancellare e non semplicemente staccare il "ramo" in modo che non sia più raggiungibile. Nella mia implementazione non ho sottocartelle con puntatori alle cartelle padre perché non l'ho trovato utile con tutte le altre funzioni, quindi devo trovare un modo che parta dalla cartella da eliminare e scenda. Per la find non ho molte idee al momento se non passare tutti i nodi, che sforerebbe la complessità richiesta per la funzione.
  • Re: Filesystem in memoria

    La find deve stampare in ordine lessicografico i risultati trovati, io ho pensato di salvare le stringhe in un albero binario, vi sembra efficiente come metodo?
Devi accedere o registrarti per scrivere nel forum
11 risposte