okami.mom/ultraviolet

git clone https://git.nkp.pet/okami.mom/ultraviolet

Vadimperf(layout): add LRU cache for layout splitting (#91)227cc8b

upstream
branchesmainupstreamall refs →
1.0 KiB69 linesraw
1package lru
2
3import (
4	"container/list"
5	"fmt"
6)
7
8type LRU[K comparable, V any] struct {
9	size int
10
11	items map[K]*list.Element
12	evict *list.List
13}
14
15type entry[K comparable, T any] struct {
16	Key   K
17	Value T
18}
19
20func New[K comparable, V any](size int) *LRU[K, V] {
21	if size < 0 {
22		panic(fmt.Sprintf("lru: negative size given: %d", size))
23	}
24
25	return &LRU[K, V]{
26		size:  size,
27		items: make(map[K]*list.Element),
28		evict: list.New(),
29	}
30}
31
32func (c *LRU[K, V]) Get(key K) (V, bool) {
33	e, ok := c.items[key]
34	if !ok {
35		var zero V
36
37		return zero, false
38	}
39
40	c.evict.MoveToFront(e)
41
42	return e.Value.(entry[K, V]).Value, true
43}
44
45func (c *LRU[K, V]) Add(key K, value V) (evicted bool) {
46	if e, ok := c.items[key]; ok {
47		c.evict.MoveToFront(e)
48		e.Value = value
49
50		return false
51	}
52
53	e := c.evict.PushFront(key)
54
55	e.Value = entry[K, V]{Key: key, Value: value}
56
57	c.items[key] = e
58
59	if c.evict.Len() <= c.size {
60		return false
61	}
62
63	if oldest := c.evict.Back(); oldest != nil {
64		c.evict.Remove(oldest)
65		delete(c.items, oldest.Value.(entry[K, V]).Key)
66	}
67
68	return true
69}