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 (hasExtension(root)) {
28
        let extensionIndex = 0
29
        const extensionLen = getExLength(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
        const nextRoot = branch[keySegment]
55
        if (!nextRoot) {
56
          return {
57
            root: root,
58
            index: index
59
          }
60
        } else {
61
          root = nextRoot
62
        }
63
      } else {
64
        break
65
      }
66
67
      index++
68
    }
69
70
    let value = getValue(root)
71
72
    if (value.length >= 32) {
73
      value = await this.graph.get(root, root.length - 1)
74
    }
75
76
    return {
77
      value: value,
78
      root: root,
79
      index: index
80
    }
81
  }
82
83
  async get (key) {
84
    key = RadixTree.formatKey(key)
85
    const result = await this._get(key)
86
    return result.value
87
  }
88
89
  async set (key, value) {
90
    key = RadixTree.formatKey(key)
91
92
    // initial set
93
    if (this.root['/'] === null) {
94
      this.root['/'] = createNode(value, key)['/']
95
      return
96
    }
97
98
    const result = await this._get(key)
99
    let root = result.root
100
101
    if (result.value) {
102
      setValue(root, value)
103
      return
104
    }
105
106
    if (result.extensionIndex !== undefined) {
107
      // split the extension node in two
108
      let extension = getExtension(root)
109
      const extensionKey = extension[result.extensionIndex]
110
      const remExtension = extension.subarray(result.extensionIndex + 1)
111
      extension = extension.subarray(0, result.extensionIndex)
112
113
      setExtension(root, remExtension)
114
      const branch = []
115
      branch[extensionKey] = {'/': root['/']}
116
      root['/'] = createNode(null, extension, branch)['/']
117
    }
118
119
    // if there are remaning key segments create an extension node
120
    if (result.index < key.length) {
121
      const keySegment = key[result.index]
122
      const extension = key.subarray(result.index + 1, key.length)
123
      const newNode = createNode(value, extension)
124
      const rootBranch = getBranch(root)
125
      rootBranch[keySegment] = newNode
126
    } else {
127
      setValue(root, value)
128
    }
129
  }
130
131
  // async delete (key) {
132
  //   key = new this.ArrayConstructor(key)
133
  //   const results = await this._get(key)
134
  //   const root = results.root
135
  //   if (results.value) {
136
  //     if (results.extensionIndex) {
137
  //       key = key.subarray(-results.extensionIndex)
138
  //     }
139
  //     const keySegment = key[key.length - 1]
140
  //     delete root[keySegment]
141
  //     if (this.isEmptyNode(root) && results.parent) {
142
  //       delete results.parent[results.parentKey]
143
  //     } else if (!root[root.length - 1]) {
144
  //       let oneNode = false
145
  //       let rNodeIndex
146
  //       for (let i = 0; i < root.length - 1; i++) {
147
  //         const el = root[i]
148
  //         if (el) {
149
  //           if (!oneNode) {
150
  //             rNodeIndex = i
151
  //             oneNode = true
152
  //           } else {
153
  //             oneNode = false
154
  //             break
155
  //           }
156
  //         }
157
  //       }
158
159
  //       if (oneNode) {
160
  //         let extension = root[rNodeIndex].extension || []
161
  //         extension = concat([rNodeIndex], extension)
162
  //         const parentExtenstion = results.parent[results.parentIndex].extension
163
  //         if (parentExtenstion) {
164
  //           extension = concat(parentExtenstion, extension)
165
  //         }
166
  //         results.parent[results.parentIndex] = {
167
  //           extension: extension,
168
  //           root: root
169
  //         }
170
  //       }
171
  //     }
172
  //   }
173
  // }
174
  static formatKey (key) {
175
    if (typeof key === 'string') {
176
      key = encoder.encode(key)
177
      return new RadixTree.ArrayConstructor(key.buffer)
178
    } else {
179
      return key
180
    }
181
  }
182
}
183
184
function getBranch (node) {
185
  return node['/'].branch
186
}
187
188
function getValue (node) {
189
  return node['/'].value
190
}
191
192
function hasExtension (node) {
193
  return !!node['/'].extension
194
}
195
196
function getExtension (node) {
197
  return RadixTree.toTypedArray(node['/'].extension[1]).subarray(0, getExLength(node))
198
}
199
200
function getExLength (node) {
201
  return node['/'].extension[0]
202
}
203
204
function setExtension (node, ex) {
205
  if (ex && ex.length) {
206
    node['/'].extension = [ex.length, new Buffer(ex.buffer)]
207
  } else {
208
    node['/'].extension = null
209
  }
210
}
211
212
function setValue (node, val) {
213
  node['/'].value = val
214
}
215
216
function createNode (value, ex, branch = []) {
217
  if (ex && ex.length) {
218
    ex = [ex.length, new Buffer(ex.buffer)]
219
  } else {
220
    ex = null
221
  }
222
223
  return {
224
    '/': {
225
      extension: ex,
226
      branch: branch,
227
      value: value
228
    }
229
  }
230
}
231