lru.gno

  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}