vectorclock.go 2.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
  1. package sortutil
  2. import (
  3. "bytes"
  4. "fmt"
  5. "sort"
  6. )
  7. /*
  8. VectorClock implements a vector clock object. The clock can record actions
  9. of actors. Each action produces a new version which can be queried.
  10. */
  11. type VectorClock struct {
  12. versionVector map[string]uint64 // Data for the cache
  13. }
  14. /*
  15. NewVectorClock creates a new vector clock datastructure.
  16. */
  17. func NewVectorClock() *VectorClock {
  18. return &VectorClock{make(map[string]uint64)}
  19. }
  20. /*
  21. CloneVectorClock clones an existing vector clock.
  22. */
  23. func CloneVectorClock(vc *VectorClock) *VectorClock {
  24. newVC := NewVectorClock()
  25. for actor, version := range vc.versionVector {
  26. newVC.versionVector[actor] = version
  27. }
  28. return newVC
  29. }
  30. /*
  31. NewDescendant creates a vector clock which is a descendant of all given vector clocks.
  32. */
  33. func NewDescendant(otherVCs ...*VectorClock) *VectorClock {
  34. newVC := NewVectorClock()
  35. for _, otherVC := range otherVCs {
  36. for actor, version := range otherVC.versionVector {
  37. if newVC.Version(actor) < version {
  38. newVC.versionVector[actor] = version
  39. }
  40. }
  41. }
  42. return newVC
  43. }
  44. /*
  45. Act records an action of an actor.
  46. */
  47. func (vc *VectorClock) Act(actor string) {
  48. if _, ok := vc.versionVector[actor]; ok {
  49. vc.versionVector[actor]++
  50. } else {
  51. vc.versionVector[actor] = 1
  52. }
  53. }
  54. /*
  55. Version returns the current version for a given actor.
  56. */
  57. func (vc *VectorClock) Version(actor string) uint64 {
  58. if v, ok := vc.versionVector[actor]; ok {
  59. return v
  60. }
  61. return 0
  62. }
  63. /*
  64. IsDescendent determines if another vector clock is a descendent of this vector clock.
  65. */
  66. func (vc *VectorClock) IsDescendent(otherVC *VectorClock) bool {
  67. // In order for vc to be considered a descendant of otherVC, each marker
  68. // in otherVC must have a corresponding marker in vc that has a revision
  69. // number greater than or equal to the marker in otherVC.
  70. for actor, version := range otherVC.versionVector {
  71. if vc.Version(actor) < version {
  72. return false
  73. }
  74. }
  75. return true
  76. }
  77. /*
  78. IsConflicting determines if another vector clock is conflicting with this vector clock.
  79. */
  80. func (vc *VectorClock) IsConflicting(otherVC *VectorClock) bool {
  81. return !(vc.IsDescendent(otherVC) || otherVC.IsDescendent(vc))
  82. }
  83. /*
  84. String returns a string representation of this vector clock.
  85. */
  86. func (vc *VectorClock) String() string {
  87. var actors []string
  88. for actor := range vc.versionVector {
  89. actors = append(actors, actor)
  90. }
  91. sort.Strings(actors)
  92. buf := &bytes.Buffer{}
  93. for _, actor := range actors {
  94. version := vc.versionVector[actor]
  95. buf.WriteString(fmt.Sprint(actor, ":", version, "\n"))
  96. }
  97. return buf.String()
  98. }