summaryrefslogtreecommitdiff
path: root/pkg/priority_queue
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/priority_queue')
-rw-r--r--pkg/priority_queue/binary_heap.go8
-rw-r--r--pkg/priority_queue/binary_heap_test.go21
-rw-r--r--pkg/priority_queue/interface.go11
-rw-r--r--pkg/priority_queue/pq.go18
-rw-r--r--pkg/priority_queue/pq_test.go2
5 files changed, 35 insertions, 25 deletions
diff --git a/pkg/priority_queue/binary_heap.go b/pkg/priority_queue/binary_heap.go
index 02d413aa..c7c148da 100644
--- a/pkg/priority_queue/binary_heap.go
+++ b/pkg/priority_queue/binary_heap.go
@@ -4,7 +4,9 @@ binary heap (min-heap) algorithm used as a core for the priority queue
package priorityqueue
-type BinHeap []PQItem
+import priorityqueue "github.com/spiral/roadrunner/v2/common/priority_queue"
+
+type BinHeap []priorityqueue.Item
func NewBinHeap() *BinHeap {
return &BinHeap{}
@@ -53,12 +55,12 @@ func (bh *BinHeap) fixDown(curr, end int) {
}
}
-func (bh *BinHeap) Insert(item PQItem) {
+func (bh *BinHeap) Insert(item priorityqueue.Item) {
*bh = append(*bh, item)
bh.fixUp()
}
-func (bh *BinHeap) GetMax() PQItem {
+func (bh *BinHeap) GetMax() priorityqueue.Item {
l := len(*bh)
if l == 0 {
return nil
diff --git a/pkg/priority_queue/binary_heap_test.go b/pkg/priority_queue/binary_heap_test.go
index afeae62c..528e8fd0 100644
--- a/pkg/priority_queue/binary_heap_test.go
+++ b/pkg/priority_queue/binary_heap_test.go
@@ -3,11 +3,26 @@ package priorityqueue
import (
"testing"
+ priorityqueue "github.com/spiral/roadrunner/v2/common/priority_queue"
"github.com/stretchr/testify/require"
)
type Test int
+func (t Test) Ack() {
+}
+
+func (t Test) Nack() {
+}
+
+func (t Test) Body() []byte {
+ return nil
+}
+
+func (t Test) Context() []byte {
+ return nil
+}
+
func (t Test) ID() string {
return ""
}
@@ -17,7 +32,7 @@ func (t Test) Priority() uint64 {
}
func TestBinHeap_Init(t *testing.T) {
- a := []PQItem{Test(2), Test(23), Test(33), Test(44), Test(1), Test(2), Test(2), Test(2), Test(4), Test(6), Test(99)}
+ a := []priorityqueue.Item{Test(2), Test(23), Test(33), Test(44), Test(1), Test(2), Test(2), Test(2), Test(4), Test(6), Test(99)}
bh := NewBinHeap()
@@ -25,9 +40,9 @@ func TestBinHeap_Init(t *testing.T) {
bh.Insert(a[i])
}
- expected := []PQItem{Test(1), Test(2), Test(2), Test(2), Test(2), Test(4), Test(6), Test(23), Test(33), Test(44), Test(99)}
+ expected := []priorityqueue.Item{Test(1), Test(2), Test(2), Test(2), Test(2), Test(4), Test(6), Test(23), Test(33), Test(44), Test(99)}
- res := make([]PQItem, 0, 12)
+ res := make([]priorityqueue.Item, 0, 12)
for i := 0; i < 11; i++ {
item := bh.GetMax()
diff --git a/pkg/priority_queue/interface.go b/pkg/priority_queue/interface.go
deleted file mode 100644
index 3cc1d575..00000000
--- a/pkg/priority_queue/interface.go
+++ /dev/null
@@ -1,11 +0,0 @@
-package priorityqueue
-
-type Queue interface {
- Insert(item PQItem)
- GetMax() PQItem
-}
-
-type PQItem interface {
- ID() string
- Priority() uint64
-}
diff --git a/pkg/priority_queue/pq.go b/pkg/priority_queue/pq.go
index 1b33cb92..2ff52a79 100644
--- a/pkg/priority_queue/pq.go
+++ b/pkg/priority_queue/pq.go
@@ -1,6 +1,10 @@
package priorityqueue
-import "sync"
+import (
+ "sync"
+
+ priorityqueue "github.com/spiral/roadrunner/v2/common/priority_queue"
+)
type PQ struct {
sync.RWMutex
@@ -13,14 +17,14 @@ func NewPriorityQueue() *PQ {
}
}
-func (p *PQ) Insert(item PQItem) {
+func (p *PQ) GetMax() priorityqueue.Item {
p.Lock()
- p.bh.Insert(item)
- p.Unlock()
+ defer p.Unlock()
+ return p.bh.GetMax()
}
-func (p *PQ) Get() PQItem {
+func (p *PQ) Insert(item priorityqueue.Item) {
p.Lock()
- defer p.Unlock()
- return p.bh.GetMax()
+ p.bh.Insert(item)
+ p.Unlock()
}
diff --git a/pkg/priority_queue/pq_test.go b/pkg/priority_queue/pq_test.go
index cdec10f5..49afe5e3 100644
--- a/pkg/priority_queue/pq_test.go
+++ b/pkg/priority_queue/pq_test.go
@@ -37,7 +37,7 @@ func TestNewPriorityQueue(t *testing.T) {
case <-stopCh:
return
default:
- it := pq.Get()
+ it := pq.GetMax()
if it == nil {
continue
}