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
115
116
117
118
119
120
121
122
123
124
|
package dynamic_bit_array
import "core:intrinsics"
/*
Note that these constants are dependent on the backing being a u64.
*/
@(private="file")
INDEX_SHIFT :: 6
@(private="file")
INDEX_MASK :: 63
Bit_Array :: struct {
bits: [dynamic]u64,
bias: int,
}
/*
In:
- ba: ^Bit_Array - a pointer to the Bit Array
- index: The bit index. Can be an enum member.
Out:
- res: The bit you're interested in.
- ok: Whether the index was valid. Returns `false` if the index is smaller than the bias.
The `ok` return value may be ignored.
*/
get :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator) -> (res: bool, ok: bool) {
idx := int(index) - ba.bias
if ba == nil || int(index) < ba.bias { return false, false }
context.allocator = allocator
leg_index := idx >> INDEX_SHIFT
bit_index := idx & INDEX_MASK
/*
If we `get` a bit that doesn't fit in the Bit Array, it's naturally `false`.
This early-out prevents unnecessary resizing.
*/
if leg_index + 1 > len(ba.bits) { return false, true }
val := u64(1 << uint(bit_index))
res = ba.bits[leg_index] & val == val
return res, true
}
/*
In:
- ba: ^Bit_Array - a pointer to the Bit Array
- index: The bit index. Can be an enum member.
Out:
- ok: Whether or not we managed to set requested bit.
`set` automatically resizes the Bit Array to accommodate the requested index if needed.
*/
set :: proc(ba: ^Bit_Array, #any_int index: uint, allocator := context.allocator) -> (ok: bool) {
idx := int(index) - ba.bias
if ba == nil || int(index) < ba.bias { return false }
context.allocator = allocator
leg_index := idx >> INDEX_SHIFT
bit_index := idx & INDEX_MASK
resize_if_needed(ba, leg_index) or_return
ba.bits[leg_index] |= 1 << uint(bit_index)
return true
}
/*
A helper function to create a Bit Array with optional bias, in case your smallest index is non-zero (including negative).
*/
create :: proc(max_index: int, min_index := 0, allocator := context.allocator) -> (res: Bit_Array, ok: bool) #optional_ok {
context.allocator = allocator
size_in_bits := max_index - min_index
if size_in_bits < 1 { return {}, false }
legs := size_in_bits >> INDEX_SHIFT
res = Bit_Array{
bias = min_index,
}
return res, resize_if_needed(&res, size_in_bits)
}
/*
Sets all bits to `false`.
*/
clear :: proc(ba: ^Bit_Array) {
if ba == nil { return }
ba.bits = {}
}
/*
Releases the memory used by the Bit Array.
*/
destroy :: proc(ba: ^Bit_Array) {
if ba == nil { return }
delete(ba.bits)
}
/*
Resizes the Bit Array. For internal use.
If you want to reserve the memory for a given-sized Bit Array up front, you can use `create`.
*/
@(private="file")
resize_if_needed :: proc(ba: ^Bit_Array, legs: int, allocator := context.allocator) -> (ok: bool) {
if ba == nil { return false }
context.allocator = allocator
if legs + 1 > len(ba.bits) {
resize(&ba.bits, legs + 1)
}
return len(ba.bits) > legs
}
|
