LRU缓存用C [英] LRU caches in C

问题描述

我需要缓存的大（但变量）号短小（1千字节到10兆字节）的文件在内存中，对于C应用程序（在* nix的环境）。因为我不想吃我所有的记忆，我想设置硬盘内存限制（例如，64兆字节）和文件名的文件推到一个哈希表的键，用最少使用的条目处置。我相信我需要的是一个LRU缓存。

真的，我宁愿不推出自己的，所以如果有人知道在哪里可以找到一个可行的图书馆，请点的方式吗？如果做不到这一点，有人可以提供C中的LRU缓存的一个简单的例子？相关文章指出，用双向链表哈希表，但我不是一个双向链表如何保持甚至不清楚LRU。

附注：我意识到这是几乎完全内存缓存的功能，但它不是我的选择。我也看了看源希望能开导自己在LRU缓存，但没有成功。

解决方案

  

相关文章指出，用双向链表哈希表，但我不是一个双向链表如何保持甚至不清楚LRU。

我只是采取一种猜测在这里，但你可以做这样的事情（使用此伪C，因为我懒惰）。以下是一些基本的数据结构：

 结构文件
{
    // 散列键
    字符串名称;    //双向链表
    文件* previous;
    FILE *下一步;    //其它文件数据...
}高速缓存结构
{
    哈希表＆LT;字符串文件* GT;表//一些现有的哈希表的实现
    文件*第一; //最近
    FILE *最后; //最近最少
}
 

和这里是如何你打开和关闭文件：

 文件*打开（缓存*高速缓存，字符串名称）
{
    如果（查找名称的cache＆GT;表成功）
    {
        文件*发现=来自哈希表中查找发现
        其移动到列表的前面
    }
    其他
    {
        FILE * NEWFILE =打开该文件，并为它创建一个新节点        在列表的开头插入它        如果（缓存满了）
        {
            从列表中删除的最后一个文件
            关闭
            从哈希表中删除它太
        }
    }
}
 

哈希表，您可以按名称快速找到节点和链接列表，可以维持其使用顺序。由于它们指向同一个节点，你可以在它们之间进行切换。这可以让你看文件按名称，但随后在列表之后移动左右。

但我可能是完全错误的关于这一切。

I need to cache a large (but variable) number of smallish (1 kilobyte to 10 megabytes) files in memory, for a C application (in a *nix environment). Since I don't want to eat all my memory, I'd like to set hard memory limit (say, 64 megabytes) and push files into a hash table with the file name as the key and dispose of the entries with the least use. What I believe I need is an LRU cache.

Really, I'd rather not roll my own so if someone knows where I can find a workable library, please point the way? Failing that, can someone provide a simple example of an LRU cache in C? 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.

Side note: I realize this is almost exactly the function of memcache, but it's not an option for me. I also took a look at the source hoping to enlighten myself on LRU caching, with no success.

解决方案

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.

I'm just taking a guess here, but you could do something like this (using pseudo-C here because I'm lazy). Here are the basic data structures:

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
}

And here's how you'd open and close a file:

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
        }
    }
}

The hashtable lets you find nodes by name quickly, and the linked-list lets you maintain them in use order. Since they point to the same nodes, you can switch between them. This lets you look a file up by name, but then move it around in the list afterwards.

But I could be totally wrong about all of this.

这篇关于LRU缓存用C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！