internal/mru: Add

8 files changed, 261 insertions, 0 deletions

diff --git a/internal/mru/doc.go b/internal/mru/doc.go
new file mode 100644
index 00000000..eef0b295
--- /dev/null
+++ b/internal/mru/doc.go
@@ -0,0 +1,8 @@
+// Package mru provides a concurrent most-recently-used ordering over keys.
+//
+// It expresses recency only,
+// never priority,
+// and it never evicts.
+// Reads are lock-free over an immutable snapshot,
+// so a concurrent reorder never perturbs an in-progress walk.
+package mru
diff --git a/internal/mru/keys.go b/internal/mru/keys.go
new file mode 100644
index 00000000..0cd9a319
--- /dev/null
+++ b/internal/mru/keys.go
@@ -0,0 +1,17 @@
+package mru
+
+// Keys returns the keys in most-recently-used order,
+// front first.
+//
+// The result is the immutable snapshot current at the call:
+// a concurrent Touch or Sync does not affect it.
+//
+// Labels: Mut-No.
+func (order *Order[K]) Keys() []K {
+	keys := order.snapshot.Load()
+	if keys == nil {
+		return nil
+	}
+
+	return *keys
+}
diff --git a/internal/mru/len.go b/internal/mru/len.go
new file mode 100644
index 00000000..38863c66
--- /dev/null
+++ b/internal/mru/len.go
@@ -0,0 +1,6 @@
+package mru
+
+// Len returns the number of keys in the order.
+func (order *Order[K]) Len() int {
+	return len(order.Keys())
+}
diff --git a/internal/mru/new.go b/internal/mru/new.go
new file mode 100644
index 00000000..221b650b
--- /dev/null
+++ b/internal/mru/new.go
@@ -0,0 +1,6 @@
+package mru
+
+// New returns a new, empty order.
+func New[K comparable]() *Order[K] {
+	return &Order[K]{} //nolint:exhaustruct
+}
diff --git a/internal/mru/order.go b/internal/mru/order.go
new file mode 100644
index 00000000..9721d852
--- /dev/null
+++ b/internal/mru/order.go
@@ -0,0 +1,25 @@
+package mru
+
+import (
+	"sync"
+	"sync/atomic"
+)
+
+// Order is a concurrent most-recently-used ordering over keys.
+//
+// The front is the most-recently-used key.
+// Order expresses recency only,
+// never priority;
+// a caller that needs a fixed priority order
+// must arrange its keys in that order itself.
+// Order never evicts.
+//
+// Reads are lock-free over an immutable snapshot,
+// so a concurrent Touch or Sync
+// never perturbs an in-progress walk.
+//
+// Labels: MT-Safe.
+type Order[K comparable] struct {
+	snapshot atomic.Pointer[[]K]
+	mu       sync.Mutex
+}
diff --git a/internal/mru/order_test.go b/internal/mru/order_test.go
new file mode 100644
index 00000000..8b667e77
--- /dev/null
+++ b/internal/mru/order_test.go
@@ -0,0 +1,121 @@
+package mru_test
+
+import (
+	"slices"
+	"sync"
+	"testing"
+
+	"lindenii.org/go/furgit/internal/mru"
+)
+
+func set(keys ...string) map[string]struct{} {
+	present := make(map[string]struct{}, len(keys))
+	for _, key := range keys {
+		present[key] = struct{}{}
+	}
+
+	return present
+}
+
+func TestTouchMovesToFront(t *testing.T) {
+	t.Parallel()
+
+	order := mru.New[string]()
+	order.Sync(set("a", "b", "c"))
+
+	order.Touch("a")
+
+	if got := order.Keys(); len(got) == 0 || got[0] != "a" {
+		t.Fatalf("after Touch(a), order = %v, want a first", got)
+	}
+
+	order.Touch("b")
+
+	if got := order.Keys(); len(got) < 2 || got[0] != "b" || got[1] != "a" {
+		t.Fatalf("after Touch(b), order = %v, want [b a ...]", got)
+	}
+}
+
+func TestSyncDropsAbsentAndKeepsSurvivorOrder(t *testing.T) {
+	t.Parallel()
+
+	order := mru.New[string]()
+	order.Sync(set("a", "b", "c"))
+
+	// Establish a deterministic recency order: c, b, a.
+	order.Touch("a")
+	order.Touch("b")
+	order.Touch("c")
+
+	if got, want := order.Keys(), []string{"c", "b", "a"}; !slices.Equal(got, want) {
+		t.Fatalf("order = %v, want %v", got, want)
+	}
+
+	order.Sync(set("a", "c"))
+
+	if got, want := order.Keys(), []string{"c", "a"}; !slices.Equal(got, want) {
+		t.Fatalf("after Sync, order = %v, want %v", got, want)
+	}
+}
+
+func TestTouchAbsentIsNoOp(t *testing.T) {
+	t.Parallel()
+
+	order := mru.New[string]()
+	order.Sync(set("a", "b"))
+	order.Touch("a")
+	order.Touch("z")
+
+	if got := order.Keys(); order.Len() != 2 || got[0] != "a" {
+		t.Fatalf("after Touch(z), order = %v, want front a and len 2", got)
+	}
+}
+
+func TestKeysIsConsistentSnapshot(t *testing.T) {
+	t.Parallel()
+
+	order := mru.New[string]()
+	order.Sync(set("a", "b"))
+
+	snapshot := order.Keys()
+	order.Sync(set("c"))
+
+	got := slices.Clone(snapshot)
+	slices.Sort(got)
+
+	if want := []string{"a", "b"}; !slices.Equal(got, want) {
+		t.Fatalf("captured snapshot = %v, want %v despite later Sync", got, want)
+	}
+
+	if cur, want := order.Keys(), []string{"c"}; !slices.Equal(cur, want) {
+		t.Fatalf("current order = %v, want %v", cur, want)
+	}
+}
+
+func TestConcurrentTouchAndKeys(t *testing.T) {
+	t.Parallel()
+
+	order := mru.New[string]()
+	order.Sync(set("a", "b", "c", "d"))
+
+	var wg sync.WaitGroup
+
+	for range 8 {
+		wg.Go(func() {
+			for range 1000 {
+				for _, key := range order.Keys() {
+					order.Touch(key)
+				}
+			}
+		})
+	}
+
+	wg.Wait()
+
+	got := slices.Clone(order.Keys())
+	slices.Sort(got)
+
+	if want := []string{"a", "b", "c", "d"}; !slices.Equal(got, want) {
+		t.Fatalf("membership corrupted: %v", got)
+	}
+}
diff --git a/internal/mru/sync.go b/internal/mru/sync.go
new file mode 100644
index 00000000..69fc3446
--- /dev/null
+++ b/internal/mru/sync.go
@@ -0,0 +1,31 @@
+package mru
+
+// Sync reconciles the order's membership to present.
+//
+// Surviving keys keep their relative recency order,
+// absent keys are dropped,
+// and newly present keys are appended after the survivors.
+func (order *Order[K]) Sync(present map[K]struct{}) {
+	order.mu.Lock()
+	defer order.mu.Unlock()
+
+	keys := order.Keys()
+
+	next := make([]K, 0, len(present))
+	seen := make(map[K]struct{}, len(present))
+
+	for _, key := range keys {
+		if _, ok := present[key]; ok {
+			next = append(next, key)
+			seen[key] = struct{}{}
+		}
+	}
+
+	for key := range present {
+		if _, ok := seen[key]; !ok {
+			next = append(next, key)
+		}
+	}
+
+	order.snapshot.Store(&next)
+}
diff --git a/internal/mru/touch.go b/internal/mru/touch.go
new file mode 100644
index 00000000..67ac6706
--- /dev/null
+++ b/internal/mru/touch.go
@@ -0,0 +1,47 @@
+package mru
+
+// Touch moves key to the front, best-effort.
+//
+// When key is already the most-recently-used,
+// Touch is lock-free and allocation-free;
+// this is the common case.
+// Otherwise Touch reorders under a non-blocking lock attempt,
+// so a read never blocks merely to reorder.
+// A contended attempt,
+// or a key that is not a member,
+// leaves the order unchanged.
+func (order *Order[K]) Touch(key K) {
+	keys := order.Keys()
+	if len(keys) == 0 || keys[0] == key {
+		return
+	}
+
+	if !order.mu.TryLock() {
+		return
+	}
+	defer order.mu.Unlock()
+
+	// The snapshot may have changed before we took the lock.
+	keys = order.Keys()
+
+	index := -1
+
+	for i, candidate := range keys {
+		if candidate == key {
+			index = i
+
+			break
+		}
+	}
+
+	if index <= 0 {
+		return
+	}
+
+	next := make([]K, 0, len(keys))
+	next = append(next, key)
+	next = append(next, keys[:index]...)
+	next = append(next, keys[index+1:]...)
+
+	order.snapshot.Store(&next)
+}