Files: 343203ced157299bd2c071287e5c9945a760fe45 / index.js
7878 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 alternitly `opts.graph` can be used |
14 | * @param opts.graph {object} an instance of [ipld-graph-builder](https://github.com/ipld/js-ipld-graph-builder) alternitvly `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 compelete travered 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 | // preseves 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 | |
78 | return {value, root, parent, index} |
79 | } |
80 | |
81 | /** |
82 | * stores a value at a given key |
83 | * @param {*} key |
84 | * @return {Promise} |
85 | */ |
86 | set (key, value) { |
87 | key = this.formatKey(key) |
88 | return this._mutationLock(this._set.bind(this, key, value)) |
89 | } |
90 | |
91 | async _set (key, value) { |
92 | if (treeNode.isEmpty(this.root)) { |
93 | this.root['/'] = createNode(key, [null, null], value)['/'] |
94 | } else { |
95 | let {root, extensionIndex, extension, index, value: rValue} = await this._get(key) |
96 | |
97 | if (rValue) { |
98 | treeNode.setValue(root, value) |
99 | } else { |
100 | if (extensionIndex !== undefined) { |
101 | // split the extension node in two |
102 | const extensionKey = extension[extensionIndex] |
103 | const remExtension = extension.subarray(extensionIndex + 1) |
104 | extension = extension.subarray(0, extensionIndex) |
105 | |
106 | treeNode.setExtension(root, remExtension) |
107 | const branch = [null, null] |
108 | branch[extensionKey] = { |
109 | '/': root['/'] |
110 | } |
111 | root['/'] = createNode(extension, branch)['/'] |
112 | } |
113 | |
114 | // if there are remaning key segments create an extension node |
115 | if (index < key.length) { |
116 | const keySegment = key[index] |
117 | const extension = key.subarray(index + 1, key.length) |
118 | const newNode = createNode(extension, [null, null], value) |
119 | const rootBranch = treeNode.getBranch(root) |
120 | rootBranch[keySegment] = newNode |
121 | treeNode.setBranch(root, rootBranch) |
122 | } else { |
123 | treeNode.setValue(root, value) |
124 | } |
125 | } |
126 | } |
127 | } |
128 | |
129 | /** |
130 | * deletes a value at a given key |
131 | * @param {*} key |
132 | * @return {Promise} |
133 | */ |
134 | delete (key) { |
135 | key = this.formatKey(key) |
136 | return this._mutationLock(this._delete.bind(this, key)) |
137 | } |
138 | |
139 | async _delete (key) { |
140 | const results = await this._get(key) |
141 | if (results.value !== undefined) { |
142 | const root = results.root |
143 | const parent = results.parent |
144 | |
145 | treeNode.deleteValue(root) |
146 | |
147 | const branch = treeNode.getBranch(root) |
148 | if (branch.some(el => el !== null)) { |
149 | joinNodes(root) |
150 | } else { |
151 | if (!parent) { |
152 | root['/'] = RadixTree.emptyTreeState |
153 | } else { |
154 | let branch = treeNode.getBranch(parent) |
155 | branch = branch.map(node => node === root ? null : node) |
156 | treeNode.setBranch(parent, branch) |
157 | await this.graph.tree(parent, 2) |
158 | |
159 | joinNodes(parent) |
160 | } |
161 | } |
162 | } |
163 | |
164 | function joinNodes (root) { |
165 | if (treeNode.getValue(root) === undefined) { |
166 | let index |
167 | const branch = treeNode.getBranch(root) |
168 | const nodes = branch.filter((node, i) => { |
169 | if (node) { |
170 | index = i |
171 | return true |
172 | } |
173 | }) |
174 | |
175 | if (nodes.length === 1) { |
176 | const child = nodes[0] |
177 | const pExtension = treeNode.getExtension(root) |
178 | const childExtension = treeNode.getExtension(child) |
179 | const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1) |
180 | |
181 | newExtension.set(pExtension) |
182 | newExtension[pExtension.length] = index |
183 | newExtension.set(childExtension, pExtension.length + 1) |
184 | |
185 | treeNode.setExtension(child, newExtension) |
186 | root['/'] = child['/'] |
187 | } |
188 | } |
189 | } |
190 | } |
191 | |
192 | /** |
193 | * returns a promise that resolve when the tree is done with all of its writes |
194 | * @returns {Promise} |
195 | */ |
196 | async done () { |
197 | let setting |
198 | while (this._setting !== setting) { |
199 | setting = this._setting |
200 | await setting |
201 | } |
202 | } |
203 | |
204 | _mutationLock (func) { |
205 | const setting = this._setting |
206 | this._setting = new Promise((resolve, reject) => { |
207 | return setting.then(() => { |
208 | return func().then(resolve).catch(reject) |
209 | }) |
210 | }) |
211 | return this._setting |
212 | } |
213 | |
214 | /** |
215 | * creates a merkle root for the current tree and stores the data perstantly |
216 | * @returns {Promise} |
217 | */ |
218 | async flush () { |
219 | await this.done() |
220 | return this.graph.flush(this.root) |
221 | } |
222 | |
223 | formatKey (key) { |
224 | key = RadixTree.formatKey(key) |
225 | return key |
226 | } |
227 | |
228 | static formatKey (key) { |
229 | if (typeof key === 'string') { |
230 | key = encoder.encode(key) |
231 | } |
232 | |
233 | if (key.constructor !== RadixTree.ArrayConstructor) { |
234 | if (Buffer.isBuffer(key)) { |
235 | return new RadixTree.ArrayConstructor(new Uint8Array(key).buffer) |
236 | } else { |
237 | return new RadixTree.ArrayConstructor(key.buffer) |
238 | } |
239 | } else { |
240 | return key |
241 | } |
242 | } |
243 | |
244 | /** |
245 | * returns the state of an empty tree |
246 | */ |
247 | static get emptyTreeState () { |
248 | return [null, null, null] |
249 | } |
250 | |
251 | /** |
252 | * returns an Uint1Array constructir which is used to repersent keys |
253 | * @returns {object} |
254 | */ |
255 | static get ArrayConstructor () { |
256 | return Uint1Array |
257 | } |
258 | |
259 | /** |
260 | * returns a merkle link for some given data |
261 | * @param {Buffer} data - the data which you would like to hash |
262 | * @returns {Buffer} |
263 | */ |
264 | static getMerkleLink (data) { |
265 | return DataStore.getMerkleLink(data) |
266 | } |
267 | } |
268 | |
269 | function createNode (ex, branch, value) { |
270 | const node = { |
271 | '/': [] |
272 | } |
273 | |
274 | treeNode.setValue(node, value) |
275 | treeNode.setExtension(node, ex) |
276 | treeNode.setBranch(node, branch) |
277 | |
278 | return node |
279 | } |
280 | |
281 | function findMatchBits (key, node) { |
282 | let extensionIndex = 0 |
283 | const extension = treeNode.getExtension(node) |
284 | const extensionLen = extension.length |
285 | |
286 | // checks the extension against the key |
287 | while (extensionIndex < extensionLen && extension[extensionIndex] === key[extensionIndex]) { |
288 | extensionIndex++ |
289 | } |
290 | |
291 | return {extensionIndex, extensionLen, extension} |
292 | } |
293 |
Built with git-ssb-web