LRU缓存在C中

Question

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

真的,我宁愿不自己动手,所以如果有人知道我在哪里可以找到一个可行的图书馆,请指明方向？如果不这样,有人可以在C中提供LRU缓存的简单示例吗？相关帖子表明一个哈希表有一个双向链表,但我甚至不清楚双链表如何保持LRU.

旁注:我意识到这几乎就是memcache的功能,但它不适合我.我还看了一下希望在LRU缓存上启发自己的消息来源,但没有成功.

Answer 1

相关帖子表明一个哈希表有一个双向链表,但我甚至不清楚双链表如何保持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
        }
    }
}

哈希表允许您快速按名称查找节点,链表允许您按使用顺序维护它们.由于它们指向相同的节点,因此您可以在它们之间切换.这使您可以按名称查找文件,但随后在列表中移动它.

但我对所有这一切都完全错了.