This depends on contain-rs/linked-hash-map#4.

Motivation:
My use-case for lru-cache involves inspecting items' heap size. Rather than hack it in, I think it would be beneficial to make the cache adaptable to whatever limit needs to be imposed.

You might have a set of heterogeneous items, each using a different amount of allocation on the heap. Maybe a more general Meter trait might help:

trait Meter<T> {
    fn measure(&self, item: &T) -> usize;
}

The default Meter could be a Count:

struct Count;

impl<T> Meter<T> for Count { 
    fn measure(&self, _: &T) -> usize { 1 }
}

Here's an implementation that would use the HeapSizeOf trait (I'd recommend this one for inclusion under a feature gate as it's generally useful.)

struct HeapSize;

impl<T: HeapSizeOf> Meter<T> for HeapSize {
    fn measure(&self, item: &T) -> usize { item.heap_size_of_children() + ::std::mem::size_of::<T>() }
}

When you add or remove an item, you add or subtract meter.measure(&item) from the maximum respectively. If the metered total exceeds the maximum while adding an item, other items must be removed in a loop until the total falls below the limit.

Caveats:

• get_mut or interior mutability could allow items to be altered such that their measure at insertion time differs from their measure at removal. We could add a UniformMeter<T> which takes no reference to individual items when measuring -- indicating that the measurement is unrelated to item size. get_mut might only be implemented when the meter is uniform, while fn get(&mut self, key: &Q) -> Option<&T> would serve as an alternative implemented for all caches. This doesn't solve the interior mutability issue, but that can be addressed the same way as in HashMap: documentation specifying that it's a logic error to modify the value such that its measure would be altered.
• insert can remove multiple items -- how do we return each of them to the caller efficiently? (maybe an iterator?)

Alternatively:

• check the measure before and after get_mut and adjust the total correspondingly. The issue here is that it would need to be done through a CacheHandle<'a, T: 'a> which contains that logic in its destructor. This would break backwards compatibility, and would need to handle returning displaced items if the size grows.
• re-measure every item in the cache whenever necessary. this seems prohibitively expensive

Looking forward to your comments and naming suggestions below.

Tag each entry with "last-used-at" timestamp, and at eviction time pick the LRU among N randomly selected entries.

This is one of the eviction policies supported by Redis: http://redis.io/topics/lru-cache

Maybe it should be a separate container though, because it won't need the linked hash map.

LinkedHashMap already opts in to {Send, Sync}, so these should be unnecessary.

This is more of a feature request. But would it be possible to make remove_lru() public?
I've been missing this when implementing an adaptative replacement cache.

Thanks!

Depends on contain-rs/linked-hash-map#34.

I made a fork that handle cache capacity using entries size rather than entries number.
I found it useful to keep control of memory usage, when cache entries are collections or strings with different legths.

I don't think it is should be merged back (that's why an issue instead of a PR), but I was wondering if you'd like to take it as a contain-rs project. Let me know!

Is it possible to implemented Serialize and Deserialize, just as LinkedHashMap did?

Something like:

extern crate lru_cache;       

use lru_cache::LruCache;
use std::sync::RwLock;

fn main() {                   
    let mut cache = LruCache::new(2);
    cache.insert(1, 10);

    let rwlock = RwLock::new(cache);
    let lock = rwlock.read().unwrap();
    let value = lock.get_mut(&1);    
    println!("{:?}", value);
}

I got:

error: cannot borrow immutable borrowed content as mutable
  --> src\main.rs:12:17
   |
12 |     let value = lock.get_mut(&1);
   |                 ^^^^

This depends on contain-rs/linked-hash-map#3.

lru_time_cache have implement this feature, but it is licensed under the GPL-3.0. Can you implement the expire time support? It would be very useful and helpful.

dashes vs underscores is causing trouble

rust-lang/cargo#2326

$ cargo --version
cargo 0.7.0 (built 2016-01-18)

$ rustc --version
rustc 1.7.0-dev

Since the capacity is restricted, it makes sense not to over- or underallocate on creation.

Please publish some of the latest changes to crates.io. I've been forced to set the dependency to point to the github repository for the time being in my project in order to use remove_lru.

Issue

use lru_cache::LruCache;

fn main() {}

#[test]
fn test_panics() {
    let mut l = LruCache::new(10);
    l.insert(1, false);
}

cargo test

This code panics when the linked-hash-map crate used by lru_cache is under version 0.5.3, because it contains uninitialized memory allocation.
The uninitialized memory problem seems to be fixed for version 0.5.3, but because the dependency is specified in Cargo.toml as

linked-hash-map = "0.5"

It means that cargo is free to choose any version >=0.5.0, and if the 0.5.1 or 0.5.2 versions are present in the local package cache, they might be picked.

Rewriting it instead as

linked-hash-map = "0.5.3"

and releasing it as new minor version 0.1.3 would fix the problem, as cargo would be forced to pick a version >=0.5.3

Thanks to cargo outdated, I noticed:

cargo outdated
Checking for SemVer compatible updates...Done
Checking for the latest updates...Done
The following dependencies have newer versions available:

    Name                        Project Ver  SemVer Compat  Latest Ver
    lru-cache->linked-hash-map     0.2.1          --          0.3.0

with_hash_state should become with_hasher.

CC contain-rs/linked-hash-map#40.