c - C 语言中的 LRU 缓存

对于 C 应用程序(在 *nix 环境中)，我需要在内存中缓存大量(但可变)数量的小(1 KB 到 10 兆字节)文件。因为我不想吃掉我所有的内存，所以我想设置硬内存限制(比如 64 兆字节)并将文件推送到以文件名为键的哈希表中，并处理最少使用的条目.我相信我需要的是 LRU 缓存。

真的，我宁愿不自己动手，所以如果有人知道我在哪里可以找到一个可行的图书馆，请指路？如果失败了，有人可以提供一个 C 语言中 LRU 缓存的简单示例吗？相关帖子指出带有双向链表的哈希表，但我什至不清楚双向链表如何保持 LRU。

旁注:我意识到这几乎正是 memcache 的功能，但它不是我的选择。我还查看了源代码，希望对 LRU 缓存有所启发，但没有成功。

最佳答案

我只是在这里猜测，但你可以做这样的事情(在这里使用伪 C，因为我很懒)。下面是基本的数据结构:

struct File
{
    // hash key
    string Name;

    // doubly-linked list
    File* Previous;
    File* Next;

    // other file data...
}

struct Cache
{
    HashTable<string, File*> Table // some existing hashtable implementation
    File* First; // most recent
    File* Last;  // least recent
}

这是您打开和关闭文件的方法:

File* Open(Cache* cache, string 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
        }
    }
}

哈希表可以让你快速地按名称查找节点，而链表可以让你按照使用顺序维护它们。由于它们指向相同的节点，因此您可以在它们之间切换。这使您可以按名称查找文件，然后在列表中移动它。

但我可能完全错了。

关于c - C 语言中的 LRU 缓存，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3027484/