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
    while (key.length > index) {
36
      if (isExtension(root)) {
37
        let extensionIndex = 0
38
        const extension = this.toTypedArray(getExtension(root))
39
        let subKey
40
        // alll extension are padded to 8 bit alignment. So we need to update
41
        // the index later to count for the added padding
42
        let padLen
43
        if (this.radix === 2) {
44
          subKey = key.slice(index, index + extension.length)
45
          padLen = subKey.length
46
          subKey = new this.ArrayConstructor(subKey.buffer)
47
          padLen = subKey.length - padLen
48
        } else {
49
          subKey = key.subarray(index, extension.length)
50
        }
51
        // checks the extension against the key
52
        while (extensionIndex < extension.length && extension[extensionIndex] === subKey[extensionIndex]) {
53
          extensionIndex++
54
        }
55
        index += extensionIndex - padLen
56
        // check if we compelete travered the extension
57
        if (extensionIndex !== extension.length) {
58
          return {
59
            extensionIndex: extensionIndex,
60
            root: root,
61
            index: index
62
          }
63
        }
64
      }
65
66
      let keySegment = key[index]
67
      if (keySegment) {
68
        const branch = getBranch(root)
69
        await this.graph.get(branch, keySegment)
70
        root = branch[keySegment]
71
      }
72
73
      index++
74
    }
75
76
    const node = getBranch(root)
77
    // get the value
78
    let value
79
    if (Array.isArray(node)) {
80
      value = node[node.length - 1]
81
    } else {
82
      value = node
83
    }
84
85
    if (value.length >= 32) {
86
      value = await this.graph.get(root, root.length - 1)
87
    }
88
89
    return {
90
      value: value,
91
      root: root,
92
      index: index
93
    }
94
  }
95
96
  async get (key) {
97
    key = this.formatKey(key)
98
    const results = await this._get(key)
99
    return results.value
100
  }
101
102
  async set (key, value) {
103
    key = this.formatKey(key)
104
105
    // initial set
106
    if (this.root['/'] === null) {
107
      this.root['/'] = {
108
        extension: new Buffer(key.buffer),
109
        node: value
110
      }
111
      return
112
    }
113
114
    const result = await this._get(key)
115
    let root = result.root
116
    let keySegment = key[result.index]
117
118
    if (result.extensionIndex !== undefined) {
119
      // split the extension node in two
120
      let extension = this.toTypedArray(getExtension(root))
121
      const extensionKey = extension[result.extensionIndex + 1]
122
      const remExtension = extension.subarray(1 - result.extensionIndex)
123
      extension = extension.subarray(0, result.extensionIndex)
124
125
      const node = getNode(root)
126
      let newNode
127
      // create the new extension node
128
      if (extension.length) {
129
        setExtension(root, new Buffer(extension.buffer))
130
        newNode = []
131
        setNode(root, newNode)
132
      } else {
133
        newNode = root['/'] = []
134
      }
135
136
      // save the remainer of the extension node
137
      if (remExtension.length) {
138
        newNode[extensionKey] = createExtension(new Buffer(remExtension.buffer), node)
139
      } else {
140
        newNode[extensionKey] = node
141
      }
142
    }
143
144
    let newNode
145
    if (result.index + 1 < key.length) {
146
      // if there are remaning key segments create an extension node
147
      const extension = key.subarray(result.index + 1, key.length)
148
      newNode = createExtension(new Buffer(extension.buffer), value)
149
    } else {
150
      newNode = value
151
    }
152
153
    let targetNode = getBranch(root)
154
155
    // set the value
156
    if (keySegment === undefined) {
157
      targetNode[this.radix] = newNode
158
    } else {
159
      targetNode[keySegment] = newNode
160
    }
161
  }
162
163
  // async delete (key) {
164
  //   key = new this.ArrayConstructor(key)
165
  //   const results = await this._get(key)
166
  //   const root = results.root
167
  //   if (results.value) {
168
  //     if (results.extensionIndex) {
169
  //       key = key.subarray(-results.extensionIndex)
170
  //     }
171
  //     const keySegment = key[key.length - 1]
172
  //     delete root[keySegment]
173
  //     if (this.isEmptyNode(root) && results.parent) {
174
  //       delete results.parent[results.parentKey]
175
  //     } else if (!root[root.length - 1]) {
176
  //       let oneNode = false
177
  //       let rNodeIndex
178
  //       for (let i = 0; i < root.length - 1; i++) {
179
  //         const el = root[i]
180
  //         if (el) {
181
  //           if (!oneNode) {
182
  //             rNodeIndex = i
183
  //             oneNode = true
184
  //           } else {
185
  //             oneNode = false
186
  //             break
187
  //           }
188
  //         }
189
  //       }
190
191
  //       if (oneNode) {
192
  //         let extension = root[rNodeIndex].extension || []
193
  //         extension = concat([rNodeIndex], extension)
194
  //         const parentExtenstion = results.parent[results.parentIndex].extension
195
  //         if (parentExtenstion) {
196
  //           extension = concat(parentExtenstion, extension)
197
  //         }
198
  //         results.parent[results.parentIndex] = {
199
  //           extension: extension,
200
  //           root: root
201
  //         }
202
  //       }
203
  //     }
204
  //   }
205
  // }
206
  isEmptyNode (node) {
207
    return node.evey(el => !el)
208
  }
209
  formatKey (key) {
210
    if (typeof key === 'string') {
211
      key = encoder.encode(key)
212
    }
213
    return new this.ArrayConstructor(key.buffer)
214
  }
215
}
216
217
function getBranch (node) {
218
  if (isExtension(node)) {
219
    return getNode(node)
220
  } else {
221
    return root['/']
222
  }
223
}
224
225
function isExtension (node) {
226
  return !!node['/'].extension
227
}
228
229
function getExtension (node) {
230
  return node['/'].extension
231
}
232
233
function getNode (node) {
234
  return node['/'].node
235
}
236
237
function setExtension (node, ex) {
238
  node['/'].extension = ex
239
}
240
241
function setNode (node, val) {
242
  node['/'].node = val
243
}
244
245
function createExtension(ex, node) {
246
  return {
247
    '/': {
248
      extension: ex,
249
      node: node
250
    }
251
  }
252
}
253