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