手撕LRU代码

package main
import (
  "container/list"
  "fmt"
  "sync"
)
type LRU struct {
  max   int                                      //存储key的最大数量
  list  *list.List                               //双向链表
  Call  func(key interface{}, value interface{}) //淘汰kv时的回调函数
  cache map[interface{}]*list.Element            //缓存
  mu    *sync.Mutex                              //互斥锁
}
type Node struct {
  Key interface{}
  Val interface{}
}
// NewLRU 返回一个LRU的实例
func NewLRU(len int) *LRU {
  return &LRU{
    max:   len,
    list:  list.New(),
    Call:  nil,
    cache: make(map[interface{}]*list.Element),
    mu:    new(sync.Mutex),
  }
}
// Add 添加一个kv到缓存中
func (lru *LRU) Add(key, val interface{}) error {
  lru.mu.Lock()
  defer lru.mu.Unlock()
  //如果存在则更新，并将结点移到最前面
  if e, ok := lru.cache[key]; ok {
    e.Value.(*Node).Val = val
    lru.list.MoveToFront(e)
    return nil
  }
  //如果不存在则头插到双向链表中
  e := lru.list.PushFront(&Node{
    Key: key,
    Val: val,
  })
  //添加至缓存中
  lru.cache[key] = e
  //如果元素的数量超过最大值了，那么把末端的淘汰
  if lru.max != 0 && lru.list.Len() > lru.max {
    if e := lru.list.Back(); e != nil {
      lru.list.Remove(e)
      node := e.Value.(*Node)
      delete(lru.cache, node.Key)
      if lru.Call != nil {
        lru.Call(node.Key, node.Val)
      }
    }
  }
  return nil
}
func (lru *LRU) Get(key interface{}) (val interface{}, ok bool) {
  lru.mu.Lock()
  defer lru.mu.Unlock()
  //如果存在，先把该kv移到链表头部再返回
  if e, ok := lru.cache[key]; ok {
    lru.list.MoveToFront(e)
    return e.Value.(*Node).Val, true
  }
  return
}
func (lru *LRU) GetAll() (data []*Node) {
  lru.mu.Lock()
  defer lru.mu.Unlock()
  for _, v := range lru.cache {
    data = append(data, v.Value.(*Node))
  }
  return data
}
func (lru *LRU) Del(key interface{}) {
  lru.mu.Lock()
  defer lru.mu.Unlock()
  if e, ok := lru.cache[key]; ok {
    lru.list.Remove(e)
    node := e.Value.(*Node)
    delete(lru.cache, node.Key)
    if lru.Call != nil {
      lru.Call(node.Key, node.Val)
    }
  }
}
func main() {
  lru := NewLRU(3)
  lru.Add("w", "1")
  lru.Add("x", "2")
  lru.Add("f", "3")
  lru.Add("c", "4")
  lru.Add("s", "5")
  for _, node := range lru.GetAll() {
    fmt.Println(node)
  }
  fmt.Println("~~~分割线~~~")
  lru.Del("f")
  for _, node := range lru.GetAll() {
    fmt.Println(node)
  }
  fmt.Println("~~~分割线~~~")
  lru.Add("qq", "68725032")
  for _, node := range lru.GetAll() {
    fmt.Println(node)
  }
}