C中的LRU缓存

我需要为C应用程序（在* nix环境中）在内存中缓存一个很大（但可变）的小文件（1千字节到10兆字节）文件。由于我不想吃掉所有的记忆，所以我想设置硬内存限制（比如64兆字节），并将文件推入散列表中，并以文件名作为关键字并处理最少使用的条目。我相信我需要的是一个LRU缓存。C中的LRU缓存

真的，我宁愿不要自己滚动，所以如果有人知道我在哪里可以找到一个可行的图书馆，请指出方向？如果没有，有人可以提供一个在C中的LRU缓存的简单例子吗？相关的帖子指出一个带有双向链表的散列表，但我甚至不清楚双链表如何保持LRU。

附注：我意识到这几乎是memcache的功能，但它不是我的选择。我也看了一下希望能够启发LRU缓存的消息来源，但没有成功。

来源

2010-06-12 lazyconfabulator

在某种程度上，这也似乎与您的操作系统的磁盘缓存功能相同。 – Thanatos 2010-06-12 04:31:17

你需要这个怎么样？如果您只是希望减少平均访问延迟，并且您正在全服务操作系统中运行，那么请让操作系统处理它。自己管理它是一种特殊情况... – dmckee 2010-06-12 04:44:08

执行大部分相同功能（提供大量小文件）的HTTP服务器通常包含自己的缓存，而不是使用操作系统的磁盘缓存。我打算把它作为一个指标，仅仅依靠操作系统来缓存并不是最佳解决方案。 – lazyconfabulator 2010-06-12 05:11:27

相关文章表明，一个双向链表的哈希表，但我甚至不清楚双向链表如何保持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 
     } 
    } 
}

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

但我可能完全错误的所有这一切。

来源

2010-06-12 05:45:54 munificent

我不知道C中有任何一般的unix环境库，但它不应该很难实现。

对于代码示例，我建议环顾四周的任何gazillion（oi）哈希表实现。无论表使用链表还是树结构进行实际处理，使用某种形式的缓存（例如MRU）并不罕见，因此它可以让您了解实现的外观。一些简单的垃圾收集器和需要页面替换算法的各种软件也值得一看。

基本上，您在访问它们时标记事物并对参考进行年龄确定。如果您增加访问时间而不是访问项目的每个对象的年龄，您显然会在访问时保存一个循环，并将权重推至到期操作。你会想做一些简单的分析，以便找到一个总体概念，说明最近的情况足够用于你的任务。当你到达这一点时，你只需相应地更新缓存。

来源

2010-06-12 04:43:19 TerryP

koders.com定位几个;一个最容易适应和重用的程序（如果你可以使用它的许可证条件）似乎是FreeType项目的this one（需要找一些有趣的有趣的预处理工作）。在最坏的情况下，它应该向您展示一种方法，您可以在C中实现LRU缓存。当然，大多数可重用的LRU缓存实现（并且网上有许多可用），当然，使用更加容易的语言（Java， C++，C＃，Python等），它们提供更强大的数据结构，通常是内存管理。

来源

2010-06-12 04:43:27

如果您使用的是Linux操作系统，我认为操作系统可以满足您的所有需求，特别是如果您利用系统调用fadvise来让系统知道下一步计划使用哪些文件。

来源

2010-06-12 05:29:38

看来你可以建立一个LRU Cache in C with uthash。

我最喜欢uthash的是它是一个简单的头文件，有很多宏，所以你的额外的依赖性保持在最低限度。

来源

2012-04-13 09:46:45

C中的LRU缓存

回答

相关问题