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