sieve_k_test.go

package sieve

import (
	"testing"
)

// TestSieveK_EvictionSurvival verifies that an item accessed k+1 times
// survives k eviction passes, while an item accessed once is evicted
// on the first pass.
func TestSieveK_EvictionSurvival(t *testing.T) {
	// Cache of 3 slots, k=3
	c := Must(New[string, int](3, WithVisitClamp(3)))

	// Fill cache: A, B, C
	c.Add("A", 1)
	c.Add("B", 2)
	c.Add("C", 3)

	t.Logf("done adding ..\n")
	// Access "A" 3 times (saturates at k=3)
	c.Get("A")
	t.Logf("done getting 1..\n")
	c.Get("A")
	t.Logf("done getting 2..\n")
	c.Get("A")
	t.Logf("done getting 3.\n")

	// Access "B" once
	c.Get("B")
	t.Logf("done getting 4.\n")

	// "C" has no accesses beyond initial add

	// Now add "D" — triggers eviction.
	// The hand starts at tail. Insertion order: A(tail)→B→C(head).
	// Wait — insertion is at head, so order is C(head)→B→A(tail).
	// Hand starts at tail (A). A has counter=3, decrement to 2, move to prev (but A is tail, prev=null, wrap to tail=...)
	// Actually let's just verify the outcome.
	c.Add("D", 4)

	// "C" was not accessed (counter=0), so it should be evicted first
	// (hand starts at tail=A which is visited, then B which is visited,
	// then C which is not visited → evict C)
	if _, ok := c.Get("C"); ok {
		t.Fatal("expected C to be evicted")
	}
	if _, ok := c.Get("A"); !ok {
		t.Fatal("expected A to survive (accessed 3 times)")
	}
	if _, ok := c.Get("B"); !ok {
		t.Fatal("expected B to survive (accessed 1 time)")
	}
	if _, ok := c.Get("D"); !ok {
		t.Fatal("expected D to be present")
	}
}

// TestSieveK_CounterSaturation verifies that 100 accesses with k=3
// means 3 eviction passes are needed to evict.
func TestSieveK_CounterSaturation(t *testing.T) {
	c := Must(New[int, int](2, WithVisitClamp(3)))

	c.Add(1, 1)
	c.Add(2, 2)

	// Access key 1 many times — saturates at 3
	for i := 0; i < 100; i++ {
		c.Get(1)
	}

	// Each eviction will try to evict key 1 but its counter decrements 3→2→1→0
	// It should survive 3 eviction passes
	// Add keys 3, 4, 5 — each forces an eviction
	c.Add(3, 3) // evicts key 2 (counter=0)
	if _, ok := c.Get(1); !ok {
		t.Fatal("key 1 should survive first eviction")
	}

	// Now cache has 1 (counter was decremented during scan) and 3
	// Access 1 again to re-increment
	c.Get(1)

	c.Add(4, 4) // evicts key 3 (counter=0)
	if _, ok := c.Get(1); !ok {
		t.Fatal("key 1 should survive second eviction")
	}
}

// TestSieveK_K1_Equivalent verifies that NewWithVisits(cap, 1) behaves
// identically to New(cap).
func TestSieveK_K1_Equivalent(t *testing.T) {
	c1 := Must(New[int, int](100))
	c2 := Must(New[int, int](100, WithVisitClamp(1)))

	// Both should use k=1 (NewWithVisits(_, 1) uses vbits=1)
	// Verify via behavior: same results for same inputs.

	// Fill and verify same behavior
	for i := 0; i < 100; i++ {
		c1.Add(i, i)
		c2.Add(i, i)
	}

	for i := 0; i < 100; i++ {
		v1, ok1 := c1.Get(i)
		v2, ok2 := c2.Get(i)
		if ok1 != ok2 || v1 != v2 {
			t.Fatalf("key %d: c1=(%d,%v) c2=(%d,%v)", i, v1, ok1, v2, ok2)
		}
	}
}