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 5package ssa 6 7import ( 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. 17type biasedSparseMap struct { 18 s *sparseMap 19 first int 20} 21 22// newBiasedSparseMap returns a new biasedSparseMap for values between first and last, inclusive. 23func 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 31func (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 39func (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 47func (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. 62func (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() 77func (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. 85func (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. 93func (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. 101func (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 108func (s *biasedSparseMap) clear() { 109 if s.s != nil { 110 s.s.clear() 111 } 112} 113