lru.gno
3.84 Kb · 169 lines
1package lru
2
3import (
4 "strconv"
5 "strings"
6
7 "chain"
8)
9
10// capacity is the fixed maximum number of entries the cache holds.
11const capacity = 8
12
13// node is a doubly-linked-list node holding a key/value pair.
14// The list is ordered MRU (head) -> LRU (tail).
15type node struct {
16 key string
17 value string
18 prev *node
19 next *node
20}
21
22// cache is a fixed-capacity LRU cache backed by a doubly-linked list and
23// an index from key -> node for O(1) lookups.
24type cache struct {
25 index map[string]*node
26 head *node // most-recently-used
27 tail *node // least-recently-used
28 size int
29 hits int
30 miss int
31}
32
33var c = &cache{index: make(map[string]*node)}
34
35// detach removes n from the linked list (does not touch the index).
36func (ca *cache) detach(n *node) {
37 if n.prev != nil {
38 n.prev.next = n.next
39 } else {
40 ca.head = n.next
41 }
42 if n.next != nil {
43 n.next.prev = n.prev
44 } else {
45 ca.tail = n.prev
46 }
47 n.prev = nil
48 n.next = nil
49}
50
51// pushFront inserts n at the head (MRU position).
52func (ca *cache) pushFront(n *node) {
53 n.prev = nil
54 n.next = ca.head
55 if ca.head != nil {
56 ca.head.prev = n
57 }
58 ca.head = n
59 if ca.tail == nil {
60 ca.tail = n
61 }
62}
63
64// touch moves an existing node to the MRU position.
65func (ca *cache) touch(n *node) {
66 ca.detach(n)
67 ca.pushFront(n)
68}
69
70// evict removes the LRU entry (tail) and returns its key.
71func (ca *cache) evict() string {
72 n := ca.tail
73 if n == nil {
74 return ""
75 }
76 ca.detach(n)
77 delete(ca.index, n.key)
78 ca.size--
79 return n.key
80}
81
82// Put inserts or updates key with value and marks it most-recently-used.
83// Evicts the least-recently-used entry if capacity is exceeded.
84func Put(cur realm, key string, value string) {
85 if n, ok := c.index[key]; ok {
86 n.value = value
87 c.touch(n)
88 chain.Emit("Put", "key", key, "op", "update")
89 return
90 }
91 n := &node{key: key, value: value}
92 c.index[key] = n
93 c.pushFront(n)
94 c.size++
95 evicted := ""
96 if c.size > capacity {
97 evicted = c.evict()
98 }
99 if evicted != "" {
100 chain.Emit("Put", "key", key, "op", "insert", "evicted", evicted)
101 } else {
102 chain.Emit("Put", "key", key, "op", "insert")
103 }
104}
105
106// Get returns the value for key and marks it most-recently-used.
107// It records a hit or a miss. The returned bool reports whether the key
108// was present.
109func Get(cur realm, key string) (string, bool) {
110 if n, ok := c.index[key]; ok {
111 c.touch(n)
112 c.hits++
113 chain.Emit("Get", "key", key, "result", "hit")
114 return n.value, true
115 }
116 c.miss++
117 chain.Emit("Get", "key", key, "result", "miss")
118 return "", false
119}
120
121// Reset clears the cache and stats.
122func Reset(cur realm) {
123 c = &cache{index: make(map[string]*node)}
124 chain.Emit("Reset")
125}
126
127// peek returns the value without affecting recency or stats (read helper).
128func peek(key string) (string, bool) {
129 if n, ok := c.index[key]; ok {
130 return n.value, true
131 }
132 return "", false
133}
134
135// Render displays the cache contents in MRU->LRU order with stats.
136func Render(path string) string {
137 var b strings.Builder
138 b.WriteString("# LRU Cache\n\n")
139 b.WriteString("A fixed-capacity least-recently-used cache.\n\n")
140
141 b.WriteString("## Stats\n\n")
142 b.WriteString("- Capacity: " + strconv.Itoa(capacity) + "\n")
143 b.WriteString("- Size: " + strconv.Itoa(c.size) + "\n")
144 b.WriteString("- Hits: " + strconv.Itoa(c.hits) + "\n")
145 b.WriteString("- Misses: " + strconv.Itoa(c.miss) + "\n")
146 total := c.hits + c.miss
147 if total > 0 {
148 // integer-percent hit rate, deterministic
149 rate := (c.hits * 100) / total
150 b.WriteString("- Hit rate: " + strconv.Itoa(rate) + "%\n")
151 } else {
152 b.WriteString("- Hit rate: n/a\n")
153 }
154 b.WriteString("\n")
155
156 b.WriteString("## Entries (MRU → LRU)\n\n")
157 if c.head == nil {
158 b.WriteString("_empty_\n")
159 return b.String()
160 }
161 b.WriteString("| # | Key | Value |\n")
162 b.WriteString("|---|-----|-------|\n")
163 i := 1
164 for n := c.head; n != nil; n = n.next {
165 b.WriteString("| " + strconv.Itoa(i) + " | " + n.key + " | " + n.value + " |\n")
166 i++
167 }
168 return b.String()
169}
