kacerrandClaude Fable 5
b290957fc9
map[string]*list.Element + doubly linked list; Get/Put move hits to the front, Put evicts from the back when at capacity, and every method (including Len) takes the mutex. Add TestLenRacesWithPut, which calls Len concurrently with a writer — the existing test only read Len after wg.Wait(), so an unsynchronized Len would never trip the race detector there. Co-Authored-By: Claude Fable 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_012MpK9niZm4jcs3mAJbxMfi
104 lines
2.6 KiB
Go
104 lines
2.6 KiB
Go
// Exercise 05 — LRU Cache
|
|
//
|
|
// ASSIGNMENT
|
|
// ----------
|
|
// Implement a thread-safe LRU cache:
|
|
//
|
|
// 1. NewLRU(capacity): holds at most `capacity` entries.
|
|
// 2. Get(key): returns (value, true) and marks the entry most-recently-used;
|
|
// (nil, false) on miss.
|
|
// 3. Put(key, value): inserts or updates; updating also marks MRU.
|
|
// When over capacity, evicts the LEAST recently used entry.
|
|
// 4. Both operations O(1). (Hint: map + container/list, or hand-roll a
|
|
// doubly linked list.)
|
|
// 5. Safe for concurrent use (tests run with -race).
|
|
//
|
|
// Run the tests: go test -race ./05-lru-cache/
|
|
package main
|
|
|
|
import (
|
|
"container/list"
|
|
"fmt"
|
|
"sync"
|
|
)
|
|
|
|
type entry struct {
|
|
key string
|
|
val any
|
|
}
|
|
type LRU struct {
|
|
// TODO: fields (mutex, capacity, map[string]*list.Element, *list.List)
|
|
// Remember: the list element must store the KEY too, or you can't
|
|
// delete the map entry on eviction.
|
|
mu sync.Mutex
|
|
capacity int
|
|
lruList *list.List
|
|
kvMap map[string]*list.Element
|
|
}
|
|
|
|
// NewLRU creates an LRU cache with the given capacity (capacity >= 1).
|
|
// TODO: implement me.
|
|
func NewLRU(capacity int) *LRU {
|
|
return &LRU{capacity: capacity, lruList: list.New(), kvMap: make(map[string]*list.Element)}
|
|
}
|
|
|
|
// Get returns the value and whether it was present. Hit = mark MRU.
|
|
// TODO: implement me.
|
|
func (c *LRU) Get(key string) (any, bool) {
|
|
c.mu.Lock()
|
|
defer c.mu.Unlock()
|
|
|
|
if el, ok := c.kvMap[key]; ok {
|
|
c.lruList.MoveToFront(el)
|
|
return el.Value.(*entry).val, true
|
|
}
|
|
|
|
return nil, false
|
|
}
|
|
|
|
// Put inserts/updates a value, evicting the LRU entry if over capacity.
|
|
// TODO: implement me.
|
|
func (c *LRU) Put(key string, val any) {
|
|
// lock mutex
|
|
c.mu.Lock()
|
|
defer c.mu.Unlock()
|
|
// if key exists, update value and move it to the front of the list and return/quit
|
|
if el, ok := c.kvMap[key]; ok {
|
|
c.lruList.MoveToFront(el)
|
|
el.Value.(*entry).val = val
|
|
return
|
|
}
|
|
|
|
// if len > capacity, remove the last element from both the list and the map
|
|
if c.lruList.Len() >= c.capacity {
|
|
// remove last element from list
|
|
lastEl := c.lruList.Back()
|
|
c.lruList.Remove(lastEl)
|
|
// remove it by key from map
|
|
delete(c.kvMap, lastEl.Value.(*entry).key)
|
|
}
|
|
|
|
// if key doesn't exist, insert'
|
|
el := c.lruList.PushFront(&entry{key: key, val: val})
|
|
c.kvMap[key] = el
|
|
|
|
}
|
|
|
|
// Len returns the current number of entries.
|
|
// TODO: implement me.
|
|
func (c *LRU) Len() int {
|
|
c.mu.Lock()
|
|
defer c.mu.Unlock()
|
|
return c.lruList.Len()
|
|
}
|
|
|
|
func main() {
|
|
c := NewLRU(2)
|
|
c.Put("a", 1)
|
|
c.Put("b", 2)
|
|
c.Get("a") // a is now MRU
|
|
c.Put("c", 3) // evicts b
|
|
_, ok := c.Get("b")
|
|
fmt.Println("b present:", ok) // false
|
|
}
|