| 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317 | 1x
1x
1x
1x
1x
1x
6x
6x
8x
1473x
704x
330x
330x
330x
2024x
2024x
473x
473x
473x
473x
473x
50592x
473x
473x
106x
1918x
1918x
1695x
1695x
1695x
1695x
1x
1694x
1694x
223x
1694x
223x
223x
1x
223x
114x
114x
114x
115x
115x
1x
115x
6x
109x
109x
109x
1x
108x
106x
106x
106x
106x
106x
106x
106x
106x
108x
105x
105x
105x
105x
105x
105x
3x
107x
107x
107x
106x
106x
106x
106x
211x
2x
104x
3x
101x
202x
101x
101x
103x
102x
102x
204x
103x
103x
102x
101x
101x
101x
101x
101x
101x
101x
101x
101x
1x
336x
28x
336x
328x
8x
217x
217x
217x
217x
217x
1x
1x
1x
1x
423x
423x
2224x
410x
106x
781x
704x
704x
704x
77x
424x
340x
340x
84x
80x
4x
2x
221x
115x
115x
115x
| const Graph = require('ipld-graph-builder')
const Buffer = require('safe-buffer').Buffer
const Uint1Array = require('uint1array')
const TextEncoder = require('text-encoding').TextEncoder
const encoder = new TextEncoder('utf-8')
const RadixTree = module.exports = class RadixTree {
/**
* @param opts
* @param opts.root {object} a merkle root to a radix tree. If none, RadixTree will create an new root.
* @param opts.graph {object} an instance of [ipld-graph-builder](https://github.com/ipld/js-ipld-graph-builder) alternitvly `opts.dag` can be used
* @param opts.dag {object} an instance if [ipfs.dag](https://github.com/ipfs/js-ipfs#dag). If there is no `opts.graph` this will be used to create a new graph instance.
*/
constructor (opts) {
this.root = opts.root || {'/': RadixTree.emptyTreeState}
this.graph = opts.graph || new Graph(opts.dag)
}
/**
* returns the state of an empty tree
*/
static get emptyTreeState () {
return [null, null]
}
/**
* returns an Uint1Array constructir which is used to repersent keys
* @returns {object}
*/
static get ArrayConstructor () {
return Uint1Array
}
/**
* converts a TypedArray or Buffer to an Uint1Array
* @param {TypedArray} array - the array to convert
* @returns {TypedArray}
*/
static toTypedArray (array) {
return new RadixTree.ArrayConstructor(new Uint8Array(array).buffer)
}
async _get (key) {
let index = 0
let root = this.root
let parent
while (1) {
// load the root
const exNode = await this.graph.get(root, EXTENSION, true)
if (exNode) {
let extensionIndex = 0
const extension = getExtension(root)
const extensionLen = extension.length
let subKey
subKey = key.slice(index, index + extensionLen)
// checks the extension against the key
while (extensionIndex < extensionLen && extension[extensionIndex] === subKey[extensionIndex]) {
extensionIndex++
}
index += extensionIndex
// check if we compelete travered the extension
if (extensionIndex !== extensionLen) {
return {
extensionIndex: extensionIndex,
root: root,
index: index
}
}
}
let keySegment = key[index]
if (keySegment !== undefined) {
const branch = getBranch(root)
await this.graph.get(branch, keySegment, true)
// preseves the '/'
const nextRoot = branch[keySegment]
if (!nextRoot) {
return {
root: root,
index: index
}
} else {
parent = root
root = nextRoot
}
} else {
break
}
index++
}
let value = getValue(root)
if (value && value['/']) {
value = await this.graph.get(root, VALUE, true)
}
return {
value: value,
root: root,
parent: parent,
index: index
}
}
/**
* gets a value given a key
* @param {*} key
* @return {Promise}
*/
async get (key) {
key = RadixTree.formatKey(key)
const result = await this._get(key)
return result.value
}
/**
* stores a value at a given key
* @param {*} key
* @return {Promise}
*/
async set (key, value) {
key = RadixTree.formatKey(key)
if (value.length > 32) {
value = {'/': value}
}
if (isEmpty(this.root)) {
this.root['/'] = createNode(key, [null, null], value)['/']
} else {
const result = await this._get(key)
let root = result.root
if (result.value) {
setValue(root, value)
} else {
if (result.extensionIndex !== undefined) {
// split the extension node in two
let extension = getExtension(root)
const extensionKey = extension[result.extensionIndex]
const remExtension = extension.subarray(result.extensionIndex + 1)
extension = extension.subarray(0, result.extensionIndex)
setExtension(root, remExtension)
const branch = [null, null]
branch[extensionKey] = {'/': root['/']}
root['/'] = createNode(extension, branch)['/']
}
// if there are remaning key segments create an extension node
if (result.index < key.length) {
const keySegment = key[result.index]
const extension = key.subarray(result.index + 1, key.length)
const newNode = createNode(extension, [null, null], value)
const rootBranch = getBranch(root)
rootBranch[keySegment] = newNode
setBranch(root, rootBranch)
} else {
setValue(root, value)
}
}
}
}
/**
* deletes a value at a given key
* @param {*} key
* @return {Promise}
*/
async delete (key) {
key = RadixTree.formatKey(key)
const results = await this._get(key)
if (results.value !== undefined) {
const root = results.root
const parent = results.parent
deleteValue(root)
const branch = getBranch(root)
if (branch.some(el => el !== null)) {
joinNodes(root)
} else {
if (!parent) {
root['/'] = RadixTree.emptyTreeState
} else {
let branch = getBranch(parent)
branch = branch.map(node => node === root ? null : node)
setBranch(parent, branch)
joinNodes(parent)
}
}
}
function joinNodes (root) {
if (getValue(root) === undefined) {
let index
const branch = getBranch(root)
const nodes = branch.filter((node, i) => {
if (node) {
index = i
return true
}
})
if (nodes.length === 1) {
const child = nodes[0]
const pExtension = getExtension(root)
const childExtension = getExtension(child)
const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1)
newExtension.set(pExtension)
newExtension[pExtension.length] = index
newExtension.set(childExtension, pExtension.length + 1)
setExtension(child, newExtension)
root['/'] = child['/']
}
}
}
}
/**
* creates a merkle root for the current tree and stores the data perstantly
* @returns {Promise}
*/
flush () {
return this.graph.flush(this.root)
}
static formatKey (key) {
if (typeof key === 'string') {
key = encoder.encode(key)
}
if (key.constructor !== RadixTree.ArrayConstructor) {
return new RadixTree.ArrayConstructor(key.buffer)
} else {
return key
}
}
}
function createNode (ex, branch, value) {
const node = {
'/': []
}
setValue(node, value)
setExtension(node, ex)
setBranch(node, branch)
return node
}
// helper functions for nodes
const LBRANCH = 0
const RBRANCH = 1
const EXTENSION = 2
const VALUE = 3
function setBranch (node, branch) {
node['/'][LBRANCH] = branch[0]
node['/'][RBRANCH] = branch[1]
}
function getBranch (node) {
return node['/'].slice(LBRANCH, 2)
}
function getValue (node) {
return node['/'][VALUE]
}
function deleteValue (node) {
node['/'].pop()
}
function getExtension (node) {
if (node['/'][EXTENSION]) {
const len = node['/'][EXTENSION][0]
const extension = RadixTree.toTypedArray(node['/'][EXTENSION].subarray(1))
return extension.subarray(0, extension.length - len)
} else {
return []
}
}
function setExtension (node, ex) {
if (ex && ex.length) {
const paddingLen = ((8 - (ex.length % 8)) % 8)
node['/'][EXTENSION] = Buffer.concat([Buffer.from([paddingLen]), Buffer.from(ex.buffer)])
} else {
if (getValue(node) === undefined && !Array.isArray(node['/'][EXTENSION])) {
node['/'].pop()
} else if (node['/'][EXTENSION] !== undefined) {
node['/'][EXTENSION] = null
}
}
}
function setValue (node, val) {
if (val !== undefined) {
node['/'][VALUE] = val
}
}
function isEmpty (node) {
const branch = getBranch(node)
return node['/'].length === 2 && branch[0] === null && branch[1] === null
}
|