bitset/node.go at master · kirg/bitset · GitHub

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
package bitset

type (
	// node is the interface that is implemented by the four types of nodes:
	// - leaf (leaf node, actual storage for bits in []uint64)
	// - inode (intermediate nodes in the tree)
	// - setnode (sparse node that indicates everything under is "set")
	// - clrnode (sparse node that indicates everything under is "clear")
	node interface {
		test(l *level, idx uint64) (set bool)
		set(l *level, idx uint64) (set bool, replace node)
		clr(l *level, idx uint64) (cleared bool, replace node)
		nextset(l *level, start uint64) (idx uint64, found bool)
		nextclr(l *level, start uint64) (idx uint64, found bool)
		prevset(l *level, start uint64) (idx uint64, found bool)
		prevclr(l *level, start uint64) (idx uint64, found bool)
	}
)

func newNode(l *level, sparse, set bool) (n node) {

	if sparse {

		if set {
			return newSparseSet(l)
		}

		return newSparseClr(l)
	}

	// non-sparse node, so count
	l.numNodes++ // #stats

	if l.leaf {

		if set {
			return newLeafSet(l)
		}

		return newLeafClr(l)
	}

	if set {
		return newInodeSet(l)
	}

	return newInodeClr(l)
}

func delNode(l *level, n node) {

	// FIXME: avoid type switch (for perf)?
	switch n.(type) {
	case *setnode:
		return

	case *clrnode:
		return

	case *inode:

		l.numNodes--

		in := n.(*inode)
		for _, nx := range in.nodes {
			delNode(l.next, nx)
		}

	case *leaf:
		l.numNodes--
	}
}

// returns an allset/allclr sparse-node to replace given node
func sparsify(l *level, n node, set bool) (replace node) {

	delNode(l, n)
	return newNode(l, true, set)
}

// returns an allset/allclr 'full' node to replace a sparse node
func desparsify(l *level, n node, set bool) (replace node) {

	delNode(l, n)
	return newNode(l, false, set)
}