Repository: dragonflyoss/Dragonfly2
Pull request #1496 (2022-07-28 03:30:04)

fix: random vertices
Signed-off-by: Gaius <gaius.qi@gmail.com>

<!--- Provide a general summary of your changes in the Title above -->

## Description
- Fix random vertices.
<!--- Describe your changes in detail -->

## Related Issue

<!--- This project only accepts pull requests related to open issues -->
<!--- If suggesting a new feature or change, please discuss it in an issue first -->
<!--- If fixing a bug, there should be an issue describing it with steps to reproduce -->
<!--- Please link to the issue here: -->

## Motivation and Context

<!--- Why is this change required? What problem does it solve? -->

## Screenshots (if appropriate)

## Types of changes

<!--- What types of changes does your code introduce? Put an `x` in all the boxes that apply: -->

- [ ] Bug fix (non-breaking change which fixes an issue)
- [x] New feature (non-breaking change which adds functionality)
- [ ] Breaking change (fix or feature that would cause existing functionality to change)
- [ ] Documentation Update (if none of the other choices apply)

## Checklist

<!--- Go over all the following points, and put an `x` in all the boxes that apply. -->
<!--- If you're unsure about any of these, don't hesitate to ask. We're here to help! -->

- [ ] My change requires a change to the documentation.
- [ ] I have updated the documentation accordingly.
- [x] I have read the **CONTRIBUTING** document.
- [ ] I have added tests to cover my changes.


codecov-commenter: # [Codecov](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1496?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) Report
> Merging [#1496](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1496?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) (980ab93) into [main](https://codecov.io/gh/dragonflyoss/Dragonfly2/commit/6f0b90c1449945023cdfe5fd35b7a1dcc980ed1c?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) (6f0b90c) will **decrease** coverage by `0.22%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1496/graphs/tree.svg?width=650&height=150&src=pr&token=PUICJYSAT7&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss)](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1496?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss)

```diff
@@            Coverage Diff             @@
##             main    #1496      +/-   ##
==========================================
- Coverage   43.50%   43.27%   -0.23%     
==========================================
  Files         116      116              
  Lines       10675    10675              
==========================================
- Hits         4644     4620      -24     
- Misses       5550     5577      +27     
+ Partials      481      478       -3     
```

| Flag | Coverage Δ | |
|---|---|---|
| Object-compatibility-e2etests | `?` | |
| e2etests | `?` | |
| unittests | `43.27% <100.00%> (-0.23%)` | :arrow_down: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Impacted Files](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1496?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) | Coverage Δ | |
|---|---|---|
| [pkg/dag/dag.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1496/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-cGtnL2RhZy9kYWcuZ28=) | `81.37% <100.00%> (ø)` | |
| [client/daemon/peer/peertask\_piecetask\_poller.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1496/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-Y2xpZW50L2RhZW1vbi9wZWVyL3BlZXJ0YXNrX3BpZWNldGFza19wb2xsZXIuZ28=) | `30.43% <0.00%> (-16.67%)` | :arrow_down: |
| [client/daemon/peer/piece\_broker.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1496/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-Y2xpZW50L2RhZW1vbi9wZWVyL3BpZWNlX2Jyb2tlci5nbw==) | `89.74% <0.00%> (-2.57%)` | :arrow_down: |
| [client/daemon/peer/peertask\_conductor.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1496/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-Y2xpZW50L2RhZW1vbi9wZWVyL3BlZXJ0YXNrX2NvbmR1Y3Rvci5nbw==) | `57.11% <0.00%> (ø)` | |


Patch:
diff --git a/pkg/dag/dag.go b/pkg/dag/dag.go
index 08b47c33..835b5269 100644
--- a/pkg/dag/dag.go
+++ b/pkg/dag/dag.go
@@ -59,16 +59,16 @@ type DAG[T comparable] interface {
 	GetVertices() map[string]*Vertex[T]
 
 	// GetRandomVertices returns random map of vertices.
-	GetRandomVertices(n uint) map[string]*Vertex[T]
+	GetRandomVertices(n uint) []*Vertex[T]
 
 	// GetVertexKeys returns keys of vertices.
 	GetVertexKeys() []string
 
 	// GetSourceVertices returns source vertices.
-	GetSourceVertices() map[string]*Vertex[T]
+	GetSourceVertices() []*Vertex[T]
 
 	// GetSinkVertices returns sink vertices.
-	GetSinkVertices() map[string]*Vertex[T]
+	GetSinkVertices() []*Vertex[T]
 
 	// VertexCount returns count of vertices.
 	VertexCount() int
@@ -147,22 +147,23 @@ func (d *dag[T]) GetVertices() map[string]*Vertex[T] {
 }
 
 // GetRandomVertices returns random map of vertices.
-func (d *dag[T]) GetRandomVertices(n uint) map[string]*Vertex[T] {
+func (d *dag[T]) GetRandomVertices(n uint) []*Vertex[T] {
 	d.mu.RLock()
 	defer d.mu.RUnlock()
 
 	keys := d.GetVertexKeys()
-	vertices := d.GetVertices()
 	if int(n) >= len(keys) {
-		return vertices
+		n = uint(len(keys))
 	}
 
 	rand.Seed(time.Now().Unix())
 	permutation := rand.Perm(len(keys))[:n]
-	randomVertices := make(map[string]*Vertex[T])
+	randomVertices := make([]*Vertex[T], 0, n)
 	for _, v := range permutation {
 		key := keys[v]
-		randomVertices[key] = vertices[key]
+		if vertex, err := d.GetVertex(key); err == nil {
+			randomVertices = append(randomVertices, vertex)
+		}
 	}
 
 	return randomVertices
@@ -270,14 +271,14 @@ func (d *dag[T]) DeleteEdge(fromVertexID, toVertexID string) error {
 }
 
 // GetSourceVertices returns source vertices.
-func (d *dag[T]) GetSourceVertices() map[string]*Vertex[T] {
+func (d *dag[T]) GetSourceVertices() []*Vertex[T] {
 	d.mu.RLock()
 	defer d.mu.RUnlock()
 
-	sourceVertices := make(map[string]*Vertex[T])
-	for k, v := range d.vertices.Items() {
-		if v.InDegree() == 0 {
-			sourceVertices[k] = v
+	var sourceVertices []*Vertex[T]
+	for _, vertex := range d.vertices.Items() {
+		if vertex.InDegree() == 0 {
+			sourceVertices = append(sourceVertices, vertex)
 		}
 	}
 
@@ -285,14 +286,14 @@ func (d *dag[T]) GetSourceVertices() map[string]*Vertex[T] {
 }
 
 // GetSinkVertices returns sink vertices.
-func (d *dag[T]) GetSinkVertices() map[string]*Vertex[T] {
+func (d *dag[T]) GetSinkVertices() []*Vertex[T] {
 	d.mu.RLock()
 	defer d.mu.RUnlock()
 
-	sinkVertices := make(map[string]*Vertex[T])
-	for k, v := range d.vertices.Items() {
-		if v.OutDegree() == 0 {
-			sinkVertices[k] = v
+	var sinkVertices []*Vertex[T]
+	for _, vertex := range d.vertices.Items() {
+		if vertex.OutDegree() == 0 {
+			sinkVertices = append(sinkVertices, vertex)
 		}
 	}
 
diff --git a/pkg/dag/mocks/dag_mock.go b/pkg/dag/mocks/dag_mock.go
index d272f267..2465794d 100644
--- a/pkg/dag/mocks/dag_mock.go
+++ b/pkg/dag/mocks/dag_mock.go
@@ -103,10 +103,10 @@ func (mr *MockDAGMockRecorder[T]) DeleteVertex(id interface{}) *gomock.Call {
 }
 
 // GetRandomVertices mocks base method.
-func (m *MockDAG[T]) GetRandomVertices(n uint) map[string]*dag.Vertex[T] {
+func (m *MockDAG[T]) GetRandomVertices(n uint) []*dag.Vertex[T] {
 	m.ctrl.T.Helper()
 	ret := m.ctrl.Call(m, "GetRandomVertices", n)
-	ret0, _ := ret[0].(map[string]*dag.Vertex[T])
+	ret0, _ := ret[0].([]*dag.Vertex[T])
 	return ret0
 }
 
@@ -117,10 +117,10 @@ func (mr *MockDAGMockRecorder[T]) GetRandomVertices(n interface{}) *gomock.Call
 }
 
 // GetSinkVertices mocks base method.
-func (m *MockDAG[T]) GetSinkVertices() map[string]*dag.Vertex[T] {
+func (m *MockDAG[T]) GetSinkVertices() []*dag.Vertex[T] {
 	m.ctrl.T.Helper()
 	ret := m.ctrl.Call(m, "GetSinkVertices")
-	ret0, _ := ret[0].(map[string]*dag.Vertex[T])
+	ret0, _ := ret[0].([]*dag.Vertex[T])
 	return ret0
 }
 
@@ -131,10 +131,10 @@ func (mr *MockDAGMockRecorder[T]) GetSinkVertices() *gomock.Call {
 }
 
 // GetSourceVertices mocks base method.
-func (m *MockDAG[T]) GetSourceVertices() map[string]*dag.Vertex[T] {
+func (m *MockDAG[T]) GetSourceVertices() []*dag.Vertex[T] {
 	m.ctrl.T.Helper()
 	ret := m.ctrl.Call(m, "GetSourceVertices")
-	ret0, _ := ret[0].(map[string]*dag.Vertex[T])
+	ret0, _ := ret[0].([]*dag.Vertex[T])
 	return ret0
 }
 


Test patch:
diff --git a/pkg/dag/dag_test.go b/pkg/dag/dag_test.go
index 73ceb1ec..8a1742fa 100644
--- a/pkg/dag/dag_test.go
+++ b/pkg/dag/dag_test.go
@@ -744,7 +744,7 @@ func TestDAGSourceVertices(t *testing.T) {
 
 				sourceVertices := d.GetSourceVertices()
 				assert.Equal(len(sourceVertices), 1)
-				assert.Equal(sourceVertices[mockVertexEID].Value, mockVertexValue)
+				assert.Equal(sourceVertices[0].Value, mockVertexValue)
 			},
 		},
 		{
@@ -791,7 +791,7 @@ func TestDAGSinkVertices(t *testing.T) {
 
 				sinkVertices := d.GetSinkVertices()
 				assert.Equal(len(sinkVertices), 1)
-				assert.Equal(sinkVertices[mockVertexFID].Value, mockVertexValue)
+				assert.Equal(sinkVertices[0].Value, mockVertexValue)
 			},
 		},
 		{