git ssb

1
const Graph = require('ipld-graph-builder')
2
const Buffer = require('safe-buffer').Buffer
3
const Uint1Array = require('uint1array')
4
const TextEncoder = require('text-encoding').TextEncoder
5
6
const encoder = new TextEncoder('utf-8')
7
8
const RadixTree = module.exports = class RadixTree {
9
  /**
10
   * @param opts
11
   * @param opts.root {object} a merkle root to a radix tree. If none, RadixTree will create an new root.
12
   * @param opts.graph {object} an instance of [ipld-graph-builder](https://github.com/ipld/js-ipld-graph-builder) alternitvly `opts.dag` can be used
13
   * @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.
14
   */
15
  constructor (opts) {
16
    this.root = opts.root || {'/': RadixTree.emptyTreeState}
17
    this.graph = opts.graph || new Graph(opts.dag)
18
  }
19
20
  /**
21
   * returns the state of an empty tree
22
   */
23
  static get emptyTreeState () {
24
    return [null, null]
25
  }
26
27
  /**
28
   * returns an Uint1Array constructir which is used to repersent keys
29
   * @returns {object}
30
   */
31
  static get ArrayConstructor () {
32
    return Uint1Array
33
  }
34
35
  /**
36
   * converts a TypedArray or Buffer to an Uint1Array
37
   * @param {TypedArray} array - the array to convert
38
   * @returns {TypedArray}
39
   */
40
  static toTypedArray (array) {
41
    return new RadixTree.ArrayConstructor(new Uint8Array(array).buffer)
42
  }
43
44
  async _get (key) {
45
    let index = 0
46
    let root = this.root
47
    let parent
48
49
    while (1) {
50
      // load the root
51
      const exNode = await this.graph.get(root, EXTENSION, true)
52
      if (exNode) {
53
        let subKey = key.subarray(index)
54
55
        // let extensionIndex = 0
56
        // const extension = getExtension(root)
57
        // const extensionLen = extension.length
58
        // // checks the extension against the key
59
        // while (extensionIndex < extensionLen && extension[extensionIndex] === subKey[extensionIndex]) {
60
        //   extensionIndex++
61
        // }
62
        const {extensionIndex, extensionLen, extension} = findMatchBits(subKey, root)
63
        index += extensionIndex
64
        // check if we compelete travered the extension
65
        if (extensionIndex !== extensionLen) {
66
          return {
67
            index: index,
68
            root: root,
69
            extension: extension,
70
            extensionIndex: extensionIndex
71
          }
72
        }
73
      }
74
75
      let keySegment = key[index]
76
      if (keySegment !== undefined) {
77
        const branch = getBranch(root)
78
        await this.graph.get(branch, keySegment, true)
79
        // preseves the '/'
80
        const nextRoot = branch[keySegment]
81
        if (!nextRoot) {
82
          return {
83
            root: root,
84
            index: index
85
          }
86
        } else {
87
          parent = root
88
          root = nextRoot
89
        }
90
      } else {
91
        break
92
      }
93
94
      index++
95
    }
96
97
    let value = getValue(root)
98
99
    if (value && value['/']) {
100
      value = await this.graph.get(root, VALUE, true)
101
    }
102
103
    return {
104
      value: value,
105
      root: root,
106
      parent: parent,
107
      index: index
108
    }
109
  }
110
111
  /**
112
   * gets a value given a key
113
   * @param {*} key
114
   * @return {Promise}
115
   */
116
  async get (key) {
117
    key = RadixTree.formatKey(key)
118
    const result = await this._get(key)
119
    return result.value
120
  }
121
122
  /**
123
   * stores a value at a given key
124
   * @param {*} key
125
   * @return {Promise}
126
   */
127
  async set (key, value) {
128
    key = RadixTree.formatKey(key)
129
130
    if (value.length > 32) {
131
      value = {'/': value}
132
    }
133
134
    if (isEmpty(this.root)) {
135
      this.root['/'] = createNode(key, [null, null], value)['/']
136
    } else {
137
      let {root, extensionIndex, extension, index, value: rValue} = await this._get(key)
138
139
      if (rValue) {
140
        setValue(root, value)
141
      } else {
142
        if (extensionIndex !== undefined) {
143
          // split the extension node in two
144
          const extensionKey = extension[extensionIndex]
145
          const remExtension = extension.subarray(extensionIndex + 1)
146
          extension = extension.subarray(0, extensionIndex)
147
148
          setExtension(root, remExtension)
149
          const branch = [null, null]
150
          branch[extensionKey] = {'/': root['/']}
151
          root['/'] = createNode(extension, branch)['/']
152
        }
153
154
        // if there are remaning key segments create an extension node
155
        if (index < key.length) {
156
          const keySegment = key[index]
157
          const extension = key.subarray(index + 1, key.length)
158
          const newNode = createNode(extension, [null, null], value)
159
          const rootBranch = getBranch(root)
160
          rootBranch[keySegment] = newNode
161
          setBranch(root, rootBranch)
162
        } else {
163
          setValue(root, value)
164
        }
165
      }
166
    }
167
  }
168
169
  /**
170
   * deletes a value at a given key
171
   * @param {*} key
172
   * @return {Promise}
173
   */
174
  async delete (key) {
175
    key = RadixTree.formatKey(key)
176
    const results = await this._get(key)
177
    if (results.value !== undefined) {
178
      const root = results.root
179
      const parent = results.parent
180
181
      deleteValue(root)
182
183
      const branch = getBranch(root)
184
      if (branch.some(el => el !== null)) {
185
        joinNodes(root)
186
      } else {
187
        if (!parent) {
188
          root['/'] = RadixTree.emptyTreeState
189
        } else {
190
          let branch = getBranch(parent)
191
          branch = branch.map(node => node === root ? null : node)
192
          setBranch(parent, branch)
193
          await this.graph.tree(parent, 2)
194
195
          joinNodes(parent)
196
        }
197
      }
198
    }
199
200
    function joinNodes (root) {
201
      if (getValue(root) === undefined) {
202
        let index
203
        const branch = getBranch(root)
204
        const nodes = branch.filter((node, i) => {
205
          if (node) {
206
            index = i
207
            return true
208
          }
209
        })
210
211
        if (nodes.length === 1) {
212
          const child = nodes[0]
213
          const pExtension = getExtension(root)
214
          const childExtension = getExtension(child)
215
          const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1)
216
217
          newExtension.set(pExtension)
218
          newExtension[pExtension.length] = index
219
          newExtension.set(childExtension, pExtension.length + 1)
220
221
          setExtension(child, newExtension)
222
          root['/'] = child['/']
223
        }
224
      }
225
    }
226
  }
227
228
  /**
229
   * creates a merkle root for the current tree and stores the data perstantly
230
   * @returns {Promise}
231
   */
232
  flush () {
233
    return this.graph.flush(this.root)
234
  }
235
236
  static formatKey (key) {
237
    if (typeof key === 'string') {
238
      key = encoder.encode(key)
239
    }
240
241
    if (key.constructor !== RadixTree.ArrayConstructor) {
242
      return new RadixTree.ArrayConstructor(key.buffer)
243
    } else {
244
      return key
245
    }
246
  }
247
}
248
249
function createNode (ex, branch, value) {
250
  const node = {
251
    '/': []
252
  }
253
254
  setValue(node, value)
255
  setExtension(node, ex)
256
  setBranch(node, branch)
257
258
  return node
259
}
260
261
// helper functions for nodes
262
const LBRANCH = 0
263
const RBRANCH = 1
264
const EXTENSION = 2
265
const VALUE = 3
266
267
function setBranch (node, branch) {
268
  node['/'][LBRANCH] = branch[0]
269
  node['/'][RBRANCH] = branch[1]
270
}
271
272
function getBranch (node) {
273
  return node['/'].slice(LBRANCH, 2)
274
}
275
276
function getValue (node) {
277
  return node['/'][VALUE]
278
}
279
280
function deleteValue (node) {
281
  node['/'].pop()
282
}
283
284
function getExtension (node) {
285
  if (node['/'][EXTENSION]) {
286
    const len = node['/'][EXTENSION][0]
287
    const extension = RadixTree.toTypedArray(node['/'][EXTENSION].subarray(1))
288
    return extension.subarray(0, extension.length - len)
289
  } else {
290
    return []
291
  }
292
}
293
294
function setExtension (node, ex) {
295
  if (ex && ex.length) {
296
    const paddingLen = ((8 - (ex.length % 8)) % 8)
297
    node['/'][EXTENSION] = Buffer.concat([Buffer.from([paddingLen]), Buffer.from(ex.buffer)])
298
  } else {
299
    if (getValue(node) === undefined && !Array.isArray(node['/'][EXTENSION])) {
300
      node['/'].pop()
301
    } else if (node['/'][EXTENSION] !== undefined) {
302
      node['/'][EXTENSION] = null
303
    }
304
  }
305
}
306
307
function setValue (node, val) {
308
  if (val !== undefined) {
309
    node['/'][VALUE] = val
310
  }
311
}
312
313
function isEmpty (node) {
314
  const branch = getBranch(node)
315
  return node['/'].length === 2 && branch[0] === null && branch[1] === null
316
}
317
318
function findMatchBits (key, node) {
319
  let extensionIndex = 0
320
  const extension = getExtension(node)
321
  const extensionLen = extension.length
322
323
  // checks the extension against the key
324
  while (extensionIndex < extensionLen && extension[extensionIndex] === key[extensionIndex]) {
325
    extensionIndex++
326
  }
327
328
  return {
329
    extensionIndex: extensionIndex,
330
    extensionLen: extensionLen,
331
    extension: extension
332
  }
333
}
334