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