vendor/github.com/tendermint/tmlibs/clist/clist_test.go

   1 package clist
   2
   3 import (
   4         "fmt"
   5         "math/rand"
   6         "runtime"
   7         "sync/atomic"
   8         "testing"
   9         "time"
  10 )
  11
  12 func TestSmall(t *testing.T) {
  13         l := New()
  14         el1 := l.PushBack(1)
  15         el2 := l.PushBack(2)
  16         el3 := l.PushBack(3)
  17         if l.Len() != 3 {
  18                 t.Error("Expected len 3, got ", l.Len())
  19         }
  20
  21         //fmt.Printf("%p %v\n", el1, el1)
  22         //fmt.Printf("%p %v\n", el2, el2)
  23         //fmt.Printf("%p %v\n", el3, el3)
  24
  25         r1 := l.Remove(el1)
  26
  27         //fmt.Printf("%p %v\n", el1, el1)
  28         //fmt.Printf("%p %v\n", el2, el2)
  29         //fmt.Printf("%p %v\n", el3, el3)
  30
  31         r2 := l.Remove(el2)
  32
  33         //fmt.Printf("%p %v\n", el1, el1)
  34         //fmt.Printf("%p %v\n", el2, el2)
  35         //fmt.Printf("%p %v\n", el3, el3)
  36
  37         r3 := l.Remove(el3)
  38
  39         if r1 != 1 {
  40                 t.Error("Expected 1, got ", r1)
  41         }
  42         if r2 != 2 {
  43                 t.Error("Expected 2, got ", r2)
  44         }
  45         if r3 != 3 {
  46                 t.Error("Expected 3, got ", r3)
  47         }
  48         if l.Len() != 0 {
  49                 t.Error("Expected len 0, got ", l.Len())
  50         }
  51
  52 }
  53
  54 /*
  55 This test is quite hacky because it relies on SetFinalizer
  56 which isn't guaranteed to run at all.
  57 */
  58 // nolint: megacheck
  59 func _TestGCFifo(t *testing.T) {
  60
  61         const numElements = 1000000
  62         l := New()
  63         gcCount := new(uint64)
  64
  65         // SetFinalizer doesn't work well with circular structures,
  66         // so we construct a trivial non-circular structure to
  67         // track.
  68         type value struct {
  69                 Int int
  70         }
  71         done := make(chan struct{})
  72
  73         for i := 0; i < numElements; i++ {
  74                 v := new(value)
  75                 v.Int = i
  76                 l.PushBack(v)
  77                 runtime.SetFinalizer(v, func(v *value) {
  78                         atomic.AddUint64(gcCount, 1)
  79                 })
  80         }
  81
  82         for el := l.Front(); el != nil; {
  83                 l.Remove(el)
  84                 //oldEl := el
  85                 el = el.Next()
  86                 //oldEl.DetachPrev()
  87                 //oldEl.DetachNext()
  88         }
  89
  90         runtime.GC()
  91         time.Sleep(time.Second * 3)
  92         runtime.GC()
  93         time.Sleep(time.Second * 3)
  94         _ = done
  95
  96         if *gcCount != numElements {
  97                 t.Errorf("Expected gcCount to be %v, got %v", numElements,
  98                         *gcCount)
  99         }
 100 }
 101
 102 /*
 103 This test is quite hacky because it relies on SetFinalizer
 104 which isn't guaranteed to run at all.
 105 */
 106 // nolint: megacheck
 107 func _TestGCRandom(t *testing.T) {
 108
 109         const numElements = 1000000
 110         l := New()
 111         gcCount := 0
 112
 113         // SetFinalizer doesn't work well with circular structures,
 114         // so we construct a trivial non-circular structure to
 115         // track.
 116         type value struct {
 117                 Int int
 118         }
 119
 120         for i := 0; i < numElements; i++ {
 121                 v := new(value)
 122                 v.Int = i
 123                 l.PushBack(v)
 124                 runtime.SetFinalizer(v, func(v *value) {
 125                         gcCount += 1
 126                 })
 127         }
 128
 129         els := make([]*CElement, 0, numElements)
 130         for el := l.Front(); el != nil; el = el.Next() {
 131                 els = append(els, el)
 132         }
 133
 134         for _, i := range rand.Perm(numElements) {
 135                 el := els[i]
 136                 l.Remove(el)
 137                 _ = el.Next()
 138         }
 139
 140         runtime.GC()
 141         time.Sleep(time.Second * 3)
 142
 143         if gcCount != numElements {
 144                 t.Errorf("Expected gcCount to be %v, got %v", numElements,
 145                         gcCount)
 146         }
 147 }
 148
 149 func TestScanRightDeleteRandom(t *testing.T) {
 150
 151         const numElements = 10000
 152         const numTimes = 1000
 153         const numScanners = 10
 154
 155         l := New()
 156         stop := make(chan struct{})
 157
 158         els := make([]*CElement, numElements)
 159         for i := 0; i < numElements; i++ {
 160                 el := l.PushBack(i)
 161                 els[i] = el
 162         }
 163
 164         // Launch scanner routines that will rapidly iterate over elements.
 165         for i := 0; i < numScanners; i++ {
 166                 go func(scannerID int) {
 167                         var el *CElement
 168                         restartCounter := 0
 169                         counter := 0
 170                 FOR_LOOP:
 171                         for {
 172                                 select {
 173                                 case <-stop:
 174                                         fmt.Println("stopped")
 175                                         break FOR_LOOP
 176                                 default:
 177                                 }
 178                                 if el == nil {
 179                                         el = l.FrontWait()
 180                                         restartCounter += 1
 181                                 }
 182                                 el = el.Next()
 183                                 counter += 1
 184                         }
 185                         fmt.Printf("Scanner %v restartCounter: %v counter: %v\n", scannerID, restartCounter, counter)
 186                 }(i)
 187         }
 188
 189         // Remove an element, push back an element.
 190         for i := 0; i < numTimes; i++ {
 191                 // Pick an element to remove
 192                 rmElIdx := rand.Intn(len(els))
 193                 rmEl := els[rmElIdx]
 194
 195                 // Remove it
 196                 l.Remove(rmEl)
 197                 //fmt.Print(".")
 198
 199                 // Insert a new element
 200                 newEl := l.PushBack(-1*i - 1)
 201                 els[rmElIdx] = newEl
 202
 203                 if i%100000 == 0 {
 204                         fmt.Printf("Pushed %vK elements so far...\n", i/1000)
 205                 }
 206
 207         }
 208
 209         // Stop scanners
 210         close(stop)
 211         time.Sleep(time.Second * 1)
 212
 213         // And remove all the elements.
 214         for el := l.Front(); el != nil; el = el.Next() {
 215                 l.Remove(el)
 216         }
 217         if l.Len() != 0 {
 218                 t.Fatal("Failed to remove all elements from CList")
 219         }
 220 }