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
5package liveness
6
7import "cmd/compile/internal/bitvec"
8
9// FNV-1 hash function constants.
10const (
11	h0 = 2166136261
12	hp = 16777619
13)
14
15// bvecSet is a set of bvecs, in initial insertion order.
16type bvecSet struct {
17	index []int           // hash -> uniq index. -1 indicates empty slot.
18	uniq  []bitvec.BitVec // unique bvecs, in insertion order
19}
20
21func (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.
53func (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.
83func (m *bvecSet) extractUnique() []bitvec.BitVec {
84	return m.uniq
85}
86
87func 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