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	"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.
16type biasedSparseMap struct {
17	s     *sparseMap
18	first int
19}
20
21// newBiasedSparseMap returns a new biasedSparseMap for values between first and last, inclusive.
22func 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
30func (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
38func (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
46func (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, or -1 if
60// x is not mapped or is out of range for s.
61func (s *biasedSparseMap) get(x uint) int32 {
62	if s == nil || s.s == nil {
63		return -1
64	}
65	if int(x) < s.first {
66		return -1
67	}
68	if int(x) >= s.cap() {
69		return -1
70	}
71	return s.s.get(ID(int(x) - s.first))
72}
73
74// getEntry returns the i'th key and value stored in s,
75// where 0 <= i < s.size()
76func (s *biasedSparseMap) getEntry(i int) (x uint, v int32) {
77	e := s.s.contents()[i]
78	x = uint(int(e.key) + s.first)
79	v = e.val
80	return
81}
82
83// add inserts x->0 into s, provided that x is in the range of keys stored in s.
84func (s *biasedSparseMap) add(x uint) {
85	if int(x) < s.first || int(x) >= s.cap() {
86		return
87	}
88	s.s.set(ID(int(x)-s.first), 0)
89}
90
91// add inserts x->v into s, provided that x is in the range of keys stored in s.
92func (s *biasedSparseMap) set(x uint, v int32) {
93	if int(x) < s.first || int(x) >= s.cap() {
94		return
95	}
96	s.s.set(ID(int(x)-s.first), v)
97}
98
99// remove removes key x from s.
100func (s *biasedSparseMap) remove(x uint) {
101	if int(x) < s.first || int(x) >= s.cap() {
102		return
103	}
104	s.s.remove(ID(int(x) - s.first))
105}
106
107func (s *biasedSparseMap) clear() {
108	if s.s != nil {
109		s.s.clear()
110	}
111}
112