Home | History | Annotate | Download | only in gc 
      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 	return bulkBvec{
     33 		words: make([]uint32, nword*count),
     34 		nbit:  nbit,
     35 		nword: nword,
     36 	}
     37 }
     38 
     39 func (b *bulkBvec) next() bvec {
     40 	out := bvec{b.nbit, b.words[:b.nword]}
     41 	b.words = b.words[b.nword:]
     42 	return out
     43 }
     44 
     45 func (bv1 bvec) Eq(bv2 bvec) bool {
     46 	if bv1.n != bv2.n {
     47 		Fatalf("bvequal: lengths %d and %d are not equal", bv1.n, bv2.n)
     48 	}
     49 	for i, x := range bv1.b {
     50 		if x != bv2.b[i] {
     51 			return false
     52 		}
     53 	}
     54 	return true
     55 }
     56 
     57 func (dst bvec) Copy(src bvec) {
     58 	for i, x := range src.b {
     59 		dst.b[i] = x
     60 	}
     61 }
     62 
     63 func (bv bvec) Get(i int32) bool {
     64 	if i < 0 || i >= bv.n {
     65 		Fatalf("bvget: index %d is out of bounds with length %d\n", i, bv.n)
     66 	}
     67 	mask := uint32(1 << uint(i%WORDBITS))
     68 	return bv.b[i>>WORDSHIFT]&mask != 0
     69 }
     70 
     71 func (bv bvec) Set(i int32) {
     72 	if i < 0 || i >= bv.n {
     73 		Fatalf("bvset: index %d is out of bounds with length %d\n", i, bv.n)
     74 	}
     75 	mask := uint32(1 << uint(i%WORDBITS))
     76 	bv.b[i/WORDBITS] |= mask
     77 }
     78 
     79 // bvnext returns the smallest index >= i for which bvget(bv, i) == 1.
     80 // If there is no such index, bvnext returns -1.
     81 func (bv bvec) Next(i int32) int32 {
     82 	if i >= bv.n {
     83 		return -1
     84 	}
     85 
     86 	// Jump i ahead to next word with bits.
     87 	if bv.b[i>>WORDSHIFT]>>uint(i&WORDMASK) == 0 {
     88 		i &^= WORDMASK
     89 		i += WORDBITS
     90 		for i < bv.n && bv.b[i>>WORDSHIFT] == 0 {
     91 			i += WORDBITS
     92 		}
     93 	}
     94 
     95 	if i >= bv.n {
     96 		return -1
     97 	}
     98 
     99 	// Find 1 bit.
    100 	w := bv.b[i>>WORDSHIFT] >> uint(i&WORDMASK)
    101 
    102 	for w&1 == 0 {
    103 		w >>= 1
    104 		i++
    105 	}
    106 
    107 	return i
    108 }
    109 
    110 func (bv bvec) IsEmpty() bool {
    111 	for i := int32(0); i < bv.n; i += WORDBITS {
    112 		if bv.b[i>>WORDSHIFT] != 0 {
    113 			return false
    114 		}
    115 	}
    116 	return true
    117 }
    118 
    119 func (bv bvec) Not() {
    120 	i := int32(0)
    121 	w := int32(0)
    122 	for ; i < bv.n; i, w = i+WORDBITS, w+1 {
    123 		bv.b[w] = ^bv.b[w]
    124 	}
    125 }
    126 
    127 // union
    128 func (dst bvec) Or(src1, src2 bvec) {
    129 	for i, x := range src1.b {
    130 		dst.b[i] = x | src2.b[i]
    131 	}
    132 }
    133 
    134 // intersection
    135 func (dst bvec) And(src1, src2 bvec) {
    136 	for i, x := range src1.b {
    137 		dst.b[i] = x & src2.b[i]
    138 	}
    139 }
    140 
    141 // difference
    142 func (dst bvec) AndNot(src1, src2 bvec) {
    143 	for i, x := range src1.b {
    144 		dst.b[i] = x &^ src2.b[i]
    145 	}
    146 }
    147 
    148 func (bv bvec) String() string {
    149 	s := make([]byte, 2+bv.n)
    150 	copy(s, "#*")
    151 	for i := int32(0); i < bv.n; i++ {
    152 		ch := byte('0')
    153 		if bv.Get(i) {
    154 			ch = '1'
    155 		}
    156 		s[2+i] = ch
    157 	}
    158 	return string(s)
    159 }
    160 
    161 func (bv bvec) Clear() {
    162 	for i := range bv.b {
    163 		bv.b[i] = 0
    164 	}
    165 }
    166