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(fromLvl int, 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, fromLvl, 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 return nil
123 }
124 if err := n.r.add(p, currLvl+1, leaf); err != nil {
125 return err
126 }
127 } else {
128 if n.l == nil {
129 // empty sub-node, add the leaf here
130 n.l = leaf
131 return nil
132 }
133 if err := n.l.add(p, currLvl+1, leaf); err != nil {
134 return err
135 }
136 }
137 case vtLeaf:
138 if bytes.Equal(n.k, leaf.k) {
139 return fmt.Errorf("key already exists. Existing node: %s, trying to add node: %s",
140 hex.EncodeToString(n.k), hex.EncodeToString(leaf.k))
141 }
142
143 oldLeaf := &node{
144 k: n.k,
145 v: n.v,
146 path: n.path,
147 }
148 // remove values from current node (converting it to mid node)
149 n.k = nil
150 n.v = nil
151 n.h = nil
152 n.path = nil
153 if err := n.downUntilDivergence(p, currLvl, oldLeaf, leaf); err != nil {
154 return err
155 }
156 case vtEmpty:
157 panic(fmt.Errorf("EMPTY %v", n)) // TODO TMP
158 default:
159 return fmt.Errorf("ERR")
160 }
161
162 return nil
163}
164
165func (n *node) downUntilDivergence(p *params, currLvl int, oldLeaf, newLeaf *node) error {
166 if currLvl > p.maxLevels-1 {
167 return fmt.Errorf("max virtual level %d", currLvl)
168 }
169
170 if oldLeaf.path[currLvl] != newLeaf.path[currLvl] {
171 // reached divergence in next level
172 if newLeaf.path[currLvl] {
173 n.l = oldLeaf
174 n.r = newLeaf
175 } else {
176 n.l = newLeaf
177 n.r = oldLeaf
178 }
179 return nil
180 }
181 // no divergence yet, continue going down
182 if newLeaf.path[currLvl] {
183 // right
184 n.r = &node{}
185 if err := n.r.downUntilDivergence(p, currLvl+1, oldLeaf, newLeaf); err != nil {
186 return err
187 }
188 } else {
189 // left
190 n.l = &node{}
191 if err := n.l.downUntilDivergence(p, currLvl+1, oldLeaf, newLeaf); err != nil {
192 return err
193 }
194 }
195
196 return nil
197}
198
199// returns an array of key-values to store in the db
200func (n *node) computeHashes(p *params, pairs [][2][]byte) ([][2][]byte, error) {
201 if pairs == nil {
202 pairs = [][2][]byte{}
203 }
204 var err error
205 t := n.typ()
206 switch t {
207 case vtLeaf:
208 leafKey, leafValue, err := newLeafValue(p.hashFunction, n.k, n.v)
209 if err != nil {
210 return pairs, err
211 }
212 n.h = leafKey
213 kv := [2][]byte{leafKey, leafValue}
214 pairs = append(pairs, kv)
215 case vtMid:
216 if n.l != nil {
217 pairs, err = n.l.computeHashes(p, pairs)
218 if err != nil {
219 return pairs, err
220 }
221 } else {
222 n.l = &node{
223 h: p.emptyHash,
224 }
225 }
226 if n.r != nil {
227 pairs, err = n.r.computeHashes(p, pairs)
228 if err != nil {
229 return pairs, err
230 }
231 } else {
232 n.r = &node{
233 h: p.emptyHash,
234 }
235 }
236 // once the sub nodes are computed, can compute the current node
237 // hash
238 k, v, err := newIntermediate(p.hashFunction, n.l.h, n.r.h)
239 if err != nil {
240 return nil, err
241 }
242 n.h = k
243 kv := [2][]byte{k, v}
244 pairs = append(pairs, kv)
245 default:
246 return nil, fmt.Errorf("ERR TMP") // TODO
247 }
248
249 return pairs, nil
250}
251
252//nolint:unused
253func (t *vt) graphviz(w io.Writer) error {
254 fmt.Fprintf(w, `digraph hierarchy {
255node [fontname=Monospace,fontsize=10,shape=box]
256`)
257 if _, err := t.root.graphviz(w, t.params, 0); err != nil {
258 return err
259 }
260 fmt.Fprintf(w, "}\n")
261 return nil
262}
263
264//nolint:unused
265func (n *node) graphviz(w io.Writer, p *params, nEmpties int) (int, error) {
266 nChars := 4 // TODO move to global constant
267 if n == nil {
268 return nEmpties, nil
269 }
270
271 t := n.typ()
272 switch t {
273 case vtLeaf:
274 leafKey, _, err := newLeafValue(p.hashFunction, n.k, n.v)
275 if err != nil {
276 return nEmpties, err
277 }
278 fmt.Fprintf(w, "\"%p\" [style=filled,label=\"%v\"];\n", n, hex.EncodeToString(leafKey[:nChars]))
279
280 fmt.Fprintf(w, "\"%p\" -> {\"k:%v\\nv:%v\"}\n", n,
281 hex.EncodeToString(n.k[:nChars]),
282 hex.EncodeToString(n.v[:nChars]))
283 fmt.Fprintf(w, "\"k:%v\\nv:%v\" [style=dashed]\n",
284 hex.EncodeToString(n.k[:nChars]),
285 hex.EncodeToString(n.v[:nChars]))
286 case vtMid:
287 fmt.Fprintf(w, "\"%p\" [label=\"\"];\n", n)
288
289 lStr := fmt.Sprintf("%p", n.l)
290 rStr := fmt.Sprintf("%p", n.r)
291 eStr := ""
292 if n.l == nil {
293 lStr = fmt.Sprintf("empty%v", nEmpties)
294 eStr += fmt.Sprintf("\"%v\" [style=dashed,label=0];\n",
295 lStr)
296 nEmpties++
297 }
298 if n.r == nil {
299 rStr = fmt.Sprintf("empty%v", nEmpties)
300 eStr += fmt.Sprintf("\"%v\" [style=dashed,label=0];\n",
301 rStr)
302 nEmpties++
303 }
304 fmt.Fprintf(w, "\"%p\" -> {\"%v\" \"%v\"}\n", n, lStr, rStr)
305 fmt.Fprint(w, eStr)
306 nEmpties, err := n.l.graphviz(w, p, nEmpties)
307 if err != nil {
308 return nEmpties, err
309 }
310 nEmpties, err = n.r.graphviz(w, p, nEmpties)
311 if err != nil {
312 return nEmpties, err
313 }
314
315 case vtEmpty:
316 default:
317 return nEmpties, fmt.Errorf("ERR")
318 }
319
320 return nEmpties, nil
321}
322
323//nolint:unused
324func (t *vt) printGraphviz() error {
325 w := bytes.NewBufferString("")
326 fmt.Fprintf(w,
327 "--------\nGraphviz:\n")
328 err := t.graphviz(w)
329 if err != nil {
330 fmt.Println(w)
331 return err
332 }
333 fmt.Fprintf(w,
334 "End of Graphviz --------\n")
335 fmt.Println(w)
336 return nil
337}