wip: Rethink cache libraries

1 files changed, 178 insertions, 0 deletions

diff --git a/lib/caching/lrucache.go b/lib/caching/lrucache.go
new file mode 100644
index 0000000..c41da09
--- /dev/null
+++ b/lib/caching/lrucache.go
@@ -0,0 +1,178 @@
+// Copyright (C) 2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package caching
+
+import (
+	"context"
+	"fmt"
+	"sync"
+)
+
+type lruEntry[K comparable, V any] struct {
+	key  K
+	val  V
+	refs int
+	del  chan struct{}
+}
+
+type lruCache[K comparable, V any] struct {
+	cap int
+	src Source[K, V]
+
+	mu sync.Mutex
+
+	len int
+
+	unused    LinkedList[lruEntry[K, V]]
+	evictable LinkedList[lruEntry[K, V]] // only entries with .refs==0
+	byName    map[K]*LinkedListEntry[lruEntry[K, V]]
+
+	waiters LinkedList[chan *LinkedListEntry[lruEntry[K, V]]]
+}
+
+// NewLRUCache returns a new Cache with a simple Least-Recently-Used eviction
+// policy.
+//
+// It is invalid (runtime-panic) to call NewLRUCache with a non-positive
+// capacity or a nil source.
+func NewLRUCache[K comparable, V any](cap int, src Source[K, V]) Cache[K, V] {
+	if cap <= 0 {
+		panic(fmt.Errorf("caching.NewLRUCache: invalid capacity: %v", cap))
+	}
+	if src == nil {
+		panic(fmt.Errorf("caching.NewLRUCache: nil source"))
+	}
+	return &lruCache[K, V]{
+		cap: cap,
+		src: src,
+	}
+}
+
+// Acquire implements Cache.
+func (c *lruCache[K, V]) Acquire(ctx context.Context, k K) *V {
+	c.mu.Lock()
+	defer c.mu.Unlock()
+	if c.byName == nil {
+		c.byName = make(map[K]*LinkedListEntry[lruEntry[K, V]], c.cap)
+	}
+
+	entry, ok := c.byName[k]
+	if ok {
+		if entry.Value.refs == 0 {
+			c.evictable.Delete(entry)
+		}
+		entry.Value.refs++
+	} else {
+		switch {
+		case !c.unused.IsEmpty():
+			entry = c.unused.Oldest()
+			c.unused.Delete(entry)
+		case c.len < c.cap:
+			entry = new(LinkedListEntry[lruEntry[K, V]])
+			c.len++
+		case !c.evictable.IsEmpty():
+			entry = c.evictable.Oldest()
+			c.evictable.Delete(entry)
+			delete(c.byName, entry.Value.key)
+		default:
+			ch := make(chan *LinkedListEntry[lruEntry[K, V]])
+			c.waiters.Store(&LinkedListEntry[chan *LinkedListEntry[lruEntry[K, V]]]{Value: ch})
+			c.mu.Unlock()
+			entry = <-ch
+			c.mu.Lock()
+		}
+
+		entry.Value.key = k
+		c.src.Load(ctx, k, &entry.Value.val)
+		entry.Value.refs = 1
+
+		c.byName[k] = entry
+	}
+
+	return &entry.Value.val
+}
+
+// Release implements Cache.
+func (c *lruCache[K, V]) Release(k K) {
+	c.mu.Lock()
+	defer c.mu.Unlock()
+
+	entry, ok := c.byName[k]
+	if !ok || entry.Value.refs <= 0 {
+		panic(fmt.Errorf("caching.lruCache.Release called on key that is not held: %v", k))
+	}
+	entry.Value.refs--
+	if entry.Value.refs == 0 {
+		del := entry.Value.del != nil
+		if del {
+			close(entry.Value.del)
+			entry.Value.del = nil
+		}
+		if c.waiters.IsEmpty() {
+			// Add it to the free-list.
+			if del {
+				delete(c.byName, k)
+				c.unused.Store(entry)
+			} else {
+				c.evictable.Store(entry)
+			}
+		} else {
+			// Someone's waiting to pop something off of the
+			// free-list; bypass the free-list and hand it directly
+			// to them.
+
+			// Make sure that no one aquires this entry between us
+			// writing it to the channel and the waiter calling
+			// c.mu.Lock().
+			delete(c.byName, k)
+
+			// Pass it to the waiter.
+			waiter := c.waiters.Oldest()
+			c.waiters.Delete(waiter)
+			waiter.Value <- entry
+		}
+	}
+}
+
+// Delete implements Cache.
+func (c *lruCache[K, V]) Delete(k K) {
+	c.mu.Lock()
+
+	entry, ok := c.byName[k]
+	if !ok {
+		return
+	}
+	if entry.Value.refs == 0 {
+		delete(c.byName, k)
+		if c.waiters.IsEmpty() {
+			c.unused.Store(entry)
+		} else {
+			waiter := c.waiters.Oldest()
+			c.waiters.Delete(waiter)
+			waiter.Value <- entry
+		}
+		c.mu.Unlock()
+	} else {
+		if entry.Value.del == nil {
+			entry.Value.del = make(chan struct{})
+		}
+		ch := entry.Value.del
+		c.mu.Unlock()
+		<-ch
+	}
+}
+
+// Flush implements Cache.
+func (c *lruCache[K, V]) Flush(ctx context.Context) {
+	c.mu.Lock()
+	defer c.mu.Unlock()
+
+	for _, entry := range c.byName {
+		c.src.Flush(ctx, &entry.Value.val)
+	}
+	for entry := c.unused.Oldest(); entry != nil; entry = entry.Newer() {
+		c.src.Flush(ctx, &entry.Value.val)
+	}
+}