-
Notifications
You must be signed in to change notification settings - Fork 0
/
utils.go
102 lines (87 loc) · 2.09 KB
/
utils.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
package cachePool
type CachePad struct {
padding [8]int64 //for avoid false share
}
const (
bitsize = 32 << (^uint(0) >> 63)
maxint = int(1<<(bitsize-1) - 1)
maxintHeadBit = 1 << (bitsize - 2)
)
// LogarithmicRange iterates from ceiled to power of two min to max,
// calling cb on each iteration.
func LogarithmicRange(min, max int, cb func(int)) {
if min == 0 {
min = 1
}
for n := CeilToPowerOfTwo(min); n <= max; n <<= 1 {
cb(n)
}
}
// IsPowerOfTwo reports whether given integer is a power of two.
func IsPowerOfTwo(n int) bool {
return n&(n-1) == 0
}
// Identity is identity.
func Identity(n int) int {
return n
}
// CeilToPowerOfTwo returns the least power of two integer value greater than
// or equal to n.
func CeilToPowerOfTwo(n int) int {
if n&maxintHeadBit != 0 && n > maxintHeadBit {
panic("argument is too large")
}
if n <= 2 {
return n
}
n--
n = fillBits(n)
n++
return n
}
// FloorToPowerOfTwo returns the greatest power of two integer value less than
// or equal to n.
func FloorToPowerOfTwo(n int) int {
if n <= 2 {
return n
}
n = fillBits(n)
n >>= 1
n++
return n
}
func fillBits(n int) int {
n |= n >> 1
n |= n >> 2
n |= n >> 4
n |= n >> 8
n |= n >> 16
n |= n >> 32
return n
}
//=========
// newDefaultHasher returns a new 64-bit FNV-1a Hasher which makes no memory allocations.
// Its Sum64 method will lay the value out in big-endian byte order.
// See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
type Hasher interface {
Sum64(string) uint64
}
func newDefaultHasher() Hasher {
return fnv64a{}
}
type fnv64a struct{}
const (
// offset64 FNVa offset basis. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
offset64 = 14695981039346656037
// prime64 FNVa prime value. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
prime64 = 1099511628211
)
// Sum64 gets the string and returns its uint64 hash value.
func (f fnv64a) Sum64(key string) uint64 {
var hash uint64 = offset64
for i := 0; i < len(key); i++ {
hash ^= uint64(key[i])
hash *= prime64
}
return hash
}