git ssb

1
const tape = require('tape')
2
const crypto = require('crypto')
3
const level = require('level-browserify')
4
const RadixTree = require('../')
5
const db = level('./testdb')
6
7
tape('set and get', async t => {
8
  const r = await RadixTree.getMerkleLink(Buffer.from([0]))
9
10
  t.equal(r.toString('hex'), '6e340b9cffb37a989ca544e6bb780a2c78901d3f', 'should hash')
11
12
  let tree = new RadixTree({
13
    db: db
14
  })
15
16
  tree.set('test', Buffer.from('cat'))
17
  let val = await tree.get('test')
18
  t.equals(val.toString(), 'cat')
19
  tree.set('te', Buffer.from('blop'))
20
  val = await tree.get('test')
21
  t.equals(val.toString(), 'cat')
22
23
  val = await tree.get('te')
24
  t.equals(val.toString(), 'blop')
25
26
  tree.set('rad', Buffer.from('cat2'))
27
28
  val = await tree.get('rad')
29
  t.equals(val.toString(), 'cat2')
30
31
  tree.set('test', Buffer.from('cat111'))
32
  val = await tree.get('test')
33
  t.equals(val.toString(), 'cat111')
34
35
  const stateRoot = await tree.flush()
36
37
  // try reteriving node from ipfs
38
  tree = new RadixTree({
39
    db: db,
40
    root: stateRoot
41
  })
42
43
  val = await tree.get('te')
44
  t.equals(val.toString(), 'blop')
45
46
  val = await tree.get('rad')
47
  t.equals(val.toString(), 'cat2')
48
49
  val = await tree.get('test')
50
  t.equals(val.toString(), 'cat111')
51
  // console.log(JSON.stringify(tree.root, null, 2))
52
  t.end()
53
})
54
55
tape('branch nodes', async t => {
56
  const tree = new RadixTree({
57
    db: db
58
  })
59
60
  let key0 = new RadixTree.ArrayConstructor([1, 1])
61
  let key1 = new RadixTree.ArrayConstructor([0, 1])
62
  let key2 = new RadixTree.ArrayConstructor([1, 0])
63
  let key3 = new RadixTree.ArrayConstructor([0, 0])
64
65
  tree.set(key0, Buffer.from('cat'))
66
  tree.set(key1, Buffer.from('cat2'))
67
  tree.set(key2, Buffer.from('cat'))
68
  tree.set(key3, Buffer.from('cat3'))
69
70
  let val = await tree.get(key0)
71
  t.equals(val.toString(), 'cat')
72
  val = await tree.get(key1)
73
  t.equals(val.toString(), 'cat2')
74
  val = await tree.get(key2)
75
  t.equals(val.toString(), 'cat')
76
  val = await tree.get(key3)
77
  t.equals(val.toString(), 'cat3')
78
79
  t.end()
80
})
81
82
tape('sub trees', async t => {
83
  const tree = new RadixTree({
84
    db: db
85
  })
86
87
  let key0 = new RadixTree.ArrayConstructor([1, 1, 1, 1, 1])
88
  let key1 = new RadixTree.ArrayConstructor([0, 1, 1, 1, 1])
89
  let key2 = new RadixTree.ArrayConstructor([1, 1, 1, 0, 1])
90
  let key3 = new RadixTree.ArrayConstructor([0, 0, 1, 0, 1])
91
92
  tree.set(key0, Buffer.from('cat'))
93
  tree.set(key1, Buffer.from('cat2'))
94
  tree.set(key2, Buffer.from('dog'))
95
  tree.set(key3, Buffer.from('cat3'))
96
97
  await tree.done()
98
  let key = new RadixTree.ArrayConstructor([1, 1, 1])
99
  let subKey1 = new RadixTree.ArrayConstructor([1, 1])
100
  let subKey2 = new RadixTree.ArrayConstructor([0, 1])
101
102
  const subTree = await tree.getSubTree(key)
103
104
  let val = await subTree.get(subKey1)
105
  t.equals(val.toString(), 'cat')
106
107
  val = await subTree.get(subKey2)
108
  t.equals(val.toString(), 'dog')
109
110
  t.end()
111
})
112
113
tape('delete', async t => {
114
  const tree = new RadixTree({
115
    db: db
116
  })
117
  tree.set('test', Buffer.from('cat'))
118
  tree.set('ter', Buffer.from('cat3'))
119
  tree.delete('te')
120
  tree.delete('test')
121
  await tree.delete('ter')
122
  t.deepEquals(tree.root['/'], RadixTree.emptyTreeState)
123
124
  // tests delete midle branchs
125
  tree.set('test', Buffer.from('cat'))
126
  tree.set('te', Buffer.from('cat2'))
127
  tree.set('ter', Buffer.from('cat3'))
128
  await tree.delete('te')
129
  let val = await tree.get('test')
130
  t.equals(val.toString(), 'cat')
131
132
  // tests delete end branchs
133
  tree.set('te', 'cat2')
134
  tree.delete('ter')
135
  tree.delete('te')
136
  await tree.delete('test')
137
  t.deepEquals(tree.root['/'], RadixTree.emptyTreeState)
138
  t.end()
139
})
140
141
tape('large values', async t => {
142
  const tree = new RadixTree({
143
    db: db
144
  })
145
  const saved = Buffer.alloc(33).fill(1)
146
  tree.set('test', saved)
147
  const value = await tree.get('test')
148
  t.equals(value.toString(), saved.toString())
149
  t.end()
150
})
151
152
tape('errors', async t => {
153
  const tree = new RadixTree({
154
    db: db,
155
    root: {
156
      '/': Buffer.alloc(20)
157
    }
158
  })
159
160
  try {
161
    await tree.get('test')
162
  } catch (e) {
163
    t.end()
164
  }
165
})
166
167
tape('random', async t => {
168
  const tree = new RadixTree({
169
    db: db
170
  })
171
  const entries = 100
172
  for (let i = 0; i < entries; i++) {
173
    const key = crypto.createHash('sha256').update(i.toString()).digest().slice(0, 20)
174
    tree.set(key, Buffer.from([i]))
175
  }
176
  // console.log(JSON.stringify(tree.root, null, 2))
177
178
  await tree.flush()
179
180
  for (let i = 0; i < entries; i++) {
181
    const key = crypto.createHash('sha256').update(i.toString()).digest().slice(0, 20)
182
    const value = await tree.get(key)
183
    t.equals(value[0], i)
184
  }
185
186
  await tree.flush()
187
  for (let i = 0; i < entries; i++) {
188
    const key = crypto.createHash('sha256').update(i.toString()).digest().slice(0, 20)
189
    await tree.delete(key)
190
  }
191
192
  t.deepEquals(tree.root['/'], RadixTree.emptyTreeState)
193
194
  t.end()
195
})
196