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