...
1
2
3
4
5 package interp
6
7
8
9
10
11
12
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
30
31
32
33 type hashmap struct {
34 keyType types.Type
35 table map[int]*entry
36 length int
37 }
38
39
40
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
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
73
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
87
88
89
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
108 func (m *hashmap) len() int {
109 if m != nil {
110 return m.length
111 }
112 return 0
113 }
114
115
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