fusen-render/priority_queue.go

package fusenrender

import (
	"bytes"
	"container/heap"
	"sync"
)

// An Slice is something we manage in a priority queue.
type Slice[T any] struct {
	Key   []byte // 键
	Value *T     // 值
	// 索引是在容器中的位置
	index int
}

type PriorityQueue[T any] struct {
	Queue HeapSlice[T]
	mu    sync.Mutex
}

func (pq *PriorityQueue[T]) Empty() bool {
	pq.mu.Lock()
	defer pq.mu.Unlock()
	return len(pq.Queue) == 0
}

func (pq *PriorityQueue[T]) Size() int64 {
	pq.mu.Lock()
	defer pq.mu.Unlock()
	return int64(pq.Queue.Len())
}

func (pq *PriorityQueue[T]) Push(x *Slice[T]) {
	pq.mu.Lock()
	defer pq.mu.Unlock()

	heap.Push(&pq.Queue, x)
}

func (pq *PriorityQueue[T]) Pop() *T {
	pq.mu.Lock()
	defer pq.mu.Unlock()

	if pq.Queue.Len() == 0 {
		return nil
	}

	return heap.Pop(&pq.Queue).(*T)
}

func NewPriorityQueue[T any]() *PriorityQueue[T] {
	return &PriorityQueue[T]{
		Queue: make(HeapSlice[T], 0),
	}
}

// A PriorityQueue implements heap.Interface and holds Items.
type HeapSlice[T any] []*Slice[T]

func (pq HeapSlice[T]) Len() int { return len(pq) }

func (pq HeapSlice[T]) Less(i, j int) bool {
	// 使用字节数组键比较
	return bytes.Compare(pq[i].Key, pq[j].Key) < 0
}

func (pq HeapSlice[T]) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *HeapSlice[T]) Push(x any) {
	n := len(*pq)
	item := x.(*Slice[T])
	item.index = n
	*pq = append(*pq, item)
}

func (pq *HeapSlice[T]) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	item.index = -1
	*pq = old[0 : n-1]
	return item.Value
}

// 这样就可以支持基于[]byte键的优先队列操作了