-
Notifications
You must be signed in to change notification settings - Fork 1.9k
/
bitmap.go
78 lines (66 loc) · 1.73 KB
/
bitmap.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
package structs
import "fmt"
// Bitmap is a simple uncompressed bitmap
type Bitmap []byte
// NewBitmap returns a bitmap with up to size indexes
func NewBitmap(size uint) (Bitmap, error) {
if size == 0 {
return nil, fmt.Errorf("bitmap must be positive size")
}
if size&7 != 0 {
return nil, fmt.Errorf("bitmap must be byte aligned")
}
b := make([]byte, size>>3)
return Bitmap(b), nil
}
// Copy returns a copy of the Bitmap
func (b Bitmap) Copy() (Bitmap, error) {
if b == nil {
return nil, fmt.Errorf("can't copy nil Bitmap")
}
raw := make([]byte, len(b))
copy(raw, b)
return Bitmap(raw), nil
}
// Size returns the size of the bitmap
func (b Bitmap) Size() uint {
return uint(len(b) << 3)
}
// Set is used to set the given index of the bitmap
func (b Bitmap) Set(idx uint) {
bucket := idx >> 3
mask := byte(1 << (idx & 7))
b[bucket] |= mask
}
// Unset is used to unset the given index of the bitmap
func (b Bitmap) Unset(idx uint) {
bucket := idx >> 3
// Mask should be all ones minus the idx position
offset := 1 << (idx & 7)
mask := byte(offset ^ 0xff)
b[bucket] &= mask
}
// Check is used to check the given index of the bitmap
func (b Bitmap) Check(idx uint) bool {
bucket := idx >> 3
mask := byte(1 << (idx & 7))
return (b[bucket] & mask) != 0
}
// Clear is used to efficiently clear the bitmap
func (b Bitmap) Clear() {
for i := range b {
b[i] = 0
}
}
// IndexesInRange returns the indexes in which the values are either set or unset based
// on the passed parameter in the passed range
func (b Bitmap) IndexesInRange(set bool, from, to uint) []int {
var indexes []int
for i := from; i <= to && i < b.Size(); i++ {
c := b.Check(i)
if c && set || !c && !set {
indexes = append(indexes, int(i))
}
}
return indexes
}