.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/ssa/interp/map.go

   1 // Copyright 2013 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 interp
   6
   7 // Custom hashtable atop map.
   8 // For use when the key's equivalence relation is not consistent with ==.
   9
  10 // The Go specification doesn't address the atomicity of map operations.
  11 // The FAQ states that an implementation is permitted to crash on
  12 // concurrent map access.
  13
  14 import (
  15         "go/types"
  16 )
  17
  18 type hashable interface {
  19         hash(t types.Type) int
  20         eq(t types.Type, x interface{}) bool
  21 }
  22
  23 type entry struct {
  24         key   hashable
  25         value value
  26         next  *entry
  27 }
  28
  29 // A hashtable atop the built-in map.  Since each bucket contains
  30 // exactly one hash value, there's no need to perform hash-equality
  31 // tests when walking the linked list.  Rehashing is done by the
  32 // underlying map.
  33 type hashmap struct {
  34         keyType types.Type
  35         table   map[int]*entry
  36         length  int // number of entries in map
  37 }
  38
  39 // makeMap returns an empty initialized map of key type kt,
  40 // preallocating space for reserve elements.
  41 func makeMap(kt types.Type, reserve int) value {
  42         if usesBuiltinMap(kt) {
  43                 return make(map[value]value, reserve)
  44         }
  45         return &hashmap{keyType: kt, table: make(map[int]*entry, reserve)}
  46 }
  47
  48 // delete removes the association for key k, if any.
  49 func (m *hashmap) delete(k hashable) {
  50         if m != nil {
  51                 hash := k.hash(m.keyType)
  52                 head := m.table[hash]
  53                 if head != nil {
  54                         if k.eq(m.keyType, head.key) {
  55                                 m.table[hash] = head.next
  56                                 m.length--
  57                                 return
  58                         }
  59                         prev := head
  60                         for e := head.next; e != nil; e = e.next {
  61                                 if k.eq(m.keyType, e.key) {
  62                                         prev.next = e.next
  63                                         m.length--
  64                                         return
  65                                 }
  66                                 prev = e
  67                         }
  68                 }
  69         }
  70 }
  71
  72 // lookup returns the value associated with key k, if present, or
  73 // value(nil) otherwise.
  74 func (m *hashmap) lookup(k hashable) value {
  75         if m != nil {
  76                 hash := k.hash(m.keyType)
  77                 for e := m.table[hash]; e != nil; e = e.next {
  78                         if k.eq(m.keyType, e.key) {
  79                                 return e.value
  80                         }
  81                 }
  82         }
  83         return nil
  84 }
  85
  86 // insert updates the map to associate key k with value v.  If there
  87 // was already an association for an eq() (though not necessarily ==)
  88 // k, the previous key remains in the map and its associated value is
  89 // updated.
  90 func (m *hashmap) insert(k hashable, v value) {
  91         hash := k.hash(m.keyType)
  92         head := m.table[hash]
  93         for e := head; e != nil; e = e.next {
  94                 if k.eq(m.keyType, e.key) {
  95                         e.value = v
  96                         return
  97                 }
  98         }
  99         m.table[hash] = &entry{
 100                 key:   k,
 101                 value: v,
 102                 next:  head,
 103         }
 104         m.length++
 105 }
 106
 107 // len returns the number of key/value associations in the map.
 108 func (m *hashmap) len() int {
 109         if m != nil {
 110                 return m.length
 111         }
 112         return 0
 113 }
 114
 115 // entries returns a rangeable map of entries.
 116 func (m *hashmap) entries() map[int]*entry {
 117         if m != nil {
 118                 return m.table
 119         }
 120         return nil
 121 }