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
  }
25
26
  /**
27
   * returns the state of an empty tree
28
   */
29
  static get emptyTreeState () {
30
    return [null, null, null]
31
  }
32
33
  /**
34
   * returns an Uint1Array constructir which is used to repersent keys
35
   * @returns {object}
36
   */
37
  static get ArrayConstructor () {
38
    return Uint1Array
39
  }
40
41
  /**
42
   * returns a merkle link for some given data
43
   * @param {Buffer} data - the data which you would like to hash
44
   * @returns {Buffer}
45
   */
46
  static getMerkleLink (data) {
47
    return DataStore.getMerkleLink(data)
48
  }
49
50
  async _get (key) {
51
    let index = 0
52
    let root = this.root
53
    let parent
54
55
    while (1) {
56
      // load the root
57
      const exNode = await this.graph.get(root, treeNode.EXTENSION, true)
58
      if (exNode) {
59
        let subKey = key.subarray(index)
60
61
        const {extensionIndex, extensionLen, extension} = findMatchBits(subKey, root)
62
        index += extensionIndex
63
        // check if we compelete travered the extension
64
        if (extensionIndex !== extensionLen) {
65
          return {
66
            index: index,
67
            root: root,
68
            extension: extension,
69
            extensionIndex: extensionIndex
70
          }
71
        }
72
      }
73
74
      let keySegment = key[index]
75
      if (keySegment !== undefined) {
76
        const branch = treeNode.getBranch(root)
77
        await this.graph.get(branch, keySegment, true)
78
        // preseves the '/'
79
        const nextRoot = branch[keySegment]
80
        if (!nextRoot) {
81
          return {
82
            root: root,
83
            index: index
84
          }
85
        } else {
86
          parent = root
87
          root = nextRoot
88
        }
89
      } else {
90
        break
91
      }
92
93
      index++
94
    }
95
96
    const value = treeNode.getValue(root)
97
98
    return {
99
      value: value,
100
      root: root,
101
      parent: parent,
102
      index: index
103
    }
104
  }
105
106
  /**
107
   * gets a value given a key
108
   * @param {*} key
109
   * @return {Promise}
110
   */
111
  async get (key) {
112
    key = RadixTree.formatKey(key)
113
    const result = await this._get(key)
114
    return result.value
115
  }
116
117
  /**
118
   * stores a value at a given key
119
   * @param {*} key
120
   * @return {Promise}
121
   */
122
  async set (key, value) {
123
    key = RadixTree.formatKey(key)
124
125
    if (treeNode.isEmpty(this.root)) {
126
      this.root['/'] = createNode(key, [null, null], value)['/']
127
    } else {
128
      let {root, extensionIndex, extension, index, value: rValue} = await this._get(key)
129
130
      if (rValue) {
131
        treeNode.setValue(root, value)
132
      } else {
133
        if (extensionIndex !== undefined) {
134
          // split the extension node in two
135
          const extensionKey = extension[extensionIndex]
136
          const remExtension = extension.subarray(extensionIndex + 1)
137
          extension = extension.subarray(0, extensionIndex)
138
139
          treeNode.setExtension(root, remExtension)
140
          const branch = [null, null]
141
          branch[extensionKey] = {'/': root['/']}
142
          root['/'] = createNode(extension, branch)['/']
143
        }
144
145
        // if there are remaning key segments create an extension node
146
        if (index < key.length) {
147
          const keySegment = key[index]
148
          const extension = key.subarray(index + 1, key.length)
149
          const newNode = createNode(extension, [null, null], value)
150
          const rootBranch = treeNode.getBranch(root)
151
          rootBranch[keySegment] = newNode
152
          treeNode.setBranch(root, rootBranch)
153
        } else {
154
          treeNode.setValue(root, value)
155
        }
156
      }
157
    }
158
  }
159
160
  /**
161
   * deletes a value at a given key
162
   * @param {*} key
163
   * @return {Promise}
164
   */
165
  async delete (key) {
166
    key = RadixTree.formatKey(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
   * creates a merkle root for the current tree and stores the data perstantly
221
   * @returns {Promise}
222
   */
223
  flush () {
224
    return this.graph.flush(this.root)
225
  }
226
227
  static formatKey (key) {
228
    if (typeof key === 'string') {
229
      key = encoder.encode(key)
230
    }
231
232
    if (key.constructor !== RadixTree.ArrayConstructor) {
233
      return new RadixTree.ArrayConstructor(key.buffer)
234
    } else {
235
      return key
236
    }
237
  }
238
}
239
240
function createNode (ex, branch, value) {
241
  const node = {
242
    '/': []
243
  }
244
245
  treeNode.setValue(node, value)
246
  treeNode.setExtension(node, ex)
247
  treeNode.setBranch(node, branch)
248
249
  return node
250
}
251
252
function findMatchBits (key, node) {
253
  let extensionIndex = 0
254
  const extension = treeNode.getExtension(node)
255
  const extensionLen = extension.length
256
257
  // checks the extension against the key
258
  while (extensionIndex < extensionLen && extension[extensionIndex] === key[extensionIndex]) {
259
    extensionIndex++
260
  }
261
262
  return {
263
    extensionIndex: extensionIndex,
264
    extensionLen: extensionLen,
265
    extension: extension
266
  }
267
}
268