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