lru思想

LRU是最近最少使用算法。一般内存管理的时候采用LRU算法可以提高性能。

将cache缓存块位置用LRU双向链表链接起来，将新加入的块直接放到链表的头，当一个块被命中后，把该块调整到链表的头，这样经过多次操作之后，最近被命中过的块就会向链表头部移动，而没有被命中的内容会向链表尾部移动，需要替换时，就直接从链表尾部替换即可。新的内容直接插入链表头部，这样就实现了LRU的思想。

算法中维护了一个freelist，用于管理空闲块的位置，每次需要插入新的内容时，就从freelist里面获取一个空闲块，将新内容复制，然后插入到链表头部；删除时就从链表尾部删除结点，然后更新到freelist里；查找一个结点时，在一般链表中的时间复杂度是O(n)，为了提高查找效率，在算法中加入了一个hash表，每次新加入的结点都会更新到hash表里，删除结点时会从hash表中移除，这样查找的时候直接从hash表里查询，获取结点的位置，从而时间复杂度为O(1)。

 

内联函数使用要点：

1.在内联函数内不允许用循环语句和开关语句。

    如果内联函数有这些语句，则编译将该函数视同普通函数那样产生函数调用代码，递归函数（自己调用自己的函数）是不能被用来做内联函数的。内联函数只适合于只有1～5行的小函数。对一个含有许多语句的大函数，函数调用和返回的开销相对来说微不足道，所以也没有必要用内联函数实现。

 2.内联函数的定义必须出现在内联函数第一次被调用之前。