Implement Clone on LruCache

[stormshield-frb]

We'd need to clone our LruCache but it does not seems possible. Is there a technical reason why Clone is not implemented ?

For the time being, I'm using the following code:

fn duplicate_lru<K, V>(lru: &LruCache<K, V>) -> LruCache<K, V>
where
    K: std::hash::Hash + std::cmp::PartialEq + std::cmp::Eq + Clone,
    V: Clone,
{
    let mut new_lru = LruCache::new(lru.cap());

    for (key, value) in lru.iter().rev() {
        new_lru.push(key.clone(), value.clone());
    }

    new_lru
}

I would be open to work on this issue if there is no particular reason why Clone should not be implemented onto LruCache.

[jeromefroe]

I can't think of any explicit reason why Clone hasn't been implemented yet, I think the need for it just hasn't come up before. If you don't mind working on it, I'd be happy to review your change!

[stormshield-frb]

Ok sure. I've look at the code a little bit and did not realized it's complexity (I've never used MaybeUninit, ptr or recursive struct in Rust). Hats off :wink:

My first though was to either derive Clone (1) or implement it manually by "cloning" all the fields (2). However, (1) is just not possible because of MaybeUninit and I think that (2) will not work because of the recursive struct LruEntry.

Do you think that the function above is correctly "cloning" the LruCache ? If it does, then I will implement Clone using this method. I you have something else in mind, I am completely listening of course (I've never used those types so I'm a little bit afraid to do introduce bugs or UB).

[jeromefroe]

My initial thought was that it might be simplest to implement it manually by cloning all the items in the cache. Would it be possible to create a new empty cache and then iterate over all the elements in the old cache and insert them into the new one? If we iterate over the items in reverse order then they will be inserted into the new cache in the correct order.

[stormshield-frb]

Would it be possible to create a new empty cache and then iterate over all the elements in the old cache and insert them into the new one? If we iterate over the items in reverse order then they will be inserted into the new cache in the correct order.

@jeromefroe Yes exactly. This is what the duplicate_lru function does (first comment in the issue). It creates a new LRU, creates an iterator over the old LRU, reverse it and then iterate over every entry in the old LRU and clone it.

If you are ok with this implementation, I'll make a PR with it.

[jeromefroe]

Oh yep, that implementation looks good to me, would be happy to review your PR :)