-
Notifications
You must be signed in to change notification settings - Fork 338
/
epoch.go
104 lines (88 loc) · 2.65 KB
/
epoch.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
// Copyright 2021 The Swarm Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package epochs implements time-based feeds using epochs as index
// and provide sequential as well as concurrent lookup algorithms
package epochs
import (
"encoding/binary"
"fmt"
"github.com/ethersphere/bee/pkg/crypto"
"github.com/ethersphere/bee/pkg/feeds"
)
const (
maxLevel = 32
)
var _ feeds.Index = (*epoch)(nil)
// epoch is referencing a slot in the epoch grid and represents an update
// it implements the feeds.Index interface
type epoch struct {
start uint64
level uint8
}
func (e *epoch) String() string {
return fmt.Sprintf("%d/%d", e.start, e.level)
}
// MarshalBinary implements the BinaryMarshaler interface
func (e *epoch) MarshalBinary() ([]byte, error) {
epochBytes := make([]byte, 8)
binary.BigEndian.PutUint64(epochBytes, e.start)
return crypto.LegacyKeccak256(append(epochBytes, e.level))
}
func next(e feeds.Index, last int64, at uint64) feeds.Index {
if e == nil {
return &epoch{0, maxLevel}
}
return e.Next(last, at)
}
// Next implements feeds.Index advancement
func (e *epoch) Next(last int64, at uint64) feeds.Index {
if e.start+e.length() > at {
return e.childAt(at)
}
return lca(at, uint64(last)).childAt(at)
}
// lca calculates the lowest common ancestor epoch given two unix times
func lca(at, after uint64) *epoch {
if after == 0 {
return &epoch{0, maxLevel}
}
diff := at - after
length := uint64(1)
var level uint8
for level < maxLevel && (length < diff || at/length != after/length) {
length <<= 1
level++
}
start := (after / length) * length
return &epoch{start, level}
}
// parent returns the ancestor of an epoch
// the call is unsafe in that it must not be called on a toplevel epoch
func (e *epoch) parent() *epoch {
length := e.length() << 1
start := (e.start / length) * length
return &epoch{start, e.level + 1}
}
// left returns the left sister of an epoch
// it is unsafe in that it must not be called on a left sister epoch
func (e *epoch) left() *epoch {
return &epoch{e.start - e.length(), e.level}
}
// at returns the left of right child epoch of an epoch depending on where `at` falls
// it is unsafe in that it must not be called with an at that does not fall within the epoch
func (e *epoch) childAt(at uint64) *epoch {
e = &epoch{e.start, e.level - 1}
if at&e.length() > 0 {
e.start |= e.length()
}
return e
}
// isLeft returns true if epoch is a left sister of its parent
func (e *epoch) isLeft() bool {
return e.start&e.length() == 0
}
// length returns the span of the epoch
func (e *epoch) length() uint64 {
return 1 << e.level
}