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 5package 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 14import ( 15 "go/types" 16) 17 18type hashable interface { 19 hash(t types.Type) int 20 eq(t types.Type, x interface{}) bool 21} 22 23type 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. 33type 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. 41func 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. 49func (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. 74func (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. 90func (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. 108func (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. 116func (m *hashmap) entries() map[int]*entry { 117 if m != nil { 118 return m.table 119 } 120 return nil 121} 122