util/ringbuffer: move generic ringbuffer from corp repo

Also add some basic tests for this implementation.

Signed-off-by: Andrew Dunham <andrew@du.nham.ca>
Change-Id: I307ebb6db91d0c172657befb276b38ccb638f828

2 files changed, 127 insertions, 0 deletions

diff --git a/util/ringbuffer/ringbuffer.go b/util/ringbuffer/ringbuffer.go
new file mode 100644
index 000000000..00310baea
--- /dev/null
+++ b/util/ringbuffer/ringbuffer.go
@@ -0,0 +1,72 @@
+// Copyright (c) Tailscale Inc & AUTHORS
+// SPDX-License-Identifier: BSD-3-Clause
+
+// Package ringbuffer contains a fixed-size concurrency-safe generic ring
+// buffer.
+package ringbuffer
+
+import "sync"
+
+// New creates a new RingBuffer containing at most max items.
+func New[T any](max int) *RingBuffer[T] {
+	return &RingBuffer[T]{
+		max: max,
+	}
+}
+
+// RingBuffer is a concurrency-safe ring buffer.
+type RingBuffer[T any] struct {
+	mu  sync.Mutex
+	pos int
+	buf []T
+	max int
+}
+
+// Add appends a new item to the RingBuffer, possibly overwriting the oldest
+// item in the buffer if it is already full.
+func (rb *RingBuffer[T]) Add(t T) {
+	rb.mu.Lock()
+	defer rb.mu.Unlock()
+	if len(rb.buf) < rb.max {
+		rb.buf = append(rb.buf, t)
+	} else {
+		rb.buf[rb.pos] = t
+		rb.pos = (rb.pos + 1) % rb.max
+	}
+}
+
+// GetAll returns a copy of all the entries in the ring buffer in the order they
+// were added.
+func (rb *RingBuffer[T]) GetAll() []T {
+	if rb == nil {
+		return nil
+	}
+	rb.mu.Lock()
+	defer rb.mu.Unlock()
+	out := make([]T, len(rb.buf))
+	for i := 0; i < len(rb.buf); i++ {
+		x := (rb.pos + i) % rb.max
+		out[i] = rb.buf[x]
+	}
+	return out
+}
+
+// Len returns the number of elements in the ring buffer. Note that this value
+// could change immediately after being returned if a concurrent caller
+// modifies the buffer.
+func (rb *RingBuffer[T]) Len() int {
+	if rb == nil {
+		return 0
+	}
+	rb.mu.Lock()
+	defer rb.mu.Unlock()
+	return len(rb.buf)
+}
+
+// Clear will empty the ring buffer.
+func (rb *RingBuffer[T]) Clear() {
+	rb.mu.Lock()
+	defer rb.mu.Unlock()
+	rb.pos = 0
+	rb.buf = nil
+}
diff --git a/util/ringbuffer/ringbuffer_test.go b/util/ringbuffer/ringbuffer_test.go
new file mode 100644
index 000000000..fae3f5328
--- /dev/null
+++ b/util/ringbuffer/ringbuffer_test.go
@@ -0,0 +1,55 @@
+// Copyright (c) Tailscale Inc & AUTHORS
+// SPDX-License-Identifier: BSD-3-Clause
+
+package ringbuffer
+
+import (
+	"reflect"
+	"testing"
+)
+
+func TestRingBuffer(t *testing.T) {
+	const numItems = 10
+	rb := New[int](numItems)
+
+	for i := 0; i < numItems-1; i++ {
+		rb.Add(i)
+	}
+
+	t.Run("NotFull", func(t *testing.T) {
+		if ll := rb.Len(); ll != numItems-1 {
+			t.Fatalf("got len %d; want %d", ll, numItems-1)
+		}
+		all := rb.GetAll()
+		want := []int{0, 1, 2, 3, 4, 5, 6, 7, 8}
+		if !reflect.DeepEqual(all, want) {
+			t.Fatalf("items mismatch\ngot: %v\nwant %v", all, want)
+		}
+	})
+
+	t.Run("Full", func(t *testing.T) {
+		// Append items to evict something
+		rb.Add(98)
+		rb.Add(99)
+
+		if ll := rb.Len(); ll != numItems {
+			t.Fatalf("got len %d; want %d", ll, numItems)
+		}
+		all := rb.GetAll()
+		want := []int{1, 2, 3, 4, 5, 6, 7, 8, 98, 99}
+		if !reflect.DeepEqual(all, want) {
+			t.Fatalf("items mismatch\ngot: %v\nwant %v", all, want)
+		}
+	})
+
+	t.Run("Clear", func(t *testing.T) {
+		rb.Clear()
+		if ll := rb.Len(); ll != 0 {
+			t.Fatalf("got len %d; want 0", ll)
+		}
+		all := rb.GetAll()
+		if len(all) != 0 {
+			t.Fatalf("got non-empty list; want empty")
+		}
+	})
+}