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 (root['/'].extension) {
37
        let extensionIndex = 0
38
        const extension = this.toTypedArray(root['/'].extension)
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(root['/'].extension)
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 = root['/'].node
126
      let newNode
127
      // create the new extension node
128
      if (extension.length) {
129
        root['/'].extension = new Buffer(extension.buffer)
130
        newNode = root['/'].node = []
131
      } else {
132
        newNode = root['/'] = []
133
      }
134
135
      // save the remainer of the extension node
136
      if (remExtension.length) {
137
        newNode[extensionKey] = {
138
          '/': {
139
            extension: new Buffer(remExtension.buffer),
140
            node: node
141
          }
142
        }
143
      } else {
144
        newNode[extensionKey] = node
145
      }
146
    }
147
148
    let newNode
149
    if (result.index + 1 < key.length) {
150
      // if there are remaning key segments create an extension node
151
      const extension = key.subarray(result.index + 1, key.length)
152
      newNode = {
153
        '/': {
154
          extension: new Buffer(extension.buffer),
155
          node: value
156
        }
157
      }
158
    } else {
159
      newNode = value
160
    }
161
162
    let targetNode = getBranch(root)
163
164
    // set the value
165
    if (keySegment === undefined) {
166
      targetNode[this.radix] = newNode
167
    } else {
168
      targetNode[keySegment] = newNode
169
    }
170
  }
171
172
  // async delete (key) {
173
  //   key = new this.ArrayConstructor(key)
174
  //   const results = await this._get(key)
175
  //   const root = results.root
176
  //   if (results.value) {
177
  //     if (results.extensionIndex) {
178
  //       key = key.subarray(-results.extensionIndex)
179
  //     }
180
  //     const keySegment = key[key.length - 1]
181
  //     delete root[keySegment]
182
  //     if (this.isEmptyNode(root) && results.parent) {
183
  //       delete results.parent[results.parentKey]
184
  //     } else if (!root[root.length - 1]) {
185
  //       let oneNode = false
186
  //       let rNodeIndex
187
  //       for (let i = 0; i < root.length - 1; i++) {
188
  //         const el = root[i]
189
  //         if (el) {
190
  //           if (!oneNode) {
191
  //             rNodeIndex = i
192
  //             oneNode = true
193
  //           } else {
194
  //             oneNode = false
195
  //             break
196
  //           }
197
  //         }
198
  //       }
199
200
  //       if (oneNode) {
201
  //         let extension = root[rNodeIndex].extension || []
202
  //         extension = concat([rNodeIndex], extension)
203
  //         const parentExtenstion = results.parent[results.parentIndex].extension
204
  //         if (parentExtenstion) {
205
  //           extension = concat(parentExtenstion, extension)
206
  //         }
207
  //         results.parent[results.parentIndex] = {
208
  //           extension: extension,
209
  //           root: root
210
  //         }
211
  //       }
212
  //     }
213
  //   }
214
  // }
215
  isEmptyNode (node) {
216
    return node.evey(el => !el)
217
  }
218
  formatKey (key) {
219
    if (typeof key === 'string') {
220
      key = encoder.encode(key)
221
    }
222
    return new this.ArrayConstructor(key.buffer)
223
  }
224
}
225
226
function getBranch (node) {
227
  if (node['/'].extension) {
228
    return node['/'].node
229
  } else {
230
    return root['/']
231
  }
232
}
233
234