-
Notifications
You must be signed in to change notification settings - Fork 10
/
bin.go
86 lines (68 loc) · 1.6 KB
/
bin.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
package quantile
import (
"math"
"strings"
)
const (
maxBinWidth = math.MaxUint16
)
type bin struct {
k Key
n uint16
}
// incrSafe performs `b.n += by` safely handling overflows. When an overflow
// occurs, we set b.n to it's max, and return the leftover amount to increment.
func (b *bin) incrSafe(by int) int {
next := by + int(b.n)
if next > maxBinWidth {
b.n = maxBinWidth
return next - maxBinWidth
}
b.n = uint16(next)
return 0
}
// appendSafe appends 1 or more bins with the given key safely handing overflow by
// inserting multiple buckets when needed.
// (1) n <= maxBinWidth : 1 bin
// (2) n > maxBinWidth : >1 bin
func appendSafe(bins []bin, k Key, n int) []bin {
if n <= maxBinWidth {
return append(bins, bin{k: k, n: uint16(n)})
}
// on overflow, insert multiple bins with the same key.
// put full bins at end
// TODO|PROD: Add validation func that sorts by key and then n (smaller bin first).
r := uint16(n % maxBinWidth)
if r != 0 {
bins = append(bins, bin{k: k, n: r})
}
for i := 0; i < int(n/maxBinWidth); i++ {
bins = append(bins, bin{k: k, n: maxBinWidth})
}
return bins
}
type binList []bin
func (bins binList) nSum() int {
s := 0
for _, b := range bins {
s += int(b.n)
}
return s
}
func (bins binList) Cap() int {
return cap(bins)
}
func (bins binList) Len() int {
return len(bins)
}
func (bins binList) ensureLen(newLen int) binList {
for cap(bins) < newLen {
bins = append(bins[:cap(bins)], bin{})
}
return bins[:newLen]
}
func (bins binList) String() string {
var w strings.Builder
printBins(&w, bins, defaultBinPerLine)
return w.String()
}