Add drafty prototype

1 files changed, 89 insertions, 0 deletions

diff --git a/internal/monitor/chunks.go b/internal/monitor/chunks.go
new file mode 100644
index 0000000..02b3802
--- /dev/null
+++ b/internal/monitor/chunks.go
@@ -0,0 +1,89 @@
+package monitor
+
+//
+// A min heap of chunks, ordered on each chunk's start index.  This makes it
+// easy to order the downloaded leaves when using multiple parallell fetchers.
+//
+// Credit: inspiration to use a heap from Aaron Gable, see
+// https://github.com/aarongable/ctaudit
+//
+
+import (
+	"container/heap"
+	"crypto/sha256"
+)
+
+type chunk struct {
+	startIndex uint64              // Index of the first leaf
+	leafHashes [][sha256.Size]byte // List of consecutive leaf hashes
+	matches    []LogEntry          // Leaves that match some criteria
+	errors     []error             // Errors that ocurred while matching on the leaves
+}
+
+type chunks []*chunk
+
+func newChunks() *chunks {
+	var h chunks
+	heap.Init((*internal)(&h))
+	return &h
+}
+
+func (h *chunks) push(c *chunk) {
+	heap.Push((*internal)(h), c)
+}
+
+func (h *chunks) pop() *chunk {
+	x := heap.Pop((*internal)(h))
+	return x.(*chunk)
+}
+
+// gap returns true if there's a gap between the provided start index and the
+// top most chunk.  If the top most chunk is in sequence, it is merged with
+// any following chunks that are also in sequence to form one larger chunk.
+func (h *chunks) gap(start uint64) bool {
+	if len(*h) == 0 {
+		return true
+	}
+
+	top := h.pop()
+	if start != top.startIndex {
+		h.push(top)
+		return true
+	}
+
+	for len(*h) > 0 {
+		c := h.pop()
+		if c.startIndex != top.startIndex+uint64(len(top.leafHashes)) {
+			h.push(c)
+			break
+		}
+
+		top.leafHashes = append(top.leafHashes, c.leafHashes...)
+		top.matches = append(top.matches, c.matches...)
+		top.errors = append(top.errors, c.errors...)
+	}
+
+	h.push(top)
+	return false
+}
+
+// internal implements the heap interface, see example:
+// https://cs.opensource.google/go/go/+/refs/tags/go1.21.5:src/container/heap/example_intheap_test.go
+type internal chunks
+
+func (h internal) Len() int           { return len(h) }
+func (h internal) Less(i, j int) bool { return h[i].startIndex < h[j].startIndex }
+func (h internal) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
+
+func (h *internal) Push(x any) {
+	*h = append(*h, x.(*chunk))
+}
+
+func (h *internal) Pop() any {
+	old := *h
+	n := len(old)
+	x := old[n-1]
+	old[n-1] = nil // avoid memory leak
+	*h = old[:n-1]
+	return x
+}