htreepage_test.go 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528
  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 TestHTreePageFetchExists(t *testing.T) {
  18. sm := storage.NewMemoryStorageManager("testsm")
  19. htree, _ := NewHTree(sm)
  20. page := htree.Root
  21. if loc := page.Location(); loc != 1 {
  22. t.Error("Unexpected root location:", loc)
  23. return
  24. }
  25. // Fill up the tree
  26. page.Put([]byte("testkey1"), "test1")
  27. page.Put([]byte("testkey2"), "test2")
  28. page.Put([]byte("testkey3"), "test3")
  29. page.Put([]byte("testkey4"), "test4")
  30. page.Put([]byte("testkey5"), "test5")
  31. page.Put([]byte("testkey6"), "test6")
  32. page.Put([]byte("testkey7"), "test7")
  33. page.Put([]byte("testkey8"), "test8")
  34. page.Put([]byte("testkey9"), "test9")
  35. page.Put([]byte("testkey10"), "test10")
  36. // Test negative cases
  37. if res, err := page.Exists([]byte("testkey40")); res != false || err != nil {
  38. t.Error("Unexpected exists result:", res, err)
  39. return
  40. }
  41. if res, _, err := page.Get([]byte("testkey40")); res != nil || err != nil {
  42. t.Error("Unexpected get result:", res, err)
  43. return
  44. }
  45. // Test positive cases
  46. if res, err := page.Exists([]byte("testkey4")); res != true || err != nil {
  47. t.Error("Unexpected exists result:", res, err)
  48. return
  49. }
  50. if res, _, err := page.Get([]byte("testkey4")); res != "test4" || err != nil {
  51. t.Error("Unexpected get result:", res, err)
  52. return
  53. }
  54. // Test error cases
  55. sm.AccessMap[8] = storage.AccessCacheAndFetchError
  56. if res, err := page.Exists([]byte("testkey4")); res != false || err.(*storage.ManagerError).Type != storage.ErrSlotNotFound {
  57. t.Error("Unexpected exists result:", res, err)
  58. return
  59. }
  60. if res, _, err := page.Get([]byte("testkey4")); res != nil || err.(*storage.ManagerError).Type != storage.ErrSlotNotFound {
  61. t.Error("Unexpected get result:", res, err)
  62. return
  63. }
  64. delete(sm.AccessMap, 8)
  65. }
  66. func TestHTreePageInsert(t *testing.T) {
  67. sm := storage.NewMemoryStorageManager("testsm")
  68. htree, _ := NewHTree(sm)
  69. page := htree.Root
  70. // Empty page operations
  71. if val, _, err := page.Get([]byte("test")); val != nil || err != nil {
  72. t.Error("Unexpected get result:", val, err)
  73. return
  74. }
  75. // Test error cases
  76. sm.AccessMap[2] = storage.AccessInsertError
  77. _, err := page.Put([]byte("testkey1"), "test1")
  78. if sfe, ok := err.(*file.StorageFileError); !ok || sfe.Type != file.ErrAlreadyInUse {
  79. t.Error("Unexpected put result:", err)
  80. return
  81. }
  82. delete(sm.AccessMap, 2)
  83. sm.AccessMap[1] = storage.AccessUpdateError
  84. if _, err := page.Put([]byte("testkey1"), "test1"); err.(*storage.ManagerError).Type != storage.ErrSlotNotFound {
  85. t.Error("Unexpected put result:", err)
  86. return
  87. }
  88. delete(sm.AccessMap, 1)
  89. // Fill the tree
  90. page.Put([]byte("testkey1"), "test1")
  91. // Test another error case
  92. sm.AccessMap[2] = storage.AccessCacheAndFetchError
  93. if _, err := page.Put([]byte("testkey2"), "test2"); err.(*storage.ManagerError).Type != storage.ErrSlotNotFound {
  94. t.Error("Unexpected put result:", err)
  95. return
  96. }
  97. delete(sm.AccessMap, 2)
  98. page.Put([]byte("testkey2"), "test2")
  99. page.Put([]byte("testkey3"), "test3")
  100. page.Put([]byte("testkey4"), "test4")
  101. page.Put([]byte("testkey5"), "test5")
  102. page.Put([]byte("testkey6"), "test6")
  103. page.Put([]byte("testkey7"), "test7")
  104. page.Put([]byte("testkey8"), "test8")
  105. // Check we have one full bucket
  106. if cc := countChildren(page); cc != 1 {
  107. t.Error("Unexpected number of children:", cc)
  108. return
  109. }
  110. // Now insert more data and see that the bucket is split
  111. // First test some error cases
  112. sm.AccessMap[3] = storage.AccessInsertError
  113. _, err = page.Put([]byte("testkey9"), "test9")
  114. if sfe, ok := err.(*file.StorageFileError); !ok || sfe.Type != file.ErrAlreadyInUse {
  115. t.Error("Unexpected put result:", err)
  116. return
  117. }
  118. delete(sm.AccessMap, 3)
  119. sm.AccessMap[1] = storage.AccessUpdateError
  120. if _, err := page.Put([]byte("testkey9"), "test9"); err.(*storage.ManagerError).Type != storage.ErrSlotNotFound {
  121. t.Error("Unexpected put result:", err)
  122. return
  123. }
  124. // Cleanup LocCount
  125. sm.LocCount--
  126. delete(sm.AccessMap, 1)
  127. // This puts the first bucket on the lowest level and extends it by 1
  128. page.Put([]byte("testkey9"), "test9")
  129. // Test sanity check for cache
  130. testMaxDepthExceededPanic(t, page, sm)
  131. // This creates a new bucket under the root
  132. page.Put([]byte("testkey10"), "test10")
  133. if cc := countChildren(page); cc != 2 {
  134. t.Error("Unexpected number of children:", cc)
  135. return
  136. }
  137. total, pages, buckets := countNodes(sm)
  138. if total != 6 || pages != 4 || buckets != 2 {
  139. t.Error("Unexpected number of nodes:", total, pages, buckets)
  140. return
  141. }
  142. // Test printing
  143. if out := htree.String(); out != "HTree: testsm (1)\n"+
  144. "HashPage 1 (depth: 0)\n"+
  145. " Hash 000000B9 (loc: 3)\n"+
  146. " HashPage 3 (depth: 1)\n"+
  147. " Hash 000000B0 (loc: 5)\n"+
  148. " HashPage 5 (depth: 2)\n"+
  149. " Hash 00000069 (loc: 7)\n"+
  150. " HashPage 7 (depth: 3)\n"+
  151. " Hash 000000AD (loc: 8)\n"+
  152. " HashBucket (9 elements, depth: 4)\n"+
  153. " [116 101 115 116 107 101 121 49] - test1\n"+
  154. " [116 101 115 116 107 101 121 50] - test2\n"+
  155. " [116 101 115 116 107 101 121 51] - test3\n"+
  156. " [116 101 115 116 107 101 121 52] - test4\n"+
  157. " [116 101 115 116 107 101 121 53] - test5\n"+
  158. " [116 101 115 116 107 101 121 54] - test6\n"+
  159. " [116 101 115 116 107 101 121 55] - test7\n"+
  160. " [116 101 115 116 107 101 121 56] - test8\n"+
  161. " [116 101 115 116 107 101 121 57] - test9\n"+
  162. " Hash 000000DE (loc: 9)\n"+
  163. " HashBucket (1 element, depth: 1)\n"+
  164. " [116 101 115 116 107 101 121 49 48] - test10\n"+
  165. " [] - <nil>\n"+
  166. " [] - <nil>\n"+
  167. " [] - <nil>\n"+
  168. " [] - <nil>\n"+
  169. " [] - <nil>\n"+
  170. " [] - <nil>\n"+
  171. " [] - <nil>\n" {
  172. t.Error("Unexpected htree output:", out)
  173. }
  174. if existing, err := page.Put([]byte("testkey10"), "test11"); existing != "test10" {
  175. t.Error("Unexpected put result", existing, err)
  176. return
  177. }
  178. }
  179. func TestHTreePageRemove(t *testing.T) {
  180. sm := storage.NewMemoryStorageManager("testsm")
  181. htree, _ := NewHTree(sm)
  182. page := htree.Root
  183. if val, err := page.Remove(nil); val != nil || err != nil {
  184. t.Error("Unexpected get result:", val, err)
  185. return
  186. }
  187. page.Put([]byte("testkey1"), "test1")
  188. page.Put([]byte("testkey2"), "test2")
  189. page.Put([]byte("testkey3"), "test3")
  190. page.Put([]byte("testkey4"), "test4")
  191. page.Put([]byte("testkey5"), "test5")
  192. page.Put([]byte("testkey6"), "test6")
  193. page.Put([]byte("testkey7"), "test7")
  194. page.Put([]byte("testkey8"), "test8")
  195. page.Put([]byte("testkey9"), "test9")
  196. page.Put([]byte("testkey10"), "test10")
  197. // Check the numbers
  198. if cc := countChildren(page); cc != 2 {
  199. t.Error("Unexpected number of children:", cc)
  200. return
  201. }
  202. total, pages, buckets := countNodes(sm)
  203. if total != 6 || pages != 4 || buckets != 2 {
  204. t.Error("Unexpected number of nodes:", total, pages, buckets)
  205. return
  206. }
  207. // Remove testkey10 which should remove a bucket
  208. res, _ := page.Put([]byte("testkey10"), nil)
  209. if res != "test10" {
  210. t.Error("Unexpected put result", res)
  211. return
  212. }
  213. if cc := countChildren(page); cc != 1 {
  214. t.Error("Unexpected number of children:", cc)
  215. return
  216. }
  217. total, pages, buckets = countNodes(sm)
  218. if total != 5 || pages != 4 || buckets != 1 {
  219. t.Error("Unexpected number of nodes:", total, pages, buckets)
  220. return
  221. }
  222. res, _ = page.Remove([]byte("testkey9"))
  223. if res != "test9" {
  224. t.Error("Unexpected remove result", res)
  225. return
  226. }
  227. _, err := page.Remove([]byte("testkey8"))
  228. if err != nil {
  229. t.Error(err)
  230. return
  231. }
  232. page.Remove([]byte("testkey7"))
  233. page.Remove([]byte("testkey6"))
  234. page.Remove([]byte("testkey5"))
  235. page.Remove([]byte("testkey4"))
  236. page.Remove([]byte("testkey3"))
  237. page.Remove([]byte("testkey2"))
  238. // Test error output when printing the tree
  239. sm.AccessMap[3] = storage.AccessCacheAndFetchError
  240. if out := htree.String(); out != "HTree: testsm (1)\n"+
  241. "HashPage 1 (depth: 0)\n"+
  242. " Hash 000000B9 (loc: 3)\n"+
  243. "Slot not found (testsm - Location:3)\n" {
  244. t.Error("Unexpected tree representation:", out)
  245. return
  246. }
  247. delete(sm.AccessMap, 3)
  248. // Check that the tree has the expected values
  249. if out := htree.String(); out != "HTree: testsm (1)\n"+
  250. "HashPage 1 (depth: 0)\n"+
  251. " Hash 000000B9 (loc: 3)\n"+
  252. " HashPage 3 (depth: 1)\n"+
  253. " Hash 000000B0 (loc: 5)\n"+
  254. " HashPage 5 (depth: 2)\n"+
  255. " Hash 00000069 (loc: 7)\n"+
  256. " HashPage 7 (depth: 3)\n"+
  257. " Hash 000000AD (loc: 8)\n"+
  258. " HashBucket (1 element, depth: 4)\n"+
  259. " [116 101 115 116 107 101 121 49] - test1\n"+
  260. " [] - <nil>\n"+
  261. " [] - <nil>\n"+
  262. " [] - <nil>\n"+
  263. " [] - <nil>\n"+
  264. " [] - <nil>\n"+
  265. " [] - <nil>\n"+
  266. " [] - <nil>\n"+
  267. " [] - <nil>\n" {
  268. t.Error("Unexpected tree representation:", out)
  269. return
  270. }
  271. res, err = page.Remove([]byte("testkey1"))
  272. if err != nil {
  273. t.Error(err)
  274. return
  275. }
  276. if out := htree.String(); out != "HTree: testsm (1)\n"+
  277. "HashPage 1 (depth: 0)\n" {
  278. t.Error("Unexpected tree representation:", out)
  279. return
  280. }
  281. // Error cases
  282. page.Put([]byte("testkey1"), "test1")
  283. page.Put([]byte("testkey2"), "test2")
  284. page.Put([]byte("testkey3"), "test3")
  285. page.Put([]byte("testkey4"), "test4")
  286. page.Put([]byte("testkey5"), "test5")
  287. page.Put([]byte("testkey6"), "test6")
  288. page.Put([]byte("testkey7"), "test7")
  289. page.Put([]byte("testkey8"), "test8")
  290. page.Put([]byte("testkey9"), "test9")
  291. page.Put([]byte("testkey10"), "test10")
  292. sm.AccessMap[16] = storage.AccessCacheAndFetchError
  293. if _, err := page.Remove([]byte("testkey1")); err.(*storage.ManagerError).Type != storage.ErrSlotNotFound {
  294. t.Error("Unexpected remove result", res)
  295. return
  296. }
  297. delete(sm.AccessMap, 16)
  298. sm.AccessMap[1] = storage.AccessUpdateError
  299. if _, err := page.Remove([]byte("testkey10")); err.(*storage.ManagerError).Type != storage.ErrSlotNotFound {
  300. t.Error("Unexpected remove result", res)
  301. return
  302. }
  303. delete(sm.AccessMap, 1)
  304. page.Remove([]byte("testkey1"))
  305. page.Remove([]byte("testkey8"))
  306. page.Remove([]byte("testkey7"))
  307. page.Remove([]byte("testkey6"))
  308. page.Remove([]byte("testkey5"))
  309. page.Remove([]byte("testkey4"))
  310. page.Remove([]byte("testkey3"))
  311. page.Remove([]byte("testkey2"))
  312. sm.AccessMap[1] = storage.AccessUpdateError
  313. if _, err := page.Remove([]byte("testkey9")); err.(*storage.ManagerError).Type != storage.ErrSlotNotFound {
  314. t.Error("Unexpected remove result", res)
  315. //return
  316. }
  317. delete(sm.AccessMap, 1)
  318. // We arrive to the same result even with all the errors
  319. // the tree is kept consistent - however there are now
  320. // orphaned data bits in the storage
  321. if out := htree.String(); out != "HTree: testsm (1)\n"+
  322. "HashPage 1 (depth: 0)\n" {
  323. t.Error("Unexpected tree representation:", out)
  324. return
  325. }
  326. }
  327. func testMaxDepthExceededPanic(t *testing.T, page *htreePage, sm *storage.MemoryStorageManager) {
  328. fn := &htreeNode{}
  329. fn.sm = sm
  330. node, _ := fn.fetchNode(8)
  331. defer func() {
  332. if r := recover(); r == nil {
  333. t.Error("Having a bucket on the lowest level which reports that it is too full should cause a panic.")
  334. }
  335. node.Depth = 4
  336. }()
  337. // The full bucket is on the lowest level - by setting the depth to 1 it
  338. // will report that it is too full even if it is located on the lowest level
  339. node.Depth = 1
  340. page.Put([]byte("testkey0"), "test9")
  341. }
  342. // Returns node numbers: total, pages, buckets
  343. //
  344. func countNodes(sm *storage.MemoryStorageManager) (int, int, int) {
  345. var total, pages, buckets int
  346. var i uint64
  347. fn := &htreeNode{}
  348. fn.sm = sm
  349. for i = 0; i < sm.LocCount; i++ {
  350. node, _ := fn.fetchNode(uint64(i))
  351. if node != nil {
  352. if node.Children != nil {
  353. total++
  354. pages++
  355. } else {
  356. total++
  357. buckets++
  358. }
  359. }
  360. }
  361. return total, pages, buckets
  362. }
  363. func countChildren(n *htreePage) int {
  364. if len(n.Children) == 0 {
  365. return 0
  366. }
  367. var count int
  368. for _, child := range n.Children {
  369. if child != 0 {
  370. count++
  371. }
  372. }
  373. return count
  374. }
  375. func TestHash(t *testing.T) {
  376. htp := &htreePage{&htreeNode{}}
  377. test := []byte{0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5}
  378. hash, _ := MurMurHashData(test, 0, len(test)-1, 42)
  379. hashstr := fmt.Sprintf("%08X", hash)
  380. if hashstr != "ACFFB715" {
  381. t.Error("Unexpected hash output:", hashstr)
  382. return
  383. }
  384. // Now check that on each level of the tree we get the right bit sequence
  385. htp.Depth = 3
  386. res := htp.hashKey(test)
  387. resstr := fmt.Sprintf("%08X", res)
  388. if resstr != "00000015" {
  389. t.Error("Unexpected hash output:", resstr)
  390. return
  391. }
  392. htp.Depth = 2
  393. res = htp.hashKey(test)
  394. resstr = fmt.Sprintf("%08X", res)
  395. if resstr != "000000B7" {
  396. t.Error("Unexpected hash output:", resstr)
  397. return
  398. }
  399. htp.Depth = 1
  400. res = htp.hashKey(test)
  401. resstr = fmt.Sprintf("%08X", res)
  402. if resstr != "000000FF" {
  403. t.Error("Unexpected hash output:", resstr)
  404. return
  405. }
  406. htp.Depth = 0
  407. res = htp.hashKey(test)
  408. resstr = fmt.Sprintf("%08X", res)
  409. if resstr != "000000AC" {
  410. t.Error("Unexpected hash output:", resstr)
  411. return
  412. }
  413. }