Caches LRU en C

Je dois mettre en cache un nombre important (mais variable) de fichiers de petite taille (1 Ko à 10 Mo) en mémoire, pour une application C (dans un environnement * nix). Puisque je ne veux pas manger toute ma mémoire, j’aimerais définir une limite de mémoire fixe (64 Mo), insérer les fichiers dans une table de hachage avec le nom du fichier comme clé et éliminer les entrées les moins utilisées . Ce dont j’ai besoin, c’est d’un cache LRU.

Vraiment, je préférerais ne pas rouler le mien, alors si quelqu’un sait où je peux trouver une bibliothèque fonctionnelle, veuillez indiquer le chemin? À défaut, quelqu’un peut-il fournir un exemple simple de cache LRU en C? Des publications associées ont indiqué qu’une table de hachage avec une liste à double liaison, mais je ne sais même pas comment une liste à double liaison conserve LRU.

Note latérale: Je réalise que c’est presque exactement la fonction de memcache, mais ce n’est pas une option pour moi. J’ai également consulté la source dans l’espoir de m’éclairer sur la mise en cache LRU, sans succès.

Des publications associées ont indiqué qu’une table de hachage avec une liste à double liaison, mais je ne sais même pas comment une liste à double liaison conserve LRU.

Je ne fais que deviner, mais vous pouvez faire quelque chose comme ça (utiliser le pseudo-C ici parce que je suis paresseux). Voici les structures de données de base:

struct File { // hash key ssortingng Name; // doubly-linked list File* Previous; File* Next; // other file data... } struct Cache { HashTable Table // some existing hashtable implementation File* First; // most recent File* Last; // least recent } 

Et voici comment ouvrir et fermer un fichier:

 File* Open(Cache* cache, ssortingng name) { if (look up name in cache->Table succeeds) { File* found = find it from the hash table lookup move it to the front of the list } else { File* newFile = open the file and create a new node for it insert it at the beginning of the list if (the cache is full now) { remove the last file from the list close it remove it from the hashtable too } } } 

La table de hachage vous permet de rechercher rapidement les nœuds par nom et la liste liée vous permet de les maintenir dans leur ordre d’utilisation. Comme ils pointent vers les mêmes nœuds, vous pouvez basculer entre eux. Cela vous permet de rechercher un fichier par son nom, puis de le déplacer ensuite dans la liste.

Mais je peux me tromper totalement à propos de tout cela.

Si vous utilisez Linux, je pense que le système d’exploitation fera tout ce dont vous avez besoin, en particulier si vous profitez de l’ fadvise système fadvise pour informer le système des fichiers que vous prévoyez d’utiliser.

koders.com localise quelques-uns; celui qui est le plus facile à adapter et à réutiliser (si les conditions de la licence vous conviennent) semble être celui du projet FreeType (il en faudra quelques-unes pour son travail intéressant, pré-processeur intéressant ). Au pire, cela devrait vous montrer une approche par laquelle vous pouvez implémenter un cache LRU en C.

La plupart des implémentations de cache LRU réutilisables (et il en existe beaucoup sur le net) utilisent bien entendu des langages plus pratiques (Java, C ++, C #, Python, …) qui offrent des structures de données plus robustes et, généralement, une gestion de la mémoire.

Il semble que vous puissiez construire un cache LRU en C avec uthash .

Ce que j’aime le plus chez Uthash, c’est qu’il s’agit d’un simple fichier d’en-tête, avec de nombreuses macros, afin que vos dépendances supplémentaires soient réduites au minimum.

Je ne connais aucune bibliothèque environnementale générale Unix en C, mais cela ne devrait pas être difficile à mettre en œuvre.

Pour des exemples de code, je suggère de regarder n’importe quelle implémentation de table de hachage gazillion (oi). Que la table utilise une liste chaînée ou une arborescence pour le traitement, il n’est pas rare qu’une forme de mise en cache soit utilisée (telle que MRU), elle peut donc vous donner une idée de ce à quoi une implémentation pourrait ressembler. Certains collecteurs de déchets simples et divers logiciels nécessitant un algorithme de remplacement de page peuvent également valoir le détour.

Fondamentalement, vous marquez les choses lorsque vous y accédez et vieillissez les références. Si vous augmentez l’âge des objects d’access plutôt que chaque pair de l’article auquel vous accédez, vous enregistrez évidemment une boucle lors des access et insérez le poids dans l’opération d’expiration. Vous voudrez peut-être établir des profils clairs afin de vous donner une idée générale de la moins récente des données. À ce stade, vous mettez à jour le cache en conséquence.