Reduce boxing about lru-rs

[Amanieu]

Have you considered using a copy of the key instead of a pointer? Generally keys are pretty small, but you would need K: Clone which may be a breaking change.

[Amanieu]

Ah nevermind, this would work poorly if the key is something like a String.

Regarding the hash table, I don't think hashbrown is a good fit, but you may be interested in Amanieu/intrusive-rs#37.

[Ralith]

I don't think hashbrown is a good fit

It'd be nice to benefit from hashbrown's optimizations. It seems like the only missing piece here is the ability for the caller to control the rehashing operation. In particular, it would be necessary for this lib to remove elements from the old table and insert them into the new one in LRU list order, constructing the correct chain as it goes.

That could be accomplished by something as simple as impl RawTable<T> { fn resize(&mut self, n: usize, rehash: impl Fn(&mut [MaybeUninit<T>], &mut [MaybeUninit<T>])) }. Is anything like that completely out of the question?

[Ralith]

On review, I think this could be accomplished with the existing interface by constructing the LRU list from bucket indices rather than raw pointers. As a bonus, I think this would allow removing nearly all of the unsafe from this crate, including the dicey uninitialized stuff.

[Ralith]

@jeromefroe, would you be interested in a PR to replace the use of pointers with bucket indices, and thereby remove all the boxing?

[jeromefroe]

@Ralith definitely, would be more than happy to review it.

[Ralith]

Hmm, bucket indexes still need to be rewritten on rehash. This would be really easy if hashbrown exposed a hook to rewrite entries on rehash, and otherwise seems infeasible.