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