LRU classes in C

Question

I need to cache a large (but variable) amount of small (from 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 would like to set a hard memory limit (say 64 megabytes) and push the files into a hash table with the file name as the key and delete the entries with the least use, It seems to me that I need the LRU cache .

Actually, I would prefer not to collapse my own, so if someone knows where I can find a workable library, specify a path? Otherwise, can anyone provide a simple example of an LRU cache in C? Related posts indicated that the hash table is a doubly linked list, but I don’t even understand how a doubly linked list contains an LRU.

Side note: I understand that this is almost a memcache function, but it is not an option for me. I also looked at a source hoping to enlighten myself on LRU caching, without success.

Answer 1

Related records indicated that the hash table is a doubly linked list, but I don’t even understand how a doubly linked list stores LRUs.

I'm just guessing here, but you can 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 is how you can open and close the 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 } } } 

A hash table allows you to quickly find nodes by name, and a linked list allows you to maintain them in order of use. Since they point to the same nodes, you can switch between them. This allows you to view the file by name, and then move it around the list in the future.

But I could be completely mistaken in all of this.

Answer 2

If you use Linux, I think that the OS will do everything you need, especially if you use the fadvise system call so that the system fadvise which files you plan to use next.

Answer 3

koders.com finds several; the one that is easiest to adapt and reuse (if you are okay with your license terms) looks like this one from the FreeType project (you will think about your, um, interesting preprocessor work). In the worst case, it should show you one approach where you can implement the LRU cache in C.

In most reusable LRU cache implementations (and can be found on the net), of course, use more convenient languages ​​(Java, C ++, C #, Python, ...) that offer stronger data structures and, like Generally, memory management.

Answer 4

It seems you can build LRU Cache in C with uthash .

What I like uthash more is a simple header file with lots of macros, so your additional dependencies are kept to a minimum.

Answer 5

I do not know the common Unix environment libraries in C, but this should not be difficult to implement.

For sample code, I suggest looking around any of the gazillion (oi) hash table implementations. Whether the table uses a linked list or a tree structure for actual processing, some form of caching (such as MRUs) is often used, so it can give you an idea of ​​what the implementation might look like. Some simple garbage collectors and various bits of software that require a page replacement algorithm can also be useful.

Basically, you mark things up when they are accessed and links increase. If you increase the age of things at access, and not every access to an accessible element, you obviously keep the cycle at access and press the weight on the expiration operation. You want to do a little profiling to find a general idea of ​​how least recent is enough! Recently enough for your task. When you get to this point, you just update the cache accordingly.