1package structs 2 3import "fmt" 4 5// Bitmap is a simple uncompressed bitmap 6type Bitmap []byte 7 8// NewBitmap returns a bitmap with up to size indexes 9func NewBitmap(size uint) (Bitmap, error) { 10 if size == 0 { 11 return nil, fmt.Errorf("bitmap must be positive size") 12 } 13 if size&7 != 0 { 14 return nil, fmt.Errorf("bitmap must be byte aligned") 15 } 16 b := make([]byte, size>>3) 17 return Bitmap(b), nil 18} 19 20// Copy returns a copy of the Bitmap 21func (b Bitmap) Copy() (Bitmap, error) { 22 if b == nil { 23 return nil, fmt.Errorf("can't copy nil Bitmap") 24 } 25 26 raw := make([]byte, len(b)) 27 copy(raw, b) 28 return Bitmap(raw), nil 29} 30 31// Size returns the size of the bitmap 32func (b Bitmap) Size() uint { 33 return uint(len(b) << 3) 34} 35 36// Set is used to set the given index of the bitmap 37func (b Bitmap) Set(idx uint) { 38 bucket := idx >> 3 39 mask := byte(1 << (idx & 7)) 40 b[bucket] |= mask 41} 42 43// Unset is used to unset the given index of the bitmap 44func (b Bitmap) Unset(idx uint) { 45 bucket := idx >> 3 46 // Mask should be all ones minus the idx position 47 offset := 1 << (idx & 7) 48 mask := byte(offset ^ 0xff) 49 b[bucket] &= mask 50} 51 52// Check is used to check the given index of the bitmap 53func (b Bitmap) Check(idx uint) bool { 54 bucket := idx >> 3 55 mask := byte(1 << (idx & 7)) 56 return (b[bucket] & mask) != 0 57} 58 59// Clear is used to efficiently clear the bitmap 60func (b Bitmap) Clear() { 61 for i := range b { 62 b[i] = 0 63 } 64} 65 66// IndexesInRange returns the indexes in which the values are either set or unset based 67// on the passed parameter in the passed range 68func (b Bitmap) IndexesInRange(set bool, from, to uint) []int { 69 var indexes []int 70 for i := from; i <= to && i < b.Size(); i++ { 71 c := b.Check(i) 72 if c && set || !c && !set { 73 indexes = append(indexes, int(i)) 74 } 75 } 76 77 return indexes 78} 79