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 extensionIndex = 0
54
        const extension = getExtension(root)
55
        const extensionLen = extension.length
56
        let subKey
57
        subKey = key.slice(index, index + extensionLen)
58
59
        // checks the extension against the key
60
        while (extensionIndex < extensionLen && extension[extensionIndex] === subKey[extensionIndex]) {
61
          extensionIndex++
62
        }
63
        index += extensionIndex
64
        // check if we compelete travered the extension
65
        if (extensionIndex !== extensionLen) {
66
          return {
67
            extensionIndex: extensionIndex,
68
            root: root,
69
            index: index
70
          }
71
        }
72
      }
73
74
      let keySegment = key[index]
75
      if (keySegment !== undefined) {
76
        const branch = 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
    let value = getValue(root)
97
98
    if (value && value['/']) {
99
      value = await this.graph.get(root, VALUE, true)
100
    }
101
102
    return {
103
      value: value,
104
      root: root,
105
      parent: parent,
106
      index: index
107
    }
108
  }
109
110
  /**
111
   * gets a value given a key
112
   * @param {*} key
113
   * @return {Promise}
114
   */
115
  async get (key) {
116
    key = RadixTree.formatKey(key)
117
    const result = await this._get(key)
118
    return result.value
119
  }
120
121
  /**
122
   * stores a value at a given key
123
   * @param {*} key
124
   * @return {Promise}
125
   */
126
  async set (key, value) {
127
    key = RadixTree.formatKey(key)
128
129
    if (value.length > 32) {
130
      value = {'/': value}
131
    }
132
133
    if (isEmpty(this.root)) {
134
      this.root['/'] = createNode(key, [null, null], value)['/']
135
    } else {
136
      const result = await this._get(key)
137
      let root = result.root
138
139
      if (result.value) {
140
        setValue(root, value)
141
      } else {
142
        if (result.extensionIndex !== undefined) {
143
          // split the extension node in two
144
          let extension = getExtension(root)
145
          const extensionKey = extension[result.extensionIndex]
146
          const remExtension = extension.subarray(result.extensionIndex + 1)
147
          extension = extension.subarray(0, result.extensionIndex)
148
149
          setExtension(root, remExtension)
150
          const branch = [null, null]
151
          branch[extensionKey] = {'/': root['/']}
152
          root['/'] = createNode(extension, branch)['/']
153
        }
154
155
        // if there are remaning key segments create an extension node
156
        if (result.index < key.length) {
157
          const keySegment = key[result.index]
158
          const extension = key.subarray(result.index + 1, key.length)
159
          const newNode = createNode(extension, [null, null], value)
160
          const rootBranch = getBranch(root)
161
          rootBranch[keySegment] = newNode
162
          setBranch(root, rootBranch)
163
        } else {
164
          setValue(root, value)
165
        }
166
      }
167
    }
168
  }
169
170
  /**
171
   * deletes a value at a given key
172
   * @param {*} key
173
   * @return {Promise}
174
   */
175
  async delete (key) {
176
    key = RadixTree.formatKey(key)
177
    const results = await this._get(key)
178
    if (results.value !== undefined) {
179
      const root = results.root
180
      const parent = results.parent
181
182
      deleteValue(root)
183
184
      const branch = getBranch(root)
185
      if (branch.some(el => el !== null)) {
186
        joinNodes(root)
187
      } else {
188
        if (!parent) {
189
          root['/'] = RadixTree.emptyTreeState
190
        } else {
191
          let branch = getBranch(parent)
192
          branch = branch.map(node => node === root ? null : node)
193
          setBranch(parent, branch)
194
          await this.graph.tree(parent, 2)
195
196
          joinNodes(parent)
197
        }
198
      }
199
    }
200
201
    function joinNodes (root) {
202
      if (getValue(root) === undefined) {
203
        let index
204
        const branch = getBranch(root)
205
        const nodes = branch.filter((node, i) => {
206
          if (node) {
207
            index = i
208
            return true
209
          }
210
        })
211
212
        if (nodes.length === 1) {
213
          const child = nodes[0]
214
          const pExtension = getExtension(root)
215
          const childExtension = getExtension(child)
216
          const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1)
217
218
          newExtension.set(pExtension)
219
          newExtension[pExtension.length] = index
220
          newExtension.set(childExtension, pExtension.length + 1)
221
222
          setExtension(child, newExtension)
223
          root['/'] = child['/']
224
        }
225
      }
226
    }
227
  }
228
229
  /**
230
   * creates a merkle root for the current tree and stores the data perstantly
231
   * @returns {Promise}
232
   */
233
  flush () {
234
    return this.graph.flush(this.root)
235
  }
236
237
  static formatKey (key) {
238
    if (typeof key === 'string') {
239
      key = encoder.encode(key)
240
    }
241
242
    if (key.constructor !== RadixTree.ArrayConstructor) {
243
      return new RadixTree.ArrayConstructor(key.buffer)
244
    } else {
245
      return key
246
    }
247
  }
248
}
249
250
function createNode (ex, branch, value) {
251
  const node = {
252
    '/': []
253
  }
254
255
  setValue(node, value)
256
  setExtension(node, ex)
257
  setBranch(node, branch)
258
259
  return node
260
}
261
262
// helper functions for nodes
263
const LBRANCH = 0
264
const RBRANCH = 1
265
const EXTENSION = 2
266
const VALUE = 3
267
268
function setBranch (node, branch) {
269
  node['/'][LBRANCH] = branch[0]
270
  node['/'][RBRANCH] = branch[1]
271
}
272
273
function getBranch (node) {
274
  return node['/'].slice(LBRANCH, 2)
275
}
276
277
function getValue (node) {
278
  return node['/'][VALUE]
279
}
280
281
function deleteValue (node) {
282
  node['/'].pop()
283
}
284
285
function getExtension (node) {
286
  if (node['/'][EXTENSION]) {
287
    const len = node['/'][EXTENSION][0]
288
    const extension = RadixTree.toTypedArray(node['/'][EXTENSION].subarray(1))
289
    return extension.subarray(0, extension.length - len)
290
  } else {
291
    return []
292
  }
293
}
294
295
function setExtension (node, ex) {
296
  if (ex && ex.length) {
297
    const paddingLen = ((8 - (ex.length % 8)) % 8)
298
    node['/'][EXTENSION] = Buffer.concat([Buffer.from([paddingLen]), Buffer.from(ex.buffer)])
299
  } else {
300
    if (getValue(node) === undefined && !Array.isArray(node['/'][EXTENSION])) {
301
      node['/'].pop()
302
    } else if (node['/'][EXTENSION] !== undefined) {
303
      node['/'][EXTENSION] = null
304
    }
305
  }
306
}
307
308
function setValue (node, val) {
309
  if (val !== undefined) {
310
    node['/'][VALUE] = val
311
  }
312
}
313
314
function isEmpty (node) {
315
  const branch = getBranch(node)
316
  return node['/'].length === 2 && branch[0] === null && branch[1] === null
317
}
318