Source file src/pkg/cmd/compile/internal/ssa/sparseset.go

     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 https://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	

View as plain text