-
Notifications
You must be signed in to change notification settings - Fork 0
/
sparse.go
90 lines (67 loc) · 2.03 KB
/
sparse.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
package bitset
import (
"math"
"unsafe"
)
// setnode defines a sparse node with all bits set
type setnode struct{}
func newSparseSet(l *level) *setnode {
return (*setnode)(unsafe.Pointer(uintptr(math.MaxUint64)))
}
func newSparseClr(l *level) *clrnode {
return (*clrnode)(nil)
}
func (sn *setnode) test(l *level, idx uint64) (set bool) {
return true // set
}
func (sn *setnode) set(l *level, idx uint64) (set bool, replace node) {
// set on a set-node -> no-op
return false, sn
}
func (sn *setnode) clr(l *level, idx uint64) (cleared bool, replace node) {
// desparsify and do 'set' on the new node
return desparsify(l, sn, true).clr(l, idx)
}
func (sn *setnode) nextset(l *level, start uint64) (idx uint64, found bool) {
return start, true
}
func (sn *setnode) prevset(l *level, start uint64) (idx uint64, found bool) {
if start >= uint64(l.total) {
return uint64(l.total - 1), true
}
return start, true
}
func (sn *setnode) nextclr(l *level, start uint64) (idx uint64, found bool) {
return math.MaxUint64, false
}
func (sn *setnode) prevclr(l *level, start uint64) (idx uint64, found bool) {
return 0, false
}
// clrnode defines a sparse node with all bits clear
type clrnode struct{}
func (cn *clrnode) test(l *level, idx uint64) (set bool) {
return false // clear
}
func (cn *clrnode) set(l *level, idx uint64) (set bool, replace node) {
// desparsify and do 'set' on the new node
return desparsify(l, cn, false).set(l, idx)
}
func (cn *clrnode) clr(l *level, idx uint64) (cleared bool, replace node) {
// clear on a clr-node -> no-op
return false, cn
}
func (cn *clrnode) nextset(l *level, start uint64) (idx uint64, found bool) {
return math.MaxUint64, false
}
func (cn *clrnode) prevset(l *level, start uint64) (idx uint64, found bool) {
return 0, false
}
func (cn *clrnode) nextclr(l *level, start uint64) (idx uint64, found bool) {
return start, true
}
func (cn *clrnode) prevclr(l *level, start uint64) (idx uint64, found bool) {
if start >= uint64(l.total) {
return uint64(l.total - 1), true
}
return start, true
}