b站源码-lru缓存学习

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

package lrucache

// Element - node to store cache item
type Element struct {
	prev, next *Element
	Key        interface{}
	Value      interface{}
}

// Next - fetch older element
func (e *Element) Next() *Element {
	return e.next
}

// Prev - fetch newer element
func (e *Element) Prev() *Element {
	return e.prev
}

// LRUCache - a data structure that is efficient to insert/fetch/delete cache items [both O(1) time complexity]
type LRUCache struct {
	cache    map[interface{}]*Element
	head     *Element
	tail     *Element
	capacity int
}

// New - create a new lru cache object
func New(capacity int) *LRUCache {
	return &LRUCache{make(map[interface{}]*Element), nil, nil, capacity}
}

// Put - put a cache item into lru cache
func (lc *LRUCache) Put(key interface{}, value interface{}) {
	if e, ok := lc.cache[key]; ok {
		e.Value = value
		lc.refresh(e)
		return
	}

	if lc.capacity == 0 {
		return
	} else if len(lc.cache) >= lc.capacity {
		// evict the oldest item
		delete(lc.cache, lc.tail.Key)
		lc.remove(lc.tail)
	}

	e := &Element{nil, lc.head, key, value}
	lc.cache[key] = e
	if len(lc.cache) != 1 {
		lc.head.prev = e
	} else {
		lc.tail = e
	}
	lc.head = e
}

// Get - get value of key from lru cache with result
func (lc *LRUCache) Get(key interface{}) (interface{}, bool) {
	if e, ok := lc.cache[key]; ok {
		lc.refresh(e)
		return e.Value, ok
	}
	return nil, false
}

// Delete - delete item by key from lru cache
func (lc *LRUCache) Delete(key interface{}) {
	if e, ok := lc.cache[key]; ok {
		delete(lc.cache, key)
		lc.remove(e)
	}
}
// for -range 遍历换成中的所有数据
// Range - calls f sequentially for each key and value present in the lru cache
func (lc *LRUCache) Range(f func(key, value interface{}) bool) {
	for i := lc.head; i != nil; i = i.Next() {
		if !f(i.Key, i.Value) {
			break
		}
	}
}

// Update - inplace update
func (lc *LRUCache) Update(key interface{}, f func(value *interface{})) {
	if e, ok := lc.cache[key]; ok {
		f(&e.Value)
		lc.refresh(e)
	}
}

// Front - get front element of lru cache
func (lc *LRUCache) Front() *Element {
	return lc.head
}

// Back - get back element of lru cache
func (lc *LRUCache) Back() *Element {
	return lc.tail
}

// Len - length of lru cache
func (lc *LRUCache) Len() int {
	return len(lc.cache)
}

// Capacity - capacity of lru cache
func (lc *LRUCache) Capacity() int {
	return lc.capacity
}

//刷新节点，等于把节点丢到 队列头部
func (lc *LRUCache) refresh(e *Element) {
	if e.prev != nil {
		// e.prev  ===>  e ====> e.next
		e.prev.next = e.next
		if e.next == nil {
			lc.tail = e.prev
		} else {
			e.next.prev = e.prev
		}
		e.prev = nil
		e.next = lc.head
		lc.head.prev = e
		lc.head = e
	}
}


//删除节点
func (lc *LRUCache) remove(e *Element) {
	//  prevE   ==>  e  ==>   nextE
	if e.prev == nil {
		//如果前一个节点被移除了，说明轮到这个节点了， 下一个节点成为头节点
		lc.head = e.next
	} else {
		// 删除该节点
		e.prev.next = e.next
	}
	if e.next == nil {
		// e前驱节点将成为 尾节点
		lc.tail = e.prev
	} else {
		// 尾部节点不为空，就不理他
		e.next.prev = e.prev
	}
}