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
  }
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
    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 perstantly
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 constructir which is used to repersent 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