LRU library

[bblum]

The standard way of representing an LRU is to have nodes be stored in a hashmap or binary search tree, with lookup-by-key, and in a linked-list which represents recency. This allows O(1) or O(logn) lookup/insert time, and constant time update/eviction with the recency list.

The representation is usually something like:

struct LRU<K,V> {
    struct node<K,V> *tree_root;
    struct node<K,V> *recency_head, *recency_tail;
}
struct node<K,V> {
    K key;
    V value;
    struct node<K,V> *tree_parent, *tree_left, *tree_right;
    struct node<K,V> *recency_prev, *recency_next;
}

This is more difficult to represent in Rust. You could do it with @mut pointers, but we all know what would go wrong there, and also that would prevent you from sharing it between tasks. You could also do it with unsafe pointers. I suggest instead representing it as a vector, and replacing the pointers with indices into the vector.

[jdm]

Servo's got an LRUCache: https://github.com/mozilla/servo/blob/master/src/components/util/cache.rs#L114

[bblum]

It has some O(n) operations, though.

[thestinger]

This is also the same data structure as OrderedDict in python and LinkedHashMap, they provide both the LRU cache use case and also a hash map recording the insertion order.

[thestinger]

Closing as a duplicate of #4988.