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.
7 // Custom hashtable atop map.
8 // For use when the key's equivalence relation is not consistent with ==.
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.
18 type hashable interface {
19 hash(t types.Type) int
20 eq(t types.Type, x interface{}) bool
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
36 length int // number of entries in map
39 // makeMap returns an empty initialized map of key type kt,
40 // preallocating space for reserve elements.
41 func makeMap(kt types.Type, reserve int) value {
42 if usesBuiltinMap(kt) {
43 return make(map[value]value, reserve)
45 return &hashmap{keyType: kt, table: make(map[int]*entry, reserve)}
48 // delete removes the association for key k, if any.
49 func (m *hashmap) delete(k hashable) {
51 hash := k.hash(m.keyType)
54 if k.eq(m.keyType, head.key) {
55 m.table[hash] = head.next
60 for e := head.next; e != nil; e = e.next {
61 if k.eq(m.keyType, e.key) {
72 // lookup returns the value associated with key k, if present, or
73 // value(nil) otherwise.
74 func (m *hashmap) lookup(k hashable) value {
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) {
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
90 func (m *hashmap) insert(k hashable, v value) {
91 hash := k.hash(m.keyType)
93 for e := head; e != nil; e = e.next {
94 if k.eq(m.keyType, e.key) {
99 m.table[hash] = &entry{
107 // len returns the number of key/value associations in the map.
108 func (m *hashmap) len() int {
115 // entries returns a rangeable map of entries.
116 func (m *hashmap) entries() map[int]*entry {