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 and true, or
    60  // 0/false if x is not mapped or is out of range for s.
    61  func (s *biasedSparseMap) get(x uint) (int32, bool) {
    62  	if s == nil || s.s == nil {
    63  		return 0, false
    64  	}
    65  	if int(x) < s.first {
    66  		return 0, false
    67  	}
    68  	if int(x) >= s.cap() {
    69  		return 0, false
    70  	}
    71  	k := ID(int(x) - s.first)
    72  	if !s.s.contains(k) {
    73  		return 0, false
    74  	}
    75  	return s.s.get(k)
    76  }
    77  
    78  // getEntry returns the i'th key and value stored in s,
    79  // where 0 <= i < s.size()
    80  func (s *biasedSparseMap) getEntry(i int) (x uint, v int32) {
    81  	e := s.s.contents()[i]
    82  	x = uint(int(e.key) + s.first)
    83  	v = e.val
    84  	return
    85  }
    86  
    87  // add inserts x->0 into s, provided that x is in the range of keys stored in s.
    88  func (s *biasedSparseMap) add(x uint) {
    89  	if int(x) < s.first || int(x) >= s.cap() {
    90  		return
    91  	}
    92  	s.s.set(ID(int(x)-s.first), 0)
    93  }
    94  
    95  // add inserts x->v into s, provided that x is in the range of keys stored in s.
    96  func (s *biasedSparseMap) set(x uint, v int32) {
    97  	if int(x) < s.first || int(x) >= s.cap() {
    98  		return
    99  	}
   100  	s.s.set(ID(int(x)-s.first), v)
   101  }
   102  
   103  // remove removes key x from s.
   104  func (s *biasedSparseMap) remove(x uint) {
   105  	if int(x) < s.first || int(x) >= s.cap() {
   106  		return
   107  	}
   108  	s.s.remove(ID(int(x) - s.first))
   109  }
   110  
   111  func (s *biasedSparseMap) clear() {
   112  	if s.s != nil {
   113  		s.s.clear()
   114  	}
   115  }
   116
View as plain text