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
module.exports = class RadixTree {
8
  constructor (opts) {
9
    this.root = opts.root || {'/': null}
10
    this.dag = opts.dag
11
    this.radix = opts.radix || 2
12
    this.graph = new Graph(this.dag)
13
  }
14
15
  get ArrayConstructor () {
16
    switch (this.radix) {
17
      case 2:
18
        return Uint1Array
19
      case 8:
20
        return Uint8Array
21
      case 16:
22
        return Uint16Array
23
      case 32:
24
        return Uint32Array
25
    }
26
  }
27
28
  toTypedArray (array) {
29
    return new this.ArrayConstructor(new Uint8Array(array).buffer)
30
  }
31
32
  async _get (key) {
33
    let index = 0
34
    let root = this.root
35
    let extensionIndex = 0
36
    while (key.length > index) {
37
      extensionIndex = 0
38
      let nextRoot
39
40
      if (root['/'].extension) {
41
        const extension = this.toTypedArray(root['/'].extension)
42
        let subKey
43
        let subKeyLen
44
        if (this.radix === 2) {
45
          subKey = key.slice(index, index + extension.length)
46
          subKeyLen = subKey.length
47
          subKey = new this.ArrayConstructor(subKey.buffer)
48
          subKeyLen = subKey.length - subKeyLen
49
        } else {
50
          subKey = key.subarray(index, extension.length)
51
        }
52
        while (extensionIndex < extension.length && extension[extensionIndex] === subKey[extensionIndex]) {
53
          extensionIndex++
54
        }
55
        index += extensionIndex - subKeyLen
56
        if (extensionIndex !== extension.length) {
57
          return {
58
            extensionIndex: extensionIndex,
59
            root: root,
60
            index: index
61
          }
62
        }
63
64
        let keySegment = key[index]
65
        if (Array.isArray(root['/'].node) && keySegment) {
66
          await this.graph.get(root['/'].node, keySegment)
67
          nextRoot = root['/'].node[keySegment]
68
          if (!nextRoot) {
69
            return {
70
              root: root,
71
              index: index
72
            }
73
          }
74
          root = nextRoot
75
        }
76
      } else {
77
        let keySegment = key[index]
78
        await this.graph.get(root, keySegment)
79
        nextRoot = root['/'][keySegment]
80
        if (!nextRoot) {
81
          return {
82
            root: root,
83
            index: index
84
          }
85
        }
86
        root = nextRoot
87
      }
88
89
      index++
90
    }
91
    let value
92
    if (root['/'].extension) {
93
      if (Array.isArray(root['/'].node)) {
94
        value = root['/'].node[root['/'].node.length - 1]
95
      } else {
96
        value = root['/'].node
97
      }
98
    } else {
99
      if (Array.isArray(root['/'])) {
100
        value = root['/'][root.length - 1]
101
      } else {
102
        value = root['/']
103
      }
104
    }
105
    if (value.length >= 32) {
106
      value = await this.graph.get(root, root.length - 1)
107
    }
108
109
    return {
110
      value: value,
111
      extensionIndex: extensionIndex,
112
      root: root,
113
      index: index
114
    }
115
  }
116
117
  async get (key) {
118
    key = this.formatKey(key)
119
    const results = await this._get(key)
120
    return results.value
121
  }
122
123
  async set (key, value) {
124
    key = this.formatKey(key)
125
126
    // initial set
127
    if (this.root['/'] === null) {
128
      this.root['/'] = {
129
        extension: new Buffer(key.buffer),
130
        node: value
131
      }
132
      return
133
    }
134
135
    const result = await this._get(key)
136
    let root = result.root
137
    let keySegment = key[result.index]
138
139
    if (result.extensionIndex !== undefined) {
140
      let extension = this.toTypedArray(root['/'].extension)
141
      // save the common part of the extension
142
      const extensionKey = extension[result.extensionIndex + 1]
143
      const remExtension = extension.subarray(1 - result.extensionIndex)
144
      extension = extension.subarray(0, result.extensionIndex)
145
      const node = root['/'].node
146
147
      if (extension.length) {
148
        root['/'].extension = new Buffer(extension.buffer)
149
        root['/'].node = []
150
        if (remExtension.length) {
151
          root['/'].node[extensionKey] = {
152
            '/': {
153
              extension: new Buffer(remExtension.buffer),
154
              node: node
155
            }
156
          }
157
        } else {
158
          root['/'].node[extensionKey] = node
159
        }
160
      } else {
161
        // there is no extension
162
        root['/'] = []
163
        if (remExtension.length) {
164
          root['/'][extensionKey] = {
165
            '/': {
166
              extension: remExtension,
167
              node: node
168
            }
169
          }
170
        } else {
171
          root['/'][extensionKey] = node
172
        }
173
      }
174
    }
175
176
    let newNode
177
    if (result.index + 1 < key.length) {
178
      // if there are remaning key segments create an extension node
179
      const extension = key.subarray(result.index + 1, key.length)
180
      newNode = {
181
        '/': {
182
          extension: new Buffer(extension.buffer),
183
          node: value
184
        }
185
      }
186
    } else {
187
      newNode = value
188
    }
189
190
    if (root['/'].extension) {
191
      if (!Array.isArray(root['/'].node)) {
192
        const val = root['/'].node
193
        root['/'].node = []
194
        root['/'].node[this.radix] = val
195
      }
196
      if (keySegment === undefined) {
197
        root['/'].node[this.radix] = newNode
198
      } else {
199
        root['/'].node[keySegment] = newNode
200
      }
201
    } else {
202
      if (keySegment === undefined) {
203
        root['/'][this.radix] = newNode
204
      } else {
205
        root['/'][keySegment] = newNode
206
      }
207
    }
208
  }
209
210
  async delete (key) {
211
    key = new this.ArrayConstructor(key)
212
    const results = await this._get(key)
213
    const root = results.root
214
    if (results.value) {
215
      if (results.extensionIndex) {
216
        key = key.subarray(-results.extensionIndex)
217
      }
218
      const keySegment = key[key.length - 1]
219
      delete root[keySegment]
220
      if (this.isEmptyNode(root) && results.parent) {
221
        delete results.parent[results.parentKey]
222
      } else if (!root[root.length - 1]) {
223
        let oneNode = false
224
        let rNodeIndex
225
        for (let i = 0; i < root.length - 1; i++) {
226
          const el = root[i]
227
          if (el) {
228
            if (!oneNode) {
229
              rNodeIndex = i
230
              oneNode = true
231
            } else {
232
              oneNode = false
233
              break
234
            }
235
          }
236
        }
237
238
        if (oneNode) {
239
          let extension = root[rNodeIndex].extension || []
240
          extension = concat([rNodeIndex], extension)
241
          const parentExtenstion = results.parent[results.parentIndex].extension
242
          if (parentExtenstion) {
243
            extension = concat(parentExtenstion, extension)
244
          }
245
          results.parent[results.parentIndex] = {
246
            extension: extension,
247
            root: root
248
          }
249
        }
250
      }
251
    }
252
  }
253
  isEmptyNode (node) {
254
    return node.evey(el => !el)
255
  }
256
  formatKey (key) {
257
    if (typeof key === 'string') {
258
      key = encoder.encode(key)
259
    }
260
    return new this.ArrayConstructor(key.buffer)
261
  }
262
}
263
264
function concat(a, b) {}
265
function readData (data) {
266
  return new Uint8Array(data)
267
}
268