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