gno.land/r/moul/x/daily/lru/v0⧉

1package lru23import (4	"strconv"5	"strings"67	"chain"8)910// capacity is the fixed maximum number of entries the cache holds.11const capacity = 81213// 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   string17	value string18	prev  *node19	next  *node20}2122// cache is a fixed-capacity LRU cache backed by a doubly-linked list and23// an index from key -> node for O(1) lookups.24type cache struct {25	index map[string]*node26	head  *node // most-recently-used27	tail  *node // least-recently-used28	size  int29	hits  int30	miss  int31}3233var c = &cache{index: make(map[string]*node)}3435// 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.next39	} else {40		ca.head = n.next41	}42	if n.next != nil {43		n.next.prev = n.prev44	} else {45		ca.tail = n.prev46	}47	n.prev = nil48	n.next = nil49}5051// pushFront inserts n at the head (MRU position).52func (ca *cache) pushFront(n *node) {53	n.prev = nil54	n.next = ca.head55	if ca.head != nil {56		ca.head.prev = n57	}58	ca.head = n59	if ca.tail == nil {60		ca.tail = n61	}62}6364// touch moves an existing node to the MRU position.65func (ca *cache) touch(n *node) {66	ca.detach(n)67	ca.pushFront(n)68}6970// evict removes the LRU entry (tail) and returns its key.71func (ca *cache) evict() string {72	n := ca.tail73	if n == nil {74		return ""75	}76	ca.detach(n)77	delete(ca.index, n.key)78	ca.size--79	return n.key80}8182// 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 = value87		c.touch(n)88		chain.Emit("Put", "key", key, "op", "update")89		return90	}91	n := &node{key: key, value: value}92	c.index[key] = n93	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}105106// 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 key108// 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, true115	}116	c.miss++117	chain.Emit("Get", "key", key, "result", "miss")118	return "", false119}120121// Reset clears the cache and stats.122func Reset(cur realm) {123	c = &cache{index: make(map[string]*node)}124	chain.Emit("Reset")125}126127// 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, true131	}132	return "", false133}134135// Render displays the cache contents in MRU->LRU order with stats.136func Render(path string) string {137	var b strings.Builder138	b.WriteString("# LRU Cache\n\n")139	b.WriteString("A fixed-capacity least-recently-used cache.\n\n")140141	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.miss147	if total > 0 {148		// integer-percent hit rate, deterministic149		rate := (c.hits * 100) / total150		b.WriteString("- Hit rate: " + strconv.Itoa(rate) + "%\n")151	} else {152		b.WriteString("- Hit rate: n/a\n")153	}154	b.WriteString("\n")155156	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 := 1164	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}170