htreebucket_test.go 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217
  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. )
  15. func TestHashBucket(t *testing.T) {
  16. tree := &HTree{}
  17. // Create a top level bucket
  18. treebucket := newHTreeBucket(tree, 1)
  19. if treebucket.Size() != 0 {
  20. t.Error("Newly created bucket should be empty")
  21. return
  22. }
  23. if !treebucket.HasRoom() {
  24. t.Error("Newly created bucket should have room")
  25. return
  26. }
  27. if treebucket.IsLeaf() {
  28. t.Error("Newly created top level bucket should not be a leaf")
  29. return
  30. }
  31. // Test nil operations and operations on an empty bucket
  32. if res := treebucket.Remove([]byte{1, 2, 3}); res != nil {
  33. t.Error("Unexpected remove result:", res)
  34. return
  35. }
  36. if res := treebucket.Put(nil, "tester"); res != nil {
  37. t.Error("Unexpected add result:", res)
  38. return
  39. }
  40. if res := treebucket.Get(nil); res != nil {
  41. t.Error("Unexpected add result:", res)
  42. return
  43. }
  44. if res := treebucket.Get([]byte{1, 2, 3}); res != nil {
  45. t.Error("Unexpected add result:", res)
  46. return
  47. }
  48. // Simple insert case
  49. treebucket.Put([]byte{1, 2, 3}, "test1")
  50. treebucket.Put([]byte{1, 2, 4}, "test2")
  51. treebucket.Put([]byte{1, 2, 5}, "test3")
  52. if len(treebucket.Keys) != 8 || len(treebucket.Values) != 8 {
  53. t.Error("Unexpected bucket content:", treebucket.String())
  54. return
  55. }
  56. if fmt.Sprint(treebucket.Keys) != "[[1 2 3] [1 2 4] [1 2 5] [] [] [] [] []]" {
  57. t.Error("Unexpected keys content:", treebucket.Keys)
  58. return
  59. }
  60. if treebucket.Size() != 3 {
  61. t.Error("Unexpected size:", treebucket.Size())
  62. return
  63. }
  64. // Remove case
  65. if res := treebucket.Remove([]byte{9, 9, 9}); res != nil {
  66. t.Error("Unexpected remove result:", res)
  67. return
  68. }
  69. if res := treebucket.Remove([]byte{1, 2, 3}); res != "test1" {
  70. t.Error("Unexpected remove result:", res)
  71. return
  72. }
  73. if fmt.Sprint(treebucket.Keys) != "[[1 2 5] [1 2 4] [] [] [] [] [] []]" {
  74. t.Error("Unexpected keys content:", treebucket.Keys)
  75. return
  76. }
  77. if treebucket.Size() != 2 {
  78. t.Error("Unexpected size:", treebucket.Size())
  79. return
  80. }
  81. // Insert again (overwrite)
  82. treebucket.Put([]byte{1, 1, 1}, "test4")
  83. if fmt.Sprint(treebucket.Keys) != "[[1 2 5] [1 2 4] [1 1 1] [] [] [] [] []]" {
  84. t.Error("Unexpected keys content:", treebucket.Keys)
  85. return
  86. }
  87. if fmt.Sprint(treebucket.Values) != "[test3 test2 test4 <nil> <nil> <nil> <nil> <nil>]" {
  88. t.Error("Unexpected VALUES content:", treebucket.Values)
  89. return
  90. }
  91. // Update case
  92. treebucket.Put([]byte{1, 1, 1}, "test5")
  93. if fmt.Sprint(treebucket.Keys) != "[[1 2 5] [1 2 4] [1 1 1] [] [] [] [] []]" {
  94. t.Error("Unexpected keys content:", treebucket.Keys)
  95. return
  96. }
  97. if fmt.Sprint(treebucket.Values) != "[test3 test2 test5 <nil> <nil> <nil> <nil> <nil>]" {
  98. t.Error("Unexpected VALUES content:", treebucket.Values)
  99. return
  100. }
  101. // Get / Exists case
  102. if treebucket.Exists([]byte{1, 1, 2}) {
  103. t.Error("Unexpected exists result")
  104. return
  105. }
  106. if treebucket.Exists(nil) {
  107. t.Error("Unexpected exists result")
  108. return
  109. }
  110. if !treebucket.Exists([]byte{1, 1, 1}) {
  111. t.Error("Unexpected exists result")
  112. return
  113. }
  114. if res := treebucket.Get([]byte{1, 1, 1}); res != "test5" {
  115. t.Error("Unexpected get result:", res)
  116. return
  117. }
  118. if res := treebucket.Get([]byte{1, 1, 2}); res != nil {
  119. t.Error("Unexpected get result:", res)
  120. return
  121. }
  122. // Fill up the bucket
  123. treebucket.Put([]byte{1, 3, 1}, "test1")
  124. treebucket.Put([]byte{1, 3, 2}, "test2")
  125. treebucket.Put([]byte{1, 3, 3}, "test3")
  126. treebucket.Put([]byte{1, 3, 4}, "test4")
  127. treebucket.Put([]byte{1, 3, 5}, "test5")
  128. if treebucket.HasRoom() {
  129. t.Error("Full bucket should have no more room")
  130. return
  131. }
  132. testOverflowPanic(t, treebucket)
  133. // Check functionality on leaf buckets
  134. treebucket.Depth = 4
  135. if !treebucket.IsLeaf() {
  136. t.Error("Bucket should be now a leaf bucket")
  137. return
  138. }
  139. // Test bucket expansion
  140. treebucket.Put([]byte{1, 3, 6}, "test6")
  141. if fmt.Sprint(treebucket.Keys) != "[[1 2 5] [1 2 4] [1 1 1] [1 3 1] [1 3 2] [1 3 3] [1 3 4] [1 3 5] [1 3 6]]" {
  142. t.Error("Unexpected keys content:", treebucket.Keys)
  143. return
  144. }
  145. if fmt.Sprint(treebucket.Values) != "[test3 test2 test5 test1 test2 test3 test4 test5 test6]" {
  146. t.Error("Unexpected VALUES content:", treebucket.Values)
  147. return
  148. }
  149. // Test string output
  150. if res := fmt.Sprint(treebucket); res != " HashBucket (9 elements, depth: 4)\n"+
  151. " [1 2 5] - test3\n"+
  152. " [1 2 4] - test2\n"+
  153. " [1 1 1] - test5\n"+
  154. " [1 3 1] - test1\n"+
  155. " [1 3 2] - test2\n"+
  156. " [1 3 3] - test3\n"+
  157. " [1 3 4] - test4\n"+
  158. " [1 3 5] - test5\n"+
  159. " [1 3 6] - test6\n" {
  160. t.Error("Unexpected string output:", res)
  161. }
  162. }
  163. func testOverflowPanic(t *testing.T, treebucket *htreeBucket) {
  164. defer func() {
  165. if r := recover(); r == nil {
  166. t.Error("Inserting into a full non-leaf bucket did not cause a panic.")
  167. }
  168. }()
  169. treebucket.Put([]byte{1, 3, 6}, "test6")
  170. }