c - C中的LRU缓存

Question

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

真的，我不想自己动手，所以如果有人知道我在哪里可以找到可用的库，请指点方向？如果做不到这一点，有人可以提供一个用 C 编写的 LRU 缓存的简单示例吗？相关帖子说是双向链表的哈希表，但我什至不清楚双向链表如何保持LRU。

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

Answer 1

Related posts indicated that a hash table with a doubly-linked list, but I'm not even clear on how a doubly-linked list keeps 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
        }
    }
}

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

但我可能完全错了。