1 files changed, 112 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/biasedsparsemap.go b/src/cmd/compile/internal/ssa/biasedsparsemap.go
new file mode 100644
index 0000000..0d35154
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/biasedsparsemap.go
@@ -0,0 +1,112 @@
+// 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()
+	}
+}