-
Notifications
You must be signed in to change notification settings - Fork 35
/
vclock.go
220 lines (197 loc) · 4.52 KB
/
vclock.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
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
package vclock
import (
"bytes"
"encoding/gob"
"fmt"
"log"
"sort"
)
// Condition constants define how to compare a vector clock against another,
// and may be ORed together when being provided to the Compare method.
type Condition int
// Constants define comparison conditions between pairs of vector
// clocks
const (
Equal Condition = 1 << iota
Ancestor
Descendant
Concurrent
)
// VClock are maps of string to uint64 where the string is the
// id of the process, and the uint64 is the clock value
type VClock map[string]uint64
// FindTicks returns the clock value for a given id, if a value is not
// found false is returned
func (vc VClock) FindTicks(id string) (uint64, bool) {
ticks, ok := vc[id]
return ticks, ok
}
// New returns a new vector clock
func New() VClock {
return VClock{}
}
// Copy returns a copy of the clock
func (vc VClock) Copy() VClock {
cp := make(map[string]uint64, len(vc))
for key, value := range vc {
cp[key] = value
}
return cp
}
// CopyFromMap copies a map to a vector clock
func (vc VClock) CopyFromMap(otherMap map[string]uint64) VClock {
return otherMap
}
// GetMap returns the map typed vector clock
func (vc VClock) GetMap() map[string]uint64 {
return map[string]uint64(vc)
}
// Set assigns a clock value to a clock index
func (vc VClock) Set(id string, ticks uint64) {
vc[id] = ticks
}
// Tick has replaced the old update
func (vc VClock) Tick(id string) {
vc[id] = vc[id] + 1
}
// LastUpdate returns the clock value of the oldest clock
func (vc VClock) LastUpdate() (last uint64) {
for key := range vc {
if vc[key] > last {
last = vc[key]
}
}
return last
}
// Merge takes the max of all clock values in other and updates the
// values of the callee
func (vc VClock) Merge(other VClock) {
for id := range other {
if vc[id] < other[id] {
vc[id] = other[id]
}
}
}
// Bytes returns an encoded vector clock
func (vc VClock) Bytes() []byte {
b := new(bytes.Buffer)
enc := gob.NewEncoder(b)
err := enc.Encode(vc)
if err != nil {
log.Fatal("Vector Clock Encode:", err)
}
return b.Bytes()
}
// FromBytes decodes a vector clock
func FromBytes(data []byte) (vc VClock, err error) {
b := new(bytes.Buffer)
b.Write(data)
clock := New()
dec := gob.NewDecoder(b)
err = dec.Decode(&clock)
return clock, err
}
// PrintVC prints the callee's vector clock to stdout
func (vc VClock) PrintVC() {
fmt.Println(vc.ReturnVCString())
}
// ReturnVCString returns a string encoding of a vector clock
func (vc VClock) ReturnVCString() string {
//sort
ids := make([]string, len(vc))
i := 0
for id := range vc {
ids[i] = id
i++
}
sort.Strings(ids)
var buffer bytes.Buffer
buffer.WriteString("{")
for i := range ids {
buffer.WriteString(fmt.Sprintf("\"%s\":%d", ids[i], vc[ids[i]]))
if i+1 < len(ids) {
buffer.WriteString(", ")
}
}
buffer.WriteString("}")
return buffer.String()
}
// Compare takes another clock and determines if it is Equal,
// Ancestor, Descendant, or Concurrent with the callee's clock.
func (vc VClock) Compare(other VClock, cond Condition) bool {
var otherIs Condition
// Preliminary qualification based on length
if len(vc) > len(other) {
if cond&(Ancestor|Concurrent) == 0 {
return false
}
otherIs = Ancestor
} else if len(vc) < len(other) {
if cond&(Descendant|Concurrent) == 0 {
return false
}
otherIs = Descendant
} else {
otherIs = Equal
}
// Compare matching items
for id := range other {
if _, found := vc[id]; found {
if other[id] > vc[id] {
switch otherIs {
case Equal:
otherIs = Descendant
break
case Ancestor:
return cond&Concurrent != 0
}
} else if other[id] < vc[id] {
switch otherIs {
case Equal:
otherIs = Ancestor
break
case Descendant:
return cond&Concurrent != 0
}
}
} else {
if otherIs == Equal {
return cond&Concurrent != 0
} else if len(other) <= len(vc) {
return cond&Concurrent != 0
}
}
}
for id := range vc {
if _, found := other[id]; found {
if other[id] > vc[id] {
switch otherIs {
case Equal:
otherIs = Descendant
break
case Ancestor:
return cond&Concurrent != 0
}
} else if other[id] < vc[id] {
switch otherIs {
case Equal:
otherIs = Ancestor
break
case Descendant:
return cond&Concurrent != 0
}
}
} else {
if otherIs == Equal {
return cond&Concurrent != 0
} else if len(vc) <= len(other) {
return cond&Concurrent != 0
}
}
}
// Equal clocks are concurrent
if otherIs == Equal && cond == Concurrent {
cond = Equal
}
return cond&otherIs != 0
}