linked_test.go 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236
  1. package udptransfer
  2. import (
  3. "fmt"
  4. "math/rand"
  5. "testing"
  6. )
  7. var lmap *linkedMap
  8. func init() {
  9. lmap = newLinkedMap(_QModeIn)
  10. }
  11. func node(seq int) *qNode {
  12. return &qNode{packet: &packet{seq: uint32(seq)}}
  13. }
  14. func Test_get(t *testing.T) {
  15. var i, n *qNode
  16. assert(!lmap.contains(0), t, "0 nil")
  17. n = node(0)
  18. lmap.head = n
  19. lmap.tail = n
  20. lmap.qmap[0] = n
  21. i = lmap.get(0)
  22. assert(i == n, t, "0=n")
  23. }
  24. func Test_insert(t *testing.T) {
  25. lmap.reset()
  26. n := node(1)
  27. // appendTail
  28. lmap.appendTail(n)
  29. assert(lmap.head == n, t, "head n")
  30. assert(lmap.tail == n, t, "head n")
  31. n = node(2)
  32. lmap.appendTail(n)
  33. assert(lmap.head != n, t, "head n")
  34. assert(lmap.tail == n, t, "head n")
  35. assert(lmap.size() == 2, t, "size")
  36. }
  37. func Test_insertAfter(t *testing.T) {
  38. n1 := lmap.get(1)
  39. n2 := n1.next
  40. n3 := node(3)
  41. lmap.insertAfter(n1, n3)
  42. assert(n1.next == n3, t, "n3")
  43. assert(n1 == n3.prev, t, "left n3")
  44. assert(n2 == n3.next, t, "n3 right")
  45. }
  46. func Test_insertBefore(t *testing.T) {
  47. n3 := lmap.get(3)
  48. n2 := n3.next
  49. n4 := node(4)
  50. lmap.insertAfter(n3, n4)
  51. assert(n3.next == n4, t, "n4")
  52. assert(n3 == n4.prev, t, "left n4")
  53. assert(n2 == n4.next, t, "n4 right")
  54. }
  55. func Test_deleteBefore(t *testing.T) {
  56. lmap.reset()
  57. for i := 1; i < 10; i++ {
  58. n := node(i)
  59. lmap.appendTail(n)
  60. }
  61. var assertRangeEquals = func(n *qNode, start, wantCount int) {
  62. var last *qNode
  63. var count int
  64. for ; n != nil; n = n.next {
  65. assert(int(n.seq) == start, t, "nseq=%d start=%d", n.seq, start)
  66. last = n
  67. start++
  68. count++
  69. }
  70. assert(last.next == nil, t, "tail nil")
  71. assert(count == wantCount, t, "count")
  72. }
  73. assertRangeEquals(lmap.head, 1, 9)
  74. var n *qNode
  75. n = lmap.get(3)
  76. n, _ = lmap.deleteBefore(n)
  77. assertRangeEquals(n, 1, 3)
  78. assert(lmap.head.seq == 4, t, "head")
  79. n = lmap.get(8)
  80. n, _ = lmap.deleteBefore(n)
  81. assertRangeEquals(n, 4, 5)
  82. assert(lmap.head.seq == 9, t, "head")
  83. n = lmap.get(9)
  84. n, _ = lmap.deleteBefore(n)
  85. assertRangeEquals(n, 9, 1)
  86. assert(lmap.size() == 0, t, "size 0")
  87. assert(lmap.head == nil, t, "head nil")
  88. assert(lmap.tail == nil, t, "tail nil")
  89. }
  90. func testBitmap(t *testing.T, bmap []uint64, prev uint32) {
  91. var j uint
  92. var k int
  93. bits := bmap[k]
  94. t.Logf("test-%d %016x", k, bits)
  95. var checkNextPage = func() {
  96. if j >= 64 {
  97. j = 0
  98. k++
  99. bits = bmap[k]
  100. t.Logf("test-%d %016x", k, bits)
  101. }
  102. }
  103. for i := lmap.head; i != nil && k < len(bmap); i = i.next {
  104. checkNextPage()
  105. dis := i.seq - prev
  106. prev = i.seq
  107. if dis == 1 {
  108. bit := (bits >> j) & 1
  109. assert(bit == 1, t, "1 bit=%d j=%d", bit, j)
  110. j++
  111. } else {
  112. for ; dis > 0; dis-- {
  113. checkNextPage()
  114. bit := (bits >> j) & 1
  115. want := uint64(0)
  116. if dis == 1 {
  117. want = 1
  118. }
  119. assert(bit == want, t, "?=%d bit=%d j=%d", want, bit, j)
  120. j++
  121. }
  122. }
  123. }
  124. // remains bits should be 0
  125. for i := j & 63; i > 0; i-- {
  126. bit := (bits >> j) & 1
  127. assert(bit == 0, t, "00 bit=%d j=%d", bit, j)
  128. j++
  129. }
  130. }
  131. func Test_bitmap(t *testing.T) {
  132. var prev uint32
  133. var head uint32 = prev + 1
  134. lmap.reset()
  135. // test 66-%3 and record holes
  136. var holes = make([]uint32, 0, 50)
  137. for i := head; i < 366; i++ {
  138. if i%3 == 0 {
  139. holes = append(holes, i)
  140. continue
  141. }
  142. n := node(int(i))
  143. lmap.appendTail(n)
  144. }
  145. bmap, tbl := lmap.makeHolesBitmap(prev)
  146. testBitmap(t, bmap, prev)
  147. lmap.reset()
  148. // full 66, do deleteByBitmap then compare
  149. for i := head; i < 366; i++ {
  150. n := node(int(i))
  151. lmap.appendTail(n)
  152. }
  153. lmap.deleteByBitmap(bmap, head, tbl)
  154. var holesResult = make([]uint32, 0, 50)
  155. for i := lmap.head; i != nil; i = i.next {
  156. if i.scnt != _SENT_OK {
  157. holesResult = append(holesResult, i.seq)
  158. }
  159. }
  160. a := fmt.Sprintf("%x", holes)
  161. b := fmt.Sprintf("%x", holesResult)
  162. assert(a == b, t, "deleteByBitmap \na=%s \nb=%s", a, b)
  163. lmap.reset()
  164. // test stride across page 1
  165. for i := head; i < 69; i++ {
  166. if i >= 63 && i <= 65 {
  167. continue
  168. }
  169. n := node(int(i))
  170. lmap.appendTail(n)
  171. }
  172. bmap, _ = lmap.makeHolesBitmap(prev)
  173. testBitmap(t, bmap, prev)
  174. lmap.reset()
  175. prev = 65
  176. head = prev + 1
  177. // test stride across page 0
  178. for i := head; i < 68; i++ {
  179. n := node(int(i))
  180. lmap.appendTail(n)
  181. }
  182. bmap, _ = lmap.makeHolesBitmap(prev)
  183. testBitmap(t, bmap, prev)
  184. }
  185. var ackbitmap []uint64
  186. func init_benchmark_map() {
  187. if lmap.size() != 640 {
  188. lmap.reset()
  189. for i := 1; i <= 640; i++ {
  190. lmap.appendTail(node(i))
  191. }
  192. ackbitmap = make([]uint64, 10)
  193. for i := 0; i < len(ackbitmap); i++ {
  194. n := rand.Int63()
  195. ackbitmap[i] = uint64(n) << 1
  196. }
  197. }
  198. }
  199. func Benchmark_make_bitmap(b *testing.B) {
  200. init_benchmark_map()
  201. for i := 0; i < b.N; i++ {
  202. lmap.makeHolesBitmap(0)
  203. }
  204. }
  205. func Benchmark_apply_bitmap(b *testing.B) {
  206. init_benchmark_map()
  207. for i := 0; i < b.N; i++ {
  208. lmap.deleteByBitmap(ackbitmap, 1, 64)
  209. }
  210. }