arbo/vt.go
vt.goRaw
1// Package arbo > vt.go implements the Virtual Tree, which computes a tree
2// without computing any hash. With the idea of once all the leafs are placed in
3// their positions, the hashes can be computed, avoiding computing a node hash
4// more than one time.
5package arbo
6
7import (
8 "bytes"
9 "encoding/hex"
10 "fmt"
11 "io"
12)
13
14type node struct {
15 l *node
16 r *node
17 k []byte
18 v []byte
19 path []bool
20 h []byte
21}
22
23type params struct {
24 maxLevels int
25 hashFunction HashFunction
26 emptyHash []byte
27}
28
29// vt stands for virtual tree. It's a tree that does not have any computed hash
30// while placing the leafs. Once all the leafs are placed, it computes all the
31// hashes. In this way, each node hash is only computed one time.
32type vt struct {
33 root *node
34 params *params
35}
36
37func newVT(maxLevels int, hash HashFunction) vt {
38 return vt{
39 root: nil,
40 params: ¶ms{
41 maxLevels: maxLevels,
42 hashFunction: hash,
43 emptyHash: make([]byte, hash.Len()), // empty
44 },
45 }
46}
47
48func (t *vt) add(k, v []byte) error {
49 leaf := newLeafNode(t.params, k, v)
50 if t.root == nil {
51 t.root = leaf
52 return nil
53 }
54
55 if err := t.root.add(t.params, 0, leaf); err != nil {
56 return err
57 }
58
59 return nil
60}
61
62// computeHashes should be called after all the vt.add is used, once all the
63// leafs are in the tree
64func (t *vt) computeHashes() ([][2][]byte, error) {
65 var pairs [][2][]byte
66 var err error
67 pairs, err = t.root.computeHashes(t.params, pairs)
68 if err != nil {
69 return pairs, err
70 }
71 return pairs, nil
72}
73
74func newLeafNode(p *params, k, v []byte) *node {
75 keyPath := make([]byte, p.hashFunction.Len())
76 copy(keyPath[:], k)
77 path := getPath(p.maxLevels, keyPath)
78 n := &node{
79 k: k,
80 v: v,
81 path: path,
82 }
83 return n
84}
85
86type virtualNodeType int
87
88const (
89 vtEmpty = 0 // for convenience uses same value that PrefixValueEmpty
90 vtLeaf = 1 // for convenience uses same value that PrefixValueLeaf
91 vtMid = 2 // for convenience uses same value that PrefixValueIntermediate
92)
93
94func (n *node) typ() virtualNodeType {
95 if n.l == nil && n.r == nil && n.k != nil {
96 return vtLeaf
97 }
98 if n.l != nil || n.r != nil {
99 return vtMid
100 }
101 return vtEmpty
102}
103
104func (n *node) add(p *params, currLvl int, leaf *node) error {
105 if currLvl > p.maxLevels-1 {
106 return fmt.Errorf("max virtual level %d", currLvl)
107 }
108
109 if n == nil {
110 // n = leaf // TMP!
111 return nil
112 }
113
114 t := n.typ()
115 switch t {
116 case vtMid:
117 if leaf.path[currLvl] {
118 //right
119 if n.r == nil {
120 // empty sub-node, add the leaf here
121 n.r = leaf
122 }
123 if err := n.r.add(p, currLvl+1, leaf); err != nil {
124 return err
125 }
126 } else {
127 if n.l == nil {
128 // empty sub-node, add the leaf here
129 n.l = leaf
130 }
131 if err := n.l.add(p, currLvl+1, leaf); err != nil {
132 return err
133 }
134 }
135 case vtLeaf:
136 if bytes.Equal(n.k, leaf.k) {
137 return fmt.Errorf("key already exists")
138 }
139
140 oldLeaf := &node{
141 k: n.k,
142 v: n.v,
143 path: n.path,
144 }
145 // remove values from current node (converting it to mid node)
146 n.k = nil
147 n.v = nil
148 n.path = nil
149 if err := n.downUntilDivergence(p, currLvl, oldLeaf, leaf); err != nil {
150 return err
151 }
152 default:
153 return fmt.Errorf("ERR")
154 }
155
156 return nil
157}
158
159func (n *node) downUntilDivergence(p *params, currLvl int, oldLeaf, newLeaf *node) error {
160 if currLvl > p.maxLevels-1 {
161 return fmt.Errorf("max virtual level %d", currLvl)
162 }
163
164 if oldLeaf.path[currLvl] != newLeaf.path[currLvl] {
165 // reached divergence in next level
166 if newLeaf.path[currLvl] {
167 n.l = oldLeaf
168 n.r = newLeaf
169 } else {
170 n.l = newLeaf
171 n.r = oldLeaf
172 }
173 return nil
174 }
175 // no divergence yet, continue going down
176 if newLeaf.path[currLvl] {
177 // right
178 n.r = &node{}
179 if err := n.r.downUntilDivergence(p, currLvl+1, oldLeaf, newLeaf); err != nil {
180 return err
181 }
182 } else {
183 // left
184 n.l = &node{}
185 if err := n.l.downUntilDivergence(p, currLvl+1, oldLeaf, newLeaf); err != nil {
186 return err
187 }
188 }
189
190 return nil
191}
192
193// returns an array of key-values to store in the db
194func (n *node) computeHashes(p *params, pairs [][2][]byte) ([][2][]byte, error) {
195 if pairs == nil {
196 pairs = [][2][]byte{}
197 }
198 var err error
199 t := n.typ()
200 switch t {
201 case vtLeaf:
202 leafKey, leafValue, err := newLeafValue(p.hashFunction, n.k, n.v)
203 if err != nil {
204 return pairs, err
205 }
206 n.h = leafKey
207 kv := [2][]byte{leafKey, leafValue}
208 pairs = append(pairs, kv)
209 case vtMid:
210 if n.l != nil {
211 pairs, err = n.l.computeHashes(p, pairs)
212 if err != nil {
213 return pairs, err
214 }
215 } else {
216 n.l = &node{
217 h: p.emptyHash,
218 }
219 }
220 if n.r != nil {
221 pairs, err = n.r.computeHashes(p, pairs)
222 if err != nil {
223 return pairs, err
224 }
225 } else {
226 n.r = &node{
227 h: p.emptyHash,
228 }
229 }
230 // once the sub nodes are computed, can compute the current node
231 // hash
232 k, v, err := newIntermediate(p.hashFunction, n.l.h, n.r.h)
233 if err != nil {
234 return nil, err
235 }
236 n.h = k
237 kv := [2][]byte{k, v}
238 pairs = append(pairs, kv)
239 default:
240 return nil, fmt.Errorf("ERR TMP") // TODO
241 }
242
243 return pairs, nil
244}
245
246//nolint:unused
247func (t *vt) graphviz(w io.Writer) error {
248 fmt.Fprintf(w, `digraph hierarchy {
249node [fontname=Monospace,fontsize=10,shape=box]
250`)
251 if _, err := t.root.graphviz(w, t.params, 0); err != nil {
252 return err
253 }
254 fmt.Fprintf(w, "}\n")
255 return nil
256}
257
258//nolint:unused
259func (n *node) graphviz(w io.Writer, p *params, nEmpties int) (int, error) {
260 nChars := 4 // TODO move to global constant
261 if n == nil {
262 return nEmpties, nil
263 }
264
265 t := n.typ()
266 switch t {
267 case vtLeaf:
268 leafKey, _, err := newLeafValue(p.hashFunction, n.k, n.v)
269 if err != nil {
270 return nEmpties, err
271 }
272 fmt.Fprintf(w, "\"%p\" [style=filled,label=\"%v\"];\n", n, hex.EncodeToString(leafKey[:nChars]))
273
274 fmt.Fprintf(w, "\"%p\" -> {\"k:%v\\nv:%v\"}\n", n,
275 hex.EncodeToString(n.k[:nChars]),
276 hex.EncodeToString(n.v[:nChars]))
277 fmt.Fprintf(w, "\"k:%v\\nv:%v\" [style=dashed]\n",
278 hex.EncodeToString(n.k[:nChars]),
279 hex.EncodeToString(n.v[:nChars]))
280 case vtMid:
281 fmt.Fprintf(w, "\"%p\" [label=\"\"];\n", n)
282
283 lStr := fmt.Sprintf("%p", n.l)
284 rStr := fmt.Sprintf("%p", n.r)
285 eStr := ""
286 if n.l == nil {
287 lStr = fmt.Sprintf("empty%v", nEmpties)
288 eStr += fmt.Sprintf("\"%v\" [style=dashed,label=0];\n",
289 lStr)
290 nEmpties++
291 }
292 if n.r == nil {
293 rStr = fmt.Sprintf("empty%v", nEmpties)
294 eStr += fmt.Sprintf("\"%v\" [style=dashed,label=0];\n",
295 rStr)
296 nEmpties++
297 }
298 fmt.Fprintf(w, "\"%p\" -> {\"%v\" \"%v\"}\n", n, lStr, rStr)
299 fmt.Fprint(w, eStr)
300 nEmpties, err := n.l.graphviz(w, p, nEmpties)
301 if err != nil {
302 return nEmpties, err
303 }
304 nEmpties, err = n.r.graphviz(w, p, nEmpties)
305 if err != nil {
306 return nEmpties, err
307 }
308
309 case vtEmpty:
310 default:
311 return nEmpties, fmt.Errorf("ERR")
312 }
313
314 return nEmpties, nil
315}
316
317//nolint:unused
318func (t *vt) printGraphviz() error {
319 w := bytes.NewBufferString("")
320 fmt.Fprintf(w,
321 "--------\nGraphviz:\n")
322 err := t.graphviz(w)
323 if err != nil {
324 fmt.Println(w)
325 return err
326 }
327 fmt.Fprintf(w,
328 "End of Graphviz --------\n")
329 fmt.Println(w)
330 return nil
331}