492 lines
13 KiB
Nim
492 lines
13 KiB
Nim
## Comprehensive Tests for LRU Cache
|
|
##
|
|
## This test suite verifies:
|
|
## - Basic cache operations (get, put, delete, clear)
|
|
## - LRU eviction policy correctness
|
|
## - Cache statistics tracking
|
|
## - Thread-safe operations
|
|
## - Edge cases and boundary conditions
|
|
|
|
import unittest
|
|
import options
|
|
import ../src/nip/resolver/lru_cache
|
|
|
|
suite "LRU Cache Construction":
|
|
test "Create cache with valid capacity":
|
|
let cache = newLRUCache[string, int](capacity = 10)
|
|
check cache.len == 0
|
|
check cache.capacity == 10
|
|
check not cache.isFull
|
|
|
|
test "Create cache with capacity 1":
|
|
let cache = newLRUCache[string, int](capacity = 1)
|
|
check cache.capacity == 1
|
|
|
|
test "Create thread-safe cache":
|
|
let cache = newLRUCache[string, int](capacity = 10, threadSafe = true)
|
|
check cache.capacity == 10
|
|
|
|
suite "Basic Cache Operations":
|
|
test "Put and get single entry":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
|
|
let value = cache.get("key1")
|
|
check value.isSome
|
|
check value.get == 100
|
|
check cache.len == 1
|
|
|
|
test "Put multiple entries":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
check cache.len == 3
|
|
check cache.get("key1").get == 100
|
|
check cache.get("key2").get == 200
|
|
check cache.get("key3").get == 300
|
|
|
|
test "Get non-existent key returns None":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
|
|
let value = cache.get("missing")
|
|
check value.isNone
|
|
|
|
test "Update existing key":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key1", 200)
|
|
|
|
check cache.len == 1
|
|
check cache.get("key1").get == 200
|
|
|
|
test "Update existing key multiple times":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key1", 200)
|
|
cache.put("key1", 300)
|
|
|
|
check cache.len == 1
|
|
check cache.get("key1").get == 300
|
|
|
|
test "Contains check":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
|
|
check "key1" in cache
|
|
check "key2" in cache
|
|
check "missing" notin cache
|
|
|
|
test "Delete existing entry":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
|
|
check cache.delete("key1")
|
|
check cache.len == 1
|
|
check "key1" notin cache
|
|
check "key2" in cache
|
|
|
|
test "Delete non-existent entry":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
|
|
check not cache.delete("missing")
|
|
check cache.len == 1
|
|
|
|
test "Clear empty cache":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.clear()
|
|
check cache.len == 0
|
|
|
|
test "Clear non-empty cache":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
cache.clear()
|
|
check cache.len == 0
|
|
check "key1" notin cache
|
|
check "key2" notin cache
|
|
check "key3" notin cache
|
|
|
|
suite "LRU Eviction Policy":
|
|
test "No eviction when under capacity":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
check cache.len == 3
|
|
check "key1" in cache
|
|
check "key2" in cache
|
|
check "key3" in cache
|
|
|
|
test "Evict least recently used when at capacity":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
cache.put("key4", 400) # Should evict key1
|
|
|
|
check cache.len == 3
|
|
check "key1" notin cache
|
|
check "key2" in cache
|
|
check "key3" in cache
|
|
check "key4" in cache
|
|
|
|
test "Evict multiple entries when adding multiple":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
cache.put("key4", 400) # Evict key1
|
|
cache.put("key5", 500) # Evict key2
|
|
|
|
check cache.len == 3
|
|
check "key1" notin cache
|
|
check "key2" notin cache
|
|
check "key3" in cache
|
|
check "key4" in cache
|
|
check "key5" in cache
|
|
|
|
test "Access updates LRU order":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
# Access key1 to make it most recently used
|
|
discard cache.get("key1")
|
|
|
|
# Add key4, should evict key2 (least recently used)
|
|
cache.put("key4", 400)
|
|
|
|
check "key1" in cache
|
|
check "key2" notin cache
|
|
check "key3" in cache
|
|
check "key4" in cache
|
|
|
|
test "Multiple accesses update LRU order":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
# Access key1 and key2
|
|
discard cache.get("key1")
|
|
discard cache.get("key2")
|
|
|
|
# Add key4, should evict key3 (least recently used)
|
|
cache.put("key4", 400)
|
|
|
|
check "key1" in cache
|
|
check "key2" in cache
|
|
check "key3" notin cache
|
|
check "key4" in cache
|
|
|
|
test "Update preserves entry and updates LRU":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
# Update key1 (makes it most recently used)
|
|
cache.put("key1", 150)
|
|
|
|
# Add key4, should evict key2
|
|
cache.put("key4", 400)
|
|
|
|
check "key1" in cache
|
|
check cache.get("key1").get == 150
|
|
check "key2" notin cache
|
|
check "key3" in cache
|
|
check "key4" in cache
|
|
|
|
test "Capacity 1 cache evicts immediately":
|
|
let cache = newLRUCache[string, int](capacity = 1)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
|
|
check cache.len == 1
|
|
check "key1" notin cache
|
|
check "key2" in cache
|
|
|
|
test "Capacity 1 cache with updates":
|
|
let cache = newLRUCache[string, int](capacity = 1)
|
|
cache.put("key1", 100)
|
|
cache.put("key1", 200)
|
|
|
|
check cache.len == 1
|
|
check cache.get("key1").get == 200
|
|
|
|
suite "Cache Statistics":
|
|
test "Track hits":
|
|
let cache = newLRUCacheWithStats[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
|
|
discard cache.get("key1")
|
|
discard cache.get("key2")
|
|
discard cache.get("key1")
|
|
|
|
let stats = cache.getStats()
|
|
check stats.hits == 3
|
|
check stats.misses == 0
|
|
|
|
test "Track misses":
|
|
let cache = newLRUCacheWithStats[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
|
|
discard cache.get("missing1")
|
|
discard cache.get("missing2")
|
|
discard cache.get("key1")
|
|
|
|
let stats = cache.getStats()
|
|
check stats.hits == 1
|
|
check stats.misses == 2
|
|
|
|
test "Track hits and misses":
|
|
let cache = newLRUCacheWithStats[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
|
|
discard cache.get("key1") # Hit
|
|
discard cache.get("missing") # Miss
|
|
discard cache.get("key1") # Hit
|
|
discard cache.get("missing") # Miss
|
|
|
|
let stats = cache.getStats()
|
|
check stats.hits == 2
|
|
check stats.misses == 2
|
|
check cache.hitRate() == 0.5
|
|
|
|
test "Track evictions":
|
|
let cache = newLRUCacheWithStats[string, int](capacity = 2)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300) # Eviction
|
|
cache.put("key4", 400) # Eviction
|
|
|
|
let stats = cache.getStats()
|
|
check stats.evictions == 2
|
|
|
|
test "No eviction on update":
|
|
let cache = newLRUCacheWithStats[string, int](capacity = 2)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key1", 150) # Update, not eviction
|
|
|
|
let stats = cache.getStats()
|
|
check stats.evictions == 0
|
|
|
|
test "Hit rate calculation":
|
|
let cache = newLRUCacheWithStats[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
|
|
discard cache.get("key1") # Hit
|
|
discard cache.get("key1") # Hit
|
|
discard cache.get("key1") # Hit
|
|
discard cache.get("missing") # Miss
|
|
|
|
check cache.hitRate() == 0.75
|
|
|
|
test "Hit rate with no accesses":
|
|
let cache = newLRUCacheWithStats[string, int](capacity = 5)
|
|
check cache.hitRate() == 0.0
|
|
|
|
test "Reset statistics":
|
|
let cache = newLRUCacheWithStats[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
discard cache.get("key1")
|
|
discard cache.get("missing")
|
|
|
|
cache.resetStats()
|
|
|
|
let stats = cache.getStats()
|
|
check stats.hits == 0
|
|
check stats.misses == 0
|
|
check stats.evictions == 0
|
|
|
|
test "Statistics after clear":
|
|
let cache = newLRUCacheWithStats[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
discard cache.get("key1")
|
|
|
|
let statsBefore = cache.getStats()
|
|
check statsBefore.size == 2
|
|
|
|
cache.clear()
|
|
|
|
let statsAfter = cache.getStats()
|
|
check statsAfter.size == 0
|
|
check statsAfter.hits == statsBefore.hits # Stats not reset
|
|
|
|
suite "Iteration":
|
|
test "Iterate over empty cache":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
|
|
var count = 0
|
|
for (key, value) in cache.items:
|
|
count += 1
|
|
|
|
check count == 0
|
|
|
|
test "Iterate over entries":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
var count = 0
|
|
var sum = 0
|
|
for (key, value) in cache.items:
|
|
count += 1
|
|
sum += value
|
|
|
|
check count == 3
|
|
check sum == 600
|
|
|
|
test "Iterate in LRU order":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
var keys: seq[string]
|
|
for (key, value) in cache.itemsLRU:
|
|
keys.add(key)
|
|
|
|
# Most recent first (key3), least recent last (key1)
|
|
check keys.len == 3
|
|
check keys[0] == "key3"
|
|
check keys[1] == "key2"
|
|
check keys[2] == "key1"
|
|
|
|
test "LRU order after access":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
# Access key1 to make it most recently used
|
|
discard cache.get("key1")
|
|
|
|
var keys: seq[string]
|
|
for (key, value) in cache.itemsLRU:
|
|
keys.add(key)
|
|
|
|
# key1 should now be first (most recent)
|
|
check keys[0] == "key1"
|
|
|
|
test "Iteration doesn't affect LRU order":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key3", 300)
|
|
|
|
# Iterate (shouldn't affect order)
|
|
for (key, value) in cache.items:
|
|
discard
|
|
|
|
# Add key4, should still evict key1
|
|
cache.put("key4", 400)
|
|
|
|
check "key1" notin cache
|
|
|
|
suite "Edge Cases":
|
|
test "Empty cache operations":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
|
|
check cache.len == 0
|
|
check cache.get("missing").isNone
|
|
check "missing" notin cache
|
|
check not cache.delete("missing")
|
|
|
|
test "Single entry cache":
|
|
let cache = newLRUCache[string, int](capacity = 1)
|
|
cache.put("key1", 100)
|
|
|
|
check cache.len == 1
|
|
check cache.isFull
|
|
check cache.get("key1").get == 100
|
|
|
|
test "Large capacity cache":
|
|
let cache = newLRUCache[string, int](capacity = 1000)
|
|
|
|
for i in 0..<500:
|
|
cache.put("key" & $i, i)
|
|
|
|
check cache.len == 500
|
|
check not cache.isFull
|
|
|
|
test "Fill cache to exact capacity":
|
|
let cache = newLRUCache[string, int](capacity = 5)
|
|
|
|
for i in 0..<5:
|
|
cache.put("key" & $i, i)
|
|
|
|
check cache.len == 5
|
|
check cache.isFull
|
|
|
|
test "Repeatedly fill and clear":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
|
|
for round in 0..<3:
|
|
for i in 0..<3:
|
|
cache.put("key" & $i, i)
|
|
check cache.len == 3
|
|
cache.clear()
|
|
check cache.len == 0
|
|
|
|
suite "Complex Scenarios":
|
|
test "Interleaved puts and gets":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
|
|
cache.put("key1", 100)
|
|
discard cache.get("key1")
|
|
cache.put("key2", 200)
|
|
discard cache.get("key1")
|
|
cache.put("key3", 300)
|
|
discard cache.get("key2")
|
|
cache.put("key4", 400) # Should evict key3
|
|
|
|
check "key1" in cache
|
|
check "key2" in cache
|
|
check "key3" notin cache
|
|
check "key4" in cache
|
|
|
|
test "Alternating updates and new entries":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
cache.put("key1", 150) # Update
|
|
cache.put("key3", 300)
|
|
cache.put("key2", 250) # Update
|
|
cache.put("key4", 400) # Should evict key3
|
|
|
|
check "key1" in cache
|
|
check "key2" in cache
|
|
check "key3" notin cache
|
|
check "key4" in cache
|
|
|
|
test "Delete and re-add":
|
|
let cache = newLRUCache[string, int](capacity = 3)
|
|
|
|
cache.put("key1", 100)
|
|
cache.put("key2", 200)
|
|
discard cache.delete("key1")
|
|
cache.put("key1", 150) # Re-add
|
|
cache.put("key3", 300)
|
|
cache.put("key4", 400) # Should evict key2
|
|
|
|
check "key1" in cache
|
|
check "key2" notin cache
|
|
check "key3" in cache
|
|
check "key4" in cache
|