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
|
package bitmap
import (
"math/bits"
)
// bitmap is a lazily initialized bitmap
type Bitmap struct {
max uint32
bits []uint64
}
func New(max uint32) *Bitmap {
return &Bitmap{max: max}
}
// add sets n in the bitmap.
//
// bits will be expanded as needed.
//
// If n is greater than max, the call has no effect.
func (b *Bitmap) Add(n uint32) {
if n > b.max {
return
}
var (
idx = n / 64
offset = n % 64
)
if l := len(b.bits); int(idx) >= l {
b.bits = append(b.bits, make([]uint64, int(idx)-l+1)...)
}
b.bits[idx] |= 1 << offset
}
// remove clears n from the bitmap.
//
// If n is not set or greater than max the call has not effect.
func (b *Bitmap) Remove(n uint32) {
var (
idx = n / 64
offset = n % 64
)
if int(idx) >= len(b.bits) {
return
}
b.bits[idx] &= ^uint64(1 << offset)
}
// next sets and returns the lowest unset bit in the bitmap.
//
// bits will be expanded if necessary.
//
// If there are no unset bits below max, the second return
// value will be false.
func (b *Bitmap) Next() (uint32, bool) {
// find the first unset bit
for i, v := range b.bits {
// skip if all bits are set
if v == ^uint64(0) {
continue
}
var (
offset = bits.TrailingZeros64(^v) // invert and count zeroes
next = uint32(i*64 + offset)
)
// check if in bounds
if next > b.max {
return next, false
}
// set bit
b.bits[i] |= 1 << uint32(offset)
return next, true
}
// no unset bits in the current slice,
// check if the full range has been allocated
if uint64(len(b.bits)*64) > uint64(b.max) {
return 0, false
}
// full range not allocated, append entry with first
// bit set
b.bits = append(b.bits, 1)
// return the value of the first bit
return uint32(len(b.bits)-1) * 64, true
}
|
