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.
5//nolint:unused,deadcode
6package arbo
7
8import (
9 "bytes"
10 "encoding/hex"
11 "fmt"
12 "io"
13)
14
15type node struct {
16 l *node
17 r *node
18 k []byte
19 v []byte
20 path []bool
21 // h []byte
22}
23
24type params struct {
25 maxLevels int
26 hashFunction HashFunction
27 emptyHash []byte
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.
33type vt struct {
34 root *node
35 params *params
36}
37
38func newVT(maxLevels int, hash HashFunction) vt {
39 return vt{
40 root: nil,
41 params: ¶ms{
42 maxLevels: maxLevels,
43 hashFunction: hash,
44 emptyHash: make([]byte, hash.Len()), // empty
45 },
46 }
47}
48
49func (t *vt) add(k, v []byte) error {
50 leaf := newLeafNode(t.params, k, v)
51 if t.root == nil {
52 t.root = leaf
53 return nil
54 }
55
56 if err := t.root.add(t.params, 0, leaf); err != nil {
57 return err
58 }
59
60 return nil
61}
62
63func newLeafNode(p *params, k, v []byte) *node {
64 keyPath := make([]byte, p.hashFunction.Len())
65 copy(keyPath[:], k)
66 path := getPath(p.maxLevels, keyPath)
67 n := &node{
68 k: k,
69 v: v,
70 path: path,
71 }
72 return n
73}
74
75type virtualNodeType int
76
77const (
78 vtEmpty = 0 // for convenience uses same value that PrefixValueEmpty
79 vtLeaf = 1 // for convenience uses same value that PrefixValueLeaf
80 vtMid = 2 // for convenience uses same value that PrefixValueIntermediate
81)
82
83func (n *node) typ() virtualNodeType {
84 if n.l == nil && n.r == nil && n.k != nil {
85 return vtLeaf
86 }
87 if n.l != nil || n.r != nil {
88 return vtMid
89 }
90 return vtEmpty
91}
92
93func (n *node) add(p *params, currLvl int, leaf *node) error {
94 if currLvl > p.maxLevels-1 {
95 return fmt.Errorf("max virtual level %d", currLvl)
96 }
97
98 if n == nil {
99 // n = leaf // TMP!
100 return nil
101 }
102
103 t := n.typ()
104 switch t {
105 case vtMid:
106 if leaf.path[currLvl] {
107 //right
108 if n.r == nil {
109 // empty sub-node, add the leaf here
110 n.r = leaf
111 }
112 if err := n.r.add(p, currLvl+1, leaf); err != nil {
113 return err
114 }
115 } else {
116 if n.l == nil {
117 // empty sub-node, add the leaf here
118 n.l = leaf
119 }
120 if err := n.l.add(p, currLvl+1, leaf); err != nil {
121 return err
122 }
123 }
124 case vtLeaf:
125 if bytes.Equal(n.k, leaf.k) {
126 return fmt.Errorf("key already exists")
127 }
128
129 oldLeaf := &node{
130 k: n.k,
131 v: n.v,
132 path: n.path,
133 }
134 // remove values from current node (converting it to mid node)
135 n.k = nil
136 n.v = nil
137 n.path = nil
138 if err := n.downUntilDivergence(p, currLvl, oldLeaf, leaf); err != nil {
139 return err
140 }
141 default:
142 return fmt.Errorf("ERR")
143 }
144
145 return nil
146}
147
148func (n *node) downUntilDivergence(p *params, currLvl int, oldLeaf, newLeaf *node) error {
149 if currLvl > p.maxLevels-1 {
150 return fmt.Errorf("max virtual level %d", currLvl)
151 }
152
153 // if oldLeaf.path[currLvl+1] != newLeaf.path[currLvl+1] {
154 if oldLeaf.path[currLvl] != newLeaf.path[currLvl] {
155 // reached divergence in next level
156 // if newLeaf.path[currLvl+1] {
157 if newLeaf.path[currLvl] {
158 n.l = oldLeaf
159 n.r = newLeaf
160 } else {
161 n.l = newLeaf
162 n.r = oldLeaf
163 }
164 return nil
165 }
166 // no divergence yet, continue going down
167 if newLeaf.path[currLvl] {
168 // right
169 n.r = &node{}
170 if err := n.r.downUntilDivergence(p, currLvl+1, oldLeaf, newLeaf); err != nil {
171 return err
172 }
173 } else {
174 // left
175 n.l = &node{}
176 if err := n.l.downUntilDivergence(p, currLvl+1, oldLeaf, newLeaf); err != nil {
177 return err
178 }
179 }
180
181 return nil
182}
183
184func (n *node) computeHashes() ([]kv, error) {
185 return nil, nil
186}
187
188func (t *vt) graphviz(w io.Writer) error {
189 fmt.Fprintf(w, `digraph hierarchy {
190node [fontname=Monospace,fontsize=10,shape=box]
191`)
192 if _, err := t.root.graphviz(w, t.params, 0); err != nil {
193 return err
194 }
195 fmt.Fprintf(w, "}\n")
196 return nil
197}
198
199func (n *node) graphviz(w io.Writer, p *params, nEmpties int) (int, error) {
200 nChars := 4 // TODO move to global constant
201 if n == nil {
202 return nEmpties, nil
203 }
204
205 t := n.typ()
206 switch t {
207 case vtLeaf:
208 leafKey, _, err := newLeafValue(p.hashFunction, n.k, n.v)
209 if err != nil {
210 return nEmpties, err
211 }
212 fmt.Fprintf(w, "\"%p\" [style=filled,label=\"%v\"];\n", n, hex.EncodeToString(leafKey[:nChars]))
213
214 fmt.Fprintf(w, "\"%p\" -> {\"k:%v\\nv:%v\"}\n", n,
215 hex.EncodeToString(n.k[:nChars]),
216 hex.EncodeToString(n.v[:nChars]))
217 fmt.Fprintf(w, "\"k:%v\\nv:%v\" [style=dashed]\n",
218 hex.EncodeToString(n.k[:nChars]),
219 hex.EncodeToString(n.v[:nChars]))
220 case vtMid:
221 fmt.Fprintf(w, "\"%p\" [label=\"\"];\n", n)
222
223 lStr := fmt.Sprintf("%p", n.l)
224 rStr := fmt.Sprintf("%p", n.r)
225 eStr := ""
226 if n.l == nil {
227 lStr = fmt.Sprintf("empty%v", nEmpties)
228 eStr += fmt.Sprintf("\"%v\" [style=dashed,label=0];\n",
229 lStr)
230 nEmpties++
231 }
232 if n.r == nil {
233 rStr = fmt.Sprintf("empty%v", nEmpties)
234 eStr += fmt.Sprintf("\"%v\" [style=dashed,label=0];\n",
235 rStr)
236 nEmpties++
237 }
238 fmt.Fprintf(w, "\"%p\" -> {\"%v\" \"%v\"}\n", n, lStr, rStr)
239 fmt.Fprint(w, eStr)
240 nEmpties, err := n.l.graphviz(w, p, nEmpties)
241 if err != nil {
242 return nEmpties, err
243 }
244 nEmpties, err = n.r.graphviz(w, p, nEmpties)
245 if err != nil {
246 return nEmpties, err
247 }
248
249 case vtEmpty:
250 default:
251 return nEmpties, fmt.Errorf("ERR")
252 }
253
254 return nEmpties, nil
255}
256
257func (t *vt) printGraphviz() error {
258 w := bytes.NewBufferString("")
259 fmt.Fprintf(w,
260 "--------\nGraphviz:\n")
261 err := t.graphviz(w)
262 if err != nil {
263 fmt.Println(w)
264 return err
265 }
266 fmt.Fprintf(w,
267 "End of Graphviz --------\n")
268 fmt.Println(w)
269 return nil
270}