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
        const {extensionIndex, extensionLen, extension} = findMatchBits(subKey, root)
52
        index += extensionIndex
53
        // check if we compelete travered the extension
54
        if (extensionIndex !== extensionLen) {
55
          return {
56
            index: index,
57
            root: root,
58
            extension: extension,
59
            extensionIndex: extensionIndex
60
          }
61
        }
62
      }
63
64
      let keySegment = key[index]
65
      if (keySegment !== undefined) {
66
        const branch = treeNode.getBranch(root)
67
        await this.graph.get(branch, keySegment, true)
68
        // preseves the '/'
69
        const nextRoot = branch[keySegment]
70
        if (!nextRoot) {
71
          return {
72
            root: root,
73
            index: index
74
          }
75
        } else {
76
          parent = root
77
          root = nextRoot
78
        }
79
      } else {
80
        break
81
      }
82
83
      index++
84
    }
85
86
    const value = treeNode.getValue(root)
87
88
    return {
89
      value: value,
90
      root: root,
91
      parent: parent,
92
      index: index
93
    }
94
  }
95
96
  /**
97
   * gets a value given a key
98
   * @param {*} key
99
   * @return {Promise}
100
   */
101
  async get (key) {
102
    key = RadixTree.formatKey(key)
103
    const result = await this._get(key)
104
    return result.value
105
  }
106
107
  /**
108
   * stores a value at a given key
109
   * @param {*} key
110
   * @return {Promise}
111
   */
112
  async set (key, value) {
113
    key = RadixTree.formatKey(key)
114
115
    if (treeNode.isEmpty(this.root)) {
116
      this.root['/'] = createNode(key, [null, null], value)['/']
117
    } else {
118
      let {root, extensionIndex, extension, index, value: rValue} = await this._get(key)
119
120
      if (rValue) {
121
        treeNode.setValue(root, value)
122
      } else {
123
        if (extensionIndex !== undefined) {
124
          // split the extension node in two
125
          const extensionKey = extension[extensionIndex]
126
          const remExtension = extension.subarray(extensionIndex + 1)
127
          extension = extension.subarray(0, extensionIndex)
128
129
          treeNode.setExtension(root, remExtension)
130
          const branch = [null, null]
131
          branch[extensionKey] = {'/': root['/']}
132
          root['/'] = createNode(extension, branch)['/']
133
        }
134
135
        // if there are remaning key segments create an extension node
136
        if (index < key.length) {
137
          const keySegment = key[index]
138
          const extension = key.subarray(index + 1, key.length)
139
          const newNode = createNode(extension, [null, null], value)
140
          const rootBranch = treeNode.getBranch(root)
141
          rootBranch[keySegment] = newNode
142
          treeNode.setBranch(root, rootBranch)
143
        } else {
144
          treeNode.setValue(root, value)
145
        }
146
      }
147
    }
148
  }
149
150
  /**
151
   * deletes a value at a given key
152
   * @param {*} key
153
   * @return {Promise}
154
   */
155
  async delete (key) {
156
    key = RadixTree.formatKey(key)
157
    const results = await this._get(key)
158
    if (results.value !== undefined) {
159
      const root = results.root
160
      const parent = results.parent
161
162
      treeNode.deleteValue(root)
163
164
      const branch = treeNode.getBranch(root)
165
      if (branch.some(el => el !== null)) {
166
        joinNodes(root)
167
      } else {
168
        if (!parent) {
169
          root['/'] = RadixTree.emptyTreeState
170
        } else {
171
          let branch = treeNode.getBranch(parent)
172
          branch = branch.map(node => node === root ? null : node)
173
          treeNode.setBranch(parent, branch)
174
          await this.graph.tree(parent, 2)
175
176
          joinNodes(parent)
177
        }
178
      }
179
    }
180
181
    function joinNodes (root) {
182
      if (treeNode.getValue(root) === undefined) {
183
        let index
184
        const branch = treeNode.getBranch(root)
185
        const nodes = branch.filter((node, i) => {
186
          if (node) {
187
            index = i
188
            return true
189
          }
190
        })
191
192
        if (nodes.length === 1) {
193
          const child = nodes[0]
194
          const pExtension = treeNode.getExtension(root)
195
          const childExtension = treeNode.getExtension(child)
196
          const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1)
197
198
          newExtension.set(pExtension)
199
          newExtension[pExtension.length] = index
200
          newExtension.set(childExtension, pExtension.length + 1)
201
202
          treeNode.setExtension(child, newExtension)
203
          root['/'] = child['/']
204
        }
205
      }
206
    }
207
  }
208
209
  /**
210
   * creates a merkle root for the current tree and stores the data perstantly
211
   * @returns {Promise}
212
   */
213
  flush () {
214
    return this.graph.flush(this.root)
215
  }
216
217
  static formatKey (key) {
218
    if (typeof key === 'string') {
219
      key = encoder.encode(key)
220
    }
221
222
    if (key.constructor !== RadixTree.ArrayConstructor) {
223
      return new RadixTree.ArrayConstructor(key.buffer)
224
    } else {
225
      return key
226
    }
227
  }
228
}
229
230
function createNode (ex, branch, value) {
231
  const node = {
232
    '/': []
233
  }
234
235
  treeNode.setValue(node, value)
236
  treeNode.setExtension(node, ex)
237
  treeNode.setBranch(node, branch)
238
239
  return node
240
}
241
242
function findMatchBits (key, node) {
243
  let extensionIndex = 0
244
  const extension = treeNode.getExtension(node)
245
  const extensionLen = extension.length
246
247
  // checks the extension against the key
248
  while (extensionIndex < extensionLen && extension[extensionIndex] === key[extensionIndex]) {
249
    extensionIndex++
250
  }
251
252
  return {
253
    extensionIndex: extensionIndex,
254
    extensionLen: extensionLen,
255
    extension: extension
256
  }
257
}
258