9.go开源groupcache项目笔记——lru代码

LRU是LeastRecently Used 近期最少使用算法。

内存管理的一种页面置换算法，对于在内存中但又不用的数据块（内存块）叫做LRU，操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。

       LRU用于实现LRU 的cache.

1      LRU文件

1.1     Cache结构体

先定义了一个cache结构体。

MaxEntries int是最大CACHE容量。

OnEvicted func(key Key, value interface{}) 是一个可选的回调函数，当一个ITEM从CACHE中清除的时候调用。

ll   *list.List是一个链表的指针

cache map[interface{}]*list.Element 是一个map类型，为列表中元素的指针。

PS：interface{}，在Go中它可以指向任意对象，也就任意对象都是先这个接口，你可以把它看成Java/C#中的Object, C/C++中的void*。list.Element其指向的类型是entry类型

1.2     其他定义

定义Key为接口，表示Key可以为任何值。

定义entry为结构体，包含key和value。其中key为Key类型，value为接口。

2      New函数

返回一个Cache结构体。

入参为一个整数，就是CACHE支持的最大容量，如果为0表示无上线

创建一个新的链表。

3      Add函数

入参为key Key,value interface{}.

首先判断当前Cache是否为nil，如果为nil则先new一个出来。

如果已经存在该key则将该元素指针移到列表前面，并将对应的值进行更新，代码如：ee.Value.(*entry).value= value 然后。

如果该key不存在，则将新的值添加到列表最前面，同时加入到Cache结构体中cache，接着判断是否超过了CACHE的最大数量，超过则调用RemoveOldest来删除最旧的entry。

4      Get函数

入参为key类型为Key。返回value和是否ok.

如果不存在缓存则直接换回。

如果存在就意味着命中，将元素指针移到列表前面，然后返回元素和TRUE

5      Remove函数

如果缓存不存在，则直接返回。

如果存在，调用removeElement移除指针。

6      RemoveOldest函数

如果缓存不存在，则直接返回。

如果有缓存则调用removeElement从列表的后端开始删除。

7      removeElement函数

入参为列表指针。

直接调用列表的Remove函数删除指针。

然后使用delete命令从map（c.cache）中删除对应的项

如果有回调函数则调用回调函数。

8      Len函数

返回列表长度，如果Cache结构体中的map为nil直接返回0.

PS：Go中实现一个类的成员方法，在func之后加类，在Go中接口的实现并不是和Java中那样子，而是只要某个类只要实现了某个接口的所有方法，即可认为该类实现了该接口。

Go中开头字母大写的变量名，类名，方法名表示对外可知，小写开头的表示对外不暴露。另外类实这种代码ele.Value.(*entry).value，其中(*entry)表示将Value转成*entry类型访问。

9      LRU_TESET

用于测试lru。

定义了两个结构体simpleStruct，complexStruct

然后定义一个变量getTests，如下

vargetTests=[]struct{

    name       string

    keyToAdd   interface{}

    keyToGet   interface{}

    expectedOkbool

}{

    {"string_hit","myKey","myKey",true},

    {"string_miss","myKey","nonsense",false},

    {"simple_struct_hit",simpleStruct{1,"two"},simpleStruct{1,"two"},true},

    {"simeple_struct_miss",simpleStruct{1,"two"},simpleStruct{0,"noway"},false},

    {"complex_struct_hit",complexStruct{1,simpleStruct{2,"three"}},

        complexStruct{1,simpleStruct{2,"three"}},true},

}

主要是两个用例如下

9.1     TestGet

从变量getTests循环获取，先调用New创建一个lru.

然后根据getTests. keyToAdd来增加缓存。每个键值都为1234.

然后在增加完后进行获取键值是否满足条件。

循环结束后测试也结束。

9.2     TestRemove

先增加一个lru。

然后增加一个键值，测试OK

然后将键值删除。检查删除是否成功。

9.3     测试结果

=== RUN TestGet

--- PASS: TestGet (0.00s)

=== RUN TestRemove

--- PASS: TestRemove(0.00s)

PASS

ok test 0.135s

 

 

 

 

---