Discussion :

[smyley]

Encore mes histoires qui continues :
Je voudrais utiliser une liste cad plusieurs entrées auxquelles on peut accéder via leur index.
Basiquement, pour ajouter un élément à la fin, on crée une nouvelle boîte qui contient la valeur et on la met à la fin de la liste. Mais pour la mettre au début ou au milieu il faut d'abord écarter toutes les boites suivantes (ou les rapprocher) avant de mettre la valeur et ça prend carrément beaucoup de temps. Par exemple, on a la liste 1, 2, 3, 4 ... on veut ajouter A à la 3e place :
1, 2, 3, 4 -> 1, 2, 3, 4, _ -> 1, 2, 3, 4, 4 -> 1, 2, 3, 3, 4 -> 1, 2, A, 3, 4 ...

Du coup même avec un abre binaire pour faciliter la localisation (même si pour l'instant j'ai un problème avec un avl tree que je ne comprend absolument pas), je ne vois pas d'alternative car même là il faudra que je décale toutes les entrées suivantes avant de mettre ma nouvelle entrée. Comment dois-je me débrouiller ?

[PRomu@ld]

L'idée pour ne pas avoir à tout décaler, consiste à utiliser une liste chaînée. Comme ça une fois que tu as trouvé où insérer l'élément (avec un arbre ou une table de hachage), il ne reste plus qu'à l'insérer sans tout décaler.

[pseudocode]

@smyley: Dans quel cas as tu besoin d'inserer un element dans un liste ? Ca a un rapport avec ton systeme de fichier in-memory ?

[smyley]

@smyley: Dans quel cas as tu besoin d'inserer un element dans un liste ? Ca a un rapport avec ton systeme de fichier in-memory ?

Ouai (pas in-memory, le tout est sur le disque)

En fait je veux pouvoir créer une List<t> mais qui soit stockée comme une suite de blocks sur le fichier. Mince .... alors pour pouvoir insérer et supprimer rapidement -> liste chainée, et pour pouvoir avoir l'élément à l'index n rapidement -> binarytree ... il faut encore que je combine les deux ?

[pseudocode]

pas in-memory, le tout est sur le disque

Ah... c'est sur que ca serait trop simple d'utiliser directement le filesystem de l'OS.

alors pour pouvoir insérer et supprimer rapidement -> liste chainée, et pour pouvoir avoir l'élément à l'index n rapidement -> binarytree ... il faut encore que je combine les deux ?

Ca dépend ce que tu entends par "combiner". Le BTree est utilisé pour la recherche, donc pour la structure des Inode. La liste chainée est utilisé pour le parcours, donc pour la structure des data block.

En général, dans un FS, l'execution des commandes d'accès aux blocks sont dans un thread séparé de celui qui génère les commandes. Donc il y a un thread qui manipule les inodes pour générer les commandes qui sont envoyées dans une file. Et il y a un autre thread qui manipule la file des commandes pour accèder aux blocks.

Il y a donc 2 niveaux d'optimisations et donc potentiellement 2 structures de données. Pour le 1er thread, une optimisation consiste a garder les inodes dans un cache mémoire. Pour le 2nd thread, une optimisation consiste a regrouper les opérations qui sont dans le même espace (secteur/piste) ou dans ton cas dans la meme "partie" du fichier réel servant de support.

[smyley]

Non non, je cherche pas aussi compliqué
Je veux juste avoir une liste de ulong et pouvoir accéder à un élément via un index c'est tout. Enfin, je sais pas ...