ref: 3fdec79ddcafde9848b60fc420bb9222a4786e1f
parent: 0105d8a22962badd6b2a7adafde89ba94978dde1
author: Runxi Yu <runxiyu@umich.edu>
date: Sun Mar 29 10:07:17 EDT 2026
commitquery: Use internal/heap for the priority queue
--- a/commitquery/node_paint_down_to_common.go
+++ b/commitquery/node_paint_down_to_common.go
@@ -21,8 +21,15 @@
lastGeneration := generationInfinity
- for query.queueHasNonStale(queue) {- idx := queue.PopNode()
+ for queue.Len() > 0 {+ idx, ok := queue.PopNode()
+ if !ok {+ break
+ }
+
+ if query.hasAnyMarks(idx, markStale) {+ continue
+ }
generation := query.effectiveGeneration(idx)
if generation > lastGeneration {--- a/commitquery/priority_queue.go
+++ b/commitquery/priority_queue.go
@@ -1,79 +1,32 @@
package commitquery
-import "container/heap"
+import internalheap "codeberg.org/lindenii/furgit/internal/heap"
// priorityQueue orders internal nodes using one query context's comparator.
type priorityQueue struct {- query *query
- items []nodeIndex
+ items *internalheap.Heap[nodeIndex]
}
// newPriorityQueue builds one empty priority queue over one query context.
func newPriorityQueue(query *query) *priorityQueue {- queue := &priorityQueue{query: query}- heap.Init(queue)
-
- return queue
+ 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 len(queue.items)
+ return queue.items.Len()
}
-// Less reports whether one heap slot sorts ahead of another.
-func (queue *priorityQueue) Less(left, right int) bool {- return queue.query.compare(queue.items[left], queue.items[right]) > 0
-}
-
-// Swap exchanges two heap slots.
-func (queue *priorityQueue) Swap(left, right int) {- queue.items[left], queue.items[right] = queue.items[right], queue.items[left]
-}
-
-// Push appends one heap element.
-func (queue *priorityQueue) Push(item any) {- idx, ok := item.(nodeIndex)
- if !ok {- panic("commitquery: heap push item is not a nodeIndex")- }
-
- queue.items = append(queue.items, idx)
-}
-
-// Pop removes one heap element.
-func (queue *priorityQueue) Pop() any {- last := len(queue.items) - 1
- item := queue.items[last]
- queue.items = queue.items[:last]
-
- return item
-}
-
// PushNode inserts one internal node.
func (queue *priorityQueue) PushNode(idx nodeIndex) {- heap.Push(queue, idx)
+ queue.items.Push(idx)
}
// PopNode removes the highest-priority internal node.
-func (queue *priorityQueue) PopNode() nodeIndex {- item := heap.Pop(queue)
-
- idx, ok := item.(nodeIndex)
- if !ok {- panic("commitquery: heap pop item is not a nodeIndex")- }
-
- return idx
-}
-
-func (query *query) queueHasNonStale(queue *priorityQueue) bool {- // TODO
- for _, idx := range queue.items {- if !query.hasAnyMarks(idx, markStale) {- return true
- }
- }
-
- return false
+func (queue *priorityQueue) PopNode() (nodeIndex, bool) {+ return queue.items.Pop()
}
--
⑨