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 LBRANCH = 0
9
const RBRANCH = 1
10
const EXTENSION = 2
11
const VALUE = 3
12
13
const RadixTree = module.exports = class RadixTree {
14
  /**
15
   * @param opts
16
   * @param opts.root {object} a merkle root to a radix tree. If none, RadixTree will create an new root.
17
   * @param opts.graph {object} an instance of [ipld-graph-builder](https://github.com/ipld/js-ipld-graph-builder) alternitvly `opts.dag` can be used
18
   * @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.
19
   */
20
  constructor (opts) {
21
    this.root = opts.root || {'/': undefined}
22
    this.graph = opts.graph || new Graph(opts.dag)
23
  }
24
25
  /**
26
   * returns an Uint1Array constructir which is used to repersent keys
27
   * @returns {object}
28
   */
29
  static get ArrayConstructor () {
30
    return Uint1Array
31
  }
32
33
  /**
34
   * converts a TypedArray or Buffer to an Uint1Array
35
   * @param {TypedArray} array - the array to convert
36
   * @returns {TypedArray}
37
   */
38
  static toTypedArray (array) {
39
    return new RadixTree.ArrayConstructor(new Uint8Array(array).buffer)
40
  }
41
42
  async _get (key) {
43
    let index = 0
44
    let root = this.root
45
    let parent
46
    while (1) {
47
      // load the root
48
      const exNode = await this.graph.get(root, EXTENSION, true)
49
      if (exNode) {
50
        let extensionIndex = 0
51
        const extensionLen = getExLength(root)
52
        const extension = getExtension(root)
53
        let subKey
54
        subKey = key.slice(index, index + extensionLen)
55
56
        // checks the extension against the key
57
        while (extensionIndex < extensionLen && extension[extensionIndex] === subKey[extensionIndex]) {
58
          extensionIndex++
59
        }
60
        index += extensionIndex
61
        // check if we compelete travered the extension
62
        if (extensionIndex !== extensionLen) {
63
          return {
64
            extensionIndex: extensionIndex,
65
            root: root,
66
            index: index
67
          }
68
        }
69
      }
70
71
      let keySegment = key[index]
72
      if (keySegment !== undefined) {
73
        const branch = 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 = getValue(root)
94
95
    if (value && value['/']) {
96
      value = await this.graph.get(root, 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 (value.length > 32) {
127
      value = {'/': value}
128
    }
129
130
    // initial set
131
    if (this.root['/'] === undefined) {
132
      this.root['/'] = createNode(key, [], value)['/']
133
    } else {
134
      const result = await this._get(key)
135
      let root = result.root
136
137
      if (result.value) {
138
        setValue(root, value)
139
      } else {
140
        if (result.extensionIndex !== undefined) {
141
          // split the extension node in two
142
          let extension = getExtension(root)
143
          const extensionKey = extension[result.extensionIndex]
144
          const remExtension = extension.subarray(result.extensionIndex + 1)
145
          extension = extension.subarray(0, result.extensionIndex)
146
147
          setExtension(root, remExtension)
148
          const branch = []
149
          branch[extensionKey] = {'/': root['/']}
150
          root['/'] = createNode(extension, branch)['/']
151
        }
152
153
        // if there are remaning key segments create an extension node
154
        if (result.index < key.length) {
155
          const keySegment = key[result.index]
156
          const extension = key.subarray(result.index + 1, key.length)
157
          const newNode = createNode(extension, [], value)
158
          const rootBranch = getBranch(root)
159
          rootBranch[keySegment] = newNode
160
          setBranch(root, rootBranch)
161
        } else {
162
          setValue(root, value)
163
        }
164
      }
165
    }
166
  }
167
168
  /**
169
   * deletes a value at a given key
170
   * @param {*} key
171
   * @return {Promise}
172
   */
173
  async delete (key) {
174
    key = RadixTree.formatKey(key)
175
    const results = await this._get(key)
176
    if (results.value !== undefined) {
177
      const root = results.root
178
      const parent = results.parent
179
180
      deleteValue(root)
181
182
      const branch = getBranch(root)
183
      if (branch.some(el => el !== undefined)) {
184
        joinNodes(root)
185
      } else {
186
        if (!parent) {
187
          root['/'] = undefined
188
        } else {
189
          let branch = getBranch(parent)
190
          branch = branch.map(node => node === root ? undefined : node)
191
          setBranch(parent, branch)
192
193
          joinNodes(parent)
194
        }
195
      }
196
    }
197
198
    function joinNodes (root) {
199
      if (getValue(root) === undefined) {
200
        let index
201
        const branch = getBranch(root)
202
        const nodes = branch.filter((node, i) => {
203
          if (node) {
204
            index = i
205
            return true
206
          }
207
        })
208
209
        if (nodes.length === 1) {
210
          const child = nodes[0]
211
          const pExtension = getExtension(root)
212
          const childExtension = getExtension(child)
213
          const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1)
214
215
          newExtension.set(pExtension)
216
          newExtension[pExtension.length] = index
217
          newExtension.set(childExtension, pExtension.length + 1)
218
219
          setExtension(child, newExtension)
220
          root['/'] = child['/']
221
        }
222
      }
223
    }
224
  }
225
226
  /**
227
   * creates a merkle root for the current tree and stores the data perstantly
228
   * @returns {Promise}
229
   */
230
  flush () {
231
    return this.graph.flush(this.root)
232
  }
233
234
  static formatKey (key) {
235
    if (typeof key === 'string') {
236
      key = encoder.encode(key)
237
    }
238
239
    if (key.constructor !== RadixTree.ArrayConstructor) {
240
      return new RadixTree.ArrayConstructor(key.buffer)
241
    } else {
242
      return key
243
    }
244
  }
245
}
246
247
function createNode (ex, branch, value) {
248
  const node = {
249
    '/': []
250
  }
251
252
  setValue(node, value)
253
  setExtension(node, ex)
254
  setBranch(node, branch)
255
256
  return node
257
}
258
259
// helper functions for nodes
260
function setBranch (node, branch) {
261
  node['/'][LBRANCH] = branch[0]
262
  node['/'][RBRANCH] = branch[1]
263
}
264
265
function getBranch (node) {
266
  return node['/'].slice(LBRANCH, 2)
267
}
268
269
function getValue (node) {
270
  return node['/'][VALUE]
271
}
272
273
function deleteValue (node) {
274
  node['/'].pop()
275
}
276
277
function getExtension (node) {
278
  if (node['/'][EXTENSION]) {
279
    return RadixTree.toTypedArray(node['/'][EXTENSION][1]).subarray(0, getExLength(node))
280
  } else {
281
    return []
282
  }
283
}
284
285
function getExLength (node) {
286
  return node['/'][EXTENSION][0]
287
}
288
289
function setExtension (node, ex) {
290
  if (ex && ex.length) {
291
    node['/'][EXTENSION] = [ex.length, Buffer.from(ex.buffer)]
292
  } else {
293
    if (getValue(node) === undefined && node['/'][EXTENSION] !== undefined) {
294
      node['/'].pop()
295
    } else if (node['/'][EXTENSION] !== undefined) {
296
      node['/'][EXTENSION] = undefined
297
    }
298
  }
299
}
300
301
function setValue (node, val) {
302
  if (val !== undefined) {
303
    node['/'][VALUE] = val
304
  }
305
}
306