-
Notifications
You must be signed in to change notification settings - Fork 846
/
SlimChain.cs
374 lines (337 loc) · 8.71 KB
/
SlimChain.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace NBitcoin
{
/// <summary>
/// A thread safe, memory optimized chain of hashes representing the current chain
/// </summary>
public class SlimChain
{
Dictionary<uint256, int> _HeightsByBlockHash;
uint256[] _BlockHashesByHeight;
int _Height;
ReaderWriterLock _lock = new ReaderWriterLock();
public SlimChain(uint256 genesis) : this(genesis, 1)
{
}
public SlimChain(uint256 genesis, int capacity)
{
if (capacity < 1)
throw new ArgumentOutOfRangeException(nameof(capacity), "Capacity should be 1 or more");
_BlockHashesByHeight = new uint256[capacity];
_HeightsByBlockHash = new Dictionary<uint256, int>(capacity);
_BlockHashesByHeight[0] = genesis;
_HeightsByBlockHash.Add(genesis, 0);
_Height = 0;
}
public int Height
{
get
{
return _Height;
}
}
public bool Contains(uint256 blockHash)
{
using (_lock.LockRead())
{
return _HeightsByBlockHash.ContainsKey(blockHash);
}
}
public bool TryGetHeight(uint256 blockHash, out int height)
{
using (_lock.LockRead())
{
return _HeightsByBlockHash.TryGetValue(blockHash, out height);
}
}
public bool TryGetHash(int height, out uint256 blockHash)
{
using (_lock.LockRead())
{
if (height > _Height || height < 0)
{
blockHash = default(uint256);
return false;
}
blockHash = _BlockHashesByHeight[height];
}
return true;
}
public void ResetToGenesis()
{
TrySetTip(Genesis, null);
}
public void SetCapacity(int capacity)
{
using (_lock.LockWrite())
{
if (capacity <= _BlockHashesByHeight.Length)
return;
var old = _BlockHashesByHeight;
_BlockHashesByHeight = new uint256[capacity];
Array.Copy(old, 0, _BlockHashesByHeight, 0, old.Length);
var oldd = _HeightsByBlockHash;
_HeightsByBlockHash = new Dictionary<uint256, int>(capacity);
foreach (var item in oldd)
_HeightsByBlockHash.Add(item.Key, item.Value);
}
}
/// <summary>
/// Set a new tip in the chain
/// </summary>
/// <param name="newTip">The new tip</param>
/// <param name="previous">The block hash before the new tip</param>
/// <param name="nopIfContainsTip">If true and the new tip is already included somewhere in the chain, do nothing</param>
/// <returns>True if newTip is the new tip</returns>
public bool TrySetTip(uint256 newTip, uint256 previous, bool nopIfContainsTip = false)
{
using (_lock.LockWrite())
{
return TrySetTipNoLock(newTip, previous, nopIfContainsTip);
}
}
private bool TrySetTipNoLock(in uint256 newTip, in uint256 previous, bool nopIfContainsTip)
{
if (newTip == null)
throw new ArgumentNullException(nameof(newTip));
if (newTip == previous)
throw new ArgumentException(message: "newTip should be different from previous");
if (newTip == _BlockHashesByHeight[_Height])
{
if (newTip != _BlockHashesByHeight[0] && _Height > 0 && _BlockHashesByHeight[_Height - 1] != previous)
throw new ArgumentException(message: "newTip is already inserted with a different previous block, this should never happen");
return true;
}
if (_HeightsByBlockHash.TryGetValue(newTip, out int newTipHeight))
{
if (newTipHeight > 0 && _BlockHashesByHeight[newTipHeight - 1] != previous)
throw new ArgumentException(message: "newTip is already inserted with a different previous block, this should never happen");
if (newTipHeight == 0 && _BlockHashesByHeight[0] != newTip)
{
throw new InvalidOperationException("Unexpected genesis block");
}
if (newTipHeight == 0 && previous != null)
throw new ArgumentException(message: "Genesis block should not have previous block", paramName: nameof(previous));
if (nopIfContainsTip)
return false;
}
if (previous == null && newTip != _BlockHashesByHeight[0])
throw new InvalidOperationException("Unexpected genesis block");
int prevHeight = -1;
if (previous != null && !_HeightsByBlockHash.TryGetValue(previous, out prevHeight))
return false;
for (int i = _Height; i > prevHeight; i--)
{
_HeightsByBlockHash.Remove(_BlockHashesByHeight[i]);
_BlockHashesByHeight[i] = null;
}
_Height = prevHeight + 1;
while (_BlockHashesByHeight.Length <= _Height)
{
var old = _BlockHashesByHeight;
_BlockHashesByHeight = new uint256[(int)((_BlockHashesByHeight.Length) * (_Height < 500_000 ? 2.0 : 1.1))];
Array.Copy(old, 0, _BlockHashesByHeight, 0, old.Length);
}
_BlockHashesByHeight[_Height] = newTip;
_HeightsByBlockHash.Add(newTip, _Height);
return true;
}
public BlockLocator GetTipLocator()
{
using (_lock.LockRead())
{
return GetLocatorNoLock(_Height);
}
}
public BlockLocator GetLocator(int height)
{
using (_lock.LockRead())
{
if (height > _Height || height < 0)
return null;
return GetLocatorNoLock(height);
}
}
public BlockLocator GetLocator(uint256 blockHash)
{
using (_lock.LockRead())
{
if (!_HeightsByBlockHash.TryGetValue(blockHash, out int height))
return null;
return GetLocatorNoLock(height);
}
}
private BlockLocator GetLocatorNoLock(int height)
{
int nStep = 1;
var vHave = new List<uint256>();
while (true)
{
vHave.Add(_BlockHashesByHeight[height]);
// Stop when we have added the genesis block.
if (height == 0)
break;
// Exponentially larger steps back, plus the genesis block.
height = Math.Max(height - nStep, 0);
if (vHave.Count > 10)
nStep *= 2;
}
var locators = new BlockLocator();
locators.Blocks = vHave;
return locators;
}
/// <summary>
/// Returns the first found block
/// </summary>
/// <param name="hashes">Hash to search for</param>
/// <returns>First found block or null</returns>
public SlimChainedBlock FindFork(BlockLocator blockLocator)
{
if (blockLocator == null)
throw new ArgumentNullException(nameof(blockLocator));
// Find the first block the caller has in the main chain
foreach (uint256 hash in blockLocator.Blocks)
{
if (_HeightsByBlockHash.TryGetValue(hash, out int height))
{
return CreateSlimBlock(height);
}
}
return null;
}
public uint256 Tip
{
get
{
using (_lock.LockRead())
{
return _BlockHashesByHeight[_Height];
}
}
}
public SlimChainedBlock TipBlock
{
get
{
using (_lock.LockRead())
{
return CreateSlimBlock(Height);
}
}
}
public SlimChainedBlock GetBlock(int height)
{
using (_lock.LockRead())
{
if (height > Height || height < 0)
return null;
return CreateSlimBlock(height);
}
}
public SlimChainedBlock GetBlock(uint256 blockHash)
{
using (_lock.LockRead())
{
if (!_HeightsByBlockHash.TryGetValue(blockHash, out int height))
return null;
return CreateSlimBlock(height);
}
}
private SlimChainedBlock CreateSlimBlock(int height)
{
return new SlimChainedBlock(_BlockHashesByHeight[height], height == 0 ? null : _BlockHashesByHeight[height - 1], height);
}
public uint256 Genesis
{
get
{
using (_lock.LockRead())
{
return _BlockHashesByHeight[0];
}
}
}
public void Save(Stream output)
{
using (_lock.LockRead())
{
var bytes = new byte[32];
for (int i = 0; i <= _Height; i++)
{
_BlockHashesByHeight[i].ToBytes(bytes);
output.Write(bytes, 0, 32);
}
}
}
public void Load(Stream input)
{
using (_lock.LockWrite())
{
var bytes = new byte[32];
uint256 prev = null;
while (input.ReadBytes(32, bytes) == 32)
{
uint256 tip = new uint256(bytes);
if (!TrySetTipNoLock(tip, prev, false))
throw new InvalidOperationException("Unexpected genesis block");
prev = tip;
}
}
}
public override string ToString()
{
using (_lock.LockRead())
{
return $"Height: {Height}, Hash: {_BlockHashesByHeight[_Height]}";
}
}
}
public class SlimChainedBlock
{
public SlimChainedBlock(uint256 hash, uint256 prev, int height)
{
if (hash == null)
throw new ArgumentNullException(nameof(hash));
if (prev == null && height != 0)
throw new ArgumentNullException(nameof(prev));
if (height < 0)
throw new ArgumentOutOfRangeException(nameof(height));
_Hash = hash;
_Previous = prev;
_Height = height;
}
private readonly uint256 _Hash;
public uint256 Hash
{
get
{
return _Hash;
}
}
private readonly uint256 _Previous;
public uint256 Previous
{
get
{
return _Previous;
}
}
private readonly int _Height;
public int Height
{
get
{
return _Height;
}
}
public override string ToString()
{
return Hash.ToString();
}
}
}