ringbuffer.gno

  1// Package ringbuffer is a fixed-capacity FIFO that overwrites its oldest entry
  2// when full, as a pure, reusable package.
  3//
  4// This is the bounded cousin of an unbounded queue, and the bound is the point:
  5// on chain an unbounded queue is an unbounded storage bill, whereas a ring
  6// buffer's cost is decided once, at construction. It is the right shape for
  7// "last N events", "recent messages", or any rolling window.
  8//
  9// Backed by a flat slice with head/length indices — no per-element allocation,
 10// no shifting on Pop.
 11//
 12// A live demo of this package is at
 13// [r/moul/x/daily/ringbufferdemo](/r/moul/x/daily/ringbufferdemo/v0).
 14package ringbuffer
 15
 16// MaxCap bounds a buffer so allocation stays predictable.
 17const MaxCap = 4096
 18
 19// RingBuffer is a fixed-capacity FIFO of strings.
 20type RingBuffer struct {
 21	buf  []string
 22	head int // index of the oldest element
 23	n    int // number of live elements
 24}
 25
 26// New returns an empty buffer of the given capacity, clamped to [0, MaxCap].
 27func New(capacity int) *RingBuffer {
 28	if capacity < 0 {
 29		capacity = 0
 30	}
 31	if capacity > MaxCap {
 32		capacity = MaxCap
 33	}
 34	return &RingBuffer{buf: make([]string, capacity)}
 35}
 36
 37// Cap returns the capacity.
 38func (r *RingBuffer) Cap() int { return len(r.buf) }
 39
 40// Len returns how many elements are live.
 41func (r *RingBuffer) Len() int { return r.n }
 42
 43// Full reports whether the next Push will overwrite.
 44func (r *RingBuffer) Full() bool { return len(r.buf) > 0 && r.n == len(r.buf) }
 45
 46// Empty reports whether there is nothing to read.
 47func (r *RingBuffer) Empty() bool { return r.n == 0 }
 48
 49// Push appends v. When the buffer is full the OLDEST element is dropped to make
 50// room, and that element is returned with dropped=true — losing data silently
 51// is the one thing a rolling window must not do.
 52//
 53// A zero-capacity buffer accepts nothing and reports the value straight back.
 54func (r *RingBuffer) Push(v string) (evicted string, dropped bool) {
 55	if len(r.buf) == 0 {
 56		return v, true
 57	}
 58	if r.n == len(r.buf) {
 59		evicted = r.buf[r.head]
 60		r.buf[r.head] = v
 61		r.head = (r.head + 1) % len(r.buf)
 62		return evicted, true
 63	}
 64	r.buf[(r.head+r.n)%len(r.buf)] = v
 65	r.n++
 66	return "", false
 67}
 68
 69// Pop removes and returns the oldest element; ok is false when empty.
 70func (r *RingBuffer) Pop() (v string, ok bool) {
 71	if r.n == 0 {
 72		return "", false
 73	}
 74	v = r.buf[r.head]
 75	r.buf[r.head] = "" // release the reference; don't pin a string we no longer own
 76	r.head = (r.head + 1) % len(r.buf)
 77	r.n--
 78	return v, true
 79}
 80
 81// Peek returns the oldest element without removing it.
 82func (r *RingBuffer) Peek() (v string, ok bool) {
 83	if r.n == 0 {
 84		return "", false
 85	}
 86	return r.buf[r.head], true
 87}
 88
 89// At returns the i-th element counting from the oldest (0 = oldest).
 90func (r *RingBuffer) At(i int) (v string, ok bool) {
 91	if i < 0 || i >= r.n {
 92		return "", false
 93	}
 94	return r.buf[(r.head+i)%len(r.buf)], true
 95}
 96
 97// Slice returns the live elements oldest-first, as an independent copy.
 98func (r *RingBuffer) Slice() []string {
 99	out := make([]string, 0, r.n)
100	for i := 0; i < r.n; i++ {
101		out = append(out, r.buf[(r.head+i)%len(r.buf)])
102	}
103	return out
104}
105
106// Reset empties the buffer, releasing every stored reference.
107func (r *RingBuffer) Reset() {
108	for i := range r.buf {
109		r.buf[i] = ""
110	}
111	r.head, r.n = 0, 0
112}