-
Notifications
You must be signed in to change notification settings - Fork 4
/
traverse.go
123 lines (115 loc) · 2.59 KB
/
traverse.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package flexbuffers
import (
"errors"
"sort"
"unsafe"
)
var (
ErrNotFound = errors.New("no element")
)
// Traverser provides optimized document traversing. Use Raw.Lookup if there is no special reason.
type Traverser struct {
buf Raw
offset int
typ Type
byteWidth int
parentWidth int
}
func (t *Traverser) digMap(key string) error {
mapOffset, err := t.buf.Indirect(t.offset, uint8(t.parentWidth))
if err != nil {
return err
}
keyBytes := *(*[]byte)(unsafe.Pointer(&key))
keysVectorInd := mapOffset - t.byteWidth*3
keysByteWidth64, err := t.buf.ReadUInt64(keysVectorInd+t.byteWidth, uint8(t.byteWidth))
if err != nil {
return err
}
keysByteWidth := int(keysByteWidth64)
keysOffset, err := t.buf.Indirect(keysVectorInd, uint8(t.byteWidth))
if err != nil {
return err
}
keysLen64, err := t.buf.ReadUInt64(keysOffset-keysByteWidth, uint8(keysByteWidth))
if err != nil {
return err
}
keysLen := int(keysLen64)
var searchErr error
foundIdx := sort.Search(keysLen, func(i int) bool {
ind, err := t.buf.Indirect(keysOffset+i*keysByteWidth, uint8(keysByteWidth))
if err != nil {
searchErr = err
return true
}
for i, c := range keyBytes {
kc := t.buf[ind+i]
if kc == 0 {
return false // -1
} else if kc > c {
return true //1
} else if kc < c {
return false // -1
}
}
return true
})
if searchErr != nil {
return searchErr
}
if foundIdx < keysLen { // found
keyDataOffset, err := t.buf.Indirect(keysOffset+foundIdx*keysByteWidth, uint8(keysByteWidth))
if err != nil {
return err
}
exactEqual := true
for i, c := range keyBytes {
kc := t.buf[keyDataOffset+i]
if kc == 0 || kc != c {
exactEqual = false
break
}
}
if exactEqual {
valuePackedType := t.buf[mapOffset+keysLen*t.byteWidth+foundIdx]
valueOffset := mapOffset + foundIdx*t.byteWidth
// proceed
t.parentWidth = t.byteWidth
t.offset = valueOffset
t.typ = Type(valuePackedType >> 2)
t.byteWidth = 1 << (valuePackedType & 3)
} else {
t.offset = -1
t.typ = FBTNull
}
} else {
t.offset = -1
t.typ = FBTNull
}
return nil
}
func (t *Traverser) Seek(path []string) error {
for _, p := range path {
if t.typ != FBTMap {
return ErrNotFound
}
if err := t.digMap(p); err != nil {
return err
}
}
return nil
}
func (t *Traverser) Current() (Reference, error) {
if t.offset == -1 {
return Reference{}, ErrNotFound
}
r := Reference{
data_: t.buf,
offset: t.offset,
parentWidth: uint8(t.parentWidth),
byteWidth: uint8(t.byteWidth),
type_: t.typ,
}
return r, r.CheckBoundary()
}