const-lru

一个简单的无std、非哈希、固定容量、固定内存使用的LRU缓存。

数据结构由几个const泛型数组支持，因此所有所需的内存都预先分配。

设计

LRU缓存结构以数组结构格式布局：所有键都在一个数组中，所有值都在另一个数组中。

结构中还存储了键的排序索引，以允许使用二分搜索进行O(log N)查找时间。

使用双链表实现LRU排序，但使用数组索引而不是指针。遵循数组结构格式，所有下一个链接数组索引在一个数组中，而所有前一个链接数组索引在另一个数组中。

为了最大化空间效率，最后一个可选泛型I指定了索引类型，可以将其设置为小于usize的位宽的无符号原始整型类型，只要它足够宽以存储缓存的容量。

use const_lru::ConstLru;
use core::mem;

assert_eq!(mem::align_of::<ConstLru<u8, u8, 255>>(), 8);
assert_eq!(mem::size_of::<ConstLru<u8, u8, 255>>(), 6656);

assert_eq!(mem::align_of::<ConstLru<u8, u8, 255, u8>>(), 1);
assert_eq!(mem::size_of::<ConstLru<u8, u8, 255, u8>>(), 1278);

时间复杂度

其中 N 是元素数量

• 检索：使用排序索引进行O(log N)查找
• 插入：使用排序索引进行O(log N)查找 + O(N)修改排序索引（类似于Vec的索引类型位操作复制）
• 删除：使用排序索引进行O(log N)查找 + O(N)修改排序索引（类似于Vec的索引类型位操作复制）
• 长度获取：O(1)，因为它存储在结构中
• 获取最近使用元素：O(1)，使用 .iter().next()
• 获取最久未使用元素：O(1)，使用 .iter().next_back()
• 获取最小键的条目：O(1)，使用 .iter_key_order().next()
• 获取最大键的条目：O(1)，使用 .iter_key_order().next_back()

动机

大多数（如果不是所有）通用的LRU缓存实现（包括但不限于 associative-cache、caches、clru、hashlink、lru）依赖于一个或多个哈希表来提供 O(1) 操作时间。虽然速度快，但这使得它们在内存受限的环境（如嵌入式系统）中的使用不太适合，因为哈希表可能会重新哈希和重新分配更多的内存。