iterator.go 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222
  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. "errors"
  13. "fmt"
  14. "devt.de/krotik/eliasdb/storage"
  15. )
  16. /*
  17. ErrNoMoreItems is assigned to LastError when Next() is called and there are no
  18. more items to iterate.
  19. */
  20. var ErrNoMoreItems = errors.New("No more items to iterate")
  21. /*
  22. HTreeIterator data structure
  23. */
  24. type HTreeIterator struct {
  25. tree *HTree // Tree to iterate
  26. nodePath []uint64 // Path in the tree we currently traversing
  27. indices []int // List of the current indices in the current path
  28. nextKey []byte // Next iterator key (overwritten by nextItem)
  29. nextValue interface{} // Next iterator value
  30. LastError error // Last encountered error
  31. }
  32. /*
  33. NewHTreeIterator creates a new HTreeIterator.
  34. */
  35. func NewHTreeIterator(tree *HTree) *HTreeIterator {
  36. it := &HTreeIterator{tree, make([]uint64, 0), make([]int, 0), nil, nil, nil}
  37. it.nodePath = append(it.nodePath, tree.Root.Location())
  38. it.indices = append(it.indices, -1)
  39. // Set the nextKey and nextValue properties
  40. it.Next()
  41. return it
  42. }
  43. /*
  44. HasNext returns if there is a next key / value pair.
  45. */
  46. func (it *HTreeIterator) HasNext() bool {
  47. return it.nextKey != nil
  48. }
  49. /*
  50. Next returns the next key / value pair.
  51. */
  52. func (it *HTreeIterator) Next() ([]byte, interface{}) {
  53. key := it.nextKey
  54. value := it.nextValue
  55. if err := it.nextItem(); err != ErrNoMoreItems && err != nil {
  56. it.LastError = err
  57. // There was a serious error terminate the iterator
  58. it.nodePath = make([]uint64, 0)
  59. it.indices = make([]int, 0)
  60. it.nextKey = nil
  61. it.nextValue = nil
  62. }
  63. return key, value
  64. }
  65. /*
  66. Retrieve the next key / value pair for the iterator. The tree might
  67. have changed significantly after the last call. We need to cope
  68. with errors as best as we can.
  69. */
  70. func (it *HTreeIterator) nextItem() error {
  71. // Check if there are more items available to iterate
  72. if len(it.nodePath) == 0 {
  73. it.nextKey = nil
  74. it.nextValue = nil
  75. return ErrNoMoreItems
  76. }
  77. // Get the current path element
  78. loc := it.nodePath[len(it.nodePath)-1]
  79. index := it.indices[len(it.indices)-1]
  80. node, err := it.tree.Root.fetchNode(loc)
  81. if err != nil {
  82. if err == storage.ErrSlotNotFound {
  83. // Something is wrong - the tree must have changed since the last
  84. // nextItem call. Remove the path element and try again.
  85. it.nodePath = it.nodePath[:len(it.nodePath)-1]
  86. it.indices = it.indices[:len(it.indices)-1]
  87. return it.nextItem()
  88. }
  89. // If it is another error there is something more serious - report it
  90. return err
  91. }
  92. if node.Children != nil {
  93. // If the current path element is a page get the next child and delegate
  94. page := &htreePage{node}
  95. page.loc = loc
  96. page.sm = it.tree.Root.sm
  97. nextChild := it.searchNextChild(page, index)
  98. if nextChild != -1 {
  99. // If we found another element then update the current index and delegate to it
  100. it.indices[len(it.indices)-1] = nextChild
  101. it.nodePath = append(it.nodePath, page.Children[nextChild])
  102. it.indices = append(it.indices, -1)
  103. return it.nextItem()
  104. }
  105. // If we finished this page remove it from the stack and continue
  106. // with the parent
  107. it.nodePath = it.nodePath[:len(it.nodePath)-1]
  108. it.indices = it.indices[:len(it.indices)-1]
  109. return it.nextItem()
  110. }
  111. // If the current path element is a bucket just iterate the elements
  112. // delegate once it has finished
  113. bucket := &htreeBucket{node}
  114. bucket.loc = loc
  115. bucket.sm = it.tree.Root.sm
  116. nextElement := it.searchNextElement(bucket, index)
  117. if nextElement != -1 {
  118. // If we found another element then update the current index and return it
  119. it.indices[len(it.indices)-1] = nextElement
  120. it.nextKey = bucket.Keys[nextElement]
  121. it.nextValue = bucket.Values[nextElement]
  122. return nil
  123. }
  124. // If we finished this bucket remove it from the stack and continue
  125. // with the parent
  126. it.nodePath = it.nodePath[:len(it.nodePath)-1]
  127. it.indices = it.indices[:len(it.indices)-1]
  128. return it.nextItem()
  129. }
  130. /*
  131. searchNextChild searches for the index of the next available page child from a given index.
  132. */
  133. func (it *HTreeIterator) searchNextChild(page *htreePage, current int) int {
  134. for i := current + 1; i < MaxPageChildren; i++ {
  135. child := page.Children[i]
  136. if child != 0 {
  137. return i
  138. }
  139. }
  140. return -1
  141. }
  142. /*
  143. searchNextElement searches for the index of the next available bucket element from a given index.
  144. */
  145. func (it *HTreeIterator) searchNextElement(bucket *htreeBucket, current int) int {
  146. next := current + 1
  147. if next < int(bucket.BucketSize) {
  148. return next
  149. }
  150. return -1
  151. }
  152. /*
  153. Return a string representation of the iterator.
  154. */
  155. func (it *HTreeIterator) String() string {
  156. return fmt.Sprintf("HTree Iterator (tree: %v)\n path: %v\n indices: %v\n next: %v / %v\n",
  157. it.tree.Root.Location(), it.nodePath, it.indices, it.nextKey, it.nextValue)
  158. }