generated from fission-codes/project-template
-
Notifications
You must be signed in to change notification settings - Fork 24
/
mmpt.ts
196 lines (163 loc) · 5.85 KB
/
mmpt.ts
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
import type { CID } from "multiformats/cid"
import * as Basic from "../basic.js"
import * as Depot from "../../../components/depot/implementation.js"
import * as Link from "../../link.js"
import { Puttable, SimpleLinks } from "../../types.js"
import { decodeCID } from "../../../common/index.js"
const nibbles = {
"0": true, "1": true, "2": true, "3": true, "4": true, "5": true, "6": true, "7": true,
"8": true, "9": true, "a": true, "b": true, "c": true, "d": true, "e": true, "f": true,
} as { [ key: string ]: boolean }
const isNibble = (str: string): boolean => nibbles[ str ] === true
type Member = {
name: string
cid: CID
}
/**
* Modified Merkle Patricia Tree
* The tree has a node weight of 16
* It stores items with hexidecimal keys and creates a new layer when a given layer has two keys that start with the same nibble
*/
export default class MMPT implements Puttable {
depot: Depot.Implementation
links: SimpleLinks
children: { [ name: string ]: MMPT }
constructor(depot: Depot.Implementation, links: SimpleLinks) {
this.links = links
this.children = {}
this.depot = depot
}
static create(depot: Depot.Implementation): MMPT {
return new MMPT(depot, {})
}
static async fromCID(depot: Depot.Implementation, cid: CID): Promise<MMPT> {
const links = await Basic.getSimpleLinks(depot, cid)
return new MMPT(depot, links)
}
async putDetailed(): Promise<Depot.PutResult> {
return Basic.putLinks(this.depot, this.links)
}
async put(): Promise<CID> {
const { cid } = await this.putDetailed()
return cid
}
async add(name: string, value: CID): Promise<void> {
if (!isNibble(name[ 0 ])) {
throw new Error(`Not a valid name, must be hexadecimal`)
}
const nextNameOrSib = this.nextTreeOrSiblingName(name)
// if already in tree, then skip
if (name === nextNameOrSib) {
// if (this.links[ name ]?.cid !== value) {
// this.manners.warn(`Adding \`${name}\` to the MMPT again with a different value. This should not happen. The original value will still be used and can loading issues. Current CID is \`${this.links[ name ]?.cid}\`, new CID is \`${value}\`.`)
// } else {
// // skip
// }
}
// if no children starting with first char of name, then add with entire name as key
else if (nextNameOrSib === null) {
this.links[ name ] = Link.make(name, value, true, 0)
}
// if multiple children with first char of names, then add to that tree
else if (nextNameOrSib.length === 1) {
const nextTree = await this.getDirectChild(nextNameOrSib)
await nextTree.add(name.slice(1), value)
await this.putAndUpdateChildLink(nextNameOrSib)
}
// if one other child with first char of name, then put both into a child tree
else {
const newTree = this.addEmptyChild(name[ 0 ])
const nextCID = this.links[ nextNameOrSib ].cid
this.removeChild(nextNameOrSib)
await Promise.all([
newTree.add(name.slice(1), value),
newTree.add(nextNameOrSib.slice(1), decodeCID(nextCID))
])
await this.putAndUpdateChildLink(name[ 0 ])
}
}
async putAndUpdateChildLink(name: string): Promise<void> {
const cidBefore = this.links[ name ]?.cid
const { cid, size } = await this.children[ name ].putDetailed()
const cidNow = this.links[ name ]?.cid
if (cidBefore != cidNow) {
// If there are changes in-between, we have to
// re-try updating. Otherwise we can overwrite changes that
// a concurrent update made
return await this.putAndUpdateChildLink(name)
}
this.links[ name ] = Link.make(name, cid, false, size)
}
addEmptyChild(name: string): MMPT {
const tree = MMPT.create(this.depot)
this.children[ name ] = tree
return tree
}
async get(name: string): Promise<CID | null> {
const nextName = this.nextTreeName(name)
if (nextName === null) return null
if (nextName.length > 1) {
return decodeCID(this.links[ nextName ].cid)
}
const nextTree = await this.getDirectChild(nextName)
return nextTree.get(name.slice(1))
}
async exists(name: string): Promise<boolean> {
return (await this.get(name)) !== null
}
async members(): Promise<Array<Member>> {
const children = await Promise.all(
Object.values(this.links).map(async ({ name, cid }) => {
if (name.length > 1) {
return [ { name, cid: decodeCID(cid) } ]
}
const child = await MMPT.fromCID(this.depot, decodeCID(cid))
const childMembers = await child.members()
return childMembers.map(mem => ({
...mem,
name: name + mem.name
}))
})
)
return children.reduce((acc, cur) => acc.concat(cur))
}
private async getDirectChild(name: string): Promise<MMPT> {
if (this.children[ name ]) {
return this.children[ name ]
}
const child = await MMPT.fromCID(
this.depot,
decodeCID(this.links[ name ].cid)
)
// check that the child wasn't added while retrieving the mmpt from the network
if (this.children[ name ]) {
return this.children[ name ]
}
this.children[ name ] = child
return child
}
private removeChild(name: string): void {
delete this.links[ name ]
if (this.children[ name ]) {
delete this.children[ name ]
}
}
private directChildExists(name: string): boolean {
return this.links[ name ] !== undefined || this.children[ name ] !== undefined
}
private nextTreeName(name: string): string | null {
if (this.directChildExists(name[ 0 ])) {
return name[ 0 ]
} else if (this.directChildExists(name)) {
return name
}
return null
}
private nextTreeOrSiblingName(name: string): string | null {
const nibble = name[ 0 ]
if (this.directChildExists(nibble)) {
return nibble
}
return Object.keys(this.links).find(child => nibble === child[ 0 ]) || null
}
}