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 sparseSet struct { 11 dense []ID 12 sparse []int32 13 } 14 15 // newSparseSet returns a sparseSet that can represent 16 // integers between 0 and n-1 17 func newSparseSet(n int) *sparseSet { 18 return &sparseSet{dense: nil, sparse: make([]int32, n)} 19 } 20 21 func (s *sparseSet) cap() int { 22 return len(s.sparse) 23 } 24 25 func (s *sparseSet) size() int { 26 return len(s.dense) 27 } 28 29 func (s *sparseSet) contains(x ID) bool { 30 i := s.sparse[x] 31 return i < int32(len(s.dense)) && s.dense[i] == x 32 } 33 34 func (s *sparseSet) add(x ID) { 35 i := s.sparse[x] 36 if i < int32(len(s.dense)) && s.dense[i] == x { 37 return 38 } 39 s.dense = append(s.dense, x) 40 s.sparse[x] = int32(len(s.dense)) - 1 41 } 42 43 func (s *sparseSet) addAll(a []ID) { 44 for _, x := range a { 45 s.add(x) 46 } 47 } 48 49 func (s *sparseSet) addAllValues(a []*Value) { 50 for _, v := range a { 51 s.add(v.ID) 52 } 53 } 54 55 func (s *sparseSet) remove(x ID) { 56 i := s.sparse[x] 57 if i < int32(len(s.dense)) && s.dense[i] == x { 58 y := s.dense[len(s.dense)-1] 59 s.dense[i] = y 60 s.sparse[y] = i 61 s.dense = s.dense[:len(s.dense)-1] 62 } 63 } 64 65 // pop removes an arbitrary element from the set. 66 // The set must be nonempty. 67 func (s *sparseSet) pop() ID { 68 x := s.dense[len(s.dense)-1] 69 s.dense = s.dense[:len(s.dense)-1] 70 return x 71 } 72 73 func (s *sparseSet) clear() { 74 s.dense = s.dense[:0] 75 } 76 77 func (s *sparseSet) contents() []ID { 78 return s.dense 79 } 80
