shithub: furgit

Download patch

ref: e0e493fbf197aabf9272e52ab0e7282e308bcdeb
parent: 69452f58fb0d6c1ed561df1e25efe51e5b3089fd
author: Runxi Yu <runxiyu@umich.edu>
date: Sun Mar 29 10:15:30 EDT 2026 

commitquery: Use our proper priority queue thingy


--- a/commitquery/node_paint_down_to_common.go
+++ b/commitquery/node_paint_down_to_common.go
@@ -1,5 +1,7 @@
 package commitquery
 
+import "codeberg.org/lindenii/furgit/internal/priorityqueue"
+
 func (query *query) paintDownToCommon(left nodeIndex, rights []nodeIndex, minGeneration uint64) error {
 	query.beginMarkPhase()
 
@@ -11,18 +13,20 @@
 		return nil
 	}
 
-	queue := newPriorityQueue(query)
-	queue.PushNode(left)
+	queue := priorityqueue.New(func(left, right nodeIndex) bool {
+		return query.compare(left, right) > 0
+	})
+	queue.Push(left)
 
 	for _, right := range rights {
 		query.setMarks(right, markRight)
-		queue.PushNode(right)
+		queue.Push(right)
 	}
 
 	lastGeneration := generationInfinity
 
 	for queue.Len() > 0 {
-		idx, ok := queue.PopNode()
+		idx, ok := queue.Pop()
 		if !ok {
 			break
 		}
@@ -54,7 +58,7 @@
 			}
 
 			query.setMarks(parent, flags)
-			queue.PushNode(parent)
+			queue.Push(parent)
 		}
 	}
 
--- a/commitquery/priority_queue.go
+++ /dev/null
@@ -1,32 +1,0 @@
-package commitquery
-
-import internalheap "codeberg.org/lindenii/furgit/internal/heap"
-
-// priorityQueue orders internal nodes using one query context's comparator.
-type priorityQueue struct {
-	items *internalheap.Heap[nodeIndex]
-}
-
-// newPriorityQueue builds one empty priority queue over one query context.
-func newPriorityQueue(query *query) *priorityQueue {
-	return &priorityQueue{
-		items: internalheap.New(func(left, right nodeIndex) bool {
-			return query.compare(left, right) > 0
-		}),
-	}
-}
-
-// Len reports the number of queued items.
-func (queue *priorityQueue) Len() int {
-	return queue.items.Len()
-}
-
-// PushNode inserts one internal node.
-func (queue *priorityQueue) PushNode(idx nodeIndex) {
-	queue.items.Push(idx)
-}
-
-// PopNode removes the highest-priority internal node.
-func (queue *priorityQueue) PopNode() (nodeIndex, bool) {
-	return queue.items.Pop()
-}
-- 
⑨