1// Copyright 2013 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package gc
6
7const (
8	WORDBITS  = 32
9	WORDMASK  = WORDBITS - 1
10	WORDSHIFT = 5
11)
12
13// A bvec is a bit vector.
14type bvec struct {
15	n int32    // number of bits in vector
16	b []uint32 // words holding bits
17}
18
19func bvalloc(n int32) bvec {
20	nword := (n + WORDBITS - 1) / WORDBITS
21	return bvec{n, make([]uint32, nword)}
22}
23
24type bulkBvec struct {
25	words []uint32
26	nbit  int32
27	nword int32
28}
29
30func bvbulkalloc(nbit int32, count int32) bulkBvec {
31	nword := (nbit + WORDBITS - 1) / WORDBITS
32	size := int64(nword) * int64(count)
33	if int64(int32(size*4)) != size*4 {
34		Fatalf("bvbulkalloc too big: nbit=%d count=%d nword=%d size=%d", nbit, count, nword, size)
35	}
36	return bulkBvec{
37		words: make([]uint32, size),
38		nbit:  nbit,
39		nword: nword,
40	}
41}
42
43func (b *bulkBvec) next() bvec {
44	out := bvec{b.nbit, b.words[:b.nword]}
45	b.words = b.words[b.nword:]
46	return out
47}
48
49func (bv1 bvec) Eq(bv2 bvec) bool {
50	if bv1.n != bv2.n {
51		Fatalf("bvequal: lengths %d and %d are not equal", bv1.n, bv2.n)
52	}
53	for i, x := range bv1.b {
54		if x != bv2.b[i] {
55			return false
56		}
57	}
58	return true
59}
60
61func (dst bvec) Copy(src bvec) {
62	copy(dst.b, src.b)
63}
64
65func (bv bvec) Get(i int32) bool {
66	if i < 0 || i >= bv.n {
67		Fatalf("bvget: index %d is out of bounds with length %d\n", i, bv.n)
68	}
69	mask := uint32(1 << uint(i%WORDBITS))
70	return bv.b[i>>WORDSHIFT]&mask != 0
71}
72
73func (bv bvec) Set(i int32) {
74	if i < 0 || i >= bv.n {
75		Fatalf("bvset: index %d is out of bounds with length %d\n", i, bv.n)
76	}
77	mask := uint32(1 << uint(i%WORDBITS))
78	bv.b[i/WORDBITS] |= mask
79}
80
81func (bv bvec) Unset(i int32) {
82	if i < 0 || i >= bv.n {
83		Fatalf("bvunset: index %d is out of bounds with length %d\n", i, bv.n)
84	}
85	mask := uint32(1 << uint(i%WORDBITS))
86	bv.b[i/WORDBITS] &^= mask
87}
88
89// bvnext returns the smallest index >= i for which bvget(bv, i) == 1.
90// If there is no such index, bvnext returns -1.
91func (bv bvec) Next(i int32) int32 {
92	if i >= bv.n {
93		return -1
94	}
95
96	// Jump i ahead to next word with bits.
97	if bv.b[i>>WORDSHIFT]>>uint(i&WORDMASK) == 0 {
98		i &^= WORDMASK
99		i += WORDBITS
100		for i < bv.n && bv.b[i>>WORDSHIFT] == 0 {
101			i += WORDBITS
102		}
103	}
104
105	if i >= bv.n {
106		return -1
107	}
108
109	// Find 1 bit.
110	w := bv.b[i>>WORDSHIFT] >> uint(i&WORDMASK)
111
112	for w&1 == 0 {
113		w >>= 1
114		i++
115	}
116
117	return i
118}
119
120func (bv bvec) IsEmpty() bool {
121	for i := int32(0); i < bv.n; i += WORDBITS {
122		if bv.b[i>>WORDSHIFT] != 0 {
123			return false
124		}
125	}
126	return true
127}
128
129func (bv bvec) Not() {
130	i := int32(0)
131	w := int32(0)
132	for ; i < bv.n; i, w = i+WORDBITS, w+1 {
133		bv.b[w] = ^bv.b[w]
134	}
135}
136
137// union
138func (dst bvec) Or(src1, src2 bvec) {
139	for i, x := range src1.b {
140		dst.b[i] = x | src2.b[i]
141	}
142}
143
144// intersection
145func (dst bvec) And(src1, src2 bvec) {
146	for i, x := range src1.b {
147		dst.b[i] = x & src2.b[i]
148	}
149}
150
151// difference
152func (dst bvec) AndNot(src1, src2 bvec) {
153	for i, x := range src1.b {
154		dst.b[i] = x &^ src2.b[i]
155	}
156}
157
158func (bv bvec) String() string {
159	s := make([]byte, 2+bv.n)
160	copy(s, "#*")
161	for i := int32(0); i < bv.n; i++ {
162		ch := byte('0')
163		if bv.Get(i) {
164			ch = '1'
165		}
166		s[2+i] = ch
167	}
168	return string(s)
169}
170
171func (bv bvec) Clear() {
172	for i := range bv.b {
173		bv.b[i] = 0
174	}
175}
176