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