You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
naza/pkg/lru/lru.go

74 lines
1.4 KiB
Go

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

// Copyright 2020, Chef. All rights reserved.
// https://github.com/q191201771/naza
//
// Use of this source code is governed by a MIT-style license
// that can be found in the License file.
//
// Author: Chef (191201771@qq.com)
package lru
import "container/list"
type Lru struct {
c int // capacity
m map[interface{}]*list.Element // mapping key -> index
l *list.List // value
}
type pair struct {
k interface{}
v interface{}
}
func New(capacity int) *Lru {
return &Lru{
c: capacity,
m: make(map[interface{}]*list.Element),
l: list.New(),
}
}
// 注意:
// 1. 无论插入前元素是否已经存在插入后元素都会存在于Lru容器中
// 2. 插入元素时,也会更新热度(不管插入前元素是否已经存在)
// @return 插入前元素已经存在则返回false
func (lru *Lru) Put(k interface{}, v interface{}) bool {
var (
exist bool
e *list.Element
)
e, exist = lru.m[k]
if exist {
lru.l.Remove(e)
delete(lru.m, k)
}
// 头部更热
e = lru.l.PushFront(pair{k, v})
lru.m[k] = e
if lru.l.Len() > lru.c {
k = lru.l.Back().Value.(pair).k
lru.l.Remove(lru.l.Back())
delete(lru.m, k)
}
return !exist
}
func (lru *Lru) Get(k interface{}) (v interface{}, exist bool) {
e, exist := lru.m[k]
if !exist {
return nil, false
}
pair := e.Value.(pair)
lru.l.MoveToFront(e)
return pair.v, true
}
func (lru *Lru) Size() int {
return lru.l.Len()
}