git ssb

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