forked from influxdata/influxdb
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bytesutil.go
114 lines (99 loc) · 2.47 KB
/
bytesutil.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
package bytesutil
import (
"bytes"
"fmt"
"sort"
)
// Sort sorts a slice of byte slices.
func Sort(a [][]byte) {
sort.Sort(byteSlices(a))
}
func IsSorted(a [][]byte) bool {
return sort.IsSorted(byteSlices(a))
}
func SearchBytes(a [][]byte, x []byte) int {
return sort.Search(len(a), func(i int) bool { return bytes.Compare(a[i], x) >= 0 })
}
// SearchBytesFixed searches a for x using a binary search. The size of a must be a multiple of
// of x or else the function panics. There returned value is the index within a where x should
// exist. The caller should ensure that x does exist at this index.
func SearchBytesFixed(a []byte, sz int, fn func(x []byte) bool) int {
if len(a)%sz != 0 {
panic(fmt.Sprintf("x is not a multiple of a: %d %d", len(a), sz))
}
i, j := 0, len(a)-sz
for i < j {
h := int(uint(i+j) >> 1)
h -= h % sz
if !fn(a[h : h+sz]) {
i = h + sz
} else {
j = h
}
}
return i
}
// Union returns the union of a & b in sorted order.
func Union(a, b [][]byte) [][]byte {
n := len(b)
if len(a) > len(b) {
n = len(a)
}
other := make([][]byte, 0, n)
for {
if len(a) > 0 && len(b) > 0 {
if cmp := bytes.Compare(a[0], b[0]); cmp == 0 {
other, a, b = append(other, a[0]), a[1:], b[1:]
} else if cmp == -1 {
other, a = append(other, a[0]), a[1:]
} else {
other, b = append(other, b[0]), b[1:]
}
} else if len(a) > 0 {
other, a = append(other, a[0]), a[1:]
} else if len(b) > 0 {
other, b = append(other, b[0]), b[1:]
} else {
return other
}
}
}
// Intersect returns the intersection of a & b in sorted order.
func Intersect(a, b [][]byte) [][]byte {
n := len(b)
if len(a) > len(b) {
n = len(a)
}
other := make([][]byte, 0, n)
for len(a) > 0 && len(b) > 0 {
if cmp := bytes.Compare(a[0], b[0]); cmp == 0 {
other, a, b = append(other, a[0]), a[1:], b[1:]
} else if cmp == -1 {
a = a[1:]
} else {
b = b[1:]
}
}
return other
}
// Clone returns a copy of b.
func Clone(b []byte) []byte {
if b == nil {
return nil
}
buf := make([]byte, len(b))
copy(buf, b)
return buf
}
// CloneSlice returns a copy of a slice of byte slices.
func CloneSlice(a [][]byte) [][]byte {
other := make([][]byte, len(a))
for i := range a {
other[i] = Clone(a[i])
}
return other
}
type byteSlices [][]byte
func (a byteSlices) Len() int { return len(a) }
func (a byteSlices) Less(i, j int) bool { return bytes.Compare(a[i], a[j]) == -1 }
func (a byteSlices) Swap(i, j int) { a[i], a[j] = a[j], a[i] }