1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93
94. 94
95. 95
96. 96
97. 97
98. 98
99. 99
100. 100
101. 101
102. 102
103. 103
104. 104
105. 105
106. 106
107. 107
108. 108
109. 109
110. 110
111. 111
112. 112
113. 113
114. 114
115. 115
116. 116
117. 117
118. 118
119. 119
120. 120
121. 121
122. 122
123. 123
124. 124
125. 125
126. 126

//  Copyright (c) 2018 Couchbase, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// 		http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package zap

import (
	"bytes"

	"github.com/blevesearch/vellum"
)

// enumerator provides an ordered traversal of multiple vellum
// iterators.  Like JOIN of iterators, the enumerator produces a
// sequence of (key, iteratorIndex, value) tuples, sorted by key ASC,
// then iteratorIndex ASC, where the same key might be seen or
// repeated across multiple child iterators.
type enumerator struct {
	itrs   []vellum.Iterator
	currKs [][]byte
	currVs []uint64

	lowK    []byte
	lowIdxs []int
	lowCurr int
}

// newEnumerator returns a new enumerator over the vellum Iterators
func newEnumerator(itrs []vellum.Iterator) (*enumerator, error) {
	rv := &enumerator{
		itrs:    itrs,
		currKs:  make([][]byte, len(itrs)),
		currVs:  make([]uint64, len(itrs)),
		lowIdxs: make([]int, 0, len(itrs)),
	}
	for i, itr := range rv.itrs {
		rv.currKs[i], rv.currVs[i] = itr.Current()
	}
	rv.updateMatches(false)
	if rv.lowK == nil && len(rv.lowIdxs) == 0 {
		return rv, vellum.ErrIteratorDone
	}
	return rv, nil
}

// updateMatches maintains the low key matches based on the currKs
func (m *enumerator) updateMatches(skipEmptyKey bool) {
	m.lowK = nil
	m.lowIdxs = m.lowIdxs[:0]
	m.lowCurr = 0

	for i, key := range m.currKs {
		if (key == nil && m.currVs[i] == 0) || // in case of empty iterator
			(len(key) == 0 && skipEmptyKey) { // skip empty keys
			continue
		}

		cmp := bytes.Compare(key, m.lowK)
		if cmp < 0 || len(m.lowIdxs) == 0 {
			// reached a new low
			m.lowK = key
			m.lowIdxs = m.lowIdxs[:0]
			m.lowIdxs = append(m.lowIdxs, i)
		} else if cmp == 0 {
			m.lowIdxs = append(m.lowIdxs, i)
		}
	}
}

// Current returns the enumerator's current key, iterator-index, and
// value.  If the enumerator is not pointing at a valid value (because
// Next returned an error previously), Current will return nil,0,0.
func (m *enumerator) Current() ([]byte, int, uint64) {
	var i int
	var v uint64
	if m.lowCurr < len(m.lowIdxs) {
		i = m.lowIdxs[m.lowCurr]
		v = m.currVs[i]
	}
	return m.lowK, i, v
}

// Next advances the enumerator to the next key/iterator/value result,
// else vellum.ErrIteratorDone is returned.
func (m *enumerator) Next() error {
	m.lowCurr += 1
	if m.lowCurr >= len(m.lowIdxs) {
		// move all the current low iterators forwards
		for _, vi := range m.lowIdxs {
			err := m.itrs[vi].Next()
			if err != nil && err != vellum.ErrIteratorDone {
				return err
			}
			m.currKs[vi], m.currVs[vi] = m.itrs[vi].Current()
		}
		// can skip any empty keys encountered at this point
		m.updateMatches(true)
	}
	if m.lowK == nil && len(m.lowIdxs) == 0 {
		return vellum.ErrIteratorDone
	}
	return nil
}

// Close all the underlying Iterators.  The first error, if any, will
// be returned.
func (m *enumerator) Close() error {
	var rv error
	for _, itr := range m.itrs {
		err := itr.Close()
		if rv == nil {
			rv = err
		}
	}
	return rv
}