go-lru-cache-ttl
File: ~/lru.go
The implementation uses three core data structures for O(1) operations:
map[string]*list.Element — O(1) key lookupscontainer/list (doubly-linked list) — O(1) LRU reordering (move-to-front, remove-back)sync.RWMutex — thread safety; Lock() for writes, RLock() for Len()Key design decisions:
| Concern | Approach |
|---|---|
| O(1) Get | Map lookup → move list element to front |
| O(1) Put | Map insert + list push-front; evict list back if at capacity |
| TTL expiration | Each entry stores expires time.Time. On Get, the stale entry is removed lazily. A background reaper goroutine (runs every TTL/2) sweeps expired entries. |
| Eviction policy | "LRU first, then expired": When at capacity, evictLocked removes the back of the list (LRU). Expired entries are removed lazily by the reaper. |
| Zero TTL | No expiration, no reaper goroutine started. |
// Core Get logic — O(1)
func (c *Cache) Get(key string) (interface{}, bool) {
c.mu.Lock()
defer c.mu.Unlock()
elem, ok := c.items[key]
if !ok {
return nil, false
}
ent := elem.Value.(*entry)
if c.ttl > 0 && time.Now().After(ent.expires) {
delete(c.items, key)
c.lru.Remove(elem)
return nil, false
}
c.lru.MoveToFront(elem)
return ent.value, true
}
// Core Put logic — O(1)
func (c *Cache) Put(key string, value interface{}) {
c.mu.Lock()
defer c.mu.Unlock()
if elem, ok := c.items[key]; ok {
ent := elem.Value.(*entry)
ent.value = value
if c.ttl > 0 {
ent.expires = time.Now().Add(c.ttl)
}
c.lru.MoveToFront(elem)
return
}
if c.lru.Len() >= c.capacity {
c.evictLocked()
}
ent := &entry{key: key, value: value}
if c.ttl > 0 {
ent.expires = time.Now().Add(c.ttl)
}
elem := c.lru.PushFront(ent)
c.items[key] = elem
}
File: ~/lru_test.go — 14 test functions covering all cases.
All 14 tests pass (2.3s) and the race detector reports no data races: ``` === RUN TestBasicGetPut — PASS === RUN TestGetNonExistent — PASS === RUN TestEviction — PASS === RUN TestLRUOrder — PASS === RUN TestUpdate — PASS === RUN TestTTLExpiration — PASS (1.10s) === RUN TestTTLWithZero — PASS === RUN TestTTLPartialExpiration — PASS (1.10s) === RUN TestConcurrentAccess — PASS (50 writers + 50 readers) === RUN TestConcurrentGetPutOnSameKey — PASS (100 goroutines, same key) === RUN TestEvictionOrderLRUBeforeExpired — PASS === RUN TestLen — PASS === RUN TestDefaultCapacity — PASS === RUN TestPutAfterEviction — PASS ok lrucache 2.308s ok lrucache 3.319s (race detector) ``` Edge cases tested: 1. **Non-existent key** → `(nil, false)` 2. **Eviction at capacity** → LRU entry removed, new entry stays 3. **LRU reordering on Get** → accessed key becomes MRU, correct LRU evicted next 4. **Update refreshes position** → updated key is MRU, old LRU evicted next 5. **TTL expiration** → item inaccessible after TTL elapses 6. **Zero TTL** → items persist indefinitely 7. **Partial expiration** → only expired items removed, fresh ones survive 8. **Concurrent reads/writes** → 50 writers + 50 readers, no races, capacity respected 9. **Same-key contention** → 100 goroutines on one key 10. **Default capacity** → `New(-1, 0)` defaults to 100 11. **Put after eviction** → eviction makes room, subsequent puts work ---
{"model": "", "problem_class": "go-lru-cache-ttl", "result": "passed", "tests": 14}File: ~/lru.go
The implementation uses three core data structures for O(1) operations:
map[string]*list.Element — O(1) key lookupscontainer/list (doubly-linked list) — O(1) LRU reordering (move-to-front, remove-back)sync.RWMutex — thread safety; Lock() for writes, RLock() for Len()Key design decisions:
| Concern | Approach |
|---|---|
| O(1) Get | Map lookup → move list element to front |
| O(1) Put | Map insert + list push-front; evict list back if at capacity |
| TTL expiration | Each entry stores expires time.Time. On Get, the stale entry is removed lazily. A background reaper goroutine (runs every TTL/2) sweeps expired entries. |
| Eviction policy | "LRU first, then expired": When at capacity, evictLocked removes the back of the list (LRU). Expired entries are removed lazily by the reaper. |
| Zero TTL | No expiration, no reaper goroutine started. |
// Core Get logic — O(1)
func (c *Cache) Get(key string) (interface{}, bool) {
c.mu.Lock()
defer c.mu.Unlock()
elem, ok := c.items[key]
if !ok {
return nil, false
}
ent := elem.Value.(*entry)
if c.ttl > 0 && time.Now().After(ent.expires) {
delete(c.items, key)
c.lru.Remove(elem)
return nil, false
}
c.lru.MoveToFront(elem)
return ent.value, true
}
// Core Put logic — O(1)
func (c *Cache) Put(key string, value interface{}) {
c.mu.Lock()
defer c.mu.Unlock()
if elem, ok := c.items[key]; ok {
ent := elem.Value.(*entry)
ent.value = value
if c.ttl > 0 {
ent.expires = time.Now().Add(c.ttl)
}
c.lru.MoveToFront(elem)
return
}
if c.lru.Len() >= c.capacity {
c.evictLocked()
}
ent := &entry{key: key, value: value}
if c.ttl > 0 {
ent.expires = time.Now().Add(c.ttl)
}
elem := c.lru.PushFront(ent)
c.items[key] = elem
}
File: ~/lru_test.go — 14 test functions covering all cases.
All 14 tests pass (2.3s) and the race detector reports no data races: ``` === RUN TestBasicGetPut — PASS === RUN TestGetNonExistent — PASS === RUN TestEviction — PASS === RUN TestLRUOrder — PASS === RUN TestUpdate — PASS === RUN TestTTLExpiration — PASS (1.10s) === RUN TestTTLWithZero — PASS === RUN TestTTLPartialExpiration — PASS (1.10s) === RUN TestConcurrentAccess — PASS (50 writers + 50 readers) === RUN TestConcurrentGetPutOnSameKey — PASS (100 goroutines, same key) === RUN TestEvictionOrderLRUBeforeExpired — PASS === RUN TestLen — PASS === RUN TestDefaultCapacity — PASS === RUN TestPutAfterEviction — PASS ok lrucache 2.308s ok lrucache 3.319s (race detector) ``` Edge cases tested: 1. **Non-existent key** → `(nil, false)` 2. **Eviction at capacity** → LRU entry removed, new entry stays 3. **LRU reordering on Get** → accessed key becomes MRU, correct LRU evicted next 4. **Update refreshes position** → updated key is MRU, old LRU evicted next 5. **TTL expiration** → item inaccessible after TTL elapses 6. **Zero TTL** → items persist indefinitely 7. **Partial expiration** → only expired items removed, fresh ones survive 8. **Concurrent reads/writes** → 50 writers + 50 readers, no races, capacity respected 9. **Same-key contention** → 100 goroutines on one key 10. **Default capacity** → `New(-1, 0)` defaults to 100 11. **Put after eviction** → eviction makes room, subsequent puts work ---
{"model": "", "problem_class": "go-lru-cache-ttl", "result": "passed", "tests": 14}