git ssb

1
const Graph = require('ipld-graph-builder')
2
const Uint1Array = require('uint1array')
3
const TextEncoder = require('text-encoding').TextEncoder
4
const DAG = require('./dag.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.graph {object} an instance of [ipld-graph-builder](https://github.com/ipld/js-ipld-graph-builder) alternitvly `opts.dag` can be used
14
   * @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.
15
   */
16
  constructor (opts) {
17
    this.root = opts.root || {
18
      '/': RadixTree.emptyTreeState
19
    }
20
21
    this.dag = opts.dag || new DAG(opts.db)
22
    this.graph = opts.graph || new Graph(this.dag)
23
  }
24
25
  /**
26
   * returns the state of an empty tree
27
   */
28
  static get emptyTreeState () {
29
    return [null, null, null]
30
  }
31
32
  /**
33
   * returns an Uint1Array constructir which is used to repersent keys
34
   * @returns {object}
35
   */
36
  static get ArrayConstructor () {
37
    return Uint1Array
38
  }
39
40
  async _get (key) {
41
    let index = 0
42
    let root = this.root
43
    let parent
44
45
    while (1) {
46
      // load the root
47
      const exNode = await this.graph.get(root, treeNode.EXTENSION, true)
48
      if (exNode) {
49
        let subKey = key.subarray(index)
50
51
        // let extensionIndex = 0
52
        // const extension = getExtension(root)
53
        // const extensionLen = extension.length
54
        // // checks the extension against the key
55
        // while (extensionIndex < extensionLen && extension[extensionIndex] === subKey[extensionIndex]) {
56
        //   extensionIndex++
57
        // }
58
        const {extensionIndex, extensionLen, extension} = findMatchBits(subKey, root)
59
        index += extensionIndex
60
        // check if we compelete travered the extension
61
        if (extensionIndex !== extensionLen) {
62
          return {
63
            index: index,
64
            root: root,
65
            extension: extension,
66
            extensionIndex: extensionIndex
67
          }
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 {
79
            root: root,
80
            index: index
81
          }
82
        } else {
83
          parent = root
84
          root = nextRoot
85
        }
86
      } else {
87
        break
88
      }
89
90
      index++
91
    }
92
93
    let value = treeNode.getValue(root)
94
95
    if (value && value['/']) {
96
      value = await this.graph.get(root, treeNode.VALUE, true)
97
    }
98
99
    return {
100
      value: value,
101
      root: root,
102
      parent: parent,
103
      index: index
104
    }
105
  }
106
107
  /**
108
   * gets a value given a key
109
   * @param {*} key
110
   * @return {Promise}
111
   */
112
  async get (key) {
113
    key = RadixTree.formatKey(key)
114
    const result = await this._get(key)
115
    return result.value
116
  }
117
118
  /**
119
   * stores a value at a given key
120
   * @param {*} key
121
   * @return {Promise}
122
   */
123
  async set (key, value) {
124
    key = RadixTree.formatKey(key)
125
126
    if (treeNode.isEmpty(this.root)) {
127
      this.root['/'] = createNode(key, [null, null], value)['/']
128
    } else {
129
      let {root, extensionIndex, extension, index, value: rValue} = await this._get(key)
130
131
      if (rValue) {
132
        treeNode.setValue(root, value)
133
      } else {
134
        if (extensionIndex !== undefined) {
135
          // split the extension node in two
136
          const extensionKey = extension[extensionIndex]
137
          const remExtension = extension.subarray(extensionIndex + 1)
138
          extension = extension.subarray(0, extensionIndex)
139
140
          treeNode.setExtension(root, remExtension)
141
          const branch = [null, null]
142
          branch[extensionKey] = {'/': root['/']}
143
          root['/'] = createNode(extension, branch)['/']
144
        }
145
146
        // if there are remaning key segments create an extension node
147
        if (index < key.length) {
148
          const keySegment = key[index]
149
          const extension = key.subarray(index + 1, key.length)
150
          const newNode = createNode(extension, [null, null], value)
151
          const rootBranch = treeNode.getBranch(root)
152
          rootBranch[keySegment] = newNode
153
          treeNode.setBranch(root, rootBranch)
154
        } else {
155
          treeNode.setValue(root, value)
156
        }
157
      }
158
    }
159
  }
160
161
  /**
162
   * deletes a value at a given key
163
   * @param {*} key
164
   * @return {Promise}
165
   */
166
  async delete (key) {
167
    key = RadixTree.formatKey(key)
168
    const results = await this._get(key)
169
    if (results.value !== undefined) {
170
      const root = results.root
171
      const parent = results.parent
172
173
      treeNode.deleteValue(root)
174
175
      const branch = treeNode.getBranch(root)
176
      if (branch.some(el => el !== null)) {
177
        joinNodes(root)
178
      } else {
179
        if (!parent) {
180
          root['/'] = RadixTree.emptyTreeState
181
        } else {
182
          let branch = treeNode.getBranch(parent)
183
          branch = branch.map(node => node === root ? null : node)
184
          treeNode.setBranch(parent, branch)
185
          await this.graph.tree(parent, 2)
186
187
          joinNodes(parent)
188
        }
189
      }
190
    }
191
192
    function joinNodes (root) {
193
      if (treeNode.getValue(root) === undefined) {
194
        let index
195
        const branch = treeNode.getBranch(root)
196
        const nodes = branch.filter((node, i) => {
197
          if (node) {
198
            index = i
199
            return true
200
          }
201
        })
202
203
        if (nodes.length === 1) {
204
          const child = nodes[0]
205
          const pExtension = treeNode.getExtension(root)
206
          const childExtension = treeNode.getExtension(child)
207
          const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1)
208
209
          newExtension.set(pExtension)
210
          newExtension[pExtension.length] = index
211
          newExtension.set(childExtension, pExtension.length + 1)
212
213
          treeNode.setExtension(child, newExtension)
214
          root['/'] = child['/']
215
        }
216
      }
217
    }
218
  }
219
220
  /**
221
   * creates a merkle root for the current tree and stores the data perstantly
222
   * @returns {Promise}
223
   */
224
  flush () {
225
    return this.graph.flush(this.root)
226
  }
227
228
  static formatKey (key) {
229
    if (typeof key === 'string') {
230
      key = encoder.encode(key)
231
    }
232
233
    if (key.constructor !== RadixTree.ArrayConstructor) {
234
      return new RadixTree.ArrayConstructor(key.buffer)
235
    } else {
236
      return key
237
    }
238
  }
239
}
240
241
function createNode (ex, branch, value) {
242
  const node = {
243
    '/': []
244
  }
245
246
  treeNode.setValue(node, value)
247
  treeNode.setExtension(node, ex)
248
  treeNode.setBranch(node, branch)
249
250
  return node
251
}
252
253
function findMatchBits (key, node) {
254
  let extensionIndex = 0
255
  const extension = treeNode.getExtension(node)
256
  const extensionLen = extension.length
257
258
  // checks the extension against the key
259
  while (extensionIndex < extensionLen && extension[extensionIndex] === key[extensionIndex]) {
260
    extensionIndex++
261
  }
262
263
  return {
264
    extensionIndex: extensionIndex,
265
    extensionLen: extensionLen,
266
    extension: extension
267
  }
268
}
269