arbo/addbatch.go
addbatch.goRaw
1package arbo
2
3import (
4 "bytes"
5 "fmt"
6 "sort"
7)
8
9/*
10
11
12AddBatch design
13===============
14
15
16CASE A: Empty Tree --> if tree is empty (root==0)
17=================================================
18- Build the full tree from bottom to top (from all the leaf to the root)
19
20
21CASE B: ALMOST CASE A, Almost empty Tree --> if Tree has numLeafs < numBuckets
22==============================================================================
23- Get the Leafs (key & value) (iterate the tree from the current root getting
24the leafs)
25- Create a new empty Tree
26- Do CASE A for the new Tree, giving the already existing key&values (leafs)
27from the original Tree + the new key&values to be added from the AddBatch call
28
29 R
30 / \
31 A *
32 / \
33 B C
34
35
36CASE C: ALMOST CASE B --> if Tree has few Leafs (but numLeafs>=numBuckets)
37==============================================================================
38- Use A, B, G, F as Roots of subtrees
39- Do CASE B for each subtree
40- Then go from L to the Root
41
42 R
43 / \
44 / \
45 / \
46 * *
47 / | / \
48 / | / \
49 / | / \
50L: A B G D
51 / \
52 / \
53 / \
54 C *
55 / \
56 / \
57 / \
58 D E
59
60
61
62CASE D: Already populated Tree
63==============================
64- Use A, B, C, D as subtree
65- Sort the Keys in Buckets that share the initial part of the path
66- For each subtree add there the new leafs
67
68 R
69 / \
70 / \
71 / \
72 * *
73 / | / \
74 / | / \
75 / | / \
76L: A B C D
77 /\ /\ / \ / \
78 ... ... ... ... ... ...
79
80
81CASE E: Already populated Tree Unbalanced
82=========================================
83- Need to fill M1 and M2, and then will be able to use CASE D
84 - Search for M1 & M2 in the inputed Keys
85 - Add M1 & M2 to the Tree
86 - From here can use CASE D
87
88 R
89 / \
90 / \
91 / \
92 * *
93 | \
94 | \
95 | \
96L: M1 * M2 * (where M1 and M2 are empty)
97 / | /
98 / | /
99 / | /
100 A * *
101 / \ | \
102 / \ | \
103 / \ | \
104 B * * C
105 / \ |\
106 ... ... | \
107 | \
108 D E
109
110
111
112Algorithm decision
113==================
114- if nLeafs==0 (root==0): CASE A
115- if nLeafs<nBuckets: CASE B
116- if nLeafs>=nBuckets && nLeafs < minLeafsThreshold: CASE C
117- else: CASE D & CASE E
118
119
120- Multiple tree.Add calls: O(n log n)
121 - Used in: cases A, B, C
122- Tree from bottom to top: O(log n)
123 - Used in: cases D, E
124
125*/
126
127// AddBatchOpt is the WIP implementation of the AddBatch method in a more
128// optimized approach.
129func (t *Tree) AddBatchOpt(keys, values [][]byte) ([]int, error) {
130 t.updateAccessTime()
131 t.Lock()
132 defer t.Unlock()
133
134 // TODO if len(keys) is not a power of 2, add padding of empty
135 // keys&values. Maybe when len(keyvalues) is not a power of 2, cut at
136 // the biggest power of 2 under the len(keys), add those 2**n key-values
137 // using the AddBatch approach, and then add the remaining key-values
138 // using tree.Add.
139
140 kvs, err := t.keysValuesToKvs(keys, values)
141 if err != nil {
142 return nil, err
143 }
144
145 t.tx, err = t.db.NewTx()
146 if err != nil {
147 return nil, err
148 }
149
150 // if nLeafs==0 (root==0): CASE A
151 e := make([]byte, t.hashFunction.Len())
152 if bytes.Equal(t.root, e) {
153 // CASE A
154 // sort keys & values by path
155 sortKvs(kvs)
156 return t.buildTreeBottomUp(kvs)
157 }
158
159 return nil, fmt.Errorf("UNIMPLEMENTED")
160}
161
162type kv struct {
163 pos int // original position in the array
164 keyPath []byte
165 k []byte
166 v []byte
167}
168
169// compareBytes compares byte slices where the bytes are compared from left to
170// right and each byte is compared by bit from right to left
171func compareBytes(a, b []byte) bool {
172 // WIP
173 for i := 0; i < len(a); i++ {
174 for j := 0; j < 8; j++ {
175 aBit := a[i] & (1 << j)
176 bBit := b[i] & (1 << j)
177 if aBit > bBit {
178 return false
179 } else if aBit < bBit {
180 return true
181 }
182 }
183 }
184 return false
185}
186
187// sortKvs sorts the kv by path
188func sortKvs(kvs []kv) {
189 sort.Slice(kvs, func(i, j int) bool {
190 return compareBytes(kvs[i].keyPath, kvs[j].keyPath)
191 })
192}
193
194func (t *Tree) keysValuesToKvs(ks, vs [][]byte) ([]kv, error) {
195 if len(ks) != len(vs) {
196 return nil, fmt.Errorf("len(keys)!=len(values) (%d!=%d)",
197 len(ks), len(vs))
198 }
199 kvs := make([]kv, len(ks))
200 for i := 0; i < len(ks); i++ {
201 keyPath := make([]byte, t.hashFunction.Len())
202 copy(keyPath[:], ks[i])
203 kvs[i].pos = i
204 kvs[i].keyPath = ks[i]
205 kvs[i].k = ks[i]
206 kvs[i].v = vs[i]
207 }
208
209 return kvs, nil
210}
211
212// keys & values must be sorted by path, and must be length multiple of 2
213// TODO return index of failed keyvaules
214func (t *Tree) buildTreeBottomUp(kvs []kv) ([]int, error) {
215 // build the leafs
216 leafKeys := make([][]byte, len(kvs))
217 for i := 0; i < len(kvs); i++ {
218 // TODO handle the case where Key&Value == 0
219 leafKey, leafValue, err := newLeafValue(t.hashFunction, kvs[i].k, kvs[i].v)
220 if err != nil {
221 return nil, err
222 }
223 // store leafKey & leafValue to db
224 if err := t.tx.Put(leafKey, leafValue); err != nil {
225 return nil, err
226 }
227 leafKeys[i] = leafKey
228 }
229 r, err := t.upFromKeys(leafKeys)
230 if err != nil {
231 return nil, err
232 }
233 t.root = r
234 return nil, nil
235}
236
237func (t *Tree) upFromKeys(ks [][]byte) ([]byte, error) {
238 if len(ks) == 1 {
239 return ks[0], nil
240 }
241
242 var rKs [][]byte
243 for i := 0; i < len(ks); i += 2 {
244 // TODO handle the case where Key&Value == 0
245 k, v, err := newIntermediate(t.hashFunction, ks[i], ks[i+1])
246 if err != nil {
247 return nil, err
248 }
249 // store k-v to db
250 if err = t.tx.Put(k, v); err != nil {
251 return nil, err
252 }
253 rKs = append(rKs, k)
254 }
255 return t.upFromKeys(rKs)
256}