iterator_test.go 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224
  1. /*
  2. * EliasDB
  3. *
  4. * Copyright 2016 Matthias Ladkau. All rights reserved.
  5. *
  6. * This Source Code Form is subject to the terms of the Mozilla Public
  7. * License, v. 2.0. If a copy of the MPL was not distributed with this
  8. * file, You can obtain one at http://mozilla.org/MPL/2.0/.
  9. */
  10. package hash
  11. import (
  12. "fmt"
  13. "testing"
  14. "devt.de/krotik/eliasdb/storage"
  15. "devt.de/krotik/eliasdb/storage/file"
  16. )
  17. func TestIterator(t *testing.T) {
  18. // Do a very simple case
  19. sm := storage.NewMemoryStorageManager("testsm")
  20. htree, _ := NewHTree(sm)
  21. page := htree.Root
  22. if loc := page.Location(); loc != 1 {
  23. t.Error("Unexpected root location:", loc)
  24. return
  25. }
  26. // Fill up the tree
  27. page.Put([]byte("testkey1"), "test1")
  28. page.Put([]byte("testkey8"), "test8")
  29. page.Put([]byte("testkey5"), "test5")
  30. it := NewHTreeIterator(htree)
  31. if k, v := it.Next(); string(k) != "testkey1" || v != "test1" {
  32. t.Error("Unexpected next result:", k, v)
  33. return
  34. }
  35. if k, v := it.Next(); string(k) != "testkey8" || v != "test8" {
  36. t.Error("Unexpected next result:", k, v)
  37. return
  38. }
  39. if k, v := it.Next(); string(k) != "testkey5" || v != "test5" {
  40. t.Error("Unexpected next result:", k, v)
  41. return
  42. }
  43. if it.HasNext() {
  44. t.Error("Iterator should be finished")
  45. return
  46. }
  47. if k, v := it.Next(); k != nil || v != nil {
  48. t.Error("Return values should be nil")
  49. return
  50. }
  51. // Create a new iterator and try the same steps again
  52. it = NewHTreeIterator(htree)
  53. if k, v := it.Next(); string(k) != "testkey1" || v != "test1" {
  54. t.Error("Unexpected next result:", k, v)
  55. return
  56. }
  57. if k, v := it.Next(); string(k) != "testkey8" || v != "test8" {
  58. t.Error("Unexpected next result:", k, v)
  59. return
  60. }
  61. // But before the iterator finishes we change the tree behind its back
  62. page.Put([]byte("testkey2"), "test2")
  63. page.Put([]byte("testkey3"), "test3")
  64. page.Put([]byte("testkey4"), "test4")
  65. page.Put([]byte("testkey6"), "test6")
  66. page.Put([]byte("testkey7"), "test7")
  67. page.Put([]byte("testkey9"), "test9")
  68. page.Put([]byte("testkey100"), "test100")
  69. page.Put([]byte("abba1"), "song1")
  70. page.Put([]byte("tfst"), "zzzz")
  71. // The tree has changed behind the iterator's back.
  72. if k, v := it.Next(); string(k) != "testkey5" || v != "test5" {
  73. t.Error("Unexpected next result:", k, v)
  74. return
  75. }
  76. // We get now all the items in the Children array of the root page which
  77. // have been inserted after the current location. The iterator then finishes
  78. // normally.
  79. if k, v := it.Next(); string(k) != "tfst" || v != "zzzz" {
  80. t.Error("Unexpected next result:", k, v)
  81. return
  82. }
  83. if it.HasNext() {
  84. t.Error("Iterator should be finished")
  85. return
  86. }
  87. if k, v := it.Next(); k != nil || v != nil {
  88. t.Error("Return values should be nil")
  89. return
  90. }
  91. // Create a new iterator and see that we can iterate everything
  92. it = NewHTreeIterator(htree)
  93. if k, v := it.Next(); string(k) != "testkey100" || v != "test100" {
  94. t.Error("Unexpected next result:", k, v)
  95. return
  96. }
  97. if k, v := it.Next(); string(k) != "abba1" || v != "song1" {
  98. t.Error("Unexpected next result:", k, v)
  99. return
  100. }
  101. if k, v := it.Next(); string(k) != "testkey1" || v != "test1" {
  102. t.Error("Unexpected next result:", k, v)
  103. return
  104. }
  105. if k, v := it.Next(); string(k) != "testkey8" || v != "test8" {
  106. t.Error("Unexpected next result:", k, v)
  107. return
  108. }
  109. if k, v := it.Next(); string(k) != "testkey5" || v != "test5" {
  110. t.Error("Unexpected next result:", k, v)
  111. return
  112. }
  113. if k, v := it.Next(); string(k) != "testkey2" || v != "test2" {
  114. t.Error("Unexpected next result:", k, v)
  115. return
  116. }
  117. if k, v := it.Next(); string(k) != "testkey3" || v != "test3" {
  118. t.Error("Unexpected next result:", k, v)
  119. return
  120. }
  121. if k, v := it.Next(); string(k) != "testkey4" || v != "test4" {
  122. t.Error("Unexpected next result:", k, v)
  123. return
  124. }
  125. if k, v := it.Next(); string(k) != "testkey6" || v != "test6" {
  126. t.Error("Unexpected next result:", k, v)
  127. return
  128. }
  129. if k, v := it.Next(); string(k) != "testkey7" || v != "test7" {
  130. t.Error("Unexpected next result:", k, v)
  131. return
  132. }
  133. if k, v := it.Next(); string(k) != "testkey9" || v != "test9" {
  134. t.Error("Unexpected next result:", k, v)
  135. return
  136. }
  137. if k, v := it.Next(); string(k) != "tfst" || v != "zzzz" {
  138. t.Error("Unexpected next result:", k, v)
  139. return
  140. }
  141. if it.HasNext() {
  142. t.Error("Iterator should be finished")
  143. return
  144. }
  145. if k, v := it.Next(); k != nil || v != nil {
  146. t.Error("Return values should be nil")
  147. return
  148. }
  149. // Test error case
  150. it = NewHTreeIterator(htree)
  151. if k, v := it.Next(); string(k) != "testkey100" || v != "test100" {
  152. t.Error("Unexpected next result:", k, v)
  153. return
  154. }
  155. sm.AccessMap[3] = storage.AccessCacheAndFetchSeriousError
  156. if k, v := it.Next(); string(k) != "abba1" || v != "song1" {
  157. t.Error("Unexpected next result:", k, v)
  158. return
  159. }
  160. if k, v := it.Next(); k != nil || v != nil {
  161. t.Error("Unexpected next result:", k, v)
  162. return
  163. }
  164. if it.LastError != file.ErrAlreadyInUse {
  165. t.Error("Unexpected last error pointer of iterator")
  166. return
  167. }
  168. delete(sm.AccessMap, 3)
  169. if fmt.Sprint(it) != "HTree Iterator (tree: 1)\n"+
  170. " path: []\n"+
  171. " indices: []\n"+
  172. " next: [] / <nil>\n" {
  173. t.Error("Unexpected tree string representation:", it)
  174. return
  175. }
  176. }