Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Playground

gnomod.toml

module = "gno.land/r/moul/x/daily/lru/v0"
gno = "0.9"

[addpkg]
  creator = "g1manfred47kzduec920z88wfr64ylksmdcedlf5"
  height = 26367
  max_deposit = "100000000ugnot"

lru.gno

package lru

import (
	"strconv"
	"strings"

	"chain"
)

// capacity is the fixed maximum number of entries the cache holds.
const capacity = 8

// node is a doubly-linked-list node holding a key/value pair.
// The list is ordered MRU (head) -> LRU (tail).
type node struct {
	key   string
	value string
	prev  *node
	next  *node
}

// cache is a fixed-capacity LRU cache backed by a doubly-linked list and
// an index from key -> node for O(1) lookups.
type cache struct {
	index map[string]*node
	head  *node // most-recently-used
	tail  *node // least-recently-used
	size  int
	hits  int
	miss  int
}

var c = &cache{index: make(map[string]*node)}

// detach removes n from the linked list (does not touch the index).
func (ca *cache) detach(n *node) {
	if n.prev != nil {
		n.prev.next = n.next
	} else {
		ca.head = n.next
	}
	if n.next != nil {
		n.next.prev = n.prev
	} else {
		ca.tail = n.prev
	}
	n.prev = nil
	n.next = nil
}

// pushFront inserts n at the head (MRU position).
func (ca *cache) pushFront(n *node) {
	n.prev = nil
	n.next = ca.head
	if ca.head != nil {
		ca.head.prev = n
	}
	ca.head = n
	if ca.tail == nil {
		ca.tail = n
	}
}

// touch moves an existing node to the MRU position.
func (ca *cache) touch(n *node) {
	ca.detach(n)
	ca.pushFront(n)
}

// evict removes the LRU entry (tail) and returns its key.
func (ca *cache) evict() string {
	n := ca.tail
	if n == nil {
		return ""
	}
	ca.detach(n)
	delete(ca.index, n.key)
	ca.size--
	return n.key
}

// Put inserts or updates key with value and marks it most-recently-used.
// Evicts the least-recently-used entry if capacity is exceeded.
func Put(cur realm, key string, value string) {
	if n, ok := c.index[key]; ok {
		n.value = value
		c.touch(n)
		chain.Emit("Put", "key", key, "op", "update")
		return
	}
	n := &node{key: key, value: value}
	c.index[key] = n
	c.pushFront(n)
	c.size++
	evicted := ""
	if c.size > capacity {
		evicted = c.evict()
	}
	if evicted != "" {
		chain.Emit("Put", "key", key, "op", "insert", "evicted", evicted)
	} else {
		chain.Emit("Put", "key", key, "op", "insert")
	}
}

// Get returns the value for key and marks it most-recently-used.
// It records a hit or a miss. The returned bool reports whether the key
// was present.
func Get(cur realm, key string) (string, bool) {
	if n, ok := c.index[key]; ok {
		c.touch(n)
		c.hits++
		chain.Emit("Get", "key", key, "result", "hit")
		return n.value, true
	}
	c.miss++
	chain.Emit("Get", "key", key, "result", "miss")
	return "", false
}

// Reset clears the cache and stats.
func Reset(cur realm) {
	c = &cache{index: make(map[string]*node)}
	chain.Emit("Reset")
}

// peek returns the value without affecting recency or stats (read helper).
func peek(key string) (string, bool) {
	if n, ok := c.index[key]; ok {
		return n.value, true
	}
	return "", false
}

// Render displays the cache contents in MRU->LRU order with stats.
func Render(path string) string {
	var b strings.Builder
	b.WriteString("# LRU Cache\n\n")
	b.WriteString("A fixed-capacity least-recently-used cache.\n\n")

	b.WriteString("## Stats\n\n")
	b.WriteString("- Capacity: " + strconv.Itoa(capacity) + "\n")
	b.WriteString("- Size: " + strconv.Itoa(c.size) + "\n")
	b.WriteString("- Hits: " + strconv.Itoa(c.hits) + "\n")
	b.WriteString("- Misses: " + strconv.Itoa(c.miss) + "\n")
	total := c.hits + c.miss
	if total > 0 {
		// integer-percent hit rate, deterministic
		rate := (c.hits * 100) / total
		b.WriteString("- Hit rate: " + strconv.Itoa(rate) + "%\n")
	} else {
		b.WriteString("- Hit rate: n/a\n")
	}
	b.WriteString("\n")

	b.WriteString("## Entries (MRU → LRU)\n\n")
	if c.head == nil {
		b.WriteString("_empty_\n")
		return b.String()
	}
	b.WriteString("| # | Key | Value |\n")
	b.WriteString("|---|-----|-------|\n")
	i := 1
	for n := c.head; n != nil; n = n.next {
		b.WriteString("| " + strconv.Itoa(i) + " | " + n.key + " | " + n.value + " |\n")
		i++
	}
	return b.String()
}