gokachu/replacement_strategy.go at master · BrokenProd/gokachu · GitHub

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
package gokachu

import "container/list"

type ReplacementStrategy uint

const (
	ReplacementStrategyNone ReplacementStrategy = iota
	ReplacementStrategyLRU                      // Least Recently Used
	ReplacementStrategyMRU                      // Most Recently Used
	ReplacementStrategyFIFO                     // First In First Out
	ReplacementStrategyLIFO                     // Last In First Out
	ReplacementStrategyLFU                      // Least Frequently Used
	ReplacementStrategyMFU                      // Most Frequently Used
)

func (g *Gokachu[K, V]) clear() {
	currentElem := g.elems.Front()

	deletedCount := 0
	for deletedCount < g.clearNum && currentElem != nil {
		delete(g.store, currentElem.Value.(*valueWithTTL[K, V]).key)
		nextElem := currentElem.Next()
		g.elems.Remove(currentElem)

		deletedCount++
		currentElem = nextElem
	}
}

func (g *Gokachu[K, V]) moveByHits(elem *list.Element) {
	prev := elem.Prev()
	next := elem.Next()

	switch g.replacementStrategy {
	case ReplacementStrategyLFU:
		if prev != nil && prev.Value.(*valueWithTTL[K, V]).hitCount > elem.Value.(*valueWithTTL[K, V]).hitCount {
			g.elems.MoveBefore(elem, prev)
			g.moveByHits(elem)

			return
		}

		if next != nil && next.Value.(*valueWithTTL[K, V]).hitCount < elem.Value.(*valueWithTTL[K, V]).hitCount {
			g.elems.MoveAfter(elem, next)
			g.moveByHits(elem)
		}

	case ReplacementStrategyMFU:
		if prev != nil && prev.Value.(*valueWithTTL[K, V]).hitCount < elem.Value.(*valueWithTTL[K, V]).hitCount {
			g.elems.MoveBefore(elem, prev)
			g.moveByHits(elem)

			return
		}

		if next != nil && next.Value.(*valueWithTTL[K, V]).hitCount > elem.Value.(*valueWithTTL[K, V]).hitCount {
			g.elems.MoveAfter(elem, next)
			g.moveByHits(elem)
		}
	}
}