- Tests for the BST algo

Signed-off-by: Valery Piashchynski <[email protected]>

2 files changed, 369 insertions, 11 deletions

diff --git a/pkg/bst/bst.go b/pkg/bst/bst.go
index 8477ceee..bbff91f4 100644
--- a/pkg/bst/bst.go
+++ b/pkg/bst/bst.go
@@ -13,7 +13,9 @@ type BST struct {
 }
 
 func NewBST() Storage {
-	return &BST{}
+	return &BST{
+		uuids: make(map[string]struct{}, 10),
+	}
 }
 
 // Insert uuid to the topic
@@ -21,12 +23,12 @@ func (b *BST) Insert(uuid string, topic string) {
 	curr := b
 
 	for {
-		if curr.topic == topic {
+		if topic == curr.topic {
 			curr.uuids[uuid] = struct{}{}
 			return
 		}
 		// if topic less than curr topic
-		if curr.topic < topic {
+		if topic < curr.topic {
 			if curr.left == nil {
 				curr.left = &BST{
 					topic: topic,
@@ -53,16 +55,13 @@ func (b *BST) Insert(uuid string, topic string) {
 func (b *BST) Get(topic string) map[string]struct{} {
 	curr := b
 	for curr != nil {
-		if curr.topic == topic {
-			return curr.uuids
-		}
-		if curr.topic < topic {
+		switch {
+		case topic < curr.topic:
 			curr = curr.left
-			continue
-		}
-		if curr.topic > topic {
+		case topic > curr.topic:
 			curr = curr.right
-			continue
+		case topic == curr.topic:
+			return curr.uuids
 		}
 	}
 
@@ -83,6 +82,8 @@ func (b *BST) removeHelper(uuid string, topic string, parent *BST) { //nolint:go
 			parent = curr
 			curr = curr.right
 		} else {
+
+			// if more than 1 topic - remove only topic, do not remove the whole vertex
 			if len(curr.uuids) > 1 {
 				if _, ok := curr.uuids[uuid]; ok {
 					delete(curr.uuids, uuid)
diff --git a/pkg/bst/bst_test.go b/pkg/bst/bst_test.go
index e8a13760..f7db68af 100644
--- a/pkg/bst/bst_test.go
+++ b/pkg/bst/bst_test.go
@@ -1,7 +1,9 @@
 package bst
 
 import (
+	"math/rand"
 	"testing"
+	"time"
 
 	"github.com/google/uuid"
 	"github.com/stretchr/testify/assert"
@@ -35,3 +37,358 @@ func TestNewBST(t *testing.T) {
 	exist3 := g.Get("comments3")
 	assert.Len(t, exist3, 100)
 }
+
+const predifined = "chat-1-2"
+
+func BenchmarkGraph(b *testing.B) {
+	g := NewBST()
+
+	for i := 0; i < 1000; i++ {
+		uid := uuid.New().String()
+		g.Insert(uuid.NewString(), uid)
+	}
+
+	g.Insert(uuid.NewString(), predifined)
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	for i := 0; i < b.N; i++ {
+		exist := g.Get(predifined)
+		_ = exist
+	}
+}
+
+func BenchmarkBigSearch(b *testing.B) {
+	g1 := NewBST()
+	g2 := NewBST()
+	g3 := NewBST()
+
+	var predefinedSlice []string
+	for i := 0; i < 1000; i++ {
+		predefinedSlice = append(predefinedSlice, uuid.NewString())
+	}
+	if predefinedSlice == nil {
+		b.FailNow()
+	}
+
+	for i := 0; i < 1000; i++ {
+		g1.Insert(uuid.NewString(), uuid.NewString())
+	}
+	for i := 0; i < 1000; i++ {
+		g2.Insert(uuid.NewString(), uuid.NewString())
+	}
+	for i := 0; i < 1000; i++ {
+		g3.Insert(uuid.NewString(), uuid.NewString())
+	}
+
+	for i := 0; i < 333; i++ {
+		g1.Insert(uuid.NewString(), predefinedSlice[i])
+	}
+
+	for i := 0; i < 333; i++ {
+		g2.Insert(uuid.NewString(), predefinedSlice[333+i])
+	}
+
+	for i := 0; i < 333; i++ {
+		g3.Insert(uuid.NewString(), predefinedSlice[666+i])
+	}
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	for i := 0; i < b.N; i++ {
+		for i := 0; i < 333; i++ {
+			exist := g1.Get(predefinedSlice[i])
+			_ = exist
+		}
+	}
+	for i := 0; i < b.N; i++ {
+		for i := 0; i < 333; i++ {
+			exist := g2.Get(predefinedSlice[333+i])
+			_ = exist
+		}
+	}
+	for i := 0; i < b.N; i++ {
+		for i := 0; i < 333; i++ {
+			exist := g3.Get(predefinedSlice[666+i])
+			_ = exist
+		}
+	}
+}
+
+func BenchmarkBigSearchWithRemoves(b *testing.B) {
+	g1 := NewBST()
+	g2 := NewBST()
+	g3 := NewBST()
+
+	var predefinedSlice []string
+	for i := 0; i < 1000; i++ {
+		predefinedSlice = append(predefinedSlice, uuid.NewString())
+	}
+	if predefinedSlice == nil {
+		b.FailNow()
+	}
+
+	for i := 0; i < 1000; i++ {
+		g1.Insert(uuid.NewString(), uuid.NewString())
+	}
+	for i := 0; i < 1000; i++ {
+		g2.Insert(uuid.NewString(), uuid.NewString())
+	}
+	for i := 0; i < 1000; i++ {
+		g3.Insert(uuid.NewString(), uuid.NewString())
+	}
+
+	for i := 0; i < 333; i++ {
+		g1.Insert(uuid.NewString(), predefinedSlice[i])
+	}
+
+	for i := 0; i < 333; i++ {
+		g2.Insert(uuid.NewString(), predefinedSlice[333+i])
+	}
+
+	for i := 0; i < 333; i++ {
+		g3.Insert(uuid.NewString(), predefinedSlice[666+i])
+	}
+
+	go func() {
+		tt := time.NewTicker(time.Millisecond)
+		for {
+			select {
+			case <-tt.C:
+				num := rand.Intn(333)
+				values := g1.Get(predefinedSlice[num])
+				for k := range values {
+					g1.Remove(k, predefinedSlice[num])
+				}
+			}
+		}
+	}()
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	for i := 0; i < b.N; i++ {
+		for i := 0; i < 333; i++ {
+			exist := g1.Get(predefinedSlice[i])
+			_ = exist
+		}
+	}
+	for i := 0; i < b.N; i++ {
+		for i := 0; i < 333; i++ {
+			exist := g2.Get(predefinedSlice[333+i])
+			_ = exist
+		}
+	}
+	for i := 0; i < b.N; i++ {
+		for i := 0; i < 333; i++ {
+			exist := g3.Get(predefinedSlice[666+i])
+			_ = exist
+		}
+	}
+}
+
+func TestGraph(t *testing.T) {
+	g := NewBST()
+
+	for i := 0; i < 1000; i++ {
+		uid := uuid.New().String()
+		g.Insert(uuid.NewString(), uid)
+	}
+
+	g.Insert(uuid.NewString(), predifined)
+
+	exist := g.Get(predifined)
+	assert.NotNil(t, exist)
+	assert.Len(t, exist, 1)
+}
+
+func TestTreeConcurrentContains(t *testing.T) {
+	g := NewBST()
+
+	key1 := uuid.NewString()
+	key2 := uuid.NewString()
+	key3 := uuid.NewString()
+	key4 := uuid.NewString()
+	key5 := uuid.NewString()
+
+	g.Insert(key1, predifined)
+	g.Insert(key2, predifined)
+	g.Insert(key3, predifined)
+	g.Insert(key4, predifined)
+	g.Insert(key5, predifined)
+
+	for i := 0; i < 100; i++ {
+		go func() {
+			_ = g.Get(predifined)
+		}()
+
+		go func() {
+			_ = g.Get(predifined)
+		}()
+
+		go func() {
+			_ = g.Get(predifined)
+		}()
+
+		go func() {
+			_ = g.Get(predifined)
+		}()
+	}
+
+	time.Sleep(time.Second * 2)
+
+	exist := g.Get(predifined)
+	assert.NotNil(t, exist)
+	assert.Len(t, exist, 5)
+}
+
+func TestGraphRemove(t *testing.T) {
+	g := NewBST()
+
+	key1 := uuid.NewString()
+	key2 := uuid.NewString()
+	key3 := uuid.NewString()
+	key4 := uuid.NewString()
+	key5 := uuid.NewString()
+
+	g.Insert(key1, predifined)
+	g.Insert(key2, predifined)
+	g.Insert(key3, predifined)
+	g.Insert(key4, predifined)
+	g.Insert(key5, predifined)
+
+	exist := g.Get(predifined)
+	assert.NotNil(t, exist)
+	assert.Len(t, exist, 5)
+
+	g.Remove(key1, predifined)
+
+	exist = g.Get(predifined)
+	assert.NotNil(t, exist)
+	assert.Len(t, exist, 4)
+}
+
+func TestBigSearch(t *testing.T) {
+	g1 := NewBST()
+	g2 := NewBST()
+	g3 := NewBST()
+
+	var predefinedSlice []string
+	for i := 0; i < 1000; i++ {
+		predefinedSlice = append(predefinedSlice, uuid.NewString())
+	}
+	if predefinedSlice == nil {
+		t.FailNow()
+	}
+
+	for i := 0; i < 1000; i++ {
+		g1.Insert(uuid.NewString(), uuid.NewString())
+	}
+	for i := 0; i < 1000; i++ {
+		g2.Insert(uuid.NewString(), uuid.NewString())
+	}
+	for i := 0; i < 1000; i++ {
+		g3.Insert(uuid.NewString(), uuid.NewString())
+	}
+
+	for i := 0; i < 333; i++ {
+		g1.Insert(uuid.NewString(), predefinedSlice[i])
+	}
+
+	for i := 0; i < 333; i++ {
+		g2.Insert(uuid.NewString(), predefinedSlice[333+i])
+	}
+
+	for i := 0; i < 333; i++ {
+		g3.Insert(uuid.NewString(), predefinedSlice[666+i])
+	}
+
+	for i := 0; i < 333; i++ {
+		exist := g1.Get(predefinedSlice[i])
+		assert.NotNil(t, exist)
+		assert.Len(t, exist, 1)
+	}
+
+	for i := 0; i < 333; i++ {
+		exist := g2.Get(predefinedSlice[333+i])
+		assert.NotNil(t, exist)
+		assert.Len(t, exist, 1)
+	}
+
+	for i := 0; i < 333; i++ {
+		exist := g3.Get(predefinedSlice[666+i])
+		assert.NotNil(t, exist)
+		assert.Len(t, exist, 1)
+	}
+}
+
+func TestBigSearchWithRemoves(t *testing.T) {
+	g1 := NewBST()
+	g2 := NewBST()
+	g3 := NewBST()
+
+	var predefinedSlice []string
+	for i := 0; i < 1000; i++ {
+		predefinedSlice = append(predefinedSlice, uuid.NewString())
+	}
+	if predefinedSlice == nil {
+		t.FailNow()
+	}
+
+	for i := 0; i < 100000; i++ {
+		g1.Insert(uuid.NewString(), uuid.NewString())
+	}
+	for i := 0; i < 100000; i++ {
+		g2.Insert(uuid.NewString(), uuid.NewString())
+	}
+	for i := 0; i < 100000; i++ {
+		g3.Insert(uuid.NewString(), uuid.NewString())
+	}
+
+	for i := 0; i < 333; i++ {
+		g1.Insert(uuid.NewString(), predefinedSlice[i])
+	}
+
+	for i := 0; i < 333; i++ {
+		g2.Insert(uuid.NewString(), predefinedSlice[333+i])
+	}
+
+	for i := 0; i < 333; i++ {
+		g3.Insert(uuid.NewString(), predefinedSlice[666+i])
+	}
+
+	time.Sleep(time.Second * 1)
+	go func() {
+		tt := time.NewTicker(time.Second)
+		for {
+			select {
+			case <-tt.C:
+				num := rand.Intn(333)
+				values := g1.Get(predefinedSlice[num])
+				for k := range values {
+					g1.Remove(k, predefinedSlice[num])
+				}
+			}
+		}
+	}()
+
+	for i := 0; i < 333; i++ {
+		exist := g1.Get(predefinedSlice[i])
+		assert.NotNil(t, exist)
+		assert.Len(t, exist, 1)
+	}
+
+	for i := 0; i < 333; i++ {
+		exist := g2.Get(predefinedSlice[333+i])
+		assert.NotNil(t, exist)
+		assert.Len(t, exist, 1)
+	}
+
+	for i := 0; i < 333; i++ {
+		exist := g3.Get(predefinedSlice[666+i])
+		assert.NotNil(t, exist)
+		assert.Len(t, exist, 1)
+	}
+}