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