Source file src/pkg/cmd/compile/internal/ssa/biasedsparsemap.go

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

View as plain text