Gecko [ 167.86.127.34 ]

Name	Size	Permission
builtin	[ DIR ]	drwxr-xr-x
testdata	[ DIR ]	drwxr-xr-x
alg.go	16.28 KB	-rw-r--r--
align.go	9.85 KB	-rw-r--r--
bexport.go	4.41 KB	-rw-r--r--
bimport.go	667 B	-rw-r--r--
bitset.go	1.15 KB	-rw-r--r--
bootstrap.go	311 B	-rw-r--r--
builtin.go	16.41 KB	-rw-r--r--
builtin_test.go	622 B	-rw-r--r--
bv.go	5.5 KB	-rw-r--r--
class_string.go	712 B	-rw-r--r--
closure.go	15.57 KB	-rw-r--r--
const.go	27.21 KB	-rw-r--r--
constFold_test.go	322.99 KB	-rw-r--r--
dcl.go	28.37 KB	-rw-r--r--
dep_test.go	587 B	-rw-r--r--
dump.go	6.37 KB	-rw-r--r--
dwinl.go	10.07 KB	-rw-r--r--
esc.go	12.22 KB	-rw-r--r--
escape.go	37.37 KB	-rw-r--r--
export.go	5.33 KB	-rw-r--r--
fixedbugs_test.go	2.23 KB	-rw-r--r--
float_test.go	11.51 KB	-rw-r--r--
fmt.go	41.71 KB	-rw-r--r--
gen.go	2.33 KB	-rw-r--r--
global_test.go	2.57 KB	-rw-r--r--
go.go	7.4 KB	-rw-r--r--
gsubr.go	9.08 KB	-rw-r--r--
iexport.go	31.65 KB	-rw-r--r--
iface_test.go	1.92 KB	-rw-r--r--
iimport.go	22.79 KB	-rw-r--r--
init.go	3.29 KB	-rw-r--r--
initorder.go	9.84 KB	-rw-r--r--
inl.go	35.08 KB	-rw-r--r--
inl_test.go	6.64 KB	-rw-r--r--
lang_test.go	1.46 KB	-rw-r--r--
lex.go	5.96 KB	-rw-r--r--
lex_test.go	3.63 KB	-rw-r--r--
logic_test.go	11.08 KB	-rw-r--r--
main.go	43.75 KB	-rw-r--r--
mapfile_mmap.go	1.21 KB	-rw-r--r--
mapfile_read.go	485 B	-rw-r--r--
mkbuiltin.go	5.34 KB	-rw-r--r--
mpfloat.go	6.56 KB	-rw-r--r--
mpint.go	5.34 KB	-rw-r--r--
noder.go	37.65 KB	-rw-r--r--
obj.go	11.44 KB	-rw-r--r--
op_string.go	4.88 KB	-rw-r--r--
order.go	37.39 KB	-rw-r--r--
pgen.go	21.66 KB	-rw-r--r--
pgen_test.go	6.01 KB	-rw-r--r--
phi.go	14.72 KB	-rw-r--r--
plive.go	44.51 KB	-rw-r--r--
pprof.go	274 B	-rw-r--r--
racewalk.go	2.61 KB	-rw-r--r--
range.go	13.72 KB	-rw-r--r--
reflect.go	48.07 KB	-rw-r--r--
reproduciblebuilds_test.go	1.46 KB	-rw-r--r--
scc.go	4.18 KB	-rw-r--r--
scope.go	2.8 KB	-rw-r--r--
scope_test.go	13.67 KB	-rw-r--r--
select.go	9.16 KB	-rw-r--r--
shift_test.go	21.46 KB	-rw-r--r--
sinit.go	26.75 KB	-rw-r--r--
sizeof_test.go	844 B	-rw-r--r--
ssa.go	224.4 KB	-rw-r--r--
ssa_test.go	5.1 KB	-rw-r--r--
subr.go	43.73 KB	-rw-r--r--
swt.go	18.51 KB	-rw-r--r--
syntax.go	36.41 KB	-rw-r--r--
timings.go	5.75 KB	-rw-r--r--
trace.go	494 B	-rw-r--r--
truncconst_test.go	1.76 KB	-rw-r--r--
typecheck.go	87.11 KB	-rw-r--r--
types.go	1.19 KB	-rw-r--r--
types_acc.go	491 B	-rw-r--r--
universe.go	10.88 KB	-rw-r--r--
unsafe.go	1.8 KB	-rw-r--r--
util.go	2.18 KB	-rw-r--r--
walk.go	101.89 KB	-rw-r--r--
zerorange_test.go	1.89 KB	-rw-r--r--

Code Editor : bv.go

// 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

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)

for w&1 == 0 {
		w >>= 1
		i++
	}

return i
}

// Len returns the minimum number of bits required to represent bv.
// The result is 0 if no bits are set in bv.
func (bv bvec) Len() int32 {
	for wi := len(bv.b) - 1; wi >= 0; wi-- {
		if w := bv.b[wi]; w != 0 {
			for i := wordBits - 1; i >= 0; i-- {
				if w>>uint(i) != 0 {
					return int32(wi)*wordBits + int32(i) + 1
				}
			}
		}
	}
	return 0
}

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
}

${this.title}

Code Editor : bv.go