-
Notifications
You must be signed in to change notification settings - Fork 0
/
random.go
143 lines (121 loc) · 3.23 KB
/
random.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
package link
import (
"bytes"
"crypto/rand"
"encoding/hex"
"errors"
"fmt"
"io"
"github.com/go-camp/link/internal"
)
// rid is an implementation of ID interface that based on random.
//
// 169 226 114 183 120 39 195 42 120 94 39 52 42 207 209 104 10 31 128 1
// |------------------------> root <-------------------------| child child |--child--|
//
// 16 bytes varint64 varint64 varint64
// random index index index
// 10 31 128
//
// 32 hex chars hex hex hex
// a9e272b77827c32a785e27342acfd168 0a 1f 8001
type rid []byte
// ridRootSize is root(min) rid bytes length.
const ridRootSize = 16
var ridZero rid
func (id rid) IsZero() bool { return len(id) == 0 }
func (id rid) copyN(n int) ID {
return append(rid(nil), id[:n]...)
}
func (id rid) Parent() ID {
if id.IsZero() || id.IsRoot() {
return ridZero
}
return id.copyN(len(id) - internal.VarintSizeInLastBytes(id[ridRootSize:]))
}
func (id rid) Index() (index uint64) {
if !id.IsZero() {
index, _ = internal.ReadVarintLast(id[ridRootSize:])
}
return
}
func (id rid) Child(index uint64) ID {
child := make(rid, len(id)+internal.VarintSize(index))
copy(child, id)
internal.PutVarint(child[len(id):], index)
return child
}
func (id rid) IsRoot() bool { return len(id) == ridRootSize }
func (id rid) Root() ID {
return id.copyN(ridRootSize)
}
func (id rid) Chain() (chain []ID) {
if id.IsZero() {
return nil
}
chain = append(chain, id.Root())
for i := ridRootSize; i < len(id); {
n := i + internal.VarintSizeInBytes(id[i:])
chain = append(chain, id.copyN(n))
i = n
}
return
}
func (id rid) Deep() (deep int) {
if id.IsZero() {
return -1
}
for i := ridRootSize; i < len(id); {
i += internal.VarintSizeInBytes(id[i:])
deep++
}
return
}
func (id rid) Equal(xid ID) bool {
if xid == nil {
return false
}
cxid, ok := xid.(rid)
if !ok {
return false
}
return bytes.Equal(id, cxid)
}
func (id rid) String() string {
return hex.EncodeToString(id)
}
// NewRandom creates an new random root id based on given reader.
// If err is not nil, root is nil.
func NewRandomFromReader(reader io.Reader) (root ID, err error) {
id := make(rid, ridRootSize)
_, err = io.ReadFull(reader, id)
if err != nil {
return
}
root = id
return
}
// NewRandom creates an new random root id based on crypto/rand.Reader.
// If err is not nil, root is nil.
func NewRandom() (root ID, err error) {
return NewRandomFromReader(rand.Reader)
}
// ParseRandom decodes hex encoded sid into an id.
func ParseRandom(sid string) (ID, error) {
var did []byte
did, err := hex.DecodeString(sid)
if err != nil {
return nil, err
}
if len(did) < ridRootSize {
return nil, fmt.Errorf("decoded id is shorter than root(min) id size %d", ridRootSize)
}
for i := ridRootSize; i < len(did); {
s := internal.VarintSizeInBytes(did[i:])
if s <= 0 {
return nil, errors.New("invalid id format")
}
i += s
}
return rid(did), nil
}