map.go

Documentation: golang.org/x/tools/go/ssa/interp

     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 int64) 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  }
   122
View as plain text