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