git ssb

0+

wanderer🌟 / js-dfinity-radix-tree



Tree: e2cd325fdcc6c86a830407f0c4c8638f3a5ad25a

Files: e2cd325fdcc6c86a830407f0c4c8638f3a5ad25a / index.js

7922 bytesRaw
1const Graph = require('ipld-graph-builder')
2const Uint1Array = require('uint1array')
3const TextEncoder = require('text-encoding').TextEncoder
4const DataStore = require('./datastore.js')
5const treeNode = require('./treeNode.js')
6
7const encoder = new TextEncoder('utf-8')
8
9module.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
270function 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
282function 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