Files: 1d810cea4ca68ef589435c4e4c4d1a1f98a071f7 / index.js
7715 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 [undefined, undefined] |
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 | const result = await this._get(key) |
134 | let root = result.root |
135 | |
136 | if (result.value) { |
137 | setValue(root, value) |
138 | } else { |
139 | if (result.extensionIndex !== undefined) { |
140 | // split the extension node in two |
141 | let extension = getExtension(root) |
142 | const extensionKey = extension[result.extensionIndex] |
143 | const remExtension = extension.subarray(result.extensionIndex + 1) |
144 | extension = extension.subarray(0, result.extensionIndex) |
145 | |
146 | setExtension(root, remExtension) |
147 | const branch = [] |
148 | branch[extensionKey] = {'/': root['/']} |
149 | root['/'] = createNode(extension, branch)['/'] |
150 | } |
151 | |
152 | // if there are remaning key segments create an extension node |
153 | if (result.index < key.length) { |
154 | const keySegment = key[result.index] |
155 | const extension = key.subarray(result.index + 1, key.length) |
156 | const newNode = createNode(extension, [], value) |
157 | const rootBranch = getBranch(root) |
158 | rootBranch[keySegment] = newNode |
159 | setBranch(root, rootBranch) |
160 | } else { |
161 | setValue(root, value) |
162 | } |
163 | } |
164 | } |
165 | |
166 | /** |
167 | * deletes a value at a given key |
168 | * @param {*} key |
169 | * @return {Promise} |
170 | */ |
171 | async delete (key) { |
172 | key = RadixTree.formatKey(key) |
173 | const results = await this._get(key) |
174 | if (results.value !== undefined) { |
175 | const root = results.root |
176 | const parent = results.parent |
177 | |
178 | deleteValue(root) |
179 | |
180 | const branch = getBranch(root) |
181 | if (branch.some(el => el !== undefined)) { |
182 | joinNodes(root) |
183 | } else { |
184 | if (!parent) { |
185 | root['/'] = RadixTree.emptyTreeState |
186 | } else { |
187 | let branch = getBranch(parent) |
188 | branch = branch.map(node => node === root ? undefined : node) |
189 | setBranch(parent, branch) |
190 | |
191 | joinNodes(parent) |
192 | } |
193 | } |
194 | } |
195 | |
196 | function joinNodes (root) { |
197 | if (getValue(root) === undefined) { |
198 | let index |
199 | const branch = getBranch(root) |
200 | const nodes = branch.filter((node, i) => { |
201 | if (node) { |
202 | index = i |
203 | return true |
204 | } |
205 | }) |
206 | |
207 | if (nodes.length === 1) { |
208 | const child = nodes[0] |
209 | const pExtension = getExtension(root) |
210 | const childExtension = getExtension(child) |
211 | const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1) |
212 | |
213 | newExtension.set(pExtension) |
214 | newExtension[pExtension.length] = index |
215 | newExtension.set(childExtension, pExtension.length + 1) |
216 | |
217 | setExtension(child, newExtension) |
218 | root['/'] = child['/'] |
219 | } |
220 | } |
221 | } |
222 | } |
223 | |
224 | /** |
225 | * creates a merkle root for the current tree and stores the data perstantly |
226 | * @returns {Promise} |
227 | */ |
228 | flush () { |
229 | return this.graph.flush(this.root) |
230 | } |
231 | |
232 | static formatKey (key) { |
233 | if (typeof key === 'string') { |
234 | key = encoder.encode(key) |
235 | } |
236 | |
237 | if (key.constructor !== RadixTree.ArrayConstructor) { |
238 | return new RadixTree.ArrayConstructor(key.buffer) |
239 | } else { |
240 | return key |
241 | } |
242 | } |
243 | } |
244 | |
245 | function createNode (ex, branch, value) { |
246 | const node = { |
247 | '/': [] |
248 | } |
249 | |
250 | setValue(node, value) |
251 | setExtension(node, ex) |
252 | setBranch(node, branch) |
253 | |
254 | return node |
255 | } |
256 | |
257 | // helper functions for nodes |
258 | const LBRANCH = 0 |
259 | const RBRANCH = 1 |
260 | const EXTENSION = 2 |
261 | const VALUE = 3 |
262 | |
263 | function setBranch (node, branch) { |
264 | node['/'][LBRANCH] = branch[0] |
265 | node['/'][RBRANCH] = branch[1] |
266 | } |
267 | |
268 | function getBranch (node) { |
269 | return node['/'].slice(LBRANCH, 2) |
270 | } |
271 | |
272 | function getValue (node) { |
273 | return node['/'][VALUE] |
274 | } |
275 | |
276 | function deleteValue (node) { |
277 | node['/'].pop() |
278 | } |
279 | |
280 | function getExtension (node) { |
281 | if (node['/'][EXTENSION]) { |
282 | const len = node['/'][EXTENSION][0] |
283 | return RadixTree.toTypedArray(node['/'][EXTENSION][1]).subarray(0, len) |
284 | } else { |
285 | return [] |
286 | } |
287 | } |
288 | |
289 | function setExtension (node, ex) { |
290 | if (ex && ex.length) { |
291 | node['/'][EXTENSION] = [ex.length, Buffer.from(ex.buffer)] |
292 | } else { |
293 | if (getValue(node) === undefined && node['/'][EXTENSION] !== undefined) { |
294 | node['/'].pop() |
295 | } else if (node['/'][EXTENSION] !== undefined) { |
296 | node['/'][EXTENSION] = undefined |
297 | } |
298 | } |
299 | } |
300 | |
301 | function setValue (node, val) { |
302 | if (val !== undefined) { |
303 | node['/'][VALUE] = val |
304 | } |
305 | } |
306 |
Built with git-ssb-web