pkg/fuzzer/queue: simplify the priority queue

We don't need the full priority queue functionality anymore. For our
purposes it's enough to only enforce the order between the elements of
different sub-queues.

4 files changed, 54 insertions, 100 deletions

diff --git a/pkg/fuzzer/queue/prio_queue.go b/pkg/fuzzer/queue/prio_queue.go
index a71afe61d..5e7c65fba 100644
--- a/pkg/fuzzer/queue/prio_queue.go
+++ b/pkg/fuzzer/queue/prio_queue.go
@@ -7,37 +7,6 @@ import (
 	"container/heap"
 )
 
-type priority []int64
-
-func (p priority) greaterThan(other priority) bool {
-	for i := range p {
-		if i >= len(other) || p[i] > other[i] {
-			return true
-		}
-		if p[i] < other[i] {
-			return false
-		}
-	}
-	for i := len(p); i < len(other); i++ {
-		if other[i] < 0 {
-			return true
-		}
-		if other[i] > 0 {
-			return false
-		}
-	}
-	return false
-}
-
-func (p priority) next() priority {
-	if len(p) == 0 {
-		return p
-	}
-	newPrio := append([]int64{}, p...)
-	newPrio[len(newPrio)-1]--
-	return newPrio
-}
-
 type priorityQueueOps[T any] struct {
 	impl priorityQueueImpl[T]
 }
@@ -46,7 +15,7 @@ func (pq *priorityQueueOps[T]) Len() int {
 	return pq.impl.Len()
 }
 
-func (pq *priorityQueueOps[T]) Push(item T, prio priority) {
+func (pq *priorityQueueOps[T]) Push(item T, prio int) {
 	heap.Push(&pq.impl, &priorityQueueItem[T]{item, prio})
 }
 
@@ -63,7 +32,7 @@ func (pq *priorityQueueOps[T]) Pop() T {
 
 type priorityQueueItem[T any] struct {
 	value T
-	prio  priority
+	prio  int
 }
 
 type priorityQueueImpl[T any] []*priorityQueueItem[T]
@@ -71,9 +40,8 @@ type priorityQueueImpl[T any] []*priorityQueueItem[T]
 func (pq priorityQueueImpl[T]) Len() int { return len(pq) }
 
 func (pq priorityQueueImpl[T]) Less(i, j int) bool {
-	// We want Pop to give us the highest, not lowest,
-	// priority so we use greater than here.
-	return pq[i].prio.greaterThan(pq[j].prio)
+	// We want Pop to give us the lowest priority.
+	return pq[i].prio < pq[j].prio
 }
 
 func (pq priorityQueueImpl[T]) Swap(i, j int) {
diff --git a/pkg/fuzzer/queue/prio_queue_test.go b/pkg/fuzzer/queue/prio_queue_test.go
index a82886bdd..76d4b836b 100644
--- a/pkg/fuzzer/queue/prio_queue_test.go
+++ b/pkg/fuzzer/queue/prio_queue_test.go
@@ -9,32 +9,15 @@ import (
 	"github.com/stretchr/testify/assert"
 )
 
-func TestNextPriority(t *testing.T) {
-	first := priority{0}
-	second := first.next()
-	third := second.next()
-	assert.True(t, first.greaterThan(second))
-	assert.True(t, second.greaterThan(third))
-}
-
-func TestPriority(t *testing.T) {
-	assert.True(t, priority{1, 2}.greaterThan(priority{1, 1}))
-	assert.True(t, priority{3, 2}.greaterThan(priority{2, 3}))
-	assert.True(t, priority{1, -5}.greaterThan(priority{1, -10}))
-	assert.True(t, priority{1}.greaterThan(priority{1, -1}))
-	assert.False(t, priority{1}.greaterThan(priority{1, 1}))
-	assert.True(t, priority{1, 0}.greaterThan(priority{1}))
-}
-
 func TestPrioQueueOrder(t *testing.T) {
 	pq := priorityQueueOps[int]{}
-	pq.Push(1, priority{1})
-	pq.Push(3, priority{3})
-	pq.Push(2, priority{2})
+	pq.Push(1, 1)
+	pq.Push(3, 3)
+	pq.Push(2, 2)
 
-	assert.Equal(t, 3, pq.Pop())
-	assert.Equal(t, 2, pq.Pop())
 	assert.Equal(t, 1, pq.Pop())
+	assert.Equal(t, 2, pq.Pop())
+	assert.Equal(t, 3, pq.Pop())
 	assert.Zero(t, pq.Pop())
 	assert.Zero(t, pq.Len())
 }
diff --git a/pkg/fuzzer/queue/queue.go b/pkg/fuzzer/queue/queue.go
index 0fd87f7c7..6ff94b9be 100644
--- a/pkg/fuzzer/queue/queue.go
+++ b/pkg/fuzzer/queue/queue.go
@@ -296,51 +296,53 @@ func (a *alternate) Next() *Request {
 	return a.base.Next()
 }
 
-type PriorityQueue struct {
-	mu       *sync.Mutex
+type DynamicOrderer struct {
+	mu       sync.Mutex
+	currPrio int
 	ops      *priorityQueueOps[*Request]
-	currPrio priority
 }
 
-func Priority() *PriorityQueue {
-	return &PriorityQueue{
-		mu:       &sync.Mutex{},
-		ops:      &priorityQueueOps[*Request]{},
-		currPrio: priority{0},
-	}
-}
-
-// AppendQueue() can be used to form nested queues.
+// DynamicOrder() can be used to form nested queues dynamically.
 // That is, if
-// q1 := pq.AppendQueue()
-// q2 := pq.AppendQueue()
+// q1 := pq.Append()
+// q2 := pq.Append()
 // All elements added via q2.Submit() will always have a *lower* priority
 // than all elements added via q1.Submit().
-func (pq *PriorityQueue) AppendQueue() *PriorityQueue {
-	pq.mu.Lock()
-	defer pq.mu.Unlock()
-	pq.currPrio = pq.currPrio.next()
-	nextPrio := append(priority{}, pq.currPrio...)
-	return &PriorityQueue{
-		// We use the same queue, therefore the same mutex.
-		mu:       pq.mu,
-		ops:      pq.ops,
-		currPrio: append(nextPrio, 0),
+func DynamicOrder() *DynamicOrderer {
+	return &DynamicOrderer{
+		ops: &priorityQueueOps[*Request]{},
 	}
 }
 
-// Each subsequent element added via Submit() will have a lower priority.
-func (pq *PriorityQueue) Submit(req *Request) {
-	pq.mu.Lock()
-	defer pq.mu.Unlock()
-	pq.currPrio = pq.currPrio.next()
-	pq.ops.Push(req, pq.currPrio)
+func (do *DynamicOrderer) Append() Executor {
+	do.mu.Lock()
+	defer do.mu.Unlock()
+	do.currPrio++
+	return &dynamicOrdererItem{
+		parent: do,
+		prio:   do.currPrio,
+	}
 }
 
-func (pq *PriorityQueue) Next() *Request {
-	pq.mu.Lock()
-	defer pq.mu.Unlock()
-	return pq.ops.Pop()
+func (do *DynamicOrderer) submit(req *Request, prio int) {
+	do.mu.Lock()
+	defer do.mu.Unlock()
+	do.ops.Push(req, prio)
+}
+
+func (do *DynamicOrderer) Next() *Request {
+	do.mu.Lock()
+	defer do.mu.Unlock()
+	return do.ops.Pop()
+}
+
+type dynamicOrdererItem struct {
+	parent *DynamicOrderer
+	prio   int
+}
+
+func (doi *dynamicOrdererItem) Submit(req *Request) {
+	doi.parent.submit(req, doi.prio)
 }
 
 type DynamicSourceCtl struct {
diff --git a/pkg/fuzzer/queue/queue_test.go b/pkg/fuzzer/queue/queue_test.go
index 34a34ccbe..a89ec0d3d 100644
--- a/pkg/fuzzer/queue/queue_test.go
+++ b/pkg/fuzzer/queue/queue_test.go
@@ -36,19 +36,20 @@ func TestPlainQueue(t *testing.T) {
 func TestPrioQueue(t *testing.T) {
 	req1, req2, req3, req4 :=
 		&Request{}, &Request{}, &Request{}, &Request{}
-	pq := Priority()
+	pq := DynamicOrder()
 
-	pq1 := pq.AppendQueue()
-	pq2 := pq.AppendQueue()
-	pq3 := pq.AppendQueue()
+	pq1 := pq.Append()
+	pq2 := pq.Append()
+	pq3 := pq.Append()
 
 	pq2.Submit(req2)
 	pq3.Submit(req3)
-	pq3.Submit(req4)
-	pq1.Submit(req1)
+	assert.Equal(t, req2, pq.Next())
 
+	pq1.Submit(req1)
 	assert.Equal(t, req1, pq.Next())
-	assert.Equal(t, req2, pq.Next())
-	assert.Equal(t, req3, pq.Next())
+
+	pq2.Submit(req4)
 	assert.Equal(t, req4, pq.Next())
+	assert.Equal(t, req3, pq.Next())
 }