-
Notifications
You must be signed in to change notification settings - Fork 0
/
ChainSlot.go
64 lines (49 loc) · 1.64 KB
/
ChainSlot.go
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
package main
import (
"math/rand"
"github.com/golang/glog"
)
func getChainSlot(chainID uint32, merkleSize uint32, merkleNonce uint32) (slotNum uint32) {
rand := merkleNonce*1103515245 + 12345
rand += chainID
rand = rand*1103515245 + 12345
slotNum = rand % merkleSize
return
}
func assignChainSlots(chainIDs map[int]uint32) (merkleNonce uint32, merkleSize uint32, chainIDIndexSlots map[uint32]uint32, slotIndexChainIDs map[uint32]uint32) {
chainIDIndexSlots = make(map[uint32]uint32)
slotIndexChainIDs = make(map[uint32]uint32)
var chainSize uint32
var slotConflict bool
chainSize = uint32(len(chainIDs))
merkleSize = 1
for merkleSize < chainSize {
merkleSize *= 2
}
glog.Info("[assignChainSlots] init merkleSize: ", merkleSize)
slotConflict = true
for retryTimes := 1; slotConflict; retryTimes++ {
merkleNonce = rand.Uint32()
slotConflict = false
for _, chainID := range chainIDs {
slot := getChainSlot(chainID, merkleSize, merkleNonce)
if conflictedChainID, ok := slotIndexChainIDs[slot]; ok {
glog.Info("[assignChainSlots] slot conflicted: chain ", conflictedChainID, " and ", chainID, " got the same slot ", slot)
slotConflict = true
// clear maps
chainIDIndexSlots = make(map[uint32]uint32)
slotIndexChainIDs = make(map[uint32]uint32)
// retry too many times, increase the merkle size
if retryTimes >= 5 {
retryTimes = 0
merkleSize *= 2
glog.Info("[assignChainSlots] merkleSize increased to ", merkleSize)
}
break
}
slotIndexChainIDs[slot] = chainID
chainIDIndexSlots[chainID] = slot
}
}
return
}