| 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 |
Members