bvset.go

     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 liveness
     6  
     7  import "cmd/compile/internal/bitvec"
     8  
     9  // FNV-1 hash function constants.
    10  const (
    11  	h0 = 2166136261
    12  	hp = 16777619
    13  )
    14  
    15  // bvecSet is a set of bvecs, in initial insertion order.
    16  type bvecSet struct {
    17  	index []int           // hash -> uniq index. -1 indicates empty slot.
    18  	uniq  []bitvec.BitVec // unique bvecs, in insertion order
    19  }
    20  
    21  func (m *bvecSet) grow() {
    22  	// Allocate new index.
    23  	n := len(m.index) * 2
    24  	if n == 0 {
    25  		n = 32
    26  	}
    27  	newIndex := make([]int, n)
    28  	for i := range newIndex {
    29  		newIndex[i] = -1
    30  	}
    31  
    32  	// Rehash into newIndex.
    33  	for i, bv := range m.uniq {
    34  		h := hashbitmap(h0, bv) % uint32(len(newIndex))
    35  		for {
    36  			j := newIndex[h]
    37  			if j < 0 {
    38  				newIndex[h] = i
    39  				break
    40  			}
    41  			h++
    42  			if h == uint32(len(newIndex)) {
    43  				h = 0
    44  			}
    45  		}
    46  	}
    47  	m.index = newIndex
    48  }
    49  
    50  // add adds bv to the set and returns its index in m.extractUnique,
    51  // and whether it is newly added.
    52  // If it is newly added, the caller must not modify bv after this.
    53  func (m *bvecSet) add(bv bitvec.BitVec) (int, bool) {
    54  	if len(m.uniq)*4 >= len(m.index) {
    55  		m.grow()
    56  	}
    57  
    58  	index := m.index
    59  	h := hashbitmap(h0, bv) % uint32(len(index))
    60  	for {
    61  		j := index[h]
    62  		if j < 0 {
    63  			// New bvec.
    64  			index[h] = len(m.uniq)
    65  			m.uniq = append(m.uniq, bv)
    66  			return len(m.uniq) - 1, true
    67  		}
    68  		jlive := m.uniq[j]
    69  		if bv.Eq(jlive) {
    70  			// Existing bvec.
    71  			return j, false
    72  		}
    73  
    74  		h++
    75  		if h == uint32(len(index)) {
    76  			h = 0
    77  		}
    78  	}
    79  }
    80  
    81  // extractUnique returns this slice of unique bit vectors in m, as
    82  // indexed by the result of bvecSet.add.
    83  func (m *bvecSet) extractUnique() []bitvec.BitVec {
    84  	return m.uniq
    85  }
    86  
    87  func hashbitmap(h uint32, bv bitvec.BitVec) uint32 {
    88  	n := int((bv.N + 31) / 32)
    89  	for i := 0; i < n; i++ {
    90  		w := bv.B[i]
    91  		h = (h * hp) ^ (w & 0xff)
    92  		h = (h * hp) ^ ((w >> 8) & 0xff)
    93  		h = (h * hp) ^ ((w >> 16) & 0xff)
    94  		h = (h * hp) ^ ((w >> 24) & 0xff)
    95  	}
    96  
    97  	return h
    98  }
    99
View as plain text