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 5 package gc 6 7 const ( 8 wordBits = 32 9 wordMask = wordBits - 1 10 wordShift = 5 11 ) 12 13 // A bvec is a bit vector. 14 type bvec struct { 15 n int32 // number of bits in vector 16 b []uint32 // words holding bits 17 } 18 19 func bvalloc(n int32) bvec { 20 nword := (n + wordBits - 1) / wordBits 21 return bvec{n, make([]uint32, nword)} 22 } 23 24 type bulkBvec struct { 25 words []uint32 26 nbit int32 27 nword int32 28 } 29 30 func 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 43 func (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 49 func (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 61 func (dst bvec) Copy(src bvec) { 62 copy(dst.b, src.b) 63 } 64 65 func (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 73 func (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 81 func (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. 91 func (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 120 func (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 129 func (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 138 func (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 145 func (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 152 func (dst bvec) AndNot(src1, src2 bvec) { 153 for i, x := range src1.b { 154 dst.b[i] = x &^ src2.b[i] 155 } 156 } 157 158 func (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 171 func (bv bvec) Clear() { 172 for i := range bv.b { 173 bv.b[i] = 0 174 } 175 } 176
