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