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