blob: 0d351544540e6f8ff3c94b2192c804971fa9a881 [file] [log] [blame]
 // Copyright 2018 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package ssa import ( "cmd/internal/src" "math" ) // A biasedSparseMap is a sparseMap for integers between J and K inclusive, // where J might be somewhat larger than zero (and K-J is probably much smaller than J). // (The motivating use case is the line numbers of statements for a single function.) // Not all features of a SparseMap are exported, and it is also easy to treat a // biasedSparseMap like a SparseSet. type biasedSparseMap struct { s *sparseMap first int } // newBiasedSparseMap returns a new biasedSparseMap for values between first and last, inclusive. func newBiasedSparseMap(first, last int) *biasedSparseMap { if first > last { return &biasedSparseMap{first: math.MaxInt32, s: nil} } return &biasedSparseMap{first: first, s: newSparseMap(1 + last - first)} } // cap returns one more than the largest key valid for s func (s *biasedSparseMap) cap() int { if s == nil || s.s == nil { return 0 } return s.s.cap() + int(s.first) } // size returns the number of entries stored in s func (s *biasedSparseMap) size() int { if s == nil || s.s == nil { return 0 } return s.s.size() } // contains reports whether x is a key in s func (s *biasedSparseMap) contains(x uint) bool { if s == nil || s.s == nil { return false } if int(x) < s.first { return false } if int(x) >= s.cap() { return false } return s.s.contains(ID(int(x) - s.first)) } // get returns the value s maps for key x, or -1 if // x is not mapped or is out of range for s. func (s *biasedSparseMap) get(x uint) int32 { if s == nil || s.s == nil { return -1 } if int(x) < s.first { return -1 } if int(x) >= s.cap() { return -1 } return s.s.get(ID(int(x) - s.first)) } // getEntry returns the i'th key and value stored in s, // where 0 <= i < s.size() func (s *biasedSparseMap) getEntry(i int) (x uint, v int32) { e := s.s.contents()[i] x = uint(int(e.key) + s.first) v = e.val return } // add inserts x->0 into s, provided that x is in the range of keys stored in s. func (s *biasedSparseMap) add(x uint) { if int(x) < s.first || int(x) >= s.cap() { return } s.s.set(ID(int(x)-s.first), 0, src.NoXPos) } // add inserts x->v into s, provided that x is in the range of keys stored in s. func (s *biasedSparseMap) set(x uint, v int32) { if int(x) < s.first || int(x) >= s.cap() { return } s.s.set(ID(int(x)-s.first), v, src.NoXPos) } // remove removes key x from s. func (s *biasedSparseMap) remove(x uint) { if int(x) < s.first || int(x) >= s.cap() { return } s.s.remove(ID(int(x) - s.first)) } func (s *biasedSparseMap) clear() { if s.s != nil { s.s.clear() } }