Repository: etcd-io/etcd
File: cache/ringbuffer.go (Go)

Code before:
// Copyright 2025 The etcd Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package cache

import (
	"fmt"
)

type ringBuffer struct {
	buffer []*batch
	// head is the index immediately after the last non-empty entry in the buffer (i.e., the next write position).
	head, tail, size int
}

// BatchPredicate lets callers decide which batches to keep (e.g. “after revision X”)
type (
	BatchPredicate func(*batch) bool
	KeyPredicate   = func([]byte) bool
)

func newRingBuffer(capacity int) *ringBuffer {
	// assume capacity > 0 – validated by Cache
	return &ringBuffer{
		buffer: make([]*batch, capacity),
	}
}

func (r *ringBuffer) Append(batch *batch) {
	if r.size == len(r.buffer) { // full → overwrite oldest
		r.tail = (r.tail + 1) % len(r.buffer)
	} else {
		r.size++
	}

	r.buffer[r.head] = batch
	r.head = (r.head + 1) % len(r.buffer)
}

// Filter returns the batches that satisfy every predicate
// TODO: use binary search on the ring buffer to locate the first entry >= nextRev instead of a full scan
func (r *ringBuffer) Filter(batchPred BatchPredicate) (batches []*batch) {
	batches = make([]*batch, 0, r.size)

	for n, i := 0, r.tail; n < r.size; n, i = n+1, (i+1)%len(r.buffer) {
		batch := r.buffer[i]
		if batch == nil {
			panic(fmt.Sprintf("ringBuffer.Filter: unexpected nil batch at index %d", i))
		}
		if batchPred == nil || batchPred(batch) {
			batches = append(batches, batch)
		}
	}
	return batches
}

// PeekLatest returns the most recently-appended batch (or nil if empty).
func (r *ringBuffer) PeekLatest() *batch {
	if r.size == 0 {
		return nil
	}
	idx := (r.head - 1 + len(r.buffer)) % len(r.buffer)
	return r.buffer[idx]
}

// PeekOldest returns the oldest batch currently stored (or nil if empty).
func (r *ringBuffer) PeekOldest() *batch {
	if r.size == 0 {
		return nil
	}
	return r.buffer[r.tail]
}

func (r *ringBuffer) RebaseHistory() {
	r.head, r.tail, r.size = 0, 0, 0
	for i := range r.buffer {
		r.buffer[i] = nil
	}
}


Review comment (suggestion):
```suggestion
func (r *ringBuffer) LatestRevision() int64 {
	if r.size == 0 {
		return 0
	}
	idx := (r.head - 1 + len(r.buffer)) % len(r.buffer)
	return r.buffer[idx].rev
}
```

Code after:

// Filter returns all events in the buffer whose ModRevision is >= minRev.
// TODO: use binary search on the ring buffer to locate the first entry >= nextRev instead of a full scan
func (r *ringBuffer) Filter(minRev int64) (eventBatches [][]*clientv3.Event) {
	eventBatches = make([][]*clientv3.Event, 0, r.size)

	for n, i := 0, r.tail; n < r.size; n, i = n+1, (i+1)%len(r.buffer) {
		eventBatch := r.buffer[i]
		if eventBatch.events == nil {
			panic(fmt.Sprintf("ringBuffer.Filter: unexpected nil eventBatch at index %d", i))
		}
		if eventBatch.rev >= minRev {
			eventBatches = append(eventBatches, eventBatch.events)
		}
	}
	return eventBatches
}

// PeekLatest returns the most recently-appended event (or nil if empty).
func (r *ringBuffer) PeekLatest() int64 {
	if r.size == 0 {
		return 0
	}
	idx := (r.head - 1 + len(r.buffer)) % len(r.buffer)
	return r.buffer[idx].rev
}

// PeekOldest returns the oldest event currently stored (or nil if empty).
func (r *ringBuffer) PeekOldest() int64 {
	if r.size == 0 {
		return 0
	}
	return r.buffer[r.tail].rev
}

func (r *ringBuffer) RebaseHistory() {
	r.head, r.tail, r.size = 0, 0, 0
	for i := range r.buffer {
		r.buffer[i] = batch{}
	}
}