Struttura dei dati per implementare un filesystem fasullo con le funzioni di complessità richieste

Devo creare un file system fasullo che in pratica memorizza il percorso di ogni elemento nella struttura. Questo file system deve essere eseguito sulla memoria primaria, quindi non devo scrivere nulla sul disco rigido.

Ho molte idee su come creare questo progetto ma alla fine, ognuno di essi non supera il test a causa dell'eccesso di utilizzo della memoria (che mi dà algoritmi più veloci).

Queste sono le funzioni che devono essere implementate con la sua complessità:

• mkdir path/to/dir con complessità O (lunghezza del percorso)
• find nameOfDir con complessità O (risorse nel filesystem + risorse trovate ^ 2)
• rm path/to/dir con complessità O (numero di risorse in quella directory)

Ultimo ma non meno importante, ogni directory può avere 1024 cartelle secondarie.

Il mio primo schizzo di questo filesystem era di usare un albero

typedef struct _treeNode{
    treeNode* parentNode;
    treeNode* rightNode;
    treeNode* leftNode;
    treeNode* childNode;
    char pathName[255];
} treeNode;

il problema con questo è che ottimizza la memoria perché potrei creare solo i nodi che sono necessari ma manca di algoritmi veloci, perché dovrei controllare ogni nodo per raggiungere il percorso desiderato. Ho anche pensato di creare una hashmap esterna (che usa le stringhe come chiavi) con un puntatore a ogni singolo nodo ma con la funzione di hash che ho testato qui

( 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;
    }

l'hashmap occupa troppa memoria perché i numeri restituiti dalla funzione hash sono molto più alti del previsto.

La mia prossima idea era ancora peggio, ovvero creare un'istanza di tutti i 1024 bambini di un array che è archiviato nel nodo padre non appena viene creato il nodo.

typedef struct _nodeArray {
    nodeArray* childDirectories[1024];
    nodeArray* parentNode;
    char* dirPath[255];
} nodeArray;

Il problema con questo è lo stesso di prima, troppa memoria utilizzata e anche il fatto che anche qui avrei dovuto cercare ogni nodo per arrivare al percorso richiesto. Potrei usare una hashmap anche qui, ma ciò aumenterebbe la memoria utilizzata ancora di più, o potrei trovare una hashmap senza collisioni che mi restituirebbe il posto giusto nel posto corretto nell'array ma al momento non ne ho uno in mente .

Ho anche pensato di ordinare l'array ma questo non cambia molto perché devi ancora passare attraverso tutti gli array e confrontare i nomi dir per arrivare dove vuoi andare, che può rendere le cose un po 'più veloci ma rimane ben oltre la complessità richiesta.

Apprezzerei molto il tuo aiuto su questo perché non riesco a capire un modo veloce (e forse più semplice) per farlo. Se puoi migliorare la mia struttura dati con alcuni esempi, mi piacerebbe molto.