/
storage.go
114 lines (92 loc) · 2.87 KB
/
storage.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 schematic
import (
"fmt"
"math"
"math/bits"
)
const defaultBits = 2
type BitArray struct {
data []int64
//bitsPerEntry Number of bits an entry takes up
bitsPerEntry int
//maxEntryValue The maximum value for a single entry, Also works as a bitmask.
//For example, if bitPerEntry is 5, maxEntryValue would be 31( (1 << bitPerEntry) -1)
maxEntryValue int64
//Number of entries in this array(blocks number)
entrySize int
}
func NewEmptyBitArray(EntrySize int) *BitArray {
b := &BitArray{
data: nil,
bitsPerEntry: defaultBits,
maxEntryValue: (1 << defaultBits) - 1,
entrySize: EntrySize,
}
dataLen := int(math.Ceil(float64(defaultBits*EntrySize) / 64))
b.data = make([]int64, dataLen)
return b
}
func NewBitArray(bits, EntrySize int, data []int64) *BitArray {
bits = max(defaultBits, bits)
b := &BitArray{
data: data,
bitsPerEntry: bits,
maxEntryValue: (1 << bits) - 1,
entrySize: EntrySize,
}
dataLen := int(math.Ceil(float64(bits*EntrySize) / 64))
if data != nil {
if len(data) != dataLen {
panic(fmt.Errorf("data length error %d, %d", len(data), dataLen))
}
} else {
b.data = make([]int64, dataLen)
}
return b
}
func (b *BitArray) BitsPerEntry() int {
return b.bitsPerEntry
}
func (b *BitArray) getBlock(index int64) int {
return b.getAt(index)
}
func (b *BitArray) getAt(index int64) int {
startOffset := index * int64(b.bitsPerEntry)
startArrIndex := int(startOffset >> 6) // startOffset / 64
endArrIndex := int(((index+1)*int64(b.bitsPerEntry) - 1) >> 6)
startBitOffset := int(startOffset & 0x3F)
if len(b.data) <= startArrIndex {
return 0
}
if startArrIndex == endArrIndex {
return int(int64(uint(b.data[startArrIndex])>>uint(startBitOffset)) & b.maxEntryValue)
} else {
endOffset := 64 - startBitOffset
return int((int64(uint(b.data[startArrIndex])>>uint(startBitOffset)) | b.data[endArrIndex]<<endOffset) & b.maxEntryValue)
}
}
func (b *BitArray) setBlock(index int64, value int) {
if bits.Len(uint(value)) > b.BitsPerEntry() {
*b = b.resize(b.bitsPerEntry+1, b.entrySize)
}
b.setAt(index, value)
}
func (b *BitArray) setAt(index int64, value int) {
startOffset := index * int64(b.bitsPerEntry)
startArrIndex := int(startOffset >> 6)
endArrIndex := int(((index+1)*int64(b.bitsPerEntry) - 1) >> 6)
startBitOffset := int(startOffset & 0x3F)
b.data[startArrIndex] = b.data[startArrIndex] & ^(b.maxEntryValue<<startBitOffset) | (int64(value)&b.maxEntryValue)<<startBitOffset
if startArrIndex != endArrIndex {
endOffset := 64 - startBitOffset
j1 := b.bitsPerEntry - endOffset
b.data[endArrIndex] = int64(uint64(b.data[endArrIndex])>>uint64(j1))<<uint64(j1) | (int64(value)&b.maxEntryValue)>>endOffset
}
}
func (b *BitArray) resize(bits, EntrySize int) BitArray {
n := NewBitArray(bits, EntrySize, nil)
for i := 0; i < b.entrySize; i++ {
n.setAt(int64(i), b.getAt(int64(i)))
}
return *n
}