1// Copyright 2015 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 ssa 6 7import "cmd/internal/src" 8 9// from https://research.swtch.com/sparse 10// in turn, from Briggs and Torczon 11 12type sparseEntry struct { 13 key ID 14 val int32 15 aux src.XPos 16} 17 18type sparseMap struct { 19 dense []sparseEntry 20 sparse []int32 21} 22 23// newSparseMap returns a sparseMap that can map 24// integers between 0 and n-1 to int32s. 25func newSparseMap(n int) *sparseMap { 26 return &sparseMap{dense: nil, sparse: make([]int32, n)} 27} 28 29func (s *sparseMap) cap() int { 30 return len(s.sparse) 31} 32 33func (s *sparseMap) size() int { 34 return len(s.dense) 35} 36 37func (s *sparseMap) contains(k ID) bool { 38 i := s.sparse[k] 39 return i < int32(len(s.dense)) && s.dense[i].key == k 40} 41 42// get returns the value for key k, or -1 if k does 43// not appear in the map. 44func (s *sparseMap) get(k ID) int32 { 45 i := s.sparse[k] 46 if i < int32(len(s.dense)) && s.dense[i].key == k { 47 return s.dense[i].val 48 } 49 return -1 50} 51 52func (s *sparseMap) set(k ID, v int32, a src.XPos) { 53 i := s.sparse[k] 54 if i < int32(len(s.dense)) && s.dense[i].key == k { 55 s.dense[i].val = v 56 s.dense[i].aux = a 57 return 58 } 59 s.dense = append(s.dense, sparseEntry{k, v, a}) 60 s.sparse[k] = int32(len(s.dense)) - 1 61} 62 63// setBit sets the v'th bit of k's value, where 0 <= v < 32 64func (s *sparseMap) setBit(k ID, v uint) { 65 if v >= 32 { 66 panic("bit index too large.") 67 } 68 i := s.sparse[k] 69 if i < int32(len(s.dense)) && s.dense[i].key == k { 70 s.dense[i].val |= 1 << v 71 return 72 } 73 s.dense = append(s.dense, sparseEntry{k, 1 << v, src.NoXPos}) 74 s.sparse[k] = int32(len(s.dense)) - 1 75} 76 77func (s *sparseMap) remove(k ID) { 78 i := s.sparse[k] 79 if i < int32(len(s.dense)) && s.dense[i].key == k { 80 y := s.dense[len(s.dense)-1] 81 s.dense[i] = y 82 s.sparse[y.key] = i 83 s.dense = s.dense[:len(s.dense)-1] 84 } 85} 86 87func (s *sparseMap) clear() { 88 s.dense = s.dense[:0] 89} 90 91func (s *sparseMap) contents() []sparseEntry { 92 return s.dense 93} 94