/
utils.go
122 lines (108 loc) · 2.7 KB
/
utils.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
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
package entry // import "berty.tech/go-ipfs-log/entry"
import (
"bytes"
"sort"
"berty.tech/go-ipfs-log/iface"
)
// Difference gets the list of values not present in both entries sets.
func Difference(a []iface.IPFSLogEntry, b []iface.IPFSLogEntry) []iface.IPFSLogEntry {
existing := map[string]bool{}
processed := map[string]bool{}
var diff []iface.IPFSLogEntry
for _, v := range a {
existing[v.GetHash().String()] = true
}
for _, v := range b {
isInFirst := existing[v.GetHash().String()]
hasBeenProcessed := processed[v.GetHash().String()]
if !isInFirst && !hasBeenProcessed {
diff = append(diff, v)
processed[v.GetHash().String()] = true
}
}
return diff
}
//func FindTails(entries []*Entry) []*Entry {
// // Reverse index { next -> entry }
// reverseIndex := map[string][]*Entry{}
// // Null index containing entries that have no parents (nexts)
// nullIndex := []*Entry{}
// // Hashes for all entries for quick lookups
// hashes := map[string]bool{}
// // Hashes of all next entries
// nexts := []cid.Cid{}
//
// for _, e := range entries {
// if len(e.Next) == 0 {
// nullIndex = append(nullIndex, e)
// }
//
// for _, nextE := range e.Next {
// reverseIndex[nextE.String()] = append(reverseIndex[nextE.String()], e)
// }
//
// nexts = append(nexts, e.Next...)
//
// hashes[e.Hash.String()] = true
// }
//
// tails := []*Entry{}
//
// for _, n := range nexts {
// if _, ok := hashes[n.String()]; !ok {
// continue
// }
//
// tails = append(tails, reverseIndex[n.String()]...)
// }
//
// tails = append(tails, nullIndex...)
//
// return NewOrderedMapFromEntries(tails).Slice()
//}
//
//func FindTailHashes(entries []*Entry) []string {
// res := []string{}
// hashes := map[string]bool{}
// for _, e := range entries {
// hashes[e.Hash.String()] = true
// }
//
// for _, e := range entries {
// nextLength := len(e.Next)
//
// for i := range e.Next {
// next := e.Next[nextLength-i]
// if _, ok := hashes[next.String()]; !ok {
// res = append([]string{e.Hash.String()}, res...)
// }
// }
// }
//
// return res
//}
// FindHeads search entries heads in an OrderedMap.
func FindHeads(entries iface.IPFSLogOrderedEntries) []iface.IPFSLogEntry {
if entries == nil {
return nil
}
var result []iface.IPFSLogEntry
items := map[string]string{}
for _, k := range entries.Keys() {
e := entries.UnsafeGet(k)
for _, n := range e.GetNext() {
items[n.String()] = e.GetHash().String()
}
}
for _, h := range entries.Keys() {
e, ok := items[h]
if ok || e != "" {
continue
}
result = append(result, entries.UnsafeGet(h))
}
sort.SliceStable(result, func(a, b int) bool {
return bytes.Compare(result[a].GetClock().GetID(), result[b].GetClock().GetID()) < 0
})
return result
}