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