- Add more tests for the BST storage

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

2 files changed, 326 insertions, 5 deletions

diff --git a/plugins/websockets/storage/storage.go b/plugins/websockets/storage/storage.go
index 34f53cfd..0557dee5 100644
--- a/plugins/websockets/storage/storage.go
+++ b/plugins/websockets/storage/storage.go
@@ -17,7 +17,7 @@ func NewStorage() *Storage {
 	}
 }
 
-func (s *Storage) Store(connID string, topics []string) {
+func (s *Storage) InsertMany(connID string, topics []string) {
 	s.Lock()
 	defer s.Unlock()
 
@@ -26,7 +26,14 @@ func (s *Storage) Store(connID string, topics []string) {
 	}
 }
 
-func (s *Storage) Remove(connID string, topics []string) {
+func (s *Storage) Insert(connID string, topic string) {
+	s.Lock()
+	defer s.Unlock()
+
+	s.BST.Insert(connID, topic)
+}
+
+func (s *Storage) RemoveMany(connID string, topics []string) {
 	s.Lock()
 	defer s.Unlock()
 
@@ -35,7 +42,29 @@ func (s *Storage) Remove(connID string, topics []string) {
 	}
 }
 
-func (s *Storage) Get(topics []string, res map[string]struct{}) {
+func (s *Storage) Remove(connID string, topic string) {
+	s.Lock()
+	defer s.Unlock()
+
+	s.BST.Remove(connID, topic)
+}
+
+// Thread safe get
+func (s *Storage) GetByPtrTS(topics []string, res map[string]struct{}) {
+	s.Lock()
+	defer s.Unlock()
+
+	for i := 0; i < len(topics); i++ {
+		d := s.BST.Get(topics[i])
+		if len(d) > 0 {
+			for ii := range d {
+				res[ii] = struct{}{}
+			}
+		}
+	}
+}
+
+func (s *Storage) GetByPtr(topics []string, res map[string]struct{}) {
 	s.RLock()
 	defer s.RUnlock()
 
diff --git a/plugins/websockets/storage/storage_test.go b/plugins/websockets/storage/storage_test.go
index 77d3180a..4072992a 100644
--- a/plugins/websockets/storage/storage_test.go
+++ b/plugins/websockets/storage/storage_test.go
@@ -1,7 +1,299 @@
 package storage
 
-import "testing"
+import (
+	"math/rand"
+	"testing"
+	"time"
 
-func TestNewStorage(t *testing.T) {
+	"github.com/google/uuid"
+	"github.com/stretchr/testify/assert"
+)
 
+const predifined = "chat-1-2"
+
+func TestNewBST(t *testing.T) {
+	// create a new bst
+	g := NewStorage()
+
+	for i := 0; i < 100; i++ {
+		g.InsertMany(uuid.NewString(), []string{"comments"})
+	}
+
+	for i := 0; i < 100; i++ {
+		g.InsertMany(uuid.NewString(), []string{"comments2"})
+	}
+
+	for i := 0; i < 100; i++ {
+		g.InsertMany(uuid.NewString(), []string{"comments3"})
+	}
+
+	res := make(map[string]struct{}, 100)
+	assert.Len(t, res, 0)
+
+	// should be 100
+	g.GetByPtr([]string{"comments"}, res)
+	assert.Len(t, res, 100)
+
+	res = make(map[string]struct{}, 100)
+	assert.Len(t, res, 0)
+
+	// should be 100
+	g.GetByPtr([]string{"comments2"}, res)
+	assert.Len(t, res, 100)
+
+	res = make(map[string]struct{}, 100)
+	assert.Len(t, res, 0)
+
+	// should be 100
+	g.GetByPtr([]string{"comments3"}, res)
+	assert.Len(t, res, 100)
+}
+
+func BenchmarkGraph(b *testing.B) {
+	g := NewStorage()
+
+	for i := 0; i < 1000; i++ {
+		uid := uuid.New().String()
+		g.InsertMany(uuid.NewString(), []string{uid})
+	}
+
+	g.Insert(uuid.NewString(), predifined)
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	res := make(map[string]struct{})
+
+	for i := 0; i < b.N; i++ {
+		g.GetByPtr([]string{predifined}, res)
+
+		for i := range res {
+			delete(res, i)
+		}
+	}
+}
+
+func BenchmarkBigSearch(b *testing.B) {
+	g1 := NewStorage()
+
+	predefinedSlice := make([]string, 0, 1000)
+	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++ {
+		g1.Insert(uuid.NewString(), predefinedSlice[i])
+	}
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	res := make(map[string]struct{}, 333)
+
+	for i := 0; i < b.N; i++ {
+		g1.GetByPtr(predefinedSlice, res)
+
+		for i := range res {
+			delete(res, i)
+		}
+	}
+}
+
+func BenchmarkBigSearchWithRemoves(b *testing.B) {
+	g1 := NewStorage()
+
+	predefinedSlice := make([]string, 0, 1000)
+	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++ {
+		g1.Insert(uuid.NewString(), predefinedSlice[i])
+	}
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	go func() {
+		tt := time.NewTicker(time.Microsecond)
+
+		res := make(map[string]struct{}, 1000)
+		for {
+			select {
+			case <-tt.C:
+				num := rand.Intn(1000) //nolint:gosec
+				g1.GetByPtr(predefinedSlice, res)
+				for k := range res {
+					g1.Remove(k, predefinedSlice[num])
+				}
+			}
+		}
+	}()
+
+	res := make(map[string]struct{}, 100)
+
+	for i := 0; i < b.N; i++ {
+		g1.GetByPtr(predefinedSlice, res)
+
+		for i := range res {
+			delete(res, i)
+		}
+	}
+}
+
+func TestBigSearchWithRemoves(t *testing.T) {
+	g1 := NewStorage()
+
+	predefinedSlice := make([]string, 0, 1000)
+	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++ {
+		g1.Insert(uuid.NewString(), predefinedSlice[i])
+	}
+
+	stopCh := make(chan struct{})
+
+	go func() {
+		tt := time.NewTicker(time.Microsecond)
+
+		res := make(map[string]struct{}, 1000)
+		for {
+			select {
+			case <-tt.C:
+				num := rand.Intn(1000) //nolint:gosec
+				g1.GetByPtr(predefinedSlice, res)
+				for k := range res {
+					g1.Remove(k, predefinedSlice[num])
+				}
+
+			case <-stopCh:
+				tt.Stop()
+				return
+			}
+		}
+	}()
+
+	res := make(map[string]struct{}, 100)
+
+	for i := 0; i < 1000; i++ {
+		g1.GetByPtr(predefinedSlice, res)
+
+		for i := range res {
+			delete(res, i)
+		}
+	}
+
+	stopCh <- struct{}{}
+}
+
+func TestGraph(t *testing.T) {
+	g := NewStorage()
+
+	for i := 0; i < 1000; i++ {
+		uid := uuid.New().String()
+		g.Insert(uuid.NewString(), uid)
+	}
+
+	g.Insert(uuid.NewString(), predifined)
+
+	res := make(map[string]struct{})
+
+	g.GetByPtr([]string{predifined}, res)
+	assert.NotEmpty(t, res)
+	assert.Len(t, res, 1)
+}
+
+func TestTreeConcurrentContains(t *testing.T) {
+	g := NewStorage()
+
+	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)
+
+	res := make(map[string]struct{}, 100)
+
+	for i := 0; i < 100; i++ {
+		go func() {
+			g.GetByPtrTS([]string{predifined}, res)
+		}()
+
+		go func() {
+			g.GetByPtrTS([]string{predifined}, res)
+		}()
+
+		go func() {
+			g.GetByPtrTS([]string{predifined}, res)
+		}()
+
+		go func() {
+			g.GetByPtrTS([]string{predifined}, res)
+		}()
+	}
+
+	time.Sleep(time.Second * 5)
+
+	res2 := make(map[string]struct{}, 5)
+
+	g.GetByPtr([]string{predifined}, res2)
+	assert.NotEmpty(t, res2)
+	assert.Len(t, res2, 5)
+}
+
+func TestGraphRemove(t *testing.T) {
+	g := NewStorage()
+
+	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)
+
+	res := make(map[string]struct{}, 5)
+	g.GetByPtr([]string{predifined}, res)
+	assert.NotEmpty(t, res)
+	assert.Len(t, res, 5)
+
+	g.Remove(key1, predifined)
+
+	res2 := make(map[string]struct{}, 4)
+	g.GetByPtr([]string{predifined}, res2)
+	assert.NotEmpty(t, res2)
+	assert.Len(t, res2, 4)
 }