biasedsparsemap.go

     1  // Copyright 2018 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  import (
     8  	"cmd/internal/src"
     9  	"math"
    10  )
    11  
    12  // A biasedSparseMap is a sparseMap for integers between J and K inclusive,
    13  // where J might be somewhat larger than zero (and K-J is probably much smaller than J).
    14  // (The motivating use case is the line numbers of statements for a single function.)
    15  // Not all features of a SparseMap are exported, and it is also easy to treat a
    16  // biasedSparseMap like a SparseSet.
    17  type biasedSparseMap struct {
    18  	s     *sparseMap
    19  	first int
    20  }
    21  
    22  // newBiasedSparseMap returns a new biasedSparseMap for values between first and last, inclusive.
    23  func newBiasedSparseMap(first, last int) *biasedSparseMap {
    24  	if first > last {
    25  		return &biasedSparseMap{first: math.MaxInt32, s: nil}
    26  	}
    27  	return &biasedSparseMap{first: first, s: newSparseMap(1 + last - first)}
    28  }
    29  
    30  // cap returns one more than the largest key valid for s
    31  func (s *biasedSparseMap) cap() int {
    32  	if s == nil || s.s == nil {
    33  		return 0
    34  	}
    35  	return s.s.cap() + int(s.first)
    36  }
    37  
    38  // size returns the number of entries stored in s
    39  func (s *biasedSparseMap) size() int {
    40  	if s == nil || s.s == nil {
    41  		return 0
    42  	}
    43  	return s.s.size()
    44  }
    45  
    46  // contains reports whether x is a key in s
    47  func (s *biasedSparseMap) contains(x uint) bool {
    48  	if s == nil || s.s == nil {
    49  		return false
    50  	}
    51  	if int(x) < s.first {
    52  		return false
    53  	}
    54  	if int(x) >= s.cap() {
    55  		return false
    56  	}
    57  	return s.s.contains(ID(int(x) - s.first))
    58  }
    59  
    60  // get returns the value s maps for key x, or -1 if
    61  // x is not mapped or is out of range for s.
    62  func (s *biasedSparseMap) get(x uint) int32 {
    63  	if s == nil || s.s == nil {
    64  		return -1
    65  	}
    66  	if int(x) < s.first {
    67  		return -1
    68  	}
    69  	if int(x) >= s.cap() {
    70  		return -1
    71  	}
    72  	return s.s.get(ID(int(x) - s.first))
    73  }
    74  
    75  // getEntry returns the i'th key and value stored in s,
    76  // where 0 <= i < s.size()
    77  func (s *biasedSparseMap) getEntry(i int) (x uint, v int32) {
    78  	e := s.s.contents()[i]
    79  	x = uint(int(e.key) + s.first)
    80  	v = e.val
    81  	return
    82  }
    83  
    84  // add inserts x->0 into s, provided that x is in the range of keys stored in s.
    85  func (s *biasedSparseMap) add(x uint) {
    86  	if int(x) < s.first || int(x) >= s.cap() {
    87  		return
    88  	}
    89  	s.s.set(ID(int(x)-s.first), 0, src.NoXPos)
    90  }
    91  
    92  // add inserts x->v into s, provided that x is in the range of keys stored in s.
    93  func (s *biasedSparseMap) set(x uint, v int32) {
    94  	if int(x) < s.first || int(x) >= s.cap() {
    95  		return
    96  	}
    97  	s.s.set(ID(int(x)-s.first), v, src.NoXPos)
    98  }
    99  
   100  // remove removes key x from s.
   101  func (s *biasedSparseMap) remove(x uint) {
   102  	if int(x) < s.first || int(x) >= s.cap() {
   103  		return
   104  	}
   105  	s.s.remove(ID(int(x) - s.first))
   106  }
   107  
   108  func (s *biasedSparseMap) clear() {
   109  	if s.s != nil {
   110  		s.s.clear()
   111  	}
   112  }
   113
View as plain text