Crate qlrumap 

The LruMap is a data structure that mimics a small subset of the standard HashMap but with the added feature that it keeps track of the least recently used nodes and optionally supports setting a Time-To-Live duration which can be used to drain nodes that have timed out.

Internals

The LruMap is implemented on top of hashbrown’s RawTable. The least recently used property is implemented using a manually maintained doubly linked list.

Structure

Simplified, the LruMap internally keeps track of the LRU linked list and the hash table.

Keys in the LruMap are handled no different than in a regular HashMap, but the application values are wrapped in a LruNode, which are nodes in the linked list.

This allows the LruMap to [whenever the application looks up value using a key] quickly (it only needs to update the link pointers) move the corresponding value’s node to the beginning of the LRU list.

Sometimes it’s necessary to access a map entry (key, value) with an LRU node as a starting point (such as when removing the oldest node), which involved finding the matching (key, value) entry given the value. One solution would be to scan the entire internal RawTable for the LruNode pointer, but for a large table this could be slow. To speed this up the LruNode stores its key hash, allowing it to use RawTable::find() to search only the keys with the matching hash.

Structs

Drain

A draining Iterator that will on each iteration return ownership of the key/value pair of the next entry in the map.

DrainFilter

A draining Iterator that will on each iteration call a closure which, if it returns true, will drain (remove and return) the current key/value pair.

DrainOld

DrainOrdered

Iterator that removes and returns every element in the LruMap.

DrainOverflow

DrainTimedout

IntoIter

A consuming iterator over the entries of an LruMap from youngest to oldest.

Iter

An iterator over the entries of a LruMap from youngest to oldest.

IterMut

A mutable iterator over the entries of a LruMap from youngest to oldest.

LruMap

A HashMap which maintains an internal least recently used nodes list.

Type Aliases

DefaultHashBuilder