sparsemap.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  // sparseKey needs to be something we can index a slice with.
    11  type sparseKey interface{ ~int | ~int32 }
    12  
    13  type sparseEntry[K sparseKey, V any] struct {
    14  	key K
    15  	val V
    16  }
    17  
    18  type genericSparseMap[K sparseKey, V any] struct {
    19  	dense  []sparseEntry[K, V]
    20  	sparse []int32
    21  }
    22  
    23  // newGenericSparseMap returns a sparseMap that can map
    24  // integers between 0 and n-1 to a value type.
    25  func newGenericSparseMap[K sparseKey, V any](n int) *genericSparseMap[K, V] {
    26  	return &genericSparseMap[K, V]{dense: nil, sparse: make([]int32, n)}
    27  }
    28  
    29  func (s *genericSparseMap[K, V]) cap() int {
    30  	return len(s.sparse)
    31  }
    32  
    33  func (s *genericSparseMap[K, V]) size() int {
    34  	return len(s.dense)
    35  }
    36  
    37  func (s *genericSparseMap[K, V]) contains(k K) 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 the zero V
    43  // if k does not appear in the map.
    44  func (s *genericSparseMap[K, V]) get(k K) (V, bool) {
    45  	i := s.sparse[k]
    46  	if i < int32(len(s.dense)) && s.dense[i].key == k {
    47  		return s.dense[i].val, true
    48  	}
    49  	var v V
    50  	return v, false
    51  }
    52  
    53  func (s *genericSparseMap[K, V]) set(k K, v V) {
    54  	i := s.sparse[k]
    55  	if i < int32(len(s.dense)) && s.dense[i].key == k {
    56  		s.dense[i].val = v
    57  		return
    58  	}
    59  	s.dense = append(s.dense, sparseEntry[K, V]{k, v})
    60  	s.sparse[k] = int32(len(s.dense)) - 1
    61  }
    62  
    63  func (s *genericSparseMap[K, V]) remove(k K) {
    64  	i := s.sparse[k]
    65  	if i < int32(len(s.dense)) && s.dense[i].key == k {
    66  		y := s.dense[len(s.dense)-1]
    67  		s.dense[i] = y
    68  		s.sparse[y.key] = i
    69  		s.dense = s.dense[:len(s.dense)-1]
    70  	}
    71  }
    72  
    73  func (s *genericSparseMap[K, V]) clear() {
    74  	s.dense = s.dense[:0]
    75  }
    76  
    77  func (s *genericSparseMap[K, V]) contents() []sparseEntry[K, V] {
    78  	return s.dense
    79  }
    80  
    81  type sparseMap = genericSparseMap[ID, int32]
    82  
    83  // newSparseMap returns a sparseMap that can map
    84  // integers between 0 and n-1 to int32s.
    85  func newSparseMap(n int) *sparseMap {
    86  	return newGenericSparseMap[ID, int32](n)
    87  }
    88
View as plain text