-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathshamap.js
More file actions
108 lines (102 loc) · 2.36 KB
/
shamap.js
File metadata and controls
108 lines (102 loc) · 2.36 KB
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
const assert = require('assert');
const makeClass = require('./utils/make-class');
const {Hash256} = require('./types');
const {HashPrefix} = require('./hash-prefixes');
const {Sha512Half: Hasher} = require('./hashes');
const ShaMapNode = makeClass({
virtuals: {
hashPrefix() {},
isLeaf() {},
isInner() {}
},
cached: {
hash() {
const hasher = Hasher.put(this.hashPrefix());
this.toBytesSink(hasher);
return hasher.finish();
}
}
});
const ShaMapLeaf = makeClass({
inherits: ShaMapNode,
ShaMapLeaf(index, item) {
ShaMapNode.call(this);
this.index = index;
this.item = item;
},
isLeaf() {
return true;
},
isInner() {
return false;
},
hashPrefix() {
return this.item.hashPrefix();
},
toBytesSink(sink) {
this.item.toBytesSink(sink);
this.index.toBytesSink(sink);
}
});
const $uper = ShaMapNode.prototype;
const ShaMapInner = makeClass({
inherits: ShaMapNode,
ShaMapInner(depth = 0) {
ShaMapNode.call(this);
this.depth = depth;
this.slotBits = 0;
this.branches = Array(16);
},
isInner() {
return true;
},
isLeaf() {
return false;
},
hashPrefix() {
return HashPrefix.innerNode;
},
setBranch(slot, branch) {
this.slotBits = this.slotBits | (1 << slot);
this.branches[slot] = branch;
},
empty() {
return this.slotBits === 0;
},
hash() {
if (this.empty()) {
return Hash256.ZERO_256;
}
return $uper.hash.call(this);
},
toBytesSink(sink) {
for (let i = 0; i < this.branches.length; i++) {
const branch = this.branches[i];
const hash = branch ? branch.hash() : Hash256.ZERO_256;
hash.toBytesSink(sink);
}
},
addItem(index, item, leaf) {
assert(index instanceof Hash256);
const nibble = index.nibblet(this.depth);
const existing = this.branches[nibble];
if (!existing) {
this.setBranch(nibble, leaf || new ShaMapLeaf(index, item));
} else if (existing.isLeaf()) {
const newInner = new ShaMapInner(this.depth + 1);
newInner.addItem(existing.index, null, existing);
newInner.addItem(index, item, leaf);
this.setBranch(nibble, newInner);
} else if (existing.isInner()) {
existing.addItem(index, item, leaf);
} else {
assert(false);
}
}
});
const ShaMap = makeClass({
inherits: ShaMapInner
});
module.exports = {
ShaMap
};