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