forked from bozaro/tech-db-forum
-
Notifications
You must be signed in to change notification settings - Fork 13
/
shortid.go
150 lines (136 loc) · 4.14 KB
/
shortid.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
package tests
import (
"math"
"math/rand"
"sync"
"time"
)
// Алфавит
type Abc struct {
alphabet []rune
bits float64
}
// Идентификатор
type Shortid struct {
abc Abc
rnd *rand.Rand
epoch time.Time // Начало времен
ms uint // Время генерации последнего значения
count uint // Кол-во идентификаторов в рамках одой и той же мс.
mx sync.Mutex // Блокировка для конкурентного доступа
}
// Создание нового генератора
func NewShortid(alphabet string) *Shortid {
return &Shortid{
rnd: rand.New(rand.NewSource(time.Now().UnixNano())),
abc: NewAbc(alphabet),
epoch: time.Date(2017, time.January, 1, 0, 0, 0, 0, time.UTC),
ms: 0,
count: 0,
}
}
func (sid *Shortid) Generate() string {
for true {
idrunes := sid.GenerateRandom()
valid := false
for c := range idrunes {
if (c >= 'a') || (c <= 'z') {
valid = true
break
}
}
if valid {
rnd := sid.rnd.Int()
flg := 1
for i, c := range idrunes {
if (c >= 'a') && (c <= 'z') {
if rnd&flg == 0 {
idrunes[i] = c + 'A' - 'a'
}
flg <<= 1
if flg == 0 {
flg = 1
}
}
}
return string(idrunes)
}
}
panic("Unreacheable code")
}
// Generate generates a new short Id.
func (sid *Shortid) GenerateRandom() []rune {
sid.mx.Lock()
defer sid.mx.Unlock()
ms, count := sid.getMsAndCounter(sid.epoch)
idrunes := sid.abc.Encode(sid.rnd, ms, 40)
if count > 0 {
idrunes = append(idrunes, sid.abc.Encode(sid.rnd, count, 0)...)
}
return idrunes
}
func (sid *Shortid) getMsAndCounter(epoch time.Time) (uint, uint) {
ms := uint(time.Now().Sub(epoch).Nanoseconds() / 1000000)
if ms <= sid.ms {
sid.count++
} else {
sid.count = 0
sid.ms = ms
}
return sid.ms, sid.count
}
// Abc returns the instance of alphabet used for representing the Ids.
func (sid *Shortid) Abc() Abc {
return sid.abc
}
// Epoch returns the value of epoch used as the beginning of millisecond counting (normally
// 2016-01-01 00:00:00 local time)
func (sid *Shortid) Epoch() time.Time {
return sid.epoch
}
// NewAbc constructs a new instance of shuffled alphabet to be used for Id representation.
func NewAbc(alphabet string) Abc {
abc := Abc{alphabet: nil, bits: math.Log2(float64(len(alphabet)))}
abc.shuffle(alphabet, 0)
return abc
}
func (abc *Abc) shuffle(alphabet string, seed uint64) {
source := []rune(alphabet)
for len(source) > 1 {
seed = (seed*9301 + 49297) % 233280
i := int(seed * uint64(len(source)) / 233280)
abc.alphabet = append(abc.alphabet, source[i])
source = append(source[:i], source[i+1:]...)
}
abc.alphabet = append(abc.alphabet, source[0])
}
// Encode encodes a given value into a slice of runes of length nsymbols. In case nsymbols==0, the
// length of the result is automatically computed from data. Even if fewer symbols is required to
// encode the data than nsymbols, all positions are used encoding 0 where required to guarantee
// uniqueness in case further data is added to the sequence. The value of digits [4,6] represents
// represents n in 2^n, which defines how much randomness flows into the algorithm: 4 -- every value
// can be represented by 4 symbols in the alphabet (permitting at most 16 values), 5 -- every value
// can be represented by 2 symbols in the alphabet (permitting at most 32 values), 6 -- every value
// is represented by exactly 1 symbol with no randomness (permitting 64 values).
func (abc *Abc) Encode(rnd *rand.Rand, val, bits uint) []rune {
nsymbols := uint(0)
randBits := uint(2)
if bits > 0 {
nsymbols = uint(math.Ceil(float64(bits) / (abc.bits - float64(randBits))))
} else if val > 0 {
nsymbols = uint(math.Ceil(math.Log2(float64(val+1)) / (abc.bits - float64(randBits))))
}
if nsymbols == 0 {
return []rune{}
}
// no random component if digits == 6
res := make([]rune, int(nsymbols))
data := val
for i := range res {
index := data % uint(len(abc.alphabet)>>randBits)
index = (index << randBits) | uint(rnd.Int31n(1<<randBits))
res[i] = abc.alphabet[index]
data /= uint(len(abc.alphabet) >> randBits)
}
return res
}