git ssb

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