blob: e32ab97ad52d2df06b3fe0f6cd9c0c9ac8ff6523 [file] [log] [blame]
 // Copyright 2013 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package gc import ( "math/bits" ) const ( wordBits = 32 wordMask = wordBits - 1 wordShift = 5 ) // A bvec is a bit vector. type bvec struct { n int32 // number of bits in vector b []uint32 // words holding bits } func bvalloc(n int32) bvec { nword := (n + wordBits - 1) / wordBits return bvec{n, make([]uint32, nword)} } type bulkBvec struct { words []uint32 nbit int32 nword int32 } func bvbulkalloc(nbit int32, count int32) bulkBvec { nword := (nbit + wordBits - 1) / wordBits size := int64(nword) * int64(count) if int64(int32(size*4)) != size*4 { Fatalf("bvbulkalloc too big: nbit=%d count=%d nword=%d size=%d", nbit, count, nword, size) } return bulkBvec{ words: make([]uint32, size), nbit: nbit, nword: nword, } } func (b *bulkBvec) next() bvec { out := bvec{b.nbit, b.words[:b.nword]} b.words = b.words[b.nword:] return out } func (bv1 bvec) Eq(bv2 bvec) bool { if bv1.n != bv2.n { Fatalf("bvequal: lengths %d and %d are not equal", bv1.n, bv2.n) } for i, x := range bv1.b { if x != bv2.b[i] { return false } } return true } func (dst bvec) Copy(src bvec) { copy(dst.b, src.b) } func (bv bvec) Get(i int32) bool { if i < 0 || i >= bv.n { Fatalf("bvget: index %d is out of bounds with length %d\n", i, bv.n) } mask := uint32(1 << uint(i%wordBits)) return bv.b[i>>wordShift]&mask != 0 } func (bv bvec) Set(i int32) { if i < 0 || i >= bv.n { Fatalf("bvset: index %d is out of bounds with length %d\n", i, bv.n) } mask := uint32(1 << uint(i%wordBits)) bv.b[i/wordBits] |= mask } func (bv bvec) Unset(i int32) { if i < 0 || i >= bv.n { Fatalf("bvunset: index %d is out of bounds with length %d\n", i, bv.n) } mask := uint32(1 << uint(i%wordBits)) bv.b[i/wordBits] &^= mask } // bvnext returns the smallest index >= i for which bvget(bv, i) == 1. // If there is no such index, bvnext returns -1. func (bv bvec) Next(i int32) int32 { if i >= bv.n { return -1 } // Jump i ahead to next word with bits. if bv.b[i>>wordShift]>>uint(i&wordMask) == 0 { i &^= wordMask i += wordBits for i < bv.n && bv.b[i>>wordShift] == 0 { i += wordBits } } if i >= bv.n { return -1 } // Find 1 bit. w := bv.b[i>>wordShift] >> uint(i&wordMask) i += int32(bits.TrailingZeros32(w)) return i } func (bv bvec) IsEmpty() bool { for _, x := range bv.b { if x != 0 { return false } } return true } func (bv bvec) Not() { for i, x := range bv.b { bv.b[i] = ^x } } // union func (dst bvec) Or(src1, src2 bvec) { if len(src1.b) == 0 { return } _, _ = dst.b[len(src1.b)-1], src2.b[len(src1.b)-1] // hoist bounds checks out of the loop for i, x := range src1.b { dst.b[i] = x | src2.b[i] } } // intersection func (dst bvec) And(src1, src2 bvec) { if len(src1.b) == 0 { return } _, _ = dst.b[len(src1.b)-1], src2.b[len(src1.b)-1] // hoist bounds checks out of the loop for i, x := range src1.b { dst.b[i] = x & src2.b[i] } } // difference func (dst bvec) AndNot(src1, src2 bvec) { if len(src1.b) == 0 { return } _, _ = dst.b[len(src1.b)-1], src2.b[len(src1.b)-1] // hoist bounds checks out of the loop for i, x := range src1.b { dst.b[i] = x &^ src2.b[i] } } func (bv bvec) String() string { s := make([]byte, 2+bv.n) copy(s, "#*") for i := int32(0); i < bv.n; i++ { ch := byte('0') if bv.Get(i) { ch = '1' } s[2+i] = ch } return string(s) } func (bv bvec) Clear() { for i := range bv.b { bv.b[i] = 0 } } // FNV-1 hash function constants. const ( H0 = 2166136261 Hp = 16777619 ) func hashbitmap(h uint32, bv bvec) uint32 { n := int((bv.n + 31) / 32) for i := 0; i < n; i++ { w := bv.b[i] h = (h * Hp) ^ (w & 0xff) h = (h * Hp) ^ ((w >> 8) & 0xff) h = (h * Hp) ^ ((w >> 16) & 0xff) h = (h * Hp) ^ ((w >> 24) & 0xff) } return h } // bvecSet is a set of bvecs, in initial insertion order. type bvecSet struct { index []int // hash -> uniq index. -1 indicates empty slot. uniq []bvec // unique bvecs, in insertion order } func (m *bvecSet) grow() { // Allocate new index. n := len(m.index) * 2 if n == 0 { n = 32 } newIndex := make([]int, n) for i := range newIndex { newIndex[i] = -1 } // Rehash into newIndex. for i, bv := range m.uniq { h := hashbitmap(H0, bv) % uint32(len(newIndex)) for { j := newIndex[h] if j < 0 { newIndex[h] = i break } h++ if h == uint32(len(newIndex)) { h = 0 } } } m.index = newIndex } // add adds bv to the set and returns its index in m.extractUniqe. // The caller must not modify bv after this. func (m *bvecSet) add(bv bvec) int { if len(m.uniq)*4 >= len(m.index) { m.grow() } index := m.index h := hashbitmap(H0, bv) % uint32(len(index)) for { j := index[h] if j < 0 { // New bvec. index[h] = len(m.uniq) m.uniq = append(m.uniq, bv) return len(m.uniq) - 1 } jlive := m.uniq[j] if bv.Eq(jlive) { // Existing bvec. return j } h++ if h == uint32(len(index)) { h = 0 } } } // extractUniqe returns this slice of unique bit vectors in m, as // indexed by the result of bvecSet.add. func (m *bvecSet) extractUniqe() []bvec { return m.uniq }