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.dag = opts.dag
15
    this.radix = 2
16
    this.graph = new Graph(this.dag)
17
  }
18
19
  static get ArrayConstructor () {
20
    return Uint1Array
21
  }
22
23
  static toTypedArray (array) {
24
    return new RadixTree.ArrayConstructor(new Uint8Array(array).buffer)
25
  }
26
27
  async _get (key) {
28
    let index = 0
29
    let root = this.root
30
    let parent
31
    while (1) {
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)
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)
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
  static 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 setBranch (node, branch) {
203
  node['/'][BRANCH] = branch
204
}
205
206
function getBranch (node) {
207
  return node['/'][BRANCH]
208
}
209
210
function getValue (node) {
211
  return node['/'][VALUE]
212
}
213
214
function deleteValue (node) {
215
  node['/'].pop()
216
}
217
218
function hasExtension (node) {
219
  return node['/'][EXTENSION].length === 2
220
}
221
222
function getExtension (node) {
223
  return RadixTree.toTypedArray(node['/'][EXTENSION][1]).subarray(0, getExLength(node))
224
}
225
226
function getExLength (node) {
227
  return node['/'][EXTENSION][0]
228
}
229
230
function setExtension (node, ex) {
231
  if (ex && ex.length) {
232
    node['/'][EXTENSION] = [ex.length, new Buffer(ex.buffer)]
233
  } else {
234
    node['/'][EXTENSION] = []
235
  }
236
}
237
238
function setValue (node, val) {
239
  node['/'][VALUE] = val
240
}
241
242
function createNode (ex, branch, value) {
243
  if (ex && ex.length) {
244
    ex = [ex.length, new Buffer(ex.buffer)]
245
  } else {
246
    ex = []
247
  }
248
249
  const node = {
250
    '/': [ex, branch]
251
  }
252
253
  if (value !== undefined) {
254
    node['/'].push(value)
255
  }
256
  return node
257
}
258