Home | History | Annotate | Download | only in gc 
      1 // Do not edit. Bootstrap copy of /usr/local/google/buildbot/src/android/build-tools/out/obj/go/src/cmd/compile/internal/gc/bv.go
      2 
      3 //line /usr/local/google/buildbot/src/android/build-tools/out/obj/go/src/cmd/compile/internal/gc/bv.go:1
      4 // Copyright 2013 The Go Authors. All rights reserved.
      5 // Use of this source code is governed by a BSD-style
      6 // license that can be found in the LICENSE file.
      7 
      8 package gc
      9 
     10 import "fmt"
     11 
     12 const (
     13 	WORDSIZE  = 4
     14 	WORDBITS  = 32
     15 	WORDMASK  = WORDBITS - 1
     16 	WORDSHIFT = 5
     17 )
     18 
     19 // A Bvec is a bit vector.
     20 type Bvec struct {
     21 	n int32    // number of bits in vector
     22 	b []uint32 // words holding bits
     23 }
     24 
     25 func bvsize(n uint32) uint32 {
     26 	return ((n + WORDBITS - 1) / WORDBITS) * WORDSIZE
     27 }
     28 
     29 func bvbits(bv Bvec) int32 {
     30 	return bv.n
     31 }
     32 
     33 func bvwords(bv Bvec) int32 {
     34 	return (bv.n + WORDBITS - 1) / WORDBITS
     35 }
     36 
     37 func bvalloc(n int32) Bvec {
     38 	return Bvec{n, make([]uint32, bvsize(uint32(n))/4)}
     39 }
     40 
     41 type bulkBvec struct {
     42 	words []uint32
     43 	nbit  int32
     44 	nword int32
     45 }
     46 
     47 func bvbulkalloc(nbit int32, count int32) bulkBvec {
     48 	nword := (nbit + WORDBITS - 1) / WORDBITS
     49 	return bulkBvec{
     50 		words: make([]uint32, nword*count),
     51 		nbit:  nbit,
     52 		nword: nword,
     53 	}
     54 }
     55 
     56 func (b *bulkBvec) next() Bvec {
     57 	out := Bvec{b.nbit, b.words[:b.nword]}
     58 	b.words = b.words[b.nword:]
     59 	return out
     60 }
     61 
     62 /* difference */
     63 func bvandnot(dst Bvec, src1 Bvec, src2 Bvec) {
     64 	for i, x := range src1.b {
     65 		dst.b[i] = x &^ src2.b[i]
     66 	}
     67 }
     68 
     69 func bvcmp(bv1 Bvec, bv2 Bvec) int {
     70 	if bv1.n != bv2.n {
     71 		Fatal("bvequal: lengths %d and %d are not equal", bv1.n, bv2.n)
     72 	}
     73 	for i, x := range bv1.b {
     74 		if x != bv2.b[i] {
     75 			return 1
     76 		}
     77 	}
     78 	return 0
     79 }
     80 
     81 func bvcopy(dst Bvec, src Bvec) {
     82 	for i, x := range src.b {
     83 		dst.b[i] = x
     84 	}
     85 }
     86 
     87 func bvconcat(src1 Bvec, src2 Bvec) Bvec {
     88 	dst := bvalloc(src1.n + src2.n)
     89 	for i := int32(0); i < src1.n; i++ {
     90 		if bvget(src1, i) != 0 {
     91 			bvset(dst, i)
     92 		}
     93 	}
     94 	for i := int32(0); i < src2.n; i++ {
     95 		if bvget(src2, i) != 0 {
     96 			bvset(dst, i+src1.n)
     97 		}
     98 	}
     99 	return dst
    100 }
    101 
    102 func bvget(bv Bvec, i int32) int {
    103 	if i < 0 || i >= bv.n {
    104 		Fatal("bvget: index %d is out of bounds with length %d\n", i, bv.n)
    105 	}
    106 	return int((bv.b[i>>WORDSHIFT] >> uint(i&WORDMASK)) & 1)
    107 }
    108 
    109 // bvnext returns the smallest index >= i for which bvget(bv, i) == 1.
    110 // If there is no such index, bvnext returns -1.
    111 func bvnext(bv Bvec, i int32) int {
    112 	if i >= bv.n {
    113 		return -1
    114 	}
    115 
    116 	// Jump i ahead to next word with bits.
    117 	if bv.b[i>>WORDSHIFT]>>uint(i&WORDMASK) == 0 {
    118 		i &^= WORDMASK
    119 		i += WORDBITS
    120 		for i < bv.n && bv.b[i>>WORDSHIFT] == 0 {
    121 			i += WORDBITS
    122 		}
    123 	}
    124 
    125 	if i >= bv.n {
    126 		return -1
    127 	}
    128 
    129 	// Find 1 bit.
    130 	w := bv.b[i>>WORDSHIFT] >> uint(i&WORDMASK)
    131 
    132 	for w&1 == 0 {
    133 		w >>= 1
    134 		i++
    135 	}
    136 
    137 	return int(i)
    138 }
    139 
    140 func bvisempty(bv Bvec) bool {
    141 	for i := int32(0); i < bv.n; i += WORDBITS {
    142 		if bv.b[i>>WORDSHIFT] != 0 {
    143 			return false
    144 		}
    145 	}
    146 	return true
    147 }
    148 
    149 func bvnot(bv Bvec) {
    150 	i := int32(0)
    151 	w := int32(0)
    152 	for ; i < bv.n; i, w = i+WORDBITS, w+1 {
    153 		bv.b[w] = ^bv.b[w]
    154 	}
    155 }
    156 
    157 /* union */
    158 func bvor(dst Bvec, src1 Bvec, src2 Bvec) {
    159 	for i, x := range src1.b {
    160 		dst.b[i] = x | src2.b[i]
    161 	}
    162 }
    163 
    164 /* intersection */
    165 func bvand(dst Bvec, src1 Bvec, src2 Bvec) {
    166 	for i, x := range src1.b {
    167 		dst.b[i] = x & src2.b[i]
    168 	}
    169 }
    170 
    171 func bvprint(bv Bvec) {
    172 	fmt.Printf("#*")
    173 	for i := int32(0); i < bv.n; i++ {
    174 		fmt.Printf("%d", bvget(bv, i))
    175 	}
    176 }
    177 
    178 func bvreset(bv Bvec, i int32) {
    179 	if i < 0 || i >= bv.n {
    180 		Fatal("bvreset: index %d is out of bounds with length %d\n", i, bv.n)
    181 	}
    182 	mask := uint32(^(1 << uint(i%WORDBITS)))
    183 	bv.b[i/WORDBITS] &= mask
    184 }
    185 
    186 func bvresetall(bv Bvec) {
    187 	for i := range bv.b {
    188 		bv.b[i] = 0
    189 	}
    190 }
    191 
    192 func bvset(bv Bvec, i int32) {
    193 	if i < 0 || i >= bv.n {
    194 		Fatal("bvset: index %d is out of bounds with length %d\n", i, bv.n)
    195 	}
    196 	mask := uint32(1 << uint(i%WORDBITS))
    197 	bv.b[i/WORDBITS] |= mask
    198 }
    199