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

Code before:
	for i, ev := range eventBatch[1:] {
		if ev.Kv.ModRevision != rev {
			panic(fmt.Sprintf("ringBuffer.Append: mixed revisions at idx %d (%d vs %d)", i+1, ev.Kv.ModRevision, rev))
		}
	}
	b := &batch{rev: rev, events: eventBatch}

	if r.size == len(r.buffer) {
		r.tail = (r.tail + 1) % len(r.buffer)
	} else {
		r.size++
	}
	r.buffer[r.head] = b
	r.head = (r.head + 1) % len(r.buffer)
}

func (r *ringBuffer) AppendMixed(events []*clientv3.Event) {
	for i := 0; i < len(events); {
		rev := events[i].Kv.ModRevision
		j := i + 1
		for j < len(events) && events[j].Kv.ModRevision == rev {
			j++
		}
		r.Append(events[i:j])
		i = j
	}
}

// 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) {
		batch := r.buffer[i]
		if batch == nil {
			panic(fmt.Sprintf("ringBuffer.Filter: unexpected nil eventBatch at index %d", i))
		}
		if batch.rev >= minRev {
			eventBatches = append(eventBatches, batch.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)

Review comment (performance):
Previous implementation was clearer. Don't use nested loops if not needed. They make code harder to follow and imply O(n^2) complexity.

If you want to avoid allocations just use the following code:
```
	start := 0
	for end := 1; end < len(events); end++ {
		if events[end].Kv.ModRevision != events[start].Kv.ModRevision {
			r.Append(events[start:end])
			start = end
		}
	}
	if start < len(events) {
		r.Append(events[start:])
	}
```

Code after:
				rev:    events[start].Kv.ModRevision,
				events: events[start:end],
			})
			start = end
		}
	}
	if start < len(events) {
		r.append(batch{
			rev:    events[start].Kv.ModRevision,
			events: events[start:],
		})
	}
}

func (r *ringBuffer) append(b batch) {
	if len(b.events) == 0 {
		return
	}
	if r.size == len(r.buffer) {
		r.tail = (r.tail + 1) % len(r.buffer)
	} else {
		r.size++
	}
	r.buffer[r.head] = b
	r.head = (r.head + 1) % len(r.buffer)
}

// 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